  We study approximation algorithms for graph pricing with vertex capacities
yet without the traditional envy-free constraint. Specifically, we have a set
of items $V$ and a set of customers $X$ where each customer $i \in X$ has a
budget $b_i$ and is interested in a bundle of items $S_i \subseteq V$ with
$|S_i| \leq 2$. However, there is a limited supply of each item: we only have
$\mu_v$ copies of item $v$ to sell for each $v \in V$. We should assign prices
$p(v)$ to each $v \in V$ and chose a subset $Y \subseteq X$ of customers so
that each $i \in Y$ can afford their bundle ($p(S_i) \leq b_i$) and at most
$\mu_v$ chosen customers have item $v$ in their bundle for each item $v \in V$.
Each customer $i \in Y$ pays $p(S_i)$ for the bundle they purchased: our goal
is to do this in a way that maximizes revenue. Such pricing problems have been
studied from the perspective of envy-freeness where we also must ensure that
$p(S_i) \geq b_i$ for each $i \notin Y$. However, the version where we simply
allocate items to customers after setting prices and do not worry about the
envy-free condition has received less attention.
  Our main result is an 8-approximation for the capacitated case via local
search and a 7.8096-approximation in simple graphs with uniform vertex
capacities. The latter is obtained by combing a more involved analysis of a
multi-swap local search algorithm for constant capacities and an LP-rounding
algorithm for larger capacities. If all capacities are bounded by a constant
$C$, we further show a multi-swap local search algorithm yields an $\left(4
\cdot \frac{2C-1}{C} + \epsilon\right)$-approximation. We also give a
$(4+\epsilon)$-approximation in simple graphs through LP rounding when all
capacities are very large as a function of $\epsilon$.
