# Core-Stability in Assignment Markets with Financially Constrained Buyers

Eleni Batziou  Decision Sciences and Systems (DSS)
Department of Informatics
Technical University of Munich
<EMAIL_ADDRESS>Martin Bichler  Decision Sciences and
Systems (DSS)
Department of Informatics
Technical University of Munich
<EMAIL_ADDRESS>Maximilian Fichtl  Decision Sciences and
Systems (DSS)
Department of Informatics
Technical University of Munich
<EMAIL_ADDRESS>
###### Abstract

We study markets where a set of indivisible items is sold to bidders with
unit-demand valuations, subject to a hard budget limit. Without financial
constraints and pure quasilinear bidders, this assignment model allows for a
simple ascending auction format that maximizes welfare and is incentive-
compatible and core-stable. Introducing budget constraints, the ascending
auction requires strong additional conditions on the unit-demand preferences
to maintain its properties. We show that, without these conditions, we cannot
hope for an incentive-compatible and core-stable mechanism. We design an
iterative algorithm that depends solely on a trivially verifiable ex-post
condition and demand queries, and with appropriate decisions made by an
auctioneer, always yields a welfare-maximizing and core-stable outcome. If
these conditions do not hold, we cannot hope for incentive-compatibility and
computing welfare-maximizing assignments and core-stable prices is hard: Even
in the presence of value queries, where bidders reveal their valuations and
budgets truthfully, we prove that the problem becomes NP-complete for the
assignment market model. The analysis complements complexity results for
markets with more complex valuations and shows that even with simple unit-
demand bidders the problem becomes intractable. This raises doubts on the
efficiency of simple auction designs as they are used in high-stakes markets,
where budget constraints typically play a role.

##  1 Introduction

The idea of a market exchange automatically channeling self-interest toward
welfare maximizing outcomes is a central theme in neoclassical economics. The
initial conjecture of the “invisible hand” goes back to Adam Smith. Formally,
the Arrow–Debreu model showed that under convex preferences and perfect
competition there must be a set of Walrasian equilibrium prices (Arrow and
Debreu, 1954). In these models, market participants are price-takers, and they
sell or buy divisible goods in order to maximize their total value subject to
their budget or initial wealth. The more recent stream of research on
competitive equilibrium theory assumes indivisible goods and quasilinear
utility functions, i.e. buyers maximize value minus the price they pay (their
payoff) and there are no budget constraints (Kelso and Crawford, 1982; Gul and
Stacchetti, 1999; Bikhchandani and Mamer, 1997; Leme and Wong, 2017; Baldwin
and Klemperer, 2019). The underlying question is under which conditions on the
preferences markets with indivisible goods can be assumed to be core-
stable111The core is the set of feasible outcomes that cannot be improved upon
by a subset of the economy’s participants. and welfare-maximizing. This
literature focuses on larger markets where bidders are assumed to be price-
takers and it emphasizes core-stability over incentive-compatibility.

For two-sided matching markets where quasilinear buyers have unit-demand,
referred to as assignment markets, welfare-maximization, core-stability and
even incentive-compatibility can be achieved with a polynomial-time auction
algorithm (Shapley and Shubik, 1971). These auctions can be interpreted as
primal-dual algorithms, where the auctioneer specifies a price vector (a
demand query) in each round and the bidders respond with their demand set,
i.e. the set of goods that maximize their payoff for given prices.

Unfortunately, it is well-known that we cannot hope for such positive results
with more general quasilinear preferences. Incentive-compatibility and core-
stability are conflicting in general markets with quasilinear utilities
(Ausubel and Milgrom, 2006). Even if we give up on incentive-compatibility,
only very restricted types of valuations (e.g., substitutes valuations) allow
for Walrasian equilibria.222A Walrasian equilibrium describes a competitive
equilibrium where supply equals demand and prices are linear (i.e., there is a
price for each good) and anonymous (i.e., the price is the same for all
participants and there is no price differentiation) (Bikhchandani and Mamer,
1997; Baldwin and Klemperer, 2019; Leme, 2017). As discused in Bikhchandani
and Ostroy (2002), under general valuations (allowing for substitutes and
complements), competitive equilibrium prices need to be non-linear and
personalized and the core can be empty.

Compared to early utility models in general equilibrium theory such as the
Fisher markets for divisible items (Eisenberg and Gale, 1959; Orlin, 2010),
quasilinear utility functions imply that bidders do not have budget
constraints. In many markets, this is too strong an assumption (Dobzinski et
al., 2008; Che and Gale, 2000; Dütting et al., 2016). Bidders might well
maximize payoff, but they need to respect budget constraints. Spectrum
auctions are just one example, where bidders have general valuations with
complements and substitutes and they are typically financially constrained
(Bichler and Goeree, 2017). Incentive-compatible mechanisms are known to be
impossible in multi-object markets (Dobzinski et al., 2008). It is interesting
to understand how core-stable and welfare-maximizing prices can be computed in
the presence of budget constraints if we assume bidders to be price-takers.
This question was recently analyzed for markets that allow for general
valuations where the auctioneer has complete information about values and
budgets (Bichler and Waldherr, 2021). The result is a spoiler: Computing the
welfare-maximizing core-stable outcome is a $\Sigma_{2}^{p}$-hard optimization
problem. Such problems are considered intractable, even for very small problem
instances.

The intuition behind this result is that the allocation and pricing problems
cannot be treated independently anymore. With quasilinear utility functions,
the auctioneer first determines the welfare-maximizing outcome and then a
corresponding price vector. If budget constraints are binding, then these
constraints on the prices need to be considered when computing the welfare-
maximizing outcome, which transforms the allocation and pricing problem into a
bilevel integer program for general valuations. Considering that budget
constraints are a reality in many markets, this casts doubts whether simple
market institutions based on polynomial-time algorithms (e.g., simple
ascending auctions as used in selling spectrum nowadays) can find a welfare-
maximizing outcome even if bidders were price-takers. General preferences as
allowed in combinatorial exchanges, might be too much to ask for. A natural
question is whether we can at least hope for core-stable and welfare-
maximizing outcomes in markets where bidders have unit-demand valuations, and
seek to maximize payoff subject budget constraints.

###  1.1 Contributions

We study the properties that can be achieved in assignment markets with unit-
demand bidders who aim to maximize their payoff but have hard budget
constraints as illustrated in the previous example. The aim of this work is to
compute welfare-maximizing and core-stable outcomes in the presence of such
financial constraints. If we cannot achieve incentive-compatibility and core-
stability with such simple valuations, also markets with more complex
preferences will not satisfy these properties.

We first introduce and analyze an iterative process that always finds a core-
stable outcome using only demand queries based on prices and no direct access
to valuations. In contrast to Aggarwal et al. (2009), where bidders’
valuations are directly queried, a distinguishing part of our algorithm is
that it relies exclusively on demand queries and provides a natural
generalization of the auction by Demange et al. (1986). Moreover, we place
emphasis on the question of when we can expect the outcome of the auction to
not only lie in the core, but also maximize welfare among all core
allocations, as welfare maximization is typically a central goal in market
design. During the auction process, the auctioneer may sometimes have to make
decisions on which buyer to exclude from certain items in subsequent rounds.
One of our main results is that, for any market instance, if the auctioneer
would be able to guess the right decisions throughout the auction, we
terminate in a welfare-maximizing core-allocation. In particular, if the
auctioneer does not have to make any such decisions - which is trivial to
check ex-post - our result implies that the auction always finds a welfare-
maximizing core-outcome. Unfortunately, we do not know ex-ante whether the
condition holds, and if it does not, welfare can be arbitrarily low.

Now, it is important to understand whether we can hope for an incentive-
compatible and welfare-maximizing core-selecting mechanism without additional
conditions beyond the already strong restriction to unit-demand valuations.
Unfortunately, the answer to this question is negative. In a novel result, we
show that no auction mechanism for the assignment market can be incentive-
compatible and core-stable when buyers face budget constraints. If we give up
on incentive-compatibility and assume full access to the true valuations
(i.e., via value queries) and buyer budgets, we can compute a core-stable and
welfare-maximizing outcome.

One might expect that the problem admits a polynomial time solution, since,
without the presence of budget constraints, the problem lies in complexity
class P. Unfortunately, a main finding of this paper shows that determining
core-stable, welfare-maximizing outcomes with financially constrained buyers
is an NP-complete optimization problem, even for the assignment market with
full access to valuations and budgets. This means, the existence of budget
constraints renders the problem of determining welfare-maximizing, core-stable
outcomes NP-hard. The hardness proof requires an involved reduction from the
maximum independent set problem. One aspect that is making the reduction
difficult is that prices need to be considered as continuous variables. These
results show that, even for the simplest type of multi-object markets, those
with only unit-demand bidders, we cannot expect core-stable and welfare-
maximizing outcomes unless additional strong conditions are satisfied that are
typically unknown ex-ante.

##  2 Related Literature

Two-sided matching markets describe markets where buyers want to win at most
one item (also known as the unit-demand model) and sellers sell only one item.
Buyers and sellers are disjoint sets of agents and each buyer forms exclusive
relationships with a seller. Such markets are central to the economic
sciences. The well-known marriage model of Gale and Shapley (1962) assumes
ordinal preferences and non-transferable utility. Shapley and Shubik (1971)
analyzed such markets with quasilinear utility functions and showed that the
core of this game is nonempty and encompasses all competitive equilibria.
Under the quasilinear utility model, buyers maximize value minus price, while
sellers maximize price minus cost. While their setting assumes access to all
valuations, Demange et al. (1986) showed that an ascending auction with only
demand queries results in a competitive equilibrium at the lowest possible
price, i.e. at the competitive equilibrium price vector that is optimal for
buyers. In such an auction, the auctioneer specifies a price vector (the
demand query) in each round, and buyers respond with their demand set, i.e.
the set of goods that maximize payoff at the prices.

The housing market of Shapley and Scarf (1974) is an example of a market
without transferable utility or monetary funds. In this market, each agent is
endowed with a good or house, and each agent is interested in one house only.
The goal of this market is to redistribute ownership of the houses in
accordance with the ordinal preferences of the agents. In such housing
markets, the core set is nonempty. If no agent is indifferent between any two
houses, then the economy has a unique competitive allocation, which is also
the unique strict core allocation. An allocation belongs to the strong core,
if no coalition of buyers and sellers can make all members as well off and at
least one member better off by trading items among themselves. We assume an
allocation belongs to the weak core if no coalition can lead to all members’
utilities improved when redistributing items amongst themselves.

Quinzii (1984) generalizes the model of Shapley and Scarf (1974) to one with
multiple agents with unit-demand and transferable but non-quasilinear utility.
Buyers derive utility from at most one good and a transfer of money. Sellers
aim at obtaining the highest possible price above a reservation level. She
proved the general existence of the core in her model, and its equivalence to
competitive equilibria. In a closely related model, Gale (1984) shows that a
competitive equilibrium always exists. These models allow for budgets, but
differ from hard budget constraints as examined in our work, where bidders are
not permitted to spend more than a certain amount of money. Alaei et al.
(2016) provide a structural characterization of utilities in competitive
equilibria and a mechanism that is group-strategyproof. These non-quasilinear
models assume utility functions that are not necessarily quasilinear, but
where small changes of prices do not lead to a discontinuous change of the
bidders’ utilities as is the case with hard budget constraints.

Closer to this paper is another line of research that focuses on assignment
markets where buyers maximize payoff subject to a hard budget constraint.
Aggarwal et al. (2009) show that an extension of the Hungarian algorithm is
incentive-compatible and bidder-optimal if the auction is in general position,
a rather specific condition that is usually unknown ex-ante and hard to check.
Typically, ascending auctions use only demand queries, namely the auctioneer
specifies a price and the bidders respond with their demand set. The auction
additionally requires value and budget queries, thereby asking for the value
of a specific good to a bidder and their budget during the auction. This is
quite different from the ascending auctions based on price-based demand
queries only, as described in Demange et al. (1986) and the subsequent
literature or compared to ascending auctions used in the field. Fujishige and
Tamura (2007) consider two-sided markets with budget-constrained bidders whose
valuation functions are more general than unit-demand. Their results imply
that in the unit-demand setting, there always exists a core allocation. These
prior results aim exclusively for core-stability, but do not attempt to
maximize welfare as done in this work.

In contrast to competitive equilibrium theory, Henzinger and Loitzenbauer
(2015) and its predecessor Dütting et al. (2013) do not aim for core-
stability. Note that with hard budget constraints, core-stability does not
imply envy-freeness. Consider for example a market with two buyers and one
seller selling a single good. If both buyers have the same budget and the same
valuation for the good, which exceeds their budget, the only possibility such
that no bidder envies the other one is that the good remains unsold. Such an
outcome is clearly not in the core, because there is a coalition of buyer and
seller who want to deviate. Note that such types of envy cannot arise without
binding budget constraints, because if the price is at the value of two
bidders, they are indifferent between getting the object or the empty set. It
depends on the considered market, whether envy-freeness and bidder-optimality
or core-stability should be preferred. While their model appears to be
reasonable in cases where all items are sold by one large seller, like ad
auctions, it may not seem reasonable for individual sellers to participate in
an auction where items remain unsold for the sake of envy-freeness. Finally,
van der Laan and Yang (2016) propose an ascending auction for the assignment
market that results in an _equilibrium under allotment_ , which is in general
not a core-stable outcome.

Core-stability and incentive-compatibility are arguably the most important
axioms in market design. Whether one can design assignment markets that
satisfy these axioms in the presence of hard budget constraints has not yet
been answered. We show that, without strong additional assumptions, this is
not possible. Importantly, even with access to all valuations and budgets, the
problem is computationally intractable for large market instances.

##  3 Preliminaries

A two-sided matching market $M=(\mathcal{B},\mathcal{S},v,b,r)$ consists of
two disjoint sets of agents $\mathcal{B}$ and $\mathcal{S}$, representing
bidders $i\in\mathcal{B}=\\{1,2,\dots,n\\}$ and goods
$j\in\mathcal{S}=\\{1,2,\dots,m\\}\cup\\{0\\}$. We identify good $j$ with the
seller owning it, i.e. each seller owns one good. The $0$-item is a dummy item
and does not have value to any bidder, meaning that receiving good $0$
corresponds no real good. Additionally, the market is defined by each bidder
$i$’s valuation $v_{i}:\mathcal{S}\rightarrow\operatorname{\mathbb{Z}}_{\geq
0}$ with $v_{i}(0)=0$ and budget $b^{i}\in\operatorname{\mathbb{Z}}_{>0}$, as
well as each seller $j$’s reserve values/ ask price
$r_{j}\in\operatorname{\mathbb{Z}}_{\geq 0}$.

A _price vector_ is a vector $p\in\operatorname{\mathbb{R}}^{\mathcal{S}}$
with $p(0)=0$, assigning price $p(j)$ to every good $j$. Bidders have quasi-
linear utilities, so if bidder $i$ receives item $j$ under prices $p$, their
utility is $\pi_{i}(j,p)=v_{i}(j)-p(j)$, if $p(j)\leq b^{i}$, and
$\pi_{i}(j,p)=-\infty$, otherwise. An _assignment_ is represented as a map
$\mu:\mathcal{B}\rightarrow\mathcal{S}$ from bidders to the items they
receive, where $|\mu^{-1}(\\{j\\})|\leq 1$ for all $j\neq 0$, so only the
dummy good may be assigned to more than one bidder. An _outcome_ is a pair
$(\mu,p)$, where $\mu$ is an assignment and $p$ is a price vector, such that
no budget constraint is violated, i.e. $p(\mu(i))\leq b^{i}$ for all
$i\in\mathcal{B}$ and only sold items may have a positive price: $p(j)>0$
implies that $|\mu^{-1}(\\{j\\})|=1$. For our iterative auction in Section
4,for the sake of simplicity, we assume all reserve prices to be equal to $0$.
The results can be easily generalized by starting the auction at the reserve
prices, and not at $0$.

In neoclassic economics, a (Benthamite) social welfare function is defined as
the sum of cardinally measurable values $v_{i}$ of all market participants. An
optimal allocation of resources is one which maximizes the social welfare in
this sense:

$\max\left\\{\sum_{i=1}^{n}v_{i}(\mu(i))\,:\,\mu\text{ is an
assignment}\right\\}$

This can be written in LP-form as

$\displaystyle\max$
$\displaystyle\,\sum_{i=1}^{n}\sum_{j=1}^{m}x_{ij}v_{i}(j)$ (1) s.t.
$\displaystyle\,\sum_{i=1}^{n}x_{ij}\leq 1\,\forall j=1,\dots,m$
$\displaystyle\,(p_{j})$ $\displaystyle\,\sum_{j=1}^{m}x_{ij}\leq 1\,\forall
i=1,\dots,n$ $\displaystyle\,(\pi_{i})$ $\displaystyle\,x\geq 0$

where the variables in parentheses denote the corresponding duals. This
assignment problem is well-known to have an integral optimal solution and can
be solved in $O(n^{4})$ (Kuhn, 1955). An integral solution $x$ corresponds to
an assignment $\mu$ via $x_{ij}=1\Leftrightarrow\mu(i)=j$. This notion of
utilitarian welfare maximization, i.e. maximizing the sum of participants’
utilities, is widely used in auction theory and competitive equilibrium
theory.

New welfare economics, in the tradition of Pareto defies the idea of
interpersonal utility comparisons and stipulates ordinal preferences. Pareto
efficiency or Pareto optimality is the key design desideratum in this
literature. A market outcome is Pareto efficient, if no market participant can
be better off without making at least one other participant worse off. With
cardinal utilities and interpersonal comparisons a welfare-maximizing outcome
is also Pareto efficient. This is because any Pareto-improvement would
increase welfare, which is not possible by definition of a welfare-maximizing
allocation. It has also been shown that the converse is true (Negishi, 1960).
Another design desideratum is that of core-stability.

######  Definition 1 (Core outcome).

Let $(\mu,p)$ be an outcome. A bidder-seller pair
$(i,j)\in\mathcal{B}\times\mathcal{S}$ is called a _blocking pair_ , if
$\pi_{i}(j,p)>\pi_{i}(\mu(i),p)$ and $p(j)<b^{i}$. $(\mu,p)$ is a _core
outcome_ , if there are no blocking pairs. We also say that $(\mu,p)$ is
_core-stable_ in this case.

The idea of a blocking pair $(i,j)$ is that both bidder $i$ and seller $j$
would strictly increase their utility, if $i$ received item $j$ instead of
$\mu(i)$: if $i$ pays $p(j)+\varepsilon$ for item $j$, then still
$\pi_{i}(j,p)-\varepsilon>\pi_{i}(\mu(i),p)$, and at the same time, the profit
of seller $j$ is increased by $\varepsilon$.

In the literature, a core outcome is often alternatively defined in the
following way: an outcome $(\mu,p)$ is in the core if there are no subsets
$\mathcal{B}^{\prime}\subseteq\mathcal{B}$ and
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ and an outcome
$(\mu^{\prime},p^{\prime})$ on
$\mathcal{B}^{\prime}\times\mathcal{S}^{\prime}$ such that
$\pi_{i}(\mu^{\prime}(i),p^{\prime})>\pi_{i}(\mu(i),p)$ for all
$i\in\mathcal{B}^{\prime}$ and $p^{\prime}(j)>p(j)$ for all
$j\in\mathcal{S}^{\prime}$ (see for example (Zhou, 2017)). These definitions
can easily be shown to be equivalent: first suppose that such subsets
$\mathcal{B}^{\prime}$ and $\mathcal{S}^{\prime}$ do exist. Then it is easy to
see that both sets are nonempty. In particular, let $i\in\mathcal{B}^{\prime}$
and $j=\mu^{\prime}(i)$. Then $p^{\prime}(j)>p(j)$, so $p(j)<b^{i}$.
Furthermore, we have $\pi_{i}(j,p)>\pi_{i}(j,p^{\prime})>\pi_{i}(\mu(i),p)$,
so $(i,j)$ is a blocking pair. On the other hand, if $(i,j)$ is a blocking
pair, then as in the above paragraph, we can set
$p^{\prime}(j)=p(j)+\varepsilon$ and get
$\pi_{i}(j,p^{\prime})>\pi_{i}(\mu(i),p)$ and $p^{\prime}(j)>p(j)$. Thus we
can choose $\mathcal{B}^{\prime}=\\{i\\}$, $\mathcal{S}^{\prime}=\\{j\\}$,
$\mu^{\prime}(i)=j$ and $p^{\prime}(j)=p(j)+\varepsilon$ in the alternative
definition.

We focus on the problem of finding welfare-maximizing core outcomes:

$\displaystyle\max\left\\{\sum_{i=1}^{n}v_{i}(\mu(i))\,:\,(\mu,p)\text{ is a
core outcome}\right\\}.$ (2)

If budgets are not binding, i.e., $b^{i}>v_{i}(j)$ for all bidders $i$ and all
goods $j$, core-stability coincides with the definition of a competitive
equilibrium. For this, let us first define the _demand set_ of bidder $i$,
which consist of the most preferred, affordable among all items at prices $p$:

$D_{i}(p)=\left\\{j\,:\,p(j)\leq
b^{i}\,\wedge\,\pi_{i}(j,p)\geq\pi_{i}(k,p)\,\forall k\text{ with }p(k)\leq
b^{i}\right\\}.$

######  Definition 2 (Competitive equilibrium).

An outcome $(\mu,p)$ is a _competitive equilibrium_ , if $\mu(i)\in D_{i}(p)$
for all bidders $i$.

The next proposition summarizes well-known equivalences of the different
notions for markets where budgets are not binding.

######  Proposition 1 (Bikhchandani and Mamer (1997)).

Suppose that $b^{i}>v_{i}(j)$ for all $i$ and $j$, and let $(\mu,p)$ be an
outcome. Then the following statements are equivalent.

  1. 1.

$(\mu,p)$ is a core outcome.

  2. 2.

$(\mu,p)$ is a competitive equilibrium.

  3. 3.

The variables defined by $x_{ij}=1\Leftrightarrow\mu(i)=j$ solve the linear
program (1) and $p_{j}=p(j)$ is a corresponding dual solution.

  4. 4.

$(\mu,p)$ is a welfare-maximizing core outcome.

This equivalence no longer remains true if bidders have binding budgets: in
general, a core outcome needs not be a competitive equilibrium, and different
core outcomes might generate very different welfare.

######  Example 1.

For a very simple example, consider two bidders $1,2$ and one item $A$.
Suppose that $v_{1}(A)=6$ and $v_{2}(A)=10$. Both bidders have the same budget
$b^{1}=b^{2}=1$. It is easy to see that there are two core outcomes: either
bidder $1$ or $2$ receives $A$ for a price of $1$, while the other bidder does
not receive an item. Both core outcomes are no competitive equilibria, since
the bidder $i$ not receiving $A$ does not receive an item in
$D_{i}(p)=\\{A\\}$. This bidder thus envies the other. Moreover, one core
outcome generates a welfare of $6$, while the other generates a welfare of
$10$. Ignoring budgets, the above LP-formulation would assign item $A$ to
bidder $2$ at a price $p(A)\in[6,10]$ \- no such price is feasible when
considering the budget constraints.

Besides, as we show, finding a welfare-maximizing core outcome is in general
NP-complete, so we cannot expect a simple LP-formulation as above to exist.
Note that efficient algorithms for determining core outcomes under budget
constraints have been discussed in the literature. However, desirable
properties like bidder-optimality and incentive-compatibility are only
guaranteed if additional assumptions on the bidders’ preferences are made.
Aggarwal et al. (2009) introduced the notion of _general position_ , a
sufficient condition for ascending auctions to indeed find the welfare-
maximizing core-stable outcome. As this condition has received considerable
attention in the literature, we provide a brief discussion:

######  Definition 3 (Aggarwal et al. (2009)).

Consider a directed bipartite graph with edges between bidders $\mathcal{B}$
and goods $\mathcal{S}$ (including dummy good $0$): For $i\in\mathcal{B}$ and
$j\in\mathcal{S}$, there is a

  * •

forward-edge from $i$ to $j$ with weight $-v_{i}(j)$

  * •

backward-edge from $j$ to $i$ with weight $v_{i}(j)$

  * •

maximum-price edge from $i$ to $j$ with weight $b^{i}-v_{i}(j)$

  * •

terminal edge from $i$ to the dummy good $0$ with weight $0$.

The auction is in general position, if for every bidder $i$, there are no two
alternating walks, following alternating forward and backward edges and ending
with a distinct maximum-price or terminal edge, having the same total weight.

######  Example 2.

Consider an auction with two bidders $1$ and $2$ with $b^{1}=b^{2}$. The
number of goods and bidders’ valuations may be chosen arbitrarily. Assume
$j\in\mathcal{S}$ is any good. Consider the following path starting from
bidder $1$: $1\rightarrow j\rightarrow 2\rightarrow j$, where the last edge is
a maximum-price edge, with total weight
$-v_{1}(j)+v_{2}(j)+(b^{2}-v_{2}(j))=b^{2}-v_{1}(j)$. Now consider the path
$1\rightarrow j$, where the only edge is a maximum-price edge, with weight
$b^{1}-v_{1}(j)$. Since $b^{1}=b^{2}$, the total weight of both paths is
equal, so the auction is not in general position.

As the example shows, the general position condition implies that in an
ascending auction, no two bidders may reach their budget limits at the same
time. Henzinger and Loitzenbauer (2015) claim the general position condition
is rather restrictive, as it excludes, for instance, symmetric bidders. They
additionally show that no polynomial-time algorithm can determine whether a
set of valuations is in general position. The general position condition is
sufficient but not necessary for the existence of a unique bidder-optimal
stable matching (Aggarwal et al., 2009), which is thus also welfare-maximizing
by our results below. As we will see, there are valuations not in general
position, but where a welfare-maximizing core allocation can still be computed
efficiently with our auction.

Let us now introduce an iterative auction that always finds a core-stable
outcome in markets with budget constrained buyers and, if a simple ex-post
condition is satisfied, maximizes welfare among all core outcomes.

##  4 An Iterative Auction

Our auction is based on the well-known auction by Demange et al. (1986)
(denoted as DGS auction from now on), which implements the Hungarian
algorithm. Contrary to Aggarwal et al. (2009), where the underlying assumption
is that bidders report their valuations and budgets to the auctioneer, in our
auction, they only have to report their demand sets at certain prices, similar
to other ascending auctions (Mishra and Parkes, 2007). We will provide
conditions when reporting demand sets truthfully is incentive-compatible.
Thus, we provide a natural generalization of the DGS auction to markets where
bidders have binding budget constraints. The simple ascending nature of our
auction also naturally motivates an ex-post optimality condition for the
returned allocation. Without loss of generality, we will assume $r_{j}=0$ in
this section.

In the auction process, we may need to “forbid” some bidder to demand a
certain item. We model this by introducing subsets
$R_{1},\dots,R_{n}\subseteq\mathcal{S}$ of goods for every bidder and define
the _restricted demand set_ to be

$D_{i}(p,R_{i})=\left\\{j\in R_{i}\,:\,p(j)\leq
b^{i}\,\wedge\pi_{i}(j,p)\geq\pi_{i}(k,p)\,\forall k\in R_{i}\text{ with
}p(k)\leq b^{i}\right\\}.$

Note that our definition of the restricted demand set coincides with the
definition of demand sets by van der Laan and Yang (2016). The set consists of
all affordable items that generate the highest utility among all items in
$R_{i}$. We introduce the well-known notions of over- and underdemanded sets
(Demange et al., 1986; Mishra and Talman, 2006), adjusted to our notion of
restricted demand sets.

######  Definition 4.

Let a price vector $p$ and sets $R_{1},\dots,R_{n}\subseteq\mathcal{S}$ with
$R_{i}\neq\emptyset\,\ \forall i$ be given. A set $T\subseteq\mathcal{S}$ is

  * •

_overdemanded_ , if $0\not\in T$ and
$|\\{i\in\mathcal{B}\,:\,D_{i}(p,R_{i})\subseteq T\\}|>|T|$, and

  * •

_underdemanded_ , if $p(j)>0$ for all $j\in T$ and
$|\\{i\in\mathcal{B}\,:\,D_{i}(p,R_{i})\cap T\neq\emptyset\\}|<|T|$.

$T$ is _minimally over-/underdemanded_ , if it does not contain a proper
over-/underdemanded subset.

Finally, we define the strict budget set of bidder $i$ by
$B_{i}(p)=\\{j\in\mathcal{S}\,:\,p(j)<b^{i}\\}$. It consists of all items with
prices strictly less than the bidder’s budget.

###  4.1 The Auction Algorithm

Algorithm 1 describes our auction. It is based on the following observation.

######  Lemma 1.

An outcome $(\mu,p)$ is in the core if and only if there are sets
$R_{1},\dots,R_{n}\subseteq\mathcal{S}$ such that $B_{i}(p)\subseteq R_{i}$
and $\mu(i)\in D_{i}(p,R_{i})$ for all $i$.

###### Proof.

Suppose first that $(\mu,p)$ is a core outcome. Set
$R_{i}=\\{j\in\mathcal{S}\,:\,p(j)<b^{i}\\}\cup\\{\mu(i)\\}$. Then $\mu(i)\in
D_{i}(p,R_{i})$, since otherwise there would exist an item $j$ with
$p(j)<b^{i}$ generating a higher utility than $\mu(i)$ \- this would
constitute a blocking pair.

Now let’s assume that there are sets $R_{i}$ as described with $\mu(i)\in
D_{i}(p,R_{i})$ for all $i$. Suppose there is a blocking pair $(i,j)$. Then
$j$ costs strictly less than $b^{i}$, so $j\in R_{i}$, and $j$ generates a
higher utility than $\mu(i)$. This would contradict $\mu(i)\in
D_{i}(p,R_{i})$. Thus, $(\mu,p)$ is a core outcome. ∎

Computing a core outcome can thus also be interpreted as computing a
“competitive equilibrium” with respect to the restricted demand sets
$D_{i}(p,R_{i})$. This is quite similar to the definition of an _equilibrium
under allotment_ of van der Laan and Yang (2016). However, they have other
requirements on the sets $R_{i}$, which, in general, cause their equilibria
not to lie in the core.

In view of Lemma 1, the goal of our auction procedure is to determine prices
$p$ together with sets $R_{i}$, such that there are neither over- nor
underdemanded sets of items. As observed in Mishra and Talman (2006), this
implies existence of an assignment $\mu:\mathcal{B}\rightarrow\mathcal{S}$,
such that every bidder receives an item in their demand set, and every item
with positive price gets assigned to some bidder. The following result is due
to the aforementioned work.

######  Proposition 2.

Suppose that with respect to the $D_{i}(p,R_{i})$, there is no over- or
underdemanded set of items. Then there is an assignment
$\mu:\mathcal{B}\rightarrow\mathcal{S}$ such that $\mu(i)\in D_{i}(p,R_{i})$
for all $i$, and for all $j\in\mathcal{S}$ with $p(j)>0$, there is some $i$
with $\mu(i)=j$.

Note that they considers markets without budgets and demand sets without
restrictions. However, their proof only uses combinatorial properties of the
demand sets, so it can be directly adapted to our setting. Thus, we omit a
proof here.

1 Set $p^{1}=(0,\dots,0)$ and $R^{1}_{i}=\mathcal{S}$ for all bidders $i$. Set
$t=1$, $O^{0}=\emptyset$ and $I^{1}=\emptyset$.

2 Request $D_{i}(p^{t},R^{t}_{i})$ from all bidders. If $t>1$ and the set
$I^{t}=\\{i\in\mathcal{B}\,:\,D_{i}(p^{t-1},R_{i}^{t-1})\subseteq
O^{t-1}\,\wedge\,D_{i}(p^{t-1},R_{i}^{t-1})\setminus
D_{i}(p^{t},R_{i}^{t})\neq\emptyset\\}$ is nonempty, go to Step 3. Otherwise,
if there is an overdemanded set, go to Step 4. Else, go to Step 5.

3 Choose a bidder $i\in I^{t}$ and define
$J_{i}^{t}=D_{i}(p^{t-1},R_{i}^{t-1})\setminus D_{i}(p^{t},R_{i}^{t})$. Set
$R_{i}^{t+1}=R_{i}^{t}\setminus J_{i}^{t}$, $O^{t}=\emptyset$ and
$p^{t+1}=p^{t-1}$. For all other bidders $i^{\prime}$, the sets
$R_{i^{\prime}}^{t+1}=R_{i^{\prime}}^{t}$ are unchanged. Set $t=t+1$ and go to
Step 2.

4 Choose a minimally overdemanded set $O^{t}$. For all $j\in O^{t}$, set
$p^{t+1}(j)=p^{t}(j)+1$. The prices for all other goods, as well as the sets
$R_{i}^{t}$ remain unchanged. Set $t=t+1$ and go to Step 2.

5 Compute an assignment $\mu$, such that $\mu(i)\in D_{i}(p^{t},R_{i}^{t})$
for all bidders $i$ and
$\mu(\mathcal{B})\subseteq\\{j\in\mathcal{S}\,:\,p^{t}(j)>0\\}$. Set $p=p^{t}$
and return $(\mu,p)$.

ALGORITHM 1 Iterative Auction

Step 3 of the auction ensures that we do not end up with underdemanded sets of
items. Moreover, sets $R_{i}^{t}$ always contain at least all items that cost
strictly less than the bidder’s budget $b^{i}$. Our proof of correctness is
similar to the one by van der Laan and Yang (2016): due to the budget
constraints, underdemanded sets of items may appear. We show that Step 3 of
the auction takes care of these sets.

######  Lemma 2.

Let $O$ be minimally overdemanded and $T\subseteq O$ with $T\neq\emptyset$.
Let prices $p$ and sets $R_{i}$ be given. Then

$|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\,\wedge\,D_{i}(p,R_{i})\cap
T\neq\emptyset\\}|>|T|.$

In particular, $T$ is not underdemanded.

The proof of this lemma can be found in the Appendix.

######  Lemma 3.

For all bidders $i\in\mathcal{B}$ and all iterations $t$ of the algorithm, we
have that $B_{i}(p)\subseteq R_{i}^{t}$. In particular, since $p^{t}(0)=0$,
$R_{i}^{t}\neq\emptyset$.

###### Proof.

Assume to the contrary that there is a minimal iteration $t+1$, such that a
bidder $i^{*}$ and a good $j^{*}$ exist with $p^{t+1}(j^{*})<b^{i^{*}}$, but
$j^{*}\not\in R_{i^{*}}^{t+1}$. Then in iteration $t$, Step 3 was executed,
since otherwise $p^{t}\leq p^{t+1}$ and $R_{i^{*}}^{t}=R_{i^{*}}^{t+1}$, so
$t+1$ would not be minimal. Hence, in iteration $t$, we have $j^{*}\in
J_{i^{*}}^{t}$ and in particular $j^{*}\in
D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})$. Because Step 3 is executed, we have
$O^{t-1}\neq\emptyset$, so in iteration $t-1$ Step 4 was executed and
$p^{t}(j^{*})=p^{t-1}(j^{*})+1=p^{t+1}(j^{*})+1\leq b^{i^{*}}$. Thus, since
from iteration $t-1$ to $t$, all prices for all preferred goods of bidder
$i^{*}$ were raised and $i^{*}$ can still afford $j^{*}$ at prices $p^{t}$,
$j^{*}\in D_{i^{*}}(p^{t},R_{i^{*}}^{t})$, so $j^{*}\not\in J_{i^{*}}^{t}$.
This is a contradiction. ∎

######  Proposition 3.

For every iteration $t$ in the auction, it holds:

  1. 1.

if there is a minimally underdemanded set of items $T$, then $T\subseteq
O^{t-1}$ and Step 3 is executed

  2. 2.

if Step 3 is executed, there is no underdemanded set of items with respect to
the $D_{i}(p^{t+1},R_{i}^{t+1})$.

###### Proof.

We prove this by induction on $t$. For $t=1$, there clearly is no
underdemanded set of items, and Step 3 is not executed.

Suppose now that $t>1$ and that the statement is true for all $1\leq s<t$.

First suppose that there exists an underdemanded set of items $T$. Therefore,
by induction, in iteration $t-1$, Step 4 must have been executed - otherwise,
there would not exist an underdemanded set. But then, using the same inductive
reasoning, there was no underdemanded set in iteration $t-1$. It is thus easy
to see that, since in iteration $t-1$ only prices for items in $O^{t-1}$ were
raised, only the demand for those items could decrease, so $T$ must be a
subset of $O^{t-1}$. By Lemma 2, we have

$|\\{i\in\mathcal{B}\,:\,D_{i}(p^{t-1},R_{i}^{t-1})\subseteq
O^{t-1}\,\cap\,D_{i}(p^{t-1},R_{i}^{t-1})\cap T\neq\emptyset\\}|>|T|.$

Thus, since $|\\{i\in\mathcal{B}\,:\,D_{i}(p^{t},R_{i}^{t})\cap
T\neq\emptyset\\}|<|T|$, there must be a bidder $i^{*}$ with
$D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})\subseteq O^{t-1}$ and
$D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})\cap T\neq\emptyset$, but
$D_{i^{*}}(p^{t},R_{i^{*}}^{t})\cap T=\emptyset$. This implies that $i^{*}\in
I^{t}$, so Step 3 is executed in iteration $t$.

Now suppose that Step 3 is executed in iteration $t$. Then again, in iteration
$t-1$, Step 4 was executed, since otherwise we would have $O^{t-1}=\emptyset$,
which implies $I^{t}=\emptyset$. By induction, there was no underdemanded set
of items in iteration $t-1$. Note that $p^{t-1}=p^{t+1}$, so only the demand
of a single bidder $i^{*}\in I^{t}$ chosen in Step 3 does change. Since
$D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})\subseteq O^{t-1}$, so
$J_{i^{*}}^{t}\subseteq O^{t-1}$, only the demand for items in $O^{t-1}$ can
decrease. However, for $T\subseteq O^{t-1}$ we have again by Lemma 2 that

$|\\{i\in\mathcal{B}\,:\,D_{i}(p^{t-1},R_{i}^{t-1})\subseteq
O^{t-1}\,\cap\,D_{i}(p^{t-1},R_{i}^{t-1})\cap T\neq\emptyset\\}|>|T|,$

and, since we only changed $R_{i^{*}}^{t-1}$, the demand for items in $T$ can
at most decrease by $1$. Thus, $T$ is not underdemanded in iteration $t+1$. ∎

Employing the previous lemmata, we can proceed to prove correctness of our
proposed auction.

######  Proposition 4.

The auction terminates after a finite number of iterations, and an assignment
$\mu$ as is described in Step 5 exists whenever this Step is reached. The
returned tuple $(\mu,p)$ constitutes a core outcome.

###### Proof.

Whenever Step 3 is executed, at least one item is removed from the set
$R_{i}^{t}$ of one bidder. Hence, Step 3 can only be called a finite number of
times. Also, prices can only be increased a finite number of times in Step 4 -
if prices of goods go to infinity, they are clearly not overdemanded at some
point anymore. Thus, in some iteration $t^{*}$, Step 5 is executed. By Lemma
3, there is no underdemanded set in iteration $t^{*}$, because otherwise Step
3 would have been executed. Similarly, there is no overdemanded set. Finally,
because of Lemma 3, no set $R_{i}^{t^{*}}$ is empty, so by Proposition 2, an
assignment $\mu$ as required exists. By Lemma 1, $(\mu,p)$ is a core outcome.
∎

######  Example 3.

Consider the example following auction with three bidders $1,2,3$ and two
items $A$ and $B$.

| $v_{i}(A)$ | $v_{i}(B)$ | $b^{i}$
---|---|---|---
Bidder $i=1$ | $10$ | $0$ | $1$
Bidder $i=2$ | $0$ | $10$ | $2$
Bidder $i=3$ | $10$ | $10$ | $10$

The auction proceeds as follows.

| $p^{t}$ | $D_{1}(p^{t},R_{1}^{t})$ | $D_{2}(p^{t},R_{2}^{t})$ | $D_{3}(p^{t},R_{3}^{t})$ | $R_{1}^{t}$ | $R_{2}^{t}$ | $R_{3}^{t}$ | $O^{t}$ | $I^{t}$
---|---|---|---|---|---|---|---|---|---
$t=1$ | $(0,0)$ | $\\{A\\}$ | $\\{B\\}$ | $\\{A,B\\}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\\{A,B\\}$ | $\emptyset$
$t=2$ | $(1,1)$ | $\\{A\\}$ | $\\{B\\}$ | $\\{A,B\\}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\\{A,B\\}$ | $\emptyset$
$t=3$ | $(2,2)$ | $\\{0\\}$ | $\\{B\\}$ | $\\{A,B\\}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\emptyset$ | $\\{1\\}$
$t=4$ | $(1,1)$ | $\\{0\\}$ | $\\{B\\}$ | $\\{A,B\\}$ | $\\{0,B\\}$ | $\mathcal{S}$ | $\mathcal{S}$ | $\emptyset$ | $\emptyset$

In iterations $t=1,2$, there is a unique minimally overdemanded set
$O^{t}=\\{A,B\\}$, and $I^{t}$ is empty. Thus, Step 4 of the auction is
executed and the prices for $A$ and $B$ are raised. In iteration $t=3$, the
set $I^{t}=\\{1\\}$ is nonempty which indicates that bidder 1’s budget was
tight for $A$ at prices $(1,1)$. Thus, we forbid $1$ to receive item $A$ and
reset the prices to $(1,1)$. Now, in iteration $t=4$, there is no overdemanded
set and $I^{t}$ is empty. Thus, there exists an assignment $\mu$ with
$\mu(i)\in D_{i}(p^{4},R_{i}^{4})$ for all $i\in\mathcal{B}$, namely
$\mu(1)=0$, $\mu(2)=B$ and $\mu(3)=A$. It is easily checked that $(\mu,p)$ is
indeed a core outcome.

######  Example 4.

Let us now consider an example of an auction where a non-trivial decision has
to be made in Step 3.

| $v_{i}(A)$ | $v_{i}(B)$ | $b^{i}$
---|---|---|---
Bidder $i=1$ | $10$ | $0$ | $3$
Bidder $i=2$ | $0$ | $11$ | $1$
Bidder $i=3$ | $5$ | $3$ | $10$

It is easy to see that after $3$ iterations through Step 4 of our auction, we
reach prices $p^{4}=(3,1)$, where bidder $1$ demands $\\{A\\}$, bidder $2$
demands $\\{B\\}$ and bidder $3$ demands $\\{A,B\\}$. Since $\\{A,B\\}$ is
minimally overdemanded, we execute Step $4$ once again to reach $p^{5}=(4,2)$,
where due to the budget constraints, we have $D_{1}(p^{5},R_{1}^{5})=\\{0\\}$
and $D_{2}(p^{5},R_{2}^{5})=\\{0\\}$, while bidder $3$ still demands
$\\{A,B\\}$. Thus, Step 3 of the auction is executed with $I^{5}=\\{1,2\\}$,
so both bidders $1$ or $2$ would be valid bidders to choose in Step 3. For the
choice $i=1$, we have $J^{5}_{i}=\\{A\\}$, while for the choice $i=2$, we have
$J^{5}_{i}=\\{B\\}$. We could thus either remove $A$ from $R^{5}_{1}$, or $B$
from $R^{5}_{2}$. Depending on our choice, we get two different core outcomes,
both supported by the prices $p=(3,1)$: one where bidder $1$ receives nothing,
bidder $2$ receives $B$ and bidder $3$ receives $A$, and one where bidder $1$
receives $A$, bidder $2$ receives nothing and bidder $3$ receives $B$. The
total welfare of the former allocation is $16$, while the one of the latter is
$13$.

###  4.2 Economic Properties

The output produced by our iterative auction is not uniquely defined - it may
depend on which bidder $i\in I^{t}$ is chosen whenever Step 3 is executed.
Indeed, we prove the following result.

######  Proposition 5.

Let $(\nu,q)$ be an arbitrary core outcome. Then bidders $i\in I^{t}$ in Step
3 can be chosen in such a way, that for the resulting outcome $(\mu,p)$ we
have that $p\leq q$ coefficient-wise, and
$\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$ for all bidders $i$.

The proof can be found in the Appendix.

We say that a core outcome is $(\mu,p)$ _Pareto optimal for the bidders_ , if
for every core outcome $(\nu,q)$ with $\pi_{i}(\nu(i),q)>\pi_{i}(\mu(i),p)$
for some bidder $i$, there is a bidder $i^{\prime}$ with
$\pi_{i^{\prime}}(\mu(i^{\prime}),p)>\pi_{i^{\prime}}(\nu(i^{\prime}),q)$.
Proposition 5 directly implies that for every core outcome which is Pareto
optimal for the bidders, there is an outcome $(\mu,p)$ reachable by the
auction with $\pi_{i}(\mu(i),p)=\pi_{i}(\nu(i),q)$ for all $i\in\mathcal{B}$.
Aggarwal et al. (2009) prove that their algorithm for computing a core-stable
outcome always finds the bidder-optimal core outcome $(\mu,p)$, whenever the
auction is in general position. Here, _bidder-optimal_ means that for every
other core outcome $(\nu,q)$ we have that
$\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$ for all $i\in\mathcal{B}$. Bidder-
optimality thus implies Pareto optimality. We show a similar result for our
auction: if the bidder to choose in Step 3 of our auction is always unique,
our auction also finds a bidder-optimal core outcome.

######  Corollary 1.

Suppose that whenever Step 3 is executed, $|I^{t}|=1$, i.e., there is a unique
bidder to choose, and let $(\mu,p)$ be the uniquely determined outcome of the
auction. Then for any core outcome $(\nu,q)$ we have that $p\leq q$ and
$\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$ for all bidders $i$, i.e., $(\mu,p)$
is bidder-optimal.

###### Proof.

Since $|I^{t}|=1$ in every iteration through Step 3, the outcome $(\mu,p)$ of
the auction is unique. Proposition 5 now directly implies that for every core
outcome $(\nu,q)$, we have $\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$ and $p\leq
q$. ∎

In particular, if the general position condition is satisfied, it can be shown
that $I^{t}$ never contains more than one bidder. Thus, our auction always
finds a bidder-optimal outcome like the auction by Aggarwal et al. (2009) in
this case.

######  Proposition 6.

Suppose the auction is in general position. Then in every iteration through
Step 3 of our iterative auction, we have that $|I^{t}|=1$, and for the unique
$i\in I^{t}$, we have $|J_{i}^{t}|=1$.

Note that in general that our ex-post condition $|I^{t}|=1$ whenever Step 3 is
reached is less demanding than the general position condition, since we do not
require $|J_{i}^{t}|=1$, and it is easy to construct examples where
$|J_{i}^{t}|>1$, but the ex-post condition is fulfilled. While our condition
is only ex-post, it is straight-forward to check for the auctioneer when the
auction is actually performed.

Let us now consider welfare-maximization properties of our auction. We first
observe that a welfare maximizing core outcome can always be found among the
ones which are Pareto optimal for the bidders.

######  Proposition 7.

Let $(\mu,p)$ and $(\nu,q)$ be core outcomes. If
$\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$ for all bidders $i$, then

$\sum_{i\in\mathcal{B}}v_{i}(\mu(i))\geq\sum_{i\in\mathcal{B}}v_{i}(\nu(i)).$

The proofs of Propositions 6 and 7 can be found in the Appendix.

As we described above, by Proposition 5, we can reach any core outcome which
is Pareto optimal for the bidders with our auction, and Proposition 7 says
that one of them must be welfare-maximizing. Now if we always have
$|I^{t}|=1$, the outcome of our auction is unique which proves our first main
result.

######  Theorem 1.

Bidders in $I^{t}$ in Step 3 of the auction can be chosen such that the
outcome of the auction is a welfare-maximizing core outcome.

In particular, if $|I^{t}|=1$ whenever Step 3 is reached, the unique outcome
of the auction is a welfare-maximizing core outcome.

Note that knowledge of the bidders’ demand sets does not suffice in order to
always choose the “correct” bidders in Step 3 to reach a welfare-maximizing
outcome. Our hardness result in Section 5 implies that even with perfect
knowledge of the bidders’ preferences, choosing the correct bidders in Step 3
is NP-hard. However, our simple ex-post condition $|I^{t}|=1$ at least gives
the auctioneer a simple certificate of optimality.

If the auction is in general position, then the auction is ex post incentive-
compatible, which follows from the original work by Demange et al. (1986) and
the paper by Aggarwal et al. (2009). The question is if this algorithm or any
other algorithm where the bidders’ preferences are no further restricted can
be incentive-compatible. Unfortunately, the answer is no because incentive-
compatibility goes against envy-freeness and therefore the core definition as
we show next.

######  Theorem 2.

In assignment markets with payoff-maximizing but budget constrained bidders
there is no incentive-compatible mechanism terminating in a core-stable
solution for every input.

###### Proof.

By the direct revelation principle, we may assume that bidders report their
exact valuations, as well as their budgets to the auctioneer. Consider a
market with three bidders $1,2,3$ and two items $A,B$. Let
$\mathcal{M}((v_{1},b^{1}),\dots,(v_{3},b^{3}))=(\mu,p)$ denote a mechanism,
mapping the bidders’ reported valuations and budgets to a core-stable outcome
with respect to their reports.

We consider instances of the above described market, where all bidders have
the same values for both items: $v_{i}(A)=v_{i}(B)=10$ for $i=1,2,3$. Let us
consider two instances, where the bidders vary their reported budget.

  1. 1.

If all bidders report $b^{i}=1$ for $i=1,2,3$, then obviously, since there are
only two items, one bidder does not receive one: for
$(\mu,p)=\mathcal{M}((v_{1},1),(v_{2},1),(v_{3},1))$, there is an $i$ with
$\mu(i)=0$. Without loss of generality, we assume that $i=3$. It is easy to
see that for core-stability to hold, bidders $1$ and $2$ both receive an item,
and that $p(A)=p(B)=1$. Bidders $1$ and $2$ have utility $9$, while bidder $3$
has utility $0$.

  2. 2.

If bidder $3$ reports $b^{3}=2$, and the other bidders report $b^{1}=b^{2}=1$,
then clearly bidder $3$ receives an item in any core-stable outcome, and
without loss of generality $\mu(3)=B$. Also the other item $A$ must
necessarily be assigned to some bidder. Again, without loss of generality, we
assume that $\mu(1)=A$ and $\mu(2)=0$. It is easy to see that $p(A)$ must be
equal to $1$ in a core outcome. Additionally, we must have $p(A)=p(B)$, since
otherwise bidder $3$ would strictly prefer item $A$ to item $B$, which would
not be envy-free. Thus, $p(A)=p(B)=1$, and bidder $3$ has a utility of $9$.

This already shows that $\mathcal{M}$ is not incentive-compatible: If all
bidders’ true budgets are equal to $1$ and they report truthfully, bidder $3$
has a utility of $0$. However, if bidder $3$ misreports $b^{3}=2$, they would
receive an item and have a utility of $9$. Note, that $p(B)=p(A)=1$ in this
case, so bidder $3$ can still afford the received item. ∎

Note that Theorem 2 does not preclude an incentive-compatible and welfare-
maximizing auction (that is not core-stable). Overall, these iterative
auctions require bidders to reveal that they are indifferent to not winning
the good once the price equals the valuation of a bidder. Only this allows
auctioneers to differentiate between a bidder dropping out due to reaching his
valuation or his budget. In practice, bidders might not always bid the null
set when price reaches value even in an incentive-compatible auction, which
can lead to inefficiencies in such iterative auctions.

##  5 A Sealed-Bid Auction

If in some iteration of the above algorithm Step 3 is reached with
$|I^{t}|>1$, the ascending auction with only demand queries does not
necessarily find the welfare-maximizing core-stable outcome. In such a case, a
combination of value and demand queries is required in order to obtain the
desired assignment. To this end, for the remaining part of this paper, we
assume the auctioneer has unlimited access to all valuations for all objects
and the budgets of all bidders. Unfortunately, the outcome and pricing problem
does not only need a different oracle but it also becomes NP-complete as we
will show next. Besides, as we mentioned above, the property of
strategyproofness does not hold.

###  5.1 A MILP Formulation

First, we show that the problem belongs to complexity class NP by modeling it
as a mixed integer linear program (MILP). Once a problem is modeled as such,
there is a polynomial-time non-deterministic algorithm, where we guess the
values of integer variables and solve the resulting linear program (LP) in
polynomial time. Bi-linear terms present in the quadratic formulation (q-BC),
namely products of continuous prices $p(j)$ and binary variables, can easily
be linearized to obtain the resulting MILP.

$\displaystyle\begin{array}[]{@{}l@{\quad}l@{\qquad}l@{}r@{}}\textrm{maximize}&\sum\limits_{i\in\mathcal{B}}\pi_{i}+\sum\limits_{j\in\mathcal{S}}\pi_{j}\\\
\textrm{subject
to}&\pi_{i}=\sum\limits_{j\in\mathcal{S}}(v_{i}(j)-p(j))m_{i}(j)&\forall
i\in\mathcal{B}&\ (1)\\\
&\pi_{j}=\sum\limits_{i\in\mathcal{B}}(p(j)-r_{j})m_{i}(j)&\forall
j\in\mathcal{S}&\ (2)\\\ &\sum\limits_{j\in\mathcal{S}}m_{i}(j)\leq 1&\forall
i\in\mathcal{B}&\ (3)\\\ &\sum\limits_{i\in\mathcal{B}}m_{i}(j)\leq 1&\forall
j\in\mathcal{S}&\ (4)\\\
&\pi_{i}\geq\big{(}v_{i}(j)-p(j)\big{)}\alpha_{i}(j)&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (5)\\\ &\pi_{j}\geq
min(v_{i}(j),b^{i})(1-y_{i}(j))&\forall i\in\mathcal{B},j\in\mathcal{S}&\
(6)\\\ &b^{i}\geq p_{j}(1-\beta_{i}(j))&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (7)\\\ &p_{j}\geq b^{i}\beta_{i}(j)&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (8)\\\
&(1-\alpha_{i}(j))+(1-\beta_{i}(j))-2\leq 2(1-y_{i}(j))+\epsilon
y_{i}(j)&\forall i\in\mathcal{B},j\in\mathcal{S}&\ (9)\\\ &r_{j}m_{i}(j)\leq
p(j)\leq min(v_{i}(j),b^{i})m_{i}(j)+M(1-m_{i}(j))&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (10)\\\ &m_{i}(j)\in\\{0,1\\}&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (11)\\\ &y_{i}(j)\in\\{0,1\\}&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (12)\\\ &\alpha_{i}(j)\in\\{0,1\\}&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (13)\\\ &\beta_{i}(j)\in\\{0,1\\}&\forall
i\in\mathcal{B},j\in\mathcal{S}&\ (14)\\\ &p(j)\geq 0&\forall
j\in\mathcal{S}&\ (15)\\\ \end{array}$ (19)

In this section, an assignment of buyer $i$ to seller $j$ is denoted as a
binary variable $m_{i}(j)$, since solving the MILP requires variable
definitions. If the resulting assignment assigns the aforementioned pair in
this fashion, then $m_{i}(j)=1$, and for all other buyers except $i$,
$m_{-i}(j)=0$. The equivalence to the previous definitions is
$m_{i}(j)=1\Leftrightarrow\mu(i)=j$. In order to check for the existence of
deviating coalitions, two additional binary variables are introduced. Setting
$\alpha_{i}(j)=0$ represents the case where bidder $i$ has a benefit from
deviating by trading with seller $j$, and $a_{i}(j)=1$ means that the bidder
is best satisfied under the current assignment. The second helper binary
variable is set to $\beta_{i}(j)=0$ if $i$ possesses a sufficient amount of
money to purchase $j$, and set to $\beta_{i}(j)=1$, if the budget of bidder
$i$ is insufficient to acquire item of seller $j$, namely the set price of
item $j$ exceeds $i$’s budget constraint. Variable $y_{i}(j)=0$ reflects the
case where bidder $i$ prefers to trade with seller $j$ and has sufficient
budget, and the variable is set to 1 if one of the two necessary conditions
does not hold.

Utilities of buyers and sellers are defined as previously argued in Section 3.
With $r_{j}$, we describe the reserve value or ask price of seller $j$.
Constraints (1) and (2) represent the utilities of buyers and sellers,
respectively. Constraints (5) and (6) guarantee core-stability. We examine all
possible deviating combinations of buyer-seller pairs for a given outcome.
Constraint (5) examines whether the corresponding payoff $\pi_{i}$ a buyer $i$
receives in the selected assignment $m$ is higher or equal to the alternative
assignment $(i,j)$ in question. In particular, this constraint checks whether
an assignment $(i,j)$ yields a higher payoff for buyer $i$, in which case
$\alpha_{i}(j)=0$. Constraint (6) tests whether a seller $j$’s payoff
$\pi_{j}$ on the optimal matching $m$ is higher or equal to the minimum value
between any buyer $i$’s budget constraint $b^{i}$ and $i$’s valuation for the
item $v_{i}(j)$, which represents the maximum possible payment seller $j$
could receive from any buyer. One or both of these conditions need to be true.
Put differently, if both buyer and seller had a higher payoff under an
alternative assignment $(i,j)$, outcome $m$ is not core-stable. In essence,
core-stability can be expressed as logical or constraint. Constraints (7) and
(8) examine whether bidder $i$ has a sufficient budget to obtain item $j$
under price $p_{j}$. Constraint (9) is responsible for handling the value of
$y_{i}(j)$ in an appropriate manner, to reflect whether a deviating coalition
of $(i,j)$ is indeed profitable and budget-feasible, for any positive value
$\epsilon<1$. The value of $y_{i}(j)$ depends on binary values
$\alpha_{i}(j),\beta_{i}(j)$, and we verify our claim by examining the
inequalities formed by the different value combinations (the tuple on the left
side represents values $\alpha_{i}(j),\beta_{i}(j),y_{i}(j)$):

$(0,0,0)\Rightarrow 1+1-2\leq 2\cdot 1-\epsilon\cdot 0\ \ (1^{*})$
$(0,0,1)\Rightarrow 1+1-2\leq 2\cdot 0-\epsilon\cdot 1\ \ (2^{*})$
$(0,1,1)\Rightarrow 1+0-2\leq 2\cdot 0-\epsilon\cdot 1\ \ (3^{*})$
$(1,0,1)\Rightarrow 0+1-2\leq 2\cdot 0-\epsilon\cdot 1\ \ (4^{*})$
$(1,1,1)\Rightarrow 0+0-2\leq 2\cdot 0-\epsilon\cdot 1\ \ (5^{*})$

In cases $(1^{*})$ and $(2^{*})$, agent $i$ has a sufficient budget and can
profit from deviating. However, inequality $(2^{*})$ is infeasible, therefore
the value of $y_{i}(j)$ cannot be set to 1 for this combination of
$\alpha_{i}(j),\beta_{i}(j)$ and is forced to 0. For the remaining cases,
either $i$ does not have sufficient budget ($\beta_{i}(j)=1$), or has no
profit from trading with $j$ ($\alpha_{i}(j)=1$), or both conditions hold. In
all the aforementioned cases, $y_{i}(j)=1$, and thus reflects the case where
no deviation is preferable from the buyer’s side.

Constraint (10) then makes sure that if an item $j$ is assigned to buyer $i$,
then the price is less than the minimum of the budget of this buyer or his
value, and it is higher than the reserve price of the seller. We can conclude
that the above formulation always results in a the welfare-maximizing core-
stable outcome for assignment markets with budget constraints.

###  5.2 Complexity Analysis

We now proceed to the proof of NP-completeness. The existence of endogenous
pricing variables renders the proof non-trivial: there is no standard method
of encoding both continuous and discrete variables, for prices and assignment,
in a problem instance. Therefore, the proof requires a more complicated
structure and special assumptions regarding the handling of item prices.
First, we formally define the decision version of the problem.

Maximum Welfare Budget Constrained Stable Bipartite Matching (MBSBM)

Input: Two disjoint sets $\mathcal{S}$ (sellers) and $\mathcal{B}$ (buyers) of
$n$ agents each, a budget $b^{i}$ for each agent $i\in\mathcal{B}$ and a
reserve value $r_{j}$ for each seller $j\in\mathcal{S}$, a value $v_{i}(j)$
for each pair of agents $i\in\mathcal{B}$ and $j\in\mathcal{S}$, and a non-
negative integer $k$.

Output: Boolean value

Question: Does there exist a stable outcome $\mu$ such that the total value
$\sum_{i\in\mathcal{B}}(v_{i}(\mu(i))-r_{\mu(i)})\geq k$?

We have already discussed that the problem is in NP, because MBSBM can be
modeled as a MILP where all the reserve values $r_{j}$ of sellers
$j\in\mathcal{S}$ are set to 0, and such problems are contained in NP (Del Pia
et al., 2017). We know that for the case when all budgets are too high and
therefore non-binding, $b^{i}\geq v_{i}(j)$ for all $i\in\mathcal{B}$ and
$j\in\mathcal{S}$, the problem is equivalent to the maximum-weight bipartite
matching, which admits a polynomial time solution via the Hungarian algorithm
(Kuhn, 1955). Core-stable prices can be derived from the duals of the
corresponding linear program (Shapley and Shubik, 1971). Therefore, the case
of interest that can result in increased computational cost is when budgets
are binding for participating buyers. For our problem, we reduce from the
Maximum Independent Set (MIS) problem, which is known to be APX-hard, thus
implying NP-hardness. Chen et al. (2021) follows a similar approach for
fractional matching without transferable utility. However, an environment with
partially transferable utility as in our case, requires special attention and
leads to significant differences.

Maximum Independent Set (MIS)

Input: A graph $G=(V,E)$, with vertices $V$ and edges $E$, and a non-negative
integer $k$.

Output: Boolean value

Question: Does there exist an Independent Set (IS) of size at least $k$, where
as IS we define a set of vertices no two of which are adjacent?

The proof uses a specific construction in which we introduce an individual
vertex and an edge gadget for each vertex and edge of the original MIS
problem. In complexity theory, when performing a reduction from computational
problem A to problem B, the term gadget refers to a subset of a problem
instance of problem B, that simulates the behavior of certain units of problem
A. Drawing from graph theory, the vertex and edge gadgets are bipartite graphs
where each edge gadget is connected to two vertex gadgets, corresponding to
the two endpoints of the original edge. Each vertex has a degree of three and
thus each vertex gadget is connected to three edge gadgets. The edge gadget
allows for two matchings between buyer and seller nodes, which all lead to the
same welfare. The vertex gadgets also allow for two feasible stable matchings,
where the welfare differs by one. The edges between an edge and a vertex
gadget are such that it is not possible to select the welfare-maximizing
matching in two consecutive vertex gadgets of two neighboring vertices,
because it would generate pairs of blocking agents in the edge gadget of the
connecting edge, i.e. a matching in the edge gadget would not be core-stable.
Similar to the original MIS problem, where there cannot be two adjacent
vertices in an IS, in our construction, there cannot be two adjacent vertex
gadgets with a high welfare matching. While in the MIS problem, we need to
find the IS that is maximal, in the MBSBM problem we need to determine the
stable matching of the overall bipartite graph that maximizes welfare. Note
that both the vertex and edge gadgets contain a pair of buyers that admit the
same budget constraint, thus leading to a violation of the general position
condition. Let us now discuss the construction and proof in detail.

####  5.2.1 Construction

Assume an instance of MIS defined on a cubic graph $G=((V,E),k)$. A cubic
graph is a graph in which all vertices have degree three. We define the
transformed instance as a bipartite graph
$G^{\prime}=(V^{\prime},E^{\prime})$, with
$V^{\prime}=\mathcal{B}\cup\mathcal{S}$, and functions
$\pi_{i}:\mathcal{S}\rightarrow\mathbb{R}_{\geq 0}$ for each buyer
$i\in\mathcal{S}$, and $\pi_{j}:\mathcal{B}\rightarrow\mathbb{R}_{\geq 0}$ for
each seller $j\in\mathcal{S}$ that represents agents’ payoffs.

  * •

$V^{\prime}$ represents the total set of agents

  * •

$\mathcal{B}$ and $\mathcal{S}$ denote the sets of buyers and sellers
respectively

  * •

$E^{\prime}$ represents the potential transactions between buyers and sellers

  * •

$\pi_{i}$ specifies the difference between the true valuation of buyer
$i\in\mathcal{B}$ for the item of seller $j\in\mathcal{S}$ and her total
budget $b^{i}$, namely $v_{i}(j)-b^{i}$

  * •

$\pi_{j}$ specifies difference between the budget of buyer $i\in\mathcal{B}$
and the reserve value of seller $s\in\mathcal{S}$, namely $b^{i}-r_{j}$

Since we assume that all assigned buyers pay prices for items equal to their
budgets, we omit prices from the payoff formulae $\pi_{i},\pi_{j}$. In Lemma 5
we show that this restriction of the prices to be at the budgets is without
loss of generality for the construction. Observe that in our construction
multiple buyers share the same budget constraint, which violates the general
position condition from Definition 3.

An assignment $\mu:\mathcal{B}\rightarrow\mathcal{S}$ in $G^{\prime}$ assigns
each edge $e\in E^{\prime}$ according to the condition
$\sum_{j\in\mathcal{S}}|\mu(i)=j|\leq 1$ for any agent $i\in\mathcal{B}$. The
utility of agent $i\in\mathcal{B}$ under assignment $\mu$ of
$(G^{\prime},\pi_{i},\pi_{j})$ is defined as $\pi_{i}(\mu):=\pi_{i}(\mu(i))$
and similarly for agent $j\in\mathcal{S}$ it holds that
$\pi_{j}(\mu):=\pi_{j}(\mu^{-1}(j))$. Given an assignment $\mu$, an edge
$(i,j)\in E^{\prime}$ is a blocking pair/ edge if $\pi_{i}(\mu(i))<\pi_{i}(j)$
and $\pi_{j}(\mu^{-1}(j))<\pi_{j}(i)$. An assignment $\mu$ is stable if it
does not contain any blocking pair of agents.

Edge Gadget. Starting from an edge $e\in E$ of the original graph $G$, we
construct the edge gadget $G^{\prime}_{e}=\mathcal{B}_{e}\cup\mathcal{S}_{e}$
as a bipartite graph, with preferences for the subgraph defined as mentioned
above and noted as $\pi_{i}:\mathcal{S}_{e}\rightarrow\mathbb{R}_{\geq 0}$ and
$\pi_{j}:\mathcal{B}_{e}\rightarrow\mathbb{R}_{\geq 0}$ for each of the two
sets respectively. The vertices represent participating $agents$.

For each edge $e=(u,u^{\prime})\in E$, we proceed to the following
construction:

  * •

Add to $\mathcal{B}_{e}$ three agents $\beta_{e},\gamma_{e},\delta_{e}$

  * •

Add to $\mathcal{S}_{e}$ three agents
$\eta_{e},\alpha^{u}_{e},\alpha^{u^{\prime}}_{e}$

  * •

Add to $\mathcal{B}_{e}$ two extra agents $\epsilon_{u}$ and
$\epsilon_{u^{\prime}}$, if not present already. These represent the
connection from edge gadget to vertex gadget.

Vertices $\alpha^{u}_{e}$ and $\alpha^{u^{\prime}}_{e}$ represent the gates to
the vertex gadgets, which are connected to the vertices
$\epsilon_{u},\epsilon_{u^{\prime}}$ of the vertex gadgets of $u,u^{\prime}$
of the original graph.

For each edge $e\in E$ of the original graph $G$, the corresponding edge
gadget consists of subgraph that agents
$\\{\beta_{e},\gamma_{e},\delta_{e}\\}\cup\\{\eta_{e},\alpha^{u}_{e},\alpha^{u^{\prime}}_{e}\\}$
induce. The detailed construction is depicted in Figure 1. Any edge not
present in the figure is assigned a value of zero.

Figure 1: The edge gadget, with corresponding buyer and seller preferences $\pi_{i},\pi_{j}$. If $u$ belongs to the independent set $IS(G)$, then we integrally match the pairs corresponding to the solid edges, otherwise we match the dashed edges. | $\alpha^{u}_{e}$ | $\eta_{e}$ | $\alpha^{u^{\prime}}_{e}$ | $b^{i}$
---|---|---|---|---
$\beta_{e}$ | 0 | $2|E|^{2}+12$ | $2|E|^{2}+11$ | 9
$\gamma_{e}$ | $2|E|^{2}+12$ | 0 | $2|E|^{2}+13$ | 7
$\delta_{e}$ | $2|E|^{2}+16$ | $2|E|^{2}+18$ | 0 | 9
$\epsilon_{u}$ | 3 | 0 | 0 | 8
$\epsilon_{u^{\prime}}$ | 0 | 0 | 7 | 8
$r_{j}$ | 5 | 8 | 1 |
Table 1: Valuation table representing valuations $v_{i}(j)$ where
$i\in\\{\beta_{e},\gamma_{e},\delta_{e},\epsilon_{u},\epsilon_{u^{\prime}}\\}$
and $j\in\\{\alpha^{u}_{e},\eta_{e},\alpha^{u^{\prime}}_{e}\\}$. $b^{i}$
corresponds to the budget of each buyer and $r_{j}$ to the reserve value of
each seller.

An important observation is, that any edge gadget $G^{\prime}_{e}$ should
contain two feasible stable assignments, with an equal total social welfare.
In every stable assignment $\mu$, at least one of
$\\{\alpha^{u}_{e},\alpha^{u^{\prime}}_{e}\\}$ is unsatisfied under $\mu$,
namely agents $\alpha^{u}_{e}$ or $\alpha^{u^{\prime}}_{e}$ have a preference
towards $\epsilon_{u}$ or $\epsilon_{u^{\prime}}$ respectively.

Vertex Gadget. In a similar manner, we construct the vertex gadget
corresponding to vertex $u\in V$.

Figure 2: The vertex gadget, with corresponding buyer and seller preferences. If $u$ belongs to the independent set $IS(G)$, then we integrally match the pairs corresponding to the solid edges, otherwise, we match the dashed edges. | $\kappa_{u}$ | $\lambda_{u}$ | $\xi_{u}$ | $N(\epsilon_{u})$ | $b^{i}$
---|---|---|---|---|---
$\epsilon_{u}$ | 0 | $|V|+17$ | $|V|+13$ | $n+16$ | 8
$\zeta_{u}$ | $|V|+9$ | 0 | $|V|+10$ | 0 | 6
$\theta_{u}$ | $|V|+9$ | $|V|+15$ | 0 | 0 | 8
$r_{j}$ | 2 | 7 | 1 | 5/1 |
Table 2: Valuation table representing valuations $v_{i}(j)$ where
$i\in\\{\epsilon_{u},\zeta_{u},\theta_{u}\\}$ and
$j\in\\{\kappa_{u},\lambda_{u},\xi_{u},N(\epsilon_{u})\\}$. $N(\epsilon_{u})$
consists of the neighboring vertices of $\epsilon_{u}$ in the edge gadgets of
$\alpha^{u}_{\epsilon_{1}},\alpha^{u}_{\epsilon_{2}},\alpha^{u}_{\epsilon_{3}}$,
since each vertex $u$ has a degree of 3. $b^{i}$ corresponds to the budget of
each buyer and $r_{j}$ to the reserve value of each seller in the vertex
gadget.

Figure 2 illustrates the vertex gadget $G^{\prime}_{u}$ corresponding to a
vertex $u\in V$, along with the preferences of buyers and sellers. Agents
colored in gray belong to set $\mathcal{B}_{u}$, and agents in white belong to
$\mathcal{S}_{u}$, defined in an analogous manner to
$\mathcal{B}_{e},\mathcal{S}_{e}$. Two feasible stable outcomes exist in
$G^{\prime}_{u}$, resulting in welfare that differs by 1: in case an
assignment indicated by the solid edges is chosen, induced welfare equals
$|V|+27$, while for an assignment of the dashed edges, welfare has a value of
$|V|+26$. The set $N(\epsilon_{u})$ represents the neighborhood of $\epsilon$,
and consists of three vertices from three distinct edge gadgets.

The following lemma provides a useful bound for the achieved social welfare of
an optimal assignment in an edge gadget.

######  Lemma 4.

Let $\mu$ be a stable assignment for edge gadget $G^{\prime}_{e}$. The total
welfare $SW$ achieved by $\mu$ is at most $|E|\cdot(6|E|^{2}+27)$. If there is
an edge $(u,u^{\prime})\in E$, where for the gadgets it holds that
$\pi_{\epsilon_{u}}(\mu(\epsilon_{u}))<\pi_{\epsilon_{u}}(\alpha^{u}_{e})$ and
$\pi_{\epsilon_{u^{\prime}}}(\mu(\epsilon_{u^{\prime}}))<\pi_{\epsilon_{u^{\prime}}}(\alpha^{u^{\prime}}_{e})$,
then $SW<|E|\cdot(6|E|^{2}+27)-|V|$.

This lemma implies that, in any welfare-maximizing assignment, edges between
$\\{\alpha^{u}_{e},\epsilon_{u}\\}$ and
$\\{\alpha^{u^{\prime}}_{e},\epsilon_{u^{\prime}}\\}$ are never chosen.
Furthermore, at most one of the conditions
$\pi_{\epsilon_{u}}(\mu(\epsilon_{u}))<\pi_{\epsilon_{u}}(\alpha^{u}_{e})$ and
$\pi_{\epsilon_{u^{\prime}}}(\mu(\epsilon_{u^{\prime}}))<\pi_{\epsilon_{u^{\prime}}}(\alpha^{u^{\prime}}_{e})$
must hold, otherwise assignment $\mu$ is not maximizing welfare.

In our construction, we fix the price for each matching to the budget
constraint of the buyer to whom a seller is matched. Next, we show that this
restriction is without loss of generality. We show in each bipartite graph,
regardless of whether it belongs to the vertex or edge gadget, the current
scheme yields all possible welfare-maximizing, core-stable outcomes.

######  Lemma 5.

Assuming that all buyers pay a price equal to their budget for their assigned
items does not impact generality, namely there does not exist a welfare-
maximizing, core-stable outcome that is not reachable through this pricing
scheme.

Finally, we build the main complexity result for MBSBM. The proof uses no
assumption on specific properties (such as general position) to hold.

######  Theorem 3.

MBSBM is NP-complete.

The proofs of Lemmata 4, 5 and of Theorem 3 can be found in the Appendix.

##  6 Conclusions

In this work, we showed that there is no incentive-compatible mechanism that
selects an outcome in the core for bidders with unit-demand valuations.
However, it is possible to expand the auction algorithm by Demange et al.
(1986), based on demand queries, which terminates with a core allocation if
bidders truthfully reveal their demand set in each round. With an additional
condition on the unit-demand valuations, this mechanism is incentive-
compatible and maximizes welfare. It is typically unknown ex-ante whether this
condition holds.

Overall, the analysis of markets with unit-demand bidders is important as it
aids our understanding about how restrictive the assumptions need to be for a
market to be efficient. In his seminal paper, Vickrey (1961) showed that
markets can be designed such that it is a dominant strategy for participants
to reveal their preferences truthfully. He allows for general valuations
(including substitutes and complements) and only poses a seemingly innocuous
assumption of payoff-maximizing bidders. Budget constraints are wide-spread
and violate the assumptions of the VCG mechanism. We prove that, even in the
simplest markets where bidders only have unit-demand valuations, incentive-
compatibility and core-stability are conflicting. In fact, even if all unit-
demand valuations and budgets were known to the auctioneer, computing a core-
stable and efficient outcome is NP-complete. As a result, claims about the
efficiency of simple (polynomial-time) market designs need to be considered
with care in the many markets where financial constraints of bidders play a
role.

## References

  * (1)
  * Aggarwal et al. (2009) Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, and Martin Pál. 2009.  General Auction Mechanism for Search Advertising _(WWW ’09)_. Association for Computing Machinery, New York, NY, USA, 241–250.
  * Alaei et al. (2016) Saeed Alaei, Kamal Jain, and Azarakhsh Malekian. 2016.  Competitive equilibria in two-sided matching markets with general utility functions.  _Operations Research_ 64, 3 (2016), 638–645.
  * Arrow and Debreu (1954) Kenneth J Arrow and Gerard Debreu. 1954.  Existence of an equilibrium for a competitive economy.  _Econometrica_ 22, 3 (1954), 265–290.
  * Ausubel and Milgrom (2006) Lawrence Ausubel and Paul Milgrom. 2006.  The Lovely but Lonely Vickrey Auction.  In _Combinatorial Auctions_. MIT Press, Cambridge, MA, Chapter 1, 17–40.
  * Baldwin and Klemperer (2019) Elizabeth Baldwin and Paul Klemperer. 2019.  Understanding preferences: demand types, and the existence of equilibrium with indivisibilities.  _Econometrica_ 87, 3 (2019), 867–932.
  * Bichler and Goeree (2017) Martin Bichler and Jacob K Goeree. 2017.  _Handbook of spectrum auction design_.  Cambridge University Press.
  * Bichler and Waldherr (2021) Martin Bichler and Stefan Waldherr. 2021.  Core-Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions.  _Operations Research_ 69 (November 2021).
  * Bikhchandani and Mamer (1997) Sushil Bikhchandani and John W Mamer. 1997.  Competitive equilibrium in an exchange economy with indivisibilities.  _Journal of Economic Theory_ 74, 2 (1997), 385–413.
  * Bikhchandani and Ostroy (2002) Sushil Bikhchandani and Joseph M Ostroy. 2002.  The package assignment model.  _Journal of Economic Theory_ 107, 2 (2002), 377–406.
  * Che and Gale (2000) Yeon-Koo Che and Ian Gale. 2000.  The optimal mechanism for selling to a budget-constrained buyer.  _Journal of Economic Theory_ 92, 2 (2000), 198–233.
  * Chen et al. (2021) Jiehua Chen, Sanjukta Roy, and Manuel Sorge. 2021.  Fractional Matchings under Preferences: Stability and Optimality. In _IJCAI_.
  * Del Pia et al. (2017) Alberto Del Pia, Santanu S Dey, and Marco Molinaro. 2017\.  Mixed-integer quadratic programming is in NP.  _Mathematical Programming_ 162, 1 (2017), 225–240.
  * Demange et al. (1986) Gabrielle Demange, David Gale, and Marilda Sotomayor. 1986\.  Multi-item auctions.  _Journal of Political Economy_ 94, 4 (1986), 863–872.
  * Dobzinski et al. (2008) Shahar Dobzinski, Ron Lavi, and Noam Nisan. 2008.  Multi-unit auctions with budget limits. In _Foundations of Computer Science (FOCS’08)_. IEEE, 260–269.
  * Dütting et al. (2016) Paul Dütting, Monika Henzinger, and Martin Starnberger. 2016\.  Auctions for heterogeneous items and budget limits.  _ACM Transactions on Economics and Computation (TEAC)_ 4, 1 (2016).
  * Dütting et al. (2013) Paul Dütting, Monika Henzinger, and Ingmar Weber. 2013\.  Sponsored search, market equilibria, and the Hungarian Method.  _Inform. Process. Lett._ 113, 3 (2013), 67–73.
  * Eisenberg and Gale (1959) Edmund Eisenberg and David Gale. 1959.  Consensus of subjective probabilities: The pari-mutuel method.  _The Annals of Mathematical Statistics_ 30, 1 (1959), 165–168.
  * Fujishige and Tamura (2007) Satoru Fujishige and Akihisa Tamura. 2007.  A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis.  _Mathematics of Operations Research_ 32, 1 (2007), 136–155.
  * Gale (1984) David Gale. 1984\.  Equilibrium in a discrete exchange economy with money.  _International Journal of Game Theory_ 13, 1 (1984), 61–64.
  * Gale and Shapley (1962) David Gale and Lloyd S Shapley. 1962.  College admissions and the stability of marriage.  _The American Mathematical Monthly_ 69, 1 (1962), 9–15.
  * Gul and Stacchetti (1999) Faruk Gul and Ennio Stacchetti. 1999.  Walrasian equilibrium with gross substitutes.  _Journal of Economic Theory_ 87 (1999), 95–124.
  * Henzinger and Loitzenbauer (2015) Monika Henzinger and Veronika Loitzenbauer. 2015.  Truthful unit-demand auctions with budgets revisited.  _Theoretical Computer Science_ 573 (2015), 1–15.
  * Kelso and Crawford (1982) Alexander S. Kelso and Vincent P. Crawford. 1982.  Job matching, coalition formation , and gross substitute.  _Econometrica_ 50, 6 (1982), 1483–1504.
  * Kuhn (1955) Harold W Kuhn. 1955\.  The Hungarian method for the assignment problem.  _Naval Research Logistics Quarterly_ 2, 1-2 (1955), 83–97.
  * Leme (2017) Renato Paes Leme. 2017\.  Gross substitutability: An algorithmic survey.  _Games and Economic Behavior_ 106 (2017), 294–316.
  * Leme and Wong (2017) Renato Paes Leme and Sam Chiu-wai Wong. 2017.  Computing Walrasian Equilibria: Fast Algorithms and Structural Properties. In _Proceedings of the28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’17)_ (Barcelona, Spain). 632–651.
  * Mishra and Parkes (2007) Debasis Mishra and David C Parkes. 2007.  Ascending price Vickrey auctions for general valuations.  _Journal of Economic Theory_ 132, 1 (2007), 335–366.
  * Mishra and Talman (2006) Debasis Mishra and Adolphus Talman. 2006.  Overdemand and Underdemand in Economies with Indivisible Goods and Unit Demands.  _CentER Discussion Paper_ No. 2006-84 (2006).
  * Negishi (1960) Takashi Negishi. 1960\.  Welfare economics and existence of an equilibrium for a competitive economy.  _Metroeconomica_ 12, 2-3 (1960), 92–97.
  * Orlin (2010) James B Orlin. 2010\.  Improved algorithms for computing Fisher’s market clearing prices: Computing Fisher’s market clearing prices. In _Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC ’10)_. 291–300.
  * Quinzii (1984) Martine Quinzii. 1984\.  Core and competitive equilibria with indivisibilities.  _International Journal of Game Theory_ 13, 1 (1984), 41–60.
  * Shapley and Scarf (1974) Lloyd S Shapley and Herbert Scarf. 1974.  On cores and indivisibility.  _Journal of mathematical economics_ 1, 1 (1974), 23–37.
  * Shapley and Shubik (1971) Lloyd S Shapley and Martin Shubik. 1971.  The assignment game I: The core.  _International Journal of Game Theory_ 1, 1 (1971), 111–130.
  * van der Laan and Yang (2016) Gerard van der Laan and Zaifu Yang. 2016.  An ascending multi-item auction with financially constrained bidders.  _Journal of Mechanism and Institution Design_ 1 (2016), 109–149.
  * Vickrey (1961) William Vickrey. 1961\.  Counterspeculation, auctions, and competitive sealed tenders.  _The Journal of Finance_ 16, 1 (1961), 8–37.
  * Zhou (2017) Yu Zhou. 2017.  A multi-item auction with budget-constrained bidders and price controls.  _Economics Letters_ 155 (2017), 76–79.

##  Appendix A Appendix

###  A.1 Proof of Lemma 2

###### Proof.

Since $O\setminus T\subseteq O$ and $O$ is minimally overdemanded, $O\setminus
T$ is not overdemanded, so

$|O|-|T|=|O\setminus T|\geq|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\setminus
T\\}|.$

Now

$\\{i\,:\,D_{i}(p,R_{i})\subseteq O\setminus
T\\}=\\{i\,:\,D_{i}(p,R_{i})\subseteq
O\\}\setminus\\{i\,:\,D_{i}(p,R_{i})\subseteq O\,\wedge\,D_{i}(p,R_{i})\cap
T\neq\emptyset\\}$

so

$|O|-|T|\geq|\\{i\,:\,D_{i}(p,R_{i})\subseteq
O\\}|-|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\,\wedge\,D_{i}(p,R_{i})\cap
T\neq\emptyset\\}|.$

By rearranging terms we get

$|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\,\wedge\,D_{i}(p,R_{i})\cap
T\neq\emptyset\\}|\geq|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\\}|-|O|+|T|$

and since $O$ is overdemanded, this implies

$|\\{i\,:\,D_{i}(p,R_{i})\subseteq O\,\wedge\,D_{i}(p,R_{i})\cap
T\neq\emptyset\\}|>|T|.$

∎

In the following we need a simple auxiliary lemma.

######  Lemma 6.

Let $(\nu,q)$ be an arbitrary outcome, and let $O\subseteq\mathcal{S}$ be a
minimally overdemanded set with respect to the demand sets $D_{i}(q,R_{i})$.
Let $\emptyset\neq J\subsetneq O$. Then there exists a bidder $i^{*}$ with
$D_{i^{*}}(q,R_{i^{*}})\subset O$, $D_{i^{*}}(q,R_{i^{*}})\cap J\neq\emptyset$
and $\nu(i^{*})\not\in J$.

###  A.2 Proof of Proposition 5

###### Proof.

We prove the following statements by induction on the iteration $t$, which
imply Proposition 5.

  * •

If in iteration $t$ Step 4 or 5 is executed, then $p^{t}\leq q$.

  * •

If in iteration $t$ Step 3 is executed, then $p^{t+1}\leq q$ and we can choose
bidder $i\in I^{t}$ such that $\nu(i)\not\in J^{t}_{i}$, and consequently, by
choosing this bidder, we have $\nu(i)\in R_{i}^{t+1}$ for all $i$.

For iteration $t=1$ this is obviously true, since only Step 4 or Step 5 can be
executed, and $p^{1}=(0,\dots,0)\leq q$.

Now suppose that $t>1$. First assume that in iteration $t$ Step 4 or 5 is
executed. If in Step $t-1$ Step 3 was executed, we have that $p^{t}=p^{t-2}$,
and since Step 3 cannot be executed twice in a row, we have by induction
$p^{t}=p^{t-2}\leq q$. Now assume that Step 4 was executed in iteration $t-1$.
Then by induction we have $p^{t-1}\leq q$. Towards a contradiction, assume
that the set $J=\\{j\in O^{t-1}\,:\,p^{t}(j)>q(j)\\}$ is not empty. Note that
for all $j\in J$ we must have $q(j)=p^{t-1}(j)$. By Lemma 6 there exists a
bidder $i^{*}$ with $D_{i^{*}}(p^{t-1},R^{t-1}_{i^{*}})\subset O^{t-1}$,
$D_{i^{*}}(p^{t-1},R^{t-1}_{i^{*}})\cap J\neq\emptyset$ and $\nu(i^{*})\not\in
J$. Thus, we have $\nu(i^{*})\notin O^{t-1}$ or $p^{t}(j)\leq q(j)$. Since
$\nu(i^{*})\in R_{i^{*}}^{t-1}$, we have for every $j\in
D_{i^{*}}(p^{t-1},R^{t-1}_{i^{*}})\cap J$ that
$\pi_{i^{*}}(\nu(i^{*}),q)<\pi_{i^{*}}(j,q)$. Consequently, since $(\nu,q)$ is
a core outcome, so $(i^{*},j)$ is no blocking pair, we must have that
$q(j)=b^{i^{*}}$. But since $q(j)=p^{t-1}(j)$ and $j\in O^{t-1}$, it would
follow that $j\notin D_{i^{*}}(p^{t},R_{i}^{t})$, so $I^{t}\neq\emptyset$ and
Step 3 is executed in iteration $t$. This contradicts our assumption that Step
4 is executed.

Now consider the case where Step 3 is executed in iteration $t$. Since Step 3
cannot be executed twice in a row, we have by induction that
$p^{t+1}=p^{t-1}\leq q$. It remains to show that there is some bidder $i\in
I^{t}$ with $\nu(i)\notin J^{t}_{i}$. Again, towards a contradiction, assume
that for all $i\in I^{t}$ we have $\nu(i)\in J_{i}^{t}$. Hence,
$p^{t-1}(\nu(i))=b^{i}$ for all $i\in I^{t}$, and since $q\geq p^{t-1}$ by
induction, we have $q(\nu(i))=b^{i}$ for all $i\in I^{t}$. Our argument is now
very similar to the one above: Consider the set $J=\\{j\in
O^{t-1}\,:\,q(j)=p^{t-1}(j)\\}$. Then $\nu(I^{t})\subseteq J$, and in
particular $J^{t}$ is nonempty. Hence there is a bidder $i^{*}$ with
$D_{i^{*}}(q,R_{i^{*}})\subset O$, $D_{i^{*}}(q,R_{i^{*}})\cap J\neq\emptyset$
and $\nu(i^{*})\not\in J$. Again, we have $\nu(i^{*})\not\in O^{t-1}$, or
$q(\nu(i^{*}))>p^{t-1}(\nu(i^{*}))$. In both cases, $i^{*}$ would prefer any
good $j$ in the intersection $D_{i^{*}}(q,R_{i^{*}})\cap J\neq\emptyset$ to
$\nu(i^{*})$ at prices $q$. But since $i^{*}\not\in I^{t}$, $b^{i^{*}}>q(j)$,
so $(i^{*},j)$ would form a blocking pair.

$I=\\{i\in\mathcal{B}\,:\,D_{i}(p^{t-1},O^{t-1})\subseteq
O^{t-1}\,\wedge\,\nu(i)\in
O^{t-1}\,\wedge\,p^{t-1}(\nu(i))=q^{t-1}(\nu(i))\\}.$

Then $I^{t}\subseteq I$, so $I$ is not empty. By Lemma 6, there is a bidder
$i^{*}\notin I$ with $D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})\subseteq O^{t-1}$ and
$\nu(I)\cap D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})\neq\emptyset$. The
$\nu(i^{*})\notin O^{t-1}$, or $q(\nu(i^{*}))>p^{t-1}(\nu(i^{*}))$. Since by
induction we have $\nu(i^{*})\in R_{i^{*}}^{t-1}$, we have that
$\pi_{i^{*}}(\nu(i^{*}),q)<\pi_{i^{*}}(j,q)$ for all $j\in\nu(I)\cap
D_{i^{*}}(p^{t-1},R_{i^{*}}^{t-1})$. But since $(\nu,q)$ is a core outcome,
for no such $j$, $(i^{*},j)$ can be a blocking pair - implying that
$b^{i^{*}}=q(j)=p^{t-1}(j)$. This is a contradiction, since it would follow
that $i^{*}\in I$.

∎

###  A.3 Proof of Proposition 6

###### Proof.

Consider the undirected bipartite graph $G$ with vertex set
$I\dot{\cup}O^{t-1}$, where
$I=\\{i\in\mathcal{B}\,:\,D_{i}(p^{t-1},R_{i}^{t-1})\subseteq O^{t-1}\\}$,
containing the edge $\\{i,j\\}$ if and only if $j\in
D_{i}(p^{t-1},R_{i}^{t-1})$. Since $O^{t-1}$ is minimally overdemanded, this
graph is connected by Lemma 6. For the sake of clarity, we denote the bidders
in $I$ by $1,\dots,r$, and the goods in $O^{t-1}$ by
$1^{\prime},\dots,s^{\prime}$, where $r=|I|$ and $s=|O^{t-1}|$.

Let $J=\\{j^{\prime}\in O^{t-1}\,:\,\exists i\in I\,:\,j^{\prime}\in
D_{i}(p^{t-1},R_{i}^{t-1})\,\wedge\,p(j^{\prime})=b^{i}\\}$ be the set of all
goods $j^{\prime}$ demanded by some bidder in $I$ with tight budget for
$j^{\prime}$. We show that $|J|=1$. To that goal, assume that this is not the
case. Then, after a possible re-indexing, there exists a path

$j_{1}\rightarrow i_{1}\rightarrow j_{2}\rightarrow\dots\rightarrow
i_{m-1}\rightarrow j_{m}$

alternating between goods and bids in $G$, where $j_{1}$ and $j_{m}$ are
distinct goods contained in $J$. Then by following the corresponding forward-
and backward edges according to Definition 3, the total weight of this walk is

$\sum_{k=1}^{m-1}v_{i_{k}}(j_{k})-v_{i_{k}}(j_{k+1}).$

For all $k\in\\{1,\dots,m-1\\}$, we have that
$\pi_{i_{k}}(j_{k},p^{t-1})=\pi_{i_{k}}(j_{k+1},p^{t-1})$, which is equivalent
to $v_{i_{k}}(j_{k})-v_{i_{k}}(j_{k+1})=p^{t-1}(j_{k})-p^{t-1}(j_{k+1})$.
Thus, the weight of the above walk is equal to
$p^{t-1}(j_{1})-p^{t-1}(j_{m})$. Now let $i_{0},i_{m}\in I$ be bidders
demanding $j_{1}$, respectively $j_{m}$ with $b^{i_{0}}=p(j_{1})$ and
$b^{i_{m}}=p(j_{m})$. Let us consider two walks starting from $i_{0}$: the
first one consists of a single maximum-price edge $i_{0}\rightarrow j_{1}$ and
has weight $b^{i_{0}}-v_{i_{0}}(j_{1})$. The second one is

$i_{0}\rightarrow j_{1}\rightarrow i_{1}\rightarrow
j_{2}\rightarrow\dots\rightarrow i_{m-1}\rightarrow j_{m}\rightarrow
i_{m}\rightarrow j_{m}$

where the last edge is a maximum-price edge. This walk has weight

$-v_{i_{0}}(j_{1})+(p^{t-1}(j_{1})-p^{t-1}(j_{m}))+v_{i_{m}}(j_{m})+(b^{j_{m}}-v_{i_{m}}(j_{m})).$

Since $b^{i_{0}}=p(j_{1})$ and $b^{i_{m}}=p(j_{m})$, this is equal to
$b^{i_{0}}-v_{i_{0}}(j_{1})$. Thus, we found two distinct paths with the same
total weight, so the auction is not in general position. It follows that
$|J|=1$.

It remains to show that $|I^{t}|=1$. To that goal, assume that $|I^{t}|>1$ and
let $i_{1},i_{2}\in I^{t}$ be distinct. Since $|J|=1$, there is a good $j\in
O^{t-1}$, demanded by both $i_{1}$ and $i_{2}$ with
$p(j)=b^{i_{1}}=b^{i_{2}}$. The walk $i_{1}\rightarrow j$ consisting of a
single maximum-price edge has weight $b^{i_{1}}-v_{i_{1}}(j)$, and the walk
$i_{1}\rightarrow j\rightarrow i_{2}\rightarrow j$ ending with a maximum-price
edge, also has weight
$-v_{i_{1}}(j)+v_{i_{2}}(j)+(b^{i_{2}}-v_{i_{2}}(j))=b^{i_{1}}-v_{i_{1}}(j)$.
Thus, the auction is not in general position, a contradiction. Hence,
$|I^{t}|=1$, and since $J=|1|$, the good $j\in D_{i}(p^{t-1},R_{i}^{t-1})$
with $p(j)=b^{i}$ for the bidder $i\in I^{t}$ is unique. ∎

###  A.4 Proof of Proposition 7

###### Proof.

We have that

$\sum_{i\in\mathcal{B}}v_{i}(\mu(i))=\sum_{i\in\mathcal{B}}\pi_{i}(\mu(i),p)+\sum_{j\in\mathcal{S}}p(j)\geq\sum_{i\in\mathcal{B}}\pi_{i}(\mu(i),p)+p(\nu(i))$

and

$\sum_{i\in\mathcal{B}}v_{i}(\nu(i))=\sum_{i\in\mathcal{B}}\pi_{i}(\nu(i),q)+\sum_{j\in\mathcal{S}}q(j)=\sum_{i\in\mathcal{B}}\pi_{i}(\nu(i),q)+q(\nu(i))$

since each good $j$ with $q(j)>0$ is assigned to some bidder by $\nu$. Thus,
it suffices to show that

$\sum_{i\in\mathcal{B}}\pi_{i}(\mu(i),p)-\pi_{i}(\nu(i),q)+p(\nu(i))-q(\nu(i))\geq
0.$

We show that each summand is non-negative by distinguishing two cases:

Case 1: $p(\nu(i))=b^{i}$. Then, since bidder $i$ receives $\nu(i)$ in the
outcome $(\nu,q)$, $q(\nu(i))\leq b^{i}=p(\nu(i))$. Since by assumption
$\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),q)$, it follows that
$\pi_{i}(\mu(i),p)-\pi_{i}(\nu(i),q)+p(\nu(i))-q(\nu(i))\geq 0$.

Case 2: $p(\nu(i))<b^{i}$. Then $\pi_{i}(\mu(i),p)\geq\pi_{i}(\nu(i),p)$ \-
otherwise, $(i,\nu(i))$ would be a blocking pair with respect to prices $p$.
Since $\pi_{i}(\nu(i),p)=\pi_{i}(\nu(i),q)+q(\nu(i))-p(\nu(i))$, we again get
that $\pi_{i}(\mu(i),p)-\pi_{i}(\nu(i),q)+p(\nu(i))-q(\nu(i))\geq 0$. ∎

###  A.5 Proof of Lemma 4

###### Proof.

We examine the edge gadget $G^{\prime}_{e}$ of edge $e=(u,u^{\prime})\in E$,
and define $\mathcal{B}_{e}:=\\{\beta_{e},\gamma_{e},\delta_{e}\\}$ as the set
of buyers and
$\mathcal{S}_{e}:=\\{\alpha^{u}_{e},\eta_{e},\alpha^{u^{\prime}}_{e}\\}$ as
the set of sellers. The total social welfare that can be achieved by agents in
$G^{\prime}_{e}$ under assignment $\mu$ is
$SW_{e}=\sum_{i\in\mathcal{B}_{e}}\pi_{i}(\mu(i))+\sum_{j\in\mathcal{S}_{e}}\pi_{j}(\mu^{-1}(j))$.

For each individual edge gadget $G^{\prime}_{e}$, we prove that the maximum
total achieved welfare is bound by

$SW_{e}\leq 3\cdot 2|E|^{2}+27$

We prove the claim as follows:

$\displaystyle SW_{e}$ $\displaystyle\
=\sum_{\begin{subarray}{c}(i,j)\in\mathcal{B}_{e}\times\mathcal{S}_{e}\\\
(i,j)\in
E(G_{e})\end{subarray}}\Big{(}|\mu(i)=j|\cdot(\pi_{i}(j)+\pi_{j}(i))\Big{)}+\Big{(}|\mu(\epsilon_{u})=\alpha^{u}_{e}|\cdot\pi_{\alpha^{u}_{e}}(\epsilon_{u})\Big{)}+\Big{(}|\mu(\epsilon_{u^{\prime}})=\alpha^{u^{\prime}}_{e}|\cdot\pi_{\alpha^{u^{\prime}}_{e}}(\epsilon_{u^{\prime}})\Big{)}$
$\displaystyle\
=\sum_{i\in\\{\gamma_{e},\delta_{e}\\}}\Big{(}|\mu(i)=\alpha^{u}_{e}|\cdot(\pi_{i}(\alpha^{u}_{e})+\pi_{\alpha^{u}_{e}}(i))\Big{)}+\sum_{i\in\\{\beta_{e},\gamma_{e}\\}}\Big{(}|\mu(i)=\alpha^{u^{\prime}}_{e}|\cdot(\pi_{i}(\alpha^{u^{\prime}}_{e})+\pi_{\alpha^{u^{\prime}}_{e}}(i))\Big{)}$
$\displaystyle\
+\sum_{i\in\\{\beta_{e},\delta_{e}\\}}\Big{(}|\mu(i)=\eta_{e}|\cdot(\pi_{i}(\eta_{e})+\pi_{\eta_{e}}(i))\Big{)}+\Big{(}|\mu(\epsilon_{u})=\alpha^{u}_{e}|\cdot\pi_{\alpha^{u}_{e}}(\epsilon_{u})\Big{)}+\Big{(}|\mu(\epsilon_{u^{\prime}})=\alpha^{u^{\prime}}_{e}|\cdot\pi_{\alpha^{u^{\prime}}_{e}}(\epsilon_{u^{\prime}})\Big{)}$
$\displaystyle\ \leq 3\cdot 2|E|^{2}+27$

We observe that each seller $\eta_{e}$ is connected to two buyer nodes inside
the edge gadget $G^{\prime}_{e}$, therefore, under assignment $\mu$, strictly
one of conditions $|\mu(\beta_{e})=\eta_{e}|$ and $|\mu(\delta_{e})=\eta_{e}|$
returns a value of 1, while the other is set to 0. Sellers $\alpha^{u}_{e}$
and $\alpha^{u^{\prime}}_{e}$ can be potentially matched to 3 different
buyers: two of them within $G^{\prime}_{e}$, and one belonging to the vertex
gadget, $u$ or $u^{\prime}$ respectively. We compute the upper bound on the
total sum of valuations of sellers and buyers, on any possible assignment
$\mu$, maintaining that every time, one pair is matched, and the remaining
conditions output 0 for all other edges connected to the pair. The resulting
social welfare $SW_{e}$ is equal to $3\cdot 2|E|^{2}+27$ only for the case
where assignment $\mu$ does not satisfy neither condition
$|\mu(\epsilon_{u})=\alpha^{u}_{e}|$ nor
$|\mu(\epsilon_{u^{\prime}})=\alpha^{u^{\prime}}_{e}|$.

We now proceed to bound the total welfare achieved under the condition that
$\pi_{\epsilon_{u}}(\mu(\epsilon_{u}))<\pi_{\epsilon_{u}}(\alpha^{u}_{e})$ and
$\pi_{\epsilon_{u^{\prime}}}(\mu(\epsilon_{u^{\prime}}))<\pi_{\epsilon_{u^{\prime}}}(\alpha^{u^{\prime}}_{e})$
hold simultaneously. Since $\mu$ is a stable outcome, from the first
condition, we derive that

$\pi_{\alpha^{u}_{e}}(\mu^{-1}(\alpha^{u}_{e}))\geq\pi_{\alpha^{u}_{e}}(\epsilon_{u})=3$
(20)

Similarly, from the second condition, we get that

$\pi_{\alpha^{u^{\prime}}_{e}}(\mu^{-1}(\alpha^{u^{\prime}}_{e}))\geq\pi_{\alpha^{u^{\prime}}_{e}}(\epsilon_{u^{\prime}})=7$
(21)

In order to ensure that Equation (3) holds, assignment $\mu$ needs to force
node $\alpha^{u}_{e}$ to be matched with $\delta_{e}$, as
$\pi_{\alpha^{u}_{e}}(\delta_{e})=4>3$ in this case. If the pair
$\\{\gamma_{e},\alpha^{u}_{e}\\}$ was matched instead, it would hold that
$\pi_{\alpha^{u}_{e}}(\gamma_{e})=2<3$, thus contradicting condition (3).

In a similar manner, for Equation (4), $\mu$ matches pair
$\\{\beta_{e},\alpha^{u^{\prime}}_{e}\\}$, achieving utility
$\pi_{\alpha^{u^{\prime}}_{e}}(\beta_{e})=8>7$.

The total welfare of assignment $\mu$ is therefore:

$\displaystyle SW_{e}$ $\displaystyle\
=\sum_{\begin{subarray}{c}(i,j)\in\mathcal{B}_{e}\times\mathcal{S}_{e}\\\
(i,j)\in
E(G_{e})\end{subarray}}\Big{(}|\mu(i)=j|\cdot(\pi_{i}(j)+\pi_{j}(i))\Big{)}+\Big{(}|\mu(\epsilon_{u})=\alpha^{u}_{e}|\cdot\pi_{\alpha^{u}_{e}}(\epsilon_{u})\Big{)}+\Big{(}|\mu(\epsilon_{u^{\prime}})=\alpha^{u^{\prime}}_{e}|\cdot\pi_{\alpha^{u^{\prime}}_{e}}(\epsilon_{u^{\prime}})\Big{)}$
$\displaystyle\
=|\mu(\delta_{e})=\alpha^{u}_{e}|\cdot(\pi_{\delta_{e}}(\alpha^{u}_{e})+\pi_{\alpha^{u}_{e}}(\delta_{e}))+|\mu(\beta_{e})=\alpha^{u^{\prime}}_{e}|\cdot(\pi_{\beta_{e}}(\alpha^{u^{\prime}}_{e})+\pi_{\alpha^{u^{\prime}}_{e}}(\beta_{e}))$
$\displaystyle\ \leq 2|E|^{2}+11+2|E|^{2}+10$ $\displaystyle\ \leq
4|E|^{2}+22$ $\displaystyle\ <6|E|^{2}+27-|V|$

since, without loss of generality, we can assume that $2|E|^{2}-|V|+5>0$, as
we are referring to cubic graphs, where $3|V|=2|E|$ and as a result the claim
trivially holds. ∎

In order to prove NP-hardness for MBSBM, we need to provide an intermediate
result concerning the existence of blocking pairs under certain assignments.

######  Lemma 7.

Consider edge $e=(u,u^{\prime})$ of $G$, and let $\mu$ be an assignment for
edge gadget $G^{\prime}_{e}$. The following two statements hold:

  1. 1.

If assignment $\mu$ satisfies $\mu(\beta_{e})=\eta_{e}$,
$\mu(\gamma_{e})=\alpha^{u^{\prime}}_{e}$ and $\mu(\delta_{e})=\alpha^{u}_{e}$
(solid edges in Figure 1), then no blocking pair of $\mu$ involves any agent
from $\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u}_{e},\eta_{e}\\}$.

  2. 2.

If assignment $\mu$ satisfies $\mu(\beta_{e})=\alpha^{u^{\prime}}_{e}$,
$\mu(\gamma_{e})=\alpha^{u}_{e}$ and $\mu(\delta_{e})=\eta_{e}$ (dashed edges
in Figure 1), then no blocking pair of $\mu$ involves any agent from
$\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u^{\prime}}_{e},\eta_{e}\\}$.

###### Proof.

For statement (1), we assume outcome $\mu$ sets values as suggested. Computing
the utilities under $\mu$ for each agent, we get:

$\pi_{\beta_{e}}(\eta_{e})=2|E|^{2}+3,\
\pi_{\gamma_{e}}(\alpha^{u^{\prime}}_{e})=2|E|^{2}+6,\
\pi_{\delta_{e}}(\alpha^{u}_{e})=2|E|^{2}+7$
$\pi_{\alpha^{u}_{e}}(\delta_{e})=4,\ \pi_{\eta_{e}}(\beta_{e})=1$

One can easily verify that agents $\beta_{e},\gamma_{e},\alpha^{u}_{e}$ are
maximizing their utility under $\mu$, and since agent $\eta_{e}$ is
indifferent between agents $\delta_{e}$ and $\beta_{e}$, they have no
incentive to deviate by forming a blocking pair with agent $\delta_{e}$.
Therefore, there does not exist a blocking pair that includes agents
$\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u}_{e},\eta_{e}\\}$.
For statement (2), we assume outcome $\mu$ sets values as suggested. Computing
the utilities under $\mu$ for each agent, we get:

$\pi_{\beta_{e}}(\alpha^{u^{\prime}}_{e})=2|E|^{2}+2,\
\pi_{\gamma_{e}}(\alpha^{u}_{e})=2|E|^{2}+5,\
\pi_{\delta_{e}}(\eta_{e})=2|E|^{2}+9$
$\pi_{\alpha^{u^{\prime}}_{e}}(\beta_{e})=8,\ \pi_{\eta_{e}}(\delta_{e})=1$

One can easily verify that agents $\delta_{e},\alpha^{u^{\prime}}_{e}$ are
maximizing their utility under $\mu$, and since agent $\eta_{e}$ is
indifferent between agents $\delta_{e}$ and $\beta_{e}$, they have no
incentive to deviate by forming a blocking pair with agent $\beta_{e}$. Given
that agent $\alpha^{u^{\prime}}_{e}$ is assigned to agent $\beta_{e}$, and is
maximizing their utility, agent $\gamma_{e}$ is assigned to agent
$\alpha^{u}_{e}$, as this constitutes their best available choice. Therefore,
there does not exist a blocking pair that includes agents
$\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u^{\prime}}_{e},\eta_{e}\\}$. ∎

###  A.6 Proof of Lemma 5

###### Proof.

We examine the edge and vertex gadgets separately, and argue that, in both
cases, setting prices equal to the winning bidders’ budgets yields all
feasible welfare-maximizing, core-stable outcomes. Formally, the set of all
welfare-maximizing, core-stable assignments coincides with the set of optimal
assignments when prices are set at the budget limit.

In a two-sided matching the welfare is defined as the gains from trade, the
value of the buyers minus that of the sellers. This means, for each match
between buyer $i$ and seller $j$, the corresponding welfare is computed as the
sum of buyer $\pi_{i}(j)=v_{i}(j)-p_{j}$ and seller payoff
$\pi_{j}(i)=p_{j}-r_{j}$, therefore prices are not included in the final sum,
which is the result of the difference between assigned items’ valuations and
seller reserve values.

We begin by analyzing the edge gadget, as seen in Figure 1. The values
depicted in Table 1 represent the true valuation of each buyer among
$\\{\beta_{e},\gamma_{e},\delta_{e}\\}$ for the item of each seller among
$\\{\alpha^{u}_{e},\eta_{e},\alpha^{u^{\prime}}_{e}\\}$. One can trivially
observe that there exist 6 feasible assignments between buyers and sellers in
the bipartite graph. As stated above, prices do not participate in the welfare
computation, and thus we can calculate the welfare-maximizing assignment based
on the buyer valuation table. Since valuations
$v_{\beta_{e}}(\alpha^{u}_{e})=v_{\gamma_{e}}(\eta_{e})=v_{\delta_{e}}(\alpha^{u^{\prime}}_{e})=0$,
only 2 among 6 assignments are stable, and simultaneously welfare-maximizing.
The two assignments $\mu_{1},\mu_{2}$ are
$\mu_{1}(\beta_{e})=\eta_{e},\mu_{1}(\gamma_{e})=\alpha^{u^{\prime}}_{e},\mu_{1}(\delta_{e})=\alpha^{u}_{e}$
and
$\mu_{2}(\beta_{e})=\alpha^{u^{\prime}}_{e},\mu_{2}(\gamma_{e})=e^{i}_{j},\mu_{2}(\delta_{e})=\eta_{e}$.
The total welfare admitted by assignments $\mu_{1},\mu_{2}$ is equal to
$6|E|^{2}+27$, while the remaining feasible assignments yield a strictly lower
welfare. Additionally, according to Lemma 7, assignments $\mu_{1},\mu_{2}$
(grey, dotted) with seller payoffs set as
$\pi_{\alpha^{u}_{e}}(\delta_{e})=b_{\delta_{e}}-r_{\alpha^{u}_{e}}=9-5=4$,
$\pi_{\eta_{e}}(\beta_{e})=b_{\beta_{e}}-r_{\eta_{e}}=9-8=1$,
$\pi_{\alpha^{u^{\prime}}_{e}}(\gamma_{e})=b_{\gamma_{e}}-r_{\alpha^{u^{\prime}}_{e}}=7-1=6$
under assignment $\mu_{1}$, and
$\pi_{\alpha^{u}_{e}}(\gamma_{e})=b_{\gamma_{e}}-r_{\alpha^{u}_{e}}=7-5=2$,
$\pi_{\eta_{e}}(\delta_{e})=b_{\delta_{e}}-r_{\eta_{e}}=9-8=1$,
$\pi_{\alpha^{u^{\prime}}_{e}}(\beta_{e})=b_{\beta_{e}}-r_{\alpha^{u^{\prime}}_{e}}=9-1=8$
under assignment $\mu_{2}$, do not generate any blocking pairs. This argument
leads to the conclusion that, for the edge gadget and corresponding valuation
table, setting prices for winning buyers equal to their budgets produces every
feasible core-stable, welfare-maximizing assignment, namely setting prices to
lower values cannot yield different stable assignments of higher or equal
welfare.

In a similar analysis, we observe that, for the vertex gadget of Figure 2, the
welfare-maximizing assignment $\mu_{3}$, based on valuations described on
Table 2, is
$\mu_{3}(\epsilon_{u})=N(\epsilon_{u}),\mu_{3}(\zeta_{u})=\xi_{u},\mu_{3}(\theta_{u})=\lambda_{u}$.
However, as suggested in Lemma 4, assignment $\mu_{0}(\epsilon_{u})$ results
in sub-optimal welfare for the overall subgraph including vertex and edge
gadget. Therefore, the welfare-maximizing assignment $\mu_{4}$ is a result of
an assignment between the vertices within the gadget. The aforementioned
assignment is
$\mu_{4}(\epsilon_{u})=\xi_{u},\mu_{3}(\zeta_{u})=\kappa_{u},\mu_{3}(\theta_{u})=\lambda_{u}$
(solid assignment in Figure 2), admitting welfare equal to $3|V|+27$. In
Theorem 3, we have shown that assignment $\mu_{4}$, for winning buyer prices
equal to their budgets is core-stable. Thus, the initial claim is true for
each vertex gadget, concluding the proof of the lemma. ∎

###  A.7 Proof of Theorem 3

###### Proof.

Let $G=(V,E)$ be a cubic graph, with sizes of vertex and edge sets defined as
$|V|$ and $|E|$ respectively. Since $G$ is assumed to be cubic, it does not
possess any isolated vertices. An instance of MIS is defined by $G$ and an
integer $k$.

A key property of cubic graphs is that all nodes must have a degree of 3.
According to the Handshaking lemma, it holds that $\sum_{u\in V}deg(u)=2|E|$,
namely the sum of degrees of all vertices of the graph is twice as large as
than the size of the edge set.

We construct an instance $<G^{\prime},\pi_{i},\pi_{j},SW>$ of MBSBM, where
$G^{\prime}=(V^{\prime},E^{\prime})$ is a bipartite graph, with
$SW=|V|\cdot(3|V|+26)+k+|E|\cdot(6|E|^{2}+27)$. For each edge $e\in E$, buyer
and seller sets of the corresponding edge gadget are defined as
$\mathcal{B}_{e},\mathcal{S}_{e}$. For each vertex $u\in V$, the respective
sets for the corresponding vertex gadget are defined as
$\mathcal{B}_{u},\mathcal{S}_{u}$. Unifying for all edge gadgets in
$G^{\prime}$, we define $\mathcal{B}_{E}=\bigcup\limits_{e\in
E}\mathcal{B}_{e}$, $\mathcal{S}_{E}=\bigcup\limits_{e\in E}\mathcal{S}_{e}$,
and for all vertex gadgets, sets $\mathcal{S}_{V}=\bigcup\limits_{u\in
V}\mathcal{S}_{u}$ and $\mathcal{B}_{V}=\bigcup\limits_{u\in
V}\mathcal{B}_{u}$. Vertex set $V^{\prime}$ consists of the union over all
vertex and edge gadgets, and therefore $\mathcal{B}=\mathcal{B}_{E}\
\cup\mathcal{B}_{V}$ and $\mathcal{S}=\mathcal{S}_{E}\ \cup\ \mathcal{S}_{V}$
represent the total number of buyers and sellers respectively. Each edge
gadget corresponding to edge $e\in E$ consists of vertices
$\mathcal{B}_{e}=\\{\beta_{e},\gamma_{e},\delta_{e}\\}$ and
$\mathcal{S}_{e}=\\{\alpha^{u}_{e},\eta_{e},\alpha^{u^{\prime}}_{e}\\}$.
Similarly, the vertex gadget corresponding to vertex $u\in V$ consists of two
disjoint sets of vertices defined as
$\mathcal{B}_{u}=\\{\epsilon_{u},\zeta_{u},\theta_{u}\\}$ and
$\mathcal{S}_{u}=\\{\kappa_{u},\lambda_{u},\xi_{u}\\}$. The vertex and edge
gadgets are defined for each vertex $u\in V$ and each edge $e\in E$ of the
original graph $G$. The total size of each set is
$|\mathcal{B}|=|\mathcal{S}|=6|E|+6|V|$.

Formally, the following claim should be proven: $G$ has an independent set
$IS(G)$ of size at least $k$ if and only if $G^{\prime}$ admits a stable
outcome with welfare at least $SW$.

The transformation from an instance of MIS to an instance of MBSBM is
performed in polynomial time. An important aspect of our construction is the
assumption that, both in edge and vertex gadgets, there exist pairs of buyers
with equal budgets. From Tables 1 and 2, one can observe that pairs of agents
$\\{\beta_{e},\delta_{e}\\}$ and $\\{\epsilon_{u},\theta_{u}\\}$ verify the
claim. Thus, the instance is not in general position, and therefore the
hardness proof holds for cases where the property is violated.

We now proceed to the forward part of the proof, namely prove that, given an
independent set $IS(G)$ of size at least $k$, we construct an assignment $\mu$
as follows:

  * •

For each $u\in V$, if $u\in IS(G)$, set
$\mu(\epsilon_{u})=\xi_{u},\mu(\zeta_{u})=\kappa_{u},\mu(\theta_{u})=\lambda_{u}$.

  * •

For each $u\in|V|$, if $u\not\in IS(G)$, set
$\mu(\epsilon_{u})=\lambda_{u},\mu(\zeta_{u})=\xi_{u},\mu(\theta_{u})=\kappa_{u}$.

  * •

For each edge $e=\\{u,u^{\prime}\\}\in E$ do:

    * –

If $u\in IS(G)$, set
$\mu(\beta_{e})=\eta_{e},\mu(\gamma_{e})=\alpha^{u^{\prime}}_{e},\mu(\delta_{e})=\alpha^{u}_{e}$,
which matches condition (1) of Lemma 7.

    * –

If $u\not\in IS(G)$, set
$\mu(\beta_{e})=\alpha^{u^{\prime}}_{e},\mu(\gamma_{e})=\alpha^{u}_{e},\mu(\delta_{e})=\eta_{e}$,
which matches condition (2) of Lemma 7.

  * •

For any pair of agents $(i,j)\in G^{\prime}$ not assigned above, set
$\mu(i)=0,\mu^{-1}(j)=0$.

Since the size of the independent set is at least $k$, we can trivially verify
that, according to the aforementioned rules, the welfare attained by the
agents of all vertex gadgets is equal to $|V|\cdot(3|V|+26)+k$ and of all edge
gadgets is $|E|\cdot(6|E|^{2}+27)$, thus achieving a total welfare of $SW$. In
what follows, we prove that outcome $\mu$ is indeed stable.

Edge Gadget. Examining the edge gadget of edge $e=\\{u,u^{\prime}\\}\in E$, we
need to prove that there does not exist any blocking pair of agents. There are
two distinct cases, as mentioned previously.

  1. 1.

If $u\in IS(G)$, then $\mu$ corresponds to condition (1) of Lemma 7.
Therefore, no blocking pair involving agents
$\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u}_{e},\eta_{e}\\}$ exists. In
this case, assigning $\alpha^{u^{\prime}}_{e}$ to $\epsilon_{u^{\prime}}$
would yield a higher utility for agent $\alpha^{u^{\prime}}_{e}$. However,
since $u^{\prime}\not\in IS(G)$, by definition
$\mu(\epsilon_{u^{\prime}})=\lambda_{u}$ and $\epsilon_{u^{\prime}}$ is
assigned to her most preferred agent, with no incentive to deviate. We
conclude that no blocking pair involving agents
$\\{\alpha^{u^{\prime}}_{e},\epsilon{u^{\prime}}\\}$, guaranteeing stability
for $\mu$.

  2. 2.

If $u\not\in IS(G)$, then $\mu$ corresponds to condition (2) of Lemma 7.
Therefore, no blocking pair involving agents
$\\{\beta_{e},\gamma_{e},\delta_{e},\alpha^{u^{\prime}}_{e},\eta_{e}\\}$
exists. In this case, assigning $\alpha^{u}_{e}$ to $\epsilon_{u}$ would yield
a higher utility for agent $\alpha^{u}_{e}$. However, since $u\not\in IS(G)$,
by definition $\mu(\epsilon_{u})=\lambda_{u}$ and $\epsilon_{u}$ is integrally
matched to her most preferred agent, with no incentive to deviate. We conclude
that no blocking pair involving agents $\\{\alpha^{u}_{e},\epsilon_{u}\\}$,
guaranteeing stability for $\mu$.

We prove a similar result for the vertex gadgets of $G^{\prime}$.

Vertex Gadget. Examining the vertex gadget of vertex $u\in V$, we again detect
two cases.

  1. 1.

If $u\in IS(G)$, then no blocking pair of $\mu$ involves agents
$\\{\xi_{u},\theta_{u},\lambda_{u}\\}$, as $\mu$ assigns them to their most
preferred agents. Therefore, no blocking pair involves agents
$\\{\zeta_{u},\kappa_{u}\\}$, since no possible combination can yield improved
payoff for all participants. As previously argued, no agent from the edge
gadget participates in a blocking pair, and thus $\epsilon_{u}$ is also not
involved in a blocking pair.

  2. 2.

If $u\not\in IS(G)$, then no blocking pair of $\mu$ involves agents
$\\{\kappa_{u},\zeta_{u},\lambda_{u}\\}$, as $\mu$ assigns them to their most
preferred agents. The same holds for agent $\epsilon_{u}$. Therefore, no
blocking pair involves agents $\\{\theta_{u},\xi_{u}\\}$, since no possible
combination can yield improved payoff for all participants.

We conclude that neither the edge nor vertex gadget contain agents involved in
blocking pairs under $\mu$. Thus, $\mu$ is stable and achieves a welfare of
$SW$.

For the reverse direction, assume $\mu$ is a stable outcome for
$<G^{\prime},\pi_{i},\pi_{j}>$ with welfare $welfare(\mu)\geq SW$. Defining a
subset of the vertices as $IS(G)=\\{u\in V\ |\ \mu(\epsilon_{u})=\xi_{u}\\}$,
we prove that $IS(G)$ is an independent set of $G$ of size at least $k$.

Firstly, we prove the desired lower bound on $|IS(G)|$. We define
$\mu(\epsilon_{u})=N(\epsilon_{u})$ as the assignment between vertex
$\epsilon_{u}$ and any of the neighboring vertices from the edge gadgets.
Summing up for all $|V|$ vertices of $G$, we get:

$\displaystyle\sum_{u\in V}$ $\displaystyle\
\Big{(}\sum_{i\in\\{\epsilon_{u},\zeta_{u},\theta_{u}\\}}\pi_{i}(\mu(i))+\sum_{j\in\\{\kappa_{u},\lambda_{u},\xi_{u}\\}}\pi_{j}(\mu^{-1}(j))\Big{)}$
$\displaystyle\ =\sum_{u\in
V}(|V|+10)\cdot|\mu(\epsilon_{u})=\lambda_{u}|+(|V|+12)\cdot|\mu(\epsilon_{u})=\xi_{u}|+(|V|+8)\cdot|\mu(\epsilon_{u})=N(\epsilon_{u})|+$
$\displaystyle\
(|V|+7)\cdot|\mu(\zeta_{u})=\kappa_{u}|+(|V|+9)\cdot|\mu(\zeta_{u})=\xi_{u}|+(|V|+7)\cdot|\mu(\theta_{u})=\kappa_{u}|+(|V|+8)\cdot|\mu(\theta_{u})=\lambda_{u}|$
$\displaystyle\ \leq\sum_{u\in
V}(|V|+10)|\mu(\epsilon_{u})=\lambda_{u}|+|\mu(\epsilon_{u})=\xi_{u}|+|\mu(\epsilon_{u})=N(\epsilon_{u})|+(|V|+8)\cdot|\mu(\zeta_{u})=\kappa_{u}|+|\mu(\zeta_{u})=\xi_{u}|+$
$\displaystyle\
(|V|+8)\cdot|\mu(\theta_{u})=\kappa_{u}|+|\mu(\theta_{u})=\lambda_{u}|+\sum_{u\in
V}|\mu(\epsilon_{u})=\lambda_{u}|$ $\displaystyle\
\leq|V|\cdot(3|V|+26)+\sum_{u\in V}|\mu(\epsilon_{u})=\lambda_{u}|$

Since $\mu$ corresponds to a binary assignment, only one condition holds true
for each of $\epsilon_{u},\zeta_{u},\theta_{u}$, and examining all possible
outcomes, we use the mean of values to provide an upper bound on utilities.
The sum of values for each vertex $\kappa_{u},\lambda_{u},\xi_{u}$ is at most
1, which is also taken into account when computing the upper bound. We can
trivially verify that, the total welfare of $\mu$ is maximized if and only if
pair ${\epsilon_{u},\xi_{u}}$ is integrally matched.

We now need to show that $|IS(G)|\geq k$. Set $IS(G)$ has been defined as the
set of vertices ${\epsilon_{u}}$ for $u\in V$, that are integrally matched to
${\xi_{u}}$. This can be expressed as $|IS(G)|=\sum_{u\in
V}|\mu(\epsilon_{u})=\xi_{u}|$. It then suffices to prove inequality
$\sum_{u\in V}|\mu(\epsilon_{u})=\xi_{u}|\geq k$, to prove the lower bound on
the size of the independent set. Since the induced welfare from all $|E|$ edge
gadgets is at most $welfare(\mu)\leq|E|\cdot(6|E|^{2}+27)$. At least
$|V|\cdot(3|V|+26)+\sum_{u\in V}|\mu(\epsilon_{u})=\xi_{u}|$ must be derived
from the vertex gadgets. Using the upper bound provided above, we conclude
that $\sum_{u\in V}|\mu(\epsilon_{u})=\xi_{u}|\geq k$, as required, thus
proving the lower bound on the size of $IS(G)$.

Finally, we need to prove that $IS(G)$ is in fact an independent set of $G$.
We prove the claim by contradiction. Suppose there is an edge
$e=\\{u,u^{\prime}\\}\in V$ and $\\{u,u^{\prime}\\}\subseteq IS(G)$. Then, for
both nodes $u,u^{\prime}$ under assignment $\mu$, it must hold that
$\pi_{\epsilon_{u}}(\mu(\epsilon_{u}))<|V|+8=\pi_{\epsilon_{u}}(\alpha^{u}_{e})$
and
$\pi_{\epsilon_{u^{\prime}}}(\mu(\epsilon_{u^{\prime}}))<|V|+8=\pi_{\epsilon_{u^{\prime}}}(\alpha^{u^{\prime}}_{e})$,
as $IS(G)$ is defined as the set of nodes $u$ that are integrally matched to
$\xi_{u}$. From Lemma 4, the induced welfare from agents of the edge gadgets
is at most $6|E|^{2}+27-|V|$, and using the previously shown bound, the
welfare induced from agents of the vertex gadgets is at most $3|V|+26+|V|$.
Therefore, the total welfare of $G^{\prime}$ under $\mu$ is lower than the
original assumption, which is a contradiction. Note that the restriction of
our prices to be at the budget constraint $b^{i}$ of the buyers
$i\in\mathcal{B}$ in the edge and vertex gadgets is without loss of generality
as shown in Lemma 5. Concluding, we have proven that indeed $IS(G)$ is an
independent set of $G$.

∎