# Computational Hardness of the Hylland-Zeckhauser Scheme

Thomas Chen
Columbia Univeristy
<EMAIL_ADDRESS>Xi Chen
Columbia University
<EMAIL_ADDRESS>Binghui Peng
Columbia University
<EMAIL_ADDRESS>Mihalis Yannakakis
Columbia University
<EMAIL_ADDRESS>
###### Abstract

We study the complexity of the classic Hylland-Zeckhauser scheme [HZ79] for
one-sided matching markets. We show that the problem of finding an
$\epsilon$-approximate equilibrium in the HZ scheme is PPAD-hard, and this
holds even when $\epsilon$ is polynomially small and when each agent has no
more than four distinct utility values. Our hardness result, when combined
with the PPAD membership result of [VY21], resolves the approximation
complexity of the HZ scheme. We also show that the problem of approximating
the optimal social welfare (the weight of the matching) achievable by HZ
equilibria within a certain constant factor is NP-hard.

##  1 Introduction

In a one-sided matching problem, there is a set $A$ of $n$ agents and a set
$G$ of $n$ goods, and we are given a specification of the preferences of the
agents for the goods.111In the statement of the problem, we have the same
number of agents and goods for simplicity. In general there can be $n_{1}$
agents, each with their own demand $d_{i}$, and $n_{2}$ goods, each with its
own supply, $s_{j}$, where $\sum_{i\in n_{1}}d_{i}=\sum_{j\in n_{2}}s_{j}$. It
is clear that this setting reduces to the simpler case of equal numbers of
agents and goods. The problem is to find a matching between the agents and the
goods (assigning a distinct good to each agent) that has desirable properties,
such as Pareto optimality, envy-freeness, incentive compatibility. This
situation, where only one side has preferences, arises in many settings, such
as assigning students to schools, assigning faculty members to committees,
workers to tasks, program committee members to papers, students to courses
with limited capacity, etc.

Since many agents may have the same or similar preferences, it is usually not
possible to offer everybody their favorite good. So a solution mechanism has
to strive to be equitable, satisfy the agents as much as possible, and
incentivize them to give their true preferences (i.e., not gain an advantage
by lying). Randomization is often useful to meet fairness requirements. A
randomized solution mechanism has probability $x_{i,j}\in[0,1]$ of matching
each agent $i$ to each good $j$; these probabilities form a doubly stochastic
matrix, i.e., a fractional perfect matching in the bipartite graph between
agents and goods. In some applications, the goods may be divisible, or they
may represent tasks or resources that can be shared among agents; in these
cases the quantities $x_{i,j}$ represent the shares of the agents in the
goods.

There are two main ways of specifying the preferences of each agent $i\in[n]$
for the goods: (1) cardinal preferences, where we are given the utility
$u_{i,j}$ of agent $i$ for each good $j\in[n]$, or (2) ordinal preferences,
where we are given the agent’s total ordering of the goods. Cardinal
preferences allow for a finer specification of the agents’ preferences
(although they may require more effort to produce them). As a result, they can
yield better assignments. Consider for instance the following example from
[HZ79]: There are 3 agents and 3 goods. The utilities of agents 1 and 2 for
the three goods are 100, 10, 0, while agent 3 has utilities 100, 80, 0. The
ordinal preferences of the three agents are the same, so any fair mechanism
will not distinguish between them, and will give them each probability 1/3 for
each good. The expected utilities of the three agents in this solution is
$36\frac{2}{3},36\frac{2}{3},60$. This solution is not Pareto optimal, i.e.,
there is another solution where all agents are better off. Agent 3 is assigned
good 2, and agents 1, 2 randomly split goods 1 and 3. The expected utilities
of the three agents in this solution are $50,50,80$.

In 1979 Hylland and Zeckhauser proposed a, by now, classic scheme for the one-
sided matching problem under cardinal preferences [HZ79]. The scheme uses a
pricing mechanism to produce an assignment of probability shares
$\\{x_{i,j}|i,j\in[n]\\}$ of goods to agents, i.e. a fractional perfect
matching, and these are then used in a standard way to generate
probabilistically an integral perfect matching. The basic idea is to imagine a
market where every agent has 1 dollar, and the goal is to find prices for the
goods and (fractional) allocations $x_{i,j}$ of goods to the agents, such that
the market clears (all goods are sold), while every agent maximizes her
utility subject to receiving a bundle of goods of size 1 and cost at most 1.
Hylland and Zeckhauser showed that such an equilibrium set of prices and
allocations always exists, using Kakutani’s fixed point theorem. Note that
money here is fictitious; no money changes hands. The only goal is to produce
the allocation (the shares $x_{i,j}$) so that it reflects the preferences of
the agents. The HZ scheme has several desirable properties: it is Pareto
optimal, envy-free [HZ79], and it is incentive compatible in the large
[HMPY18]. The scheme has been extended and generalized in various ways since
then.

Although the HZ scheme has several nice properties, one impediment is that,
despite much effort, there is no efficient algorithm known to compute an
equilibrium solution. This has remained an open problem till now. In [AJKT17],
Alaei, Khalilabadi and Tardos gave polynomial-time algorithms for the case
that the number of goods or the number of agents is a fixed constant (the case
of a constant number of goods can be derived also from [DK08]). Recently in
[VY21], Vazirani and Yannakakis gave a polynomial-time algorithm for the bi-
valued case, where every agent’s utilities take only two values. They also
gave an example showing that the equilibrium prices and allocations can be
inherently irrational. In the general case, they showed that the problem of
computing an equilibrium solution is in the class FIXP. Furthermore, computing
an $\epsilon$-approximate equilibrium is in the class PPAD, where in an
approximate equilibrium an agent may get a slightly suboptimal allocation and
may spend $1+\epsilon$ dollars. They leave open the problem whether computing
an exact or approximate equilibrium is complete for the classes.

In this paper we resolve the complexity of computing an approximate
equilibrium of the HZ scheme. Our main result is:

######  Theorem 1.1 (Main).

The problem of computing an $\epsilon$-approximate equilibrium of the HZ
scheme is PPAD-complete when $\epsilon=1/n^{c}$ for any constant $c>0$.

In our construction, every agent has at most 4 different utilities for the
goods. Thus, the problem is PPAD-complete even for 4-valued utilities222The
case of a small number of values is natural. For example, the authors have
been in committees that ask them to rate their level of interest in the
submissions by values in a limited range, e.g. 0-4.. We leave the 3-valued
case open. We give however a simple example with values in $\\{0,0.5,1\\}$
showing that there can be multiple disconnected equilibria, thus suggesting
that usual convex programming methods may not work (at least a convex program
will not include all equilibria).

A given instance of the one-sided matching problem may have multiple HZ
equilibria. All of them are Pareto optimal, but some may be preferable to
others when other criteria are considered. One such criterion is the social
welfare, i.e., the total weight of the matching (or the sum of utilities of
agents). We study the problem of approximating the optimal social welfare
achievable by an HZ equilibrium. We show that this is an NP-hard problem:

######  Theorem 1.2.

Given an instance of the one-side matching problem and a value $w$, it is NP-
hard to distinguish the case that the maximum social welfare of an HZ
equilibrium is at least $w$ from the case that it is at most
$(\frac{175}{176}+\epsilon)w$ for any constant $\epsilon>0$.

###  1.1 Proof Overview

We give an overview of the proof of Theorem 1.1. To prove the problem of
finding an approximate HZ equilibrium is PPAD-hard, we give a polynomial-time
reduction from threshold games, introduced recently by Papadimitriou and Peng
[PP21]. A threshold game is defined on a directed graph $G=(V,E)$, with a
variable $x_{v}\in[0,1]$ associated with each node $v\in V$. The equilibrium
condition is characterized by a comparison operator: $x_{v}=1$ if
$\sum_{(u,v)\in E}x_{u}\leq 1/2-\kappa$; $x_{v}=0$ if $\sum_{(u,v)\in
E}x_{u}\geq 1/2+\kappa$ and $x_{v}$ can take an arbitrary value in $[0,1]$,
otherwise. The PPAD-hardness of threshold game is proved in [PP21], and it
holds for some positive constant $\kappa>0$ and for sparse graphs. As we will
see later, the use of threshold games significantly simplifies the reduction.

From a high-level view, our reduction follows the general framework of
previous hardness results on market equilibria [CDDT09, CT09, VY11, CPY17]: we
use prices of an HZ market to simulate variables $x_{v}$ in a threshold game
and the construction is based on the design of two gadgets: _variable gadgets_
for each $v\in V$ (to simulate variables $x_{v}$ and enforce the equilibrium
condition at each node $v$) and _edge gadgets_ for each $e=(u,v)\in E$ (to
simulate the action of sending $x_{u}$ to the sum at $x_{v}$ in the threshold
game). However, a major challenge of working with the HZ scheme is that it is
difficult to characterize the equilibrium behavior of agents in this model, as
it is complex, nonlinear, and does not admit a closed form solution. As a
consequence, it is hard both, to analyze even small instances, and to
synthesize instances with desired characteristics. Below we discuss some of
the key ideas behind the construction.

Variable gadgets. To simulate variables $x_{v}$ of a threshold game, our
starting point is the following simple sub-market. There are two agents and
two goods. Both agents have utility $1$ for good $1$ and utility
$\frac{1}{2\delta^{-1}-1}$ for good $2$ ($0<\delta<1$ which should be
considered as a small constant as discussed below). It is easy to observe that
the set of equilbrium prices are $(p,2-p)$ for $p\in[0,\delta]$. After scaling
by $1/\delta$, the price $p$ of good $1$ in this sub-market can be used to
simulate a variable $x_{v}\in[0,1]$ in the threshold game. So we create such a
sub-market $M_{v}$ for each node $v$ and denote the price of good $1$ in
$M_{v}$ by $p_{v}$. To finish the reduction, it suffices to create agents that
are interested in goods in $M_{u}$ and $M_{v}$, for each edge $e=(u,v)\in E$,
such that the total allocation of goods from $M_{v}$ to them is captured by
$-p_{u}$.333The negative allocation may look strange but can be achieved
(essentially) by offsetting the supply carefully. The agents created for this
task are what we referred to earlier as the edge gadget for $e$. If achieved,
the total allocation of goods of $M_{v}$ to agents outside would give the
desired linear form $-\sum_{(u,v)\in E}p_{u}$ which is a scaled version of
$-\sum_{(u,v)\in E}x_{u}$. The sub-market $M_{v}$ can help enforce the
equilibrium condition of the threshold game. When $\sum_{(u,v)\in E}x_{u}$ is
too small (so the allocation to agents outside is high due to the negative
sign), there is a shortage of goods of $M_{v}$, which would lead to
$p_{v}\approx\delta$ and thus, $x_{v}\approx 1$; on the other hand, if the sum
is too large, then there is a surplus of goods in the sub-market $M_{v}$,
which forces $p_{v}\approx 0$ and thus, $x_{v}\approx 0$.

Edge gadgets. The key technical challenge lies in the construction of edge
gadgets. Our first attempt is to create an agent who has utility $1/2$ for
good $1$ in $M_{u}$ and utility $1$ for good $2$ in $M_{v}$ (with price
$2-p_{v}$). The optimal bundle for this agent, however, is not easy to work
with at first sight: for example, the agent is allocated
$\frac{1-p_{u}}{2-p_{u}-p_{v}}$ unit of good $2$ in $M_{v}$. The first key
idea of our reduction is to use first order approximation to simplify a
complex function. That is to say, we set $\delta$ to be a sufficiently small
constant and apply first-order approximation on the allocation. Ignoring
constant factors and constant or lower-order terms, the agent described
earlier has $D_{u}\approx p_{u}-p_{v}$ unit of good $1$ in $M_{u}$ and
$D_{v}\approx p_{v}-p_{u}$ unit of good $2$ in $M_{v}$ in her optimal bundle.
This, however, is far from what we hoped for, as (1) we don’t want $p_{v}$ to
appear in $D_{v}$, and (2) we want $D_{u}=0$. (Notably if we use this agent as
our edge gadget for every $e\in E$, then they together are essentially
simulating a threshold game over an undirected graph, which admits trivial
equilibria.) What about agents with a different set of utilities for goods in
$M_{u}$ and $M_{v}$? Perhaps surprisingly, all our attempts fail and there is
a fundamental reason for that: it can be shown that, no matter how the
utilities are set, the allocation of goods in $M_{v}$ is always monotonically
increasing with $p_{v}$, which is undesirable for our purpose.

We circumvent this obstacle using the following three steps. First, we
introduce extra goods with a fixed price $2$ into the picture (where the fixed
price can be enforced easily by creating agents who are interested in these
goods only). Second, we replace the current variable gadget with a richer sub-
market with three goods, with the price of the new good set to be
$\frac{(1+p_{v})}{2}$. Agents in our edge gadget can now have access to these
new goods which give us a larger design space for their utilities and
equilibrium behavior. The last step, which is the second key idea of our
reduction, is to use discrete functions to approximate a continuous function.
This is essential in our proof and we believe it might be of independent
interest in reductions of similar settings. Concretely, we design agents that
perform comparison operations: there are two possible optimal bundles for each
of these agents, and which one it is depends on the sign (in a robust sense)
of a certain affine linear form of $p_{u}$ and $p_{v}$. The agent behaves like
a step function, which is not useful on its own. However, when combined, one
can construct a series of agents by enumerating utilities; these lead to
careful cancellations that make sure the total allocation $D_{u}$ of goods
from $M_{u}$ is $0$ as desired.

###  1.2 Related Work

We have already mentioned the most relevant work on the complexity of the
Hylland-Zeckhauser scheme. The problem of computing an exact HZ equilibrium is
in FIXP, and computing an approximate equilibrium is in PPAD [VY21].
Polynomial-time algorithms for a fixed number of agents or goods were given in
[AJKT17]. It has been a longstanding open problem about whether there is a
polynomial-time algorithm in the general case.

The input in the one-sided matching problem is the same as in the classical
assignment problem (equivalently, maximum weight perfect matching problem in
bipartite graphs). This is one of the most well-studied problems in Operations
Research and Computer Science, and several very efficient algorithms have been
developed for it over the years. The difference in the one-sided matching
problem is that the primary consideration is to produce a solution that has
certain desirable fairness and optimality properties for the agents; the goal
is not simply the maximization of the weight of the matching. As we show in
this paper, computing an HZ solution for the one-sided matching problem is
probably computationally harder: it is PPAD-hard to compute any approximate HZ
solution, and if we want to maximize the total weight of the matching as a
secondary criterion then the problem becomes NP-hard.

In the case of ordinal preferences for the agents in the one-sided matching
problem, there are other schemes with nice properties: the Random Priority
(also called Random Serial Dictatorship) scheme [AS98, Mou18] and the
Probabilistic Serial scheme [BM01]. These have polynomial-time (randomized)
algorithms. However, since they are based only on ordinal preferences, they
are suboptimal with respect to the agents’ utilities, as the earlier simple
example shows.

The setting in the HZ scheme is the same as in the linear Fisher market model:
the input consists of the utilities $u_{i,j}$ of the agents for the goods, and
the problem is to compute equilibrium prices and allocations. The only
difference is that when an agent picks her optimal bundle of goods, she must
get exactly one unit (in addition to the cost being within the budget of 1
dollar), i.e. the solution must be a (fractional) perfect matching. Although
this may seem like a small difference, it has a substantial effect both in the
structure of the problem and in its computational complexity: exact solutions
may be irrational, and as we show in this paper, finding an approximate
solution is PPAD-hard. The linear Fisher model has been studied extensively
and there are polynomial-time algorithms for computing equilibria in this
model, as well as in the more general Arrow-Debreu model with linear utilities
[DPSV08, Orl10, Jai07].

There is furthermore extensive work on markets with more complex utility
functions than linear, such as piecewise linear, Leontief, CES utilities and
others, and for many of them it is PPAD-hard or FIXP-hard to compute an
approximate or exact equilibrium (e.g. [CDDT09, CT09, VY11, CPY17, EY10,
GMVY17]).

Several researchers have proposed Hylland-Zeckhauser-type mechanisms for a
number of applications, e.g. see [Bud11, HMPY18, Le17, McL18]. There are also
recent works that have generalized and extended the basic HZ scheme in several
directions, for example to two-sided matching markets and to an Arrow-Debreu-
type setting where the agents own initial endowments [EMZ19a, EMZ19b, GTV20].
Note that in the case of initial endowments, an HZ equilibrium may not always
exist, so some approximation or slack is needed to ensure existence (see
[EMZ19a, GTV20]).

##  2 Preliminaries

We write $[n]$ to denote $\\{1,2,\ldots,n\\}$. Given two integers $n$ and $m$
we use $[n:m]$ to denote integers between $n$ and $m$, with $[n:m]=\emptyset$
when $m<n$. Given two real number $x,y\in\mathbb{R}$, we use $x=y\pm\epsilon$
to denote $x\in[y-\epsilon,y+\epsilon]$.

###  2.1 The Hylland-Zeckhauser Scheme

We provide a formal description of the Hylland-Zeckhauser scheme for one-sided
matching markets [HZ79, VY21]. It will be convenient for us to describe it
using the language of linear Fisher markets. An _HZ market_ $M$ consists of a
set $A=[n]$ of $n$ agents and a set $G=[n]$ of $n$ (infinitely) divisible
goods. Each agent $i\in A$ has one dollar and there is one unit of each good
$j\in G$ in the market. We write $u_{i,j}\in[0,1]$444As it will become clear
in Definition 2.1, shifting and scaling utilities of agents does not change
the set of HZ equilibria. We assume utilities to lie in $[0,1]$ because we
will consider an additive approximation of HZ equilibria in Definition 2.3. to
denote the utility of one unit of good $j$ to agent $i$, for each $i\in A$ and
$j\in G$. Hence an HZ market $M$ is specified by a positive integer $n$ and
utilities $(u_{i,j}:i,j\in[n])$.

Given an HZ market $M$ with $n$ agents and goods, an _HZ equilibrium_ [HZ79]
consists of an allocation $x=(x_{i,j}:i,j\in[n])$ and a price vector
$p=(p_{j}:j\in[n])$ that are nonnegative and satisfy a list of properties to
be described in Definition 2.1. Given $x$ and $p$, we will refer to
$x_{i}=(x_{i,j}:j\in[n])$ as the _bundle of goods allocated to agent $i$_. The
_cost_ of the bundle $x_{i}$ is given by $\sum_{j\in[n]}p_{j}x_{i,j}$ and the
_value_ of $x_{i}$ to agent $i$ is $\sum_{j\in[n]}u_{i,j}x_{i,j}$. We are
ready to define HZ equilibria:

######  Definition 2.1 (HZ Equilibria [HZ79]).

A pair $(x,p)$, where $x=(x_{i,j}:i,j\in[n])\in\mathbb{R}_{\geq 0}^{n\times
n}$ and $p=(p_{i}:i\in[n])\in\mathbb{R}^{n}_{\geq 0}$, is an _HZ equilibrium_
of an HZ market $M$ if:

  1. 1.

The total allocation of each good $j\in[n]$ is $1$ unit, i.e.,
$\sum_{i\in[n]}x_{i,j}=1$.

  2. 2.

The total allocation of each agent $i\in[n]$ is $1$ unit, i.e.,
$\sum_{j\in[n]}x_{i,j}=1$.

  3. 3.

The cost of the bundle $x_{i}$ of each agent $i\in[n]$ is at most $1$, i.e.,
$\smash{\sum_{j\in[n]}p_{j}x_{i,j}\leq 1}$.

  4. 4.

For each $i\in[n]$, $x_{i}$ maximizes its value $\sum_{j\in[n]}u_{i,j}x_{i,j}$
to agent $i$ subject to 2 and 3 above.555We note that in [HZ79, VY21], $x_{i}$
is required (as a tie-breaking rule) to minimize its cost among all those that
maximize the value subject to items 2 and 3. This is needed to ensure Pareto
optimality of the equilibrium allocations. However, we do not need this
condition for our hardness results, and this only makes the results stronger.
So for simplicity, we omit the condition from the definition of exact and
approximate equilibria.

Equivalently the last condition in the definition above can be captured by the
following LP:

maximize $\displaystyle\sum_{j\in[n]}u_{i,j}x_{i,j}$ s.t.
$\displaystyle\sum_{j\in[n]}x_{i,j}=1,\ \sum_{j\in[n]}p_{j}x_{i,j}\leq 1,\
\text{and}\ x_{i,j}\geq 0\ \text{for all $j\in[n]$}.$

Taking $\mu_{i}$ and $\alpha_{i}$ to be the dual variables, one has the
following dual LP that will be useful:

minimize $\displaystyle\alpha_{i}+\mu_{i}$ s.t. $\displaystyle\alpha_{i}\geq
0\ \text{and}\ \alpha_{i}p_{j}+\mu_{i}\geq u_{i,j},\ \text{for all
$j\in[n]$}.$

We will refer to the LP (and its dual LP) above as the LP (or dual LP) for
agent $i$ with respect to the price vector $p$. Let $\textsf{value}_{p}(i)$
denote their optimal value. Then it captures the optimal value of any bundle
of goods to agent $i$ subject to conditions 2 and 3 in Definition 2.1.

Hylland and Zeckhauser [HZ79] showed that an HZ equilibrium always exists:

######  Theorem 2.2 (Existence [HZ79]).

Every HZ market admits an HZ equilibrium.

If $(x,p)$ is an equilibrium, then it is easy to see that if we scale the
difference of all prices from 1, the resulting price vector $p^{\prime}$
together with the same allocation $x$ forms also an equilibrium; i.e. for any
$r>0$ with $r\leq\min\\{1/(1-p_{j})|p_{j}<1\\}$, setting
$p^{\prime}_{j}=1+r(p_{j}-1)$ for all $j\in[n]$ yields a vector $p^{\prime}$
such that $(x,p^{\prime})$ is also an equilibrium (see [VY21]). The reason is
that this scaling does not affect the set of feasible allocations, as can be
easily seen, and $\textsf{value}_{p^{\prime}}(i)=\textsf{value}_{p}(i)$ for
all agents $i\in[n]$. That is, price vectors related to each other by this
scaling are in a sense equivalent. A consequence of this observation is that
we may always assume w.l.o.g. that an equilibrium contains a good with price 0
[HZ79]: If one of the goods has price $<1$, then we can always scale the
prices so that the minimum price is 0. On the other hand if all prices in an
equilibrium are $\geq 1$, then all prices must be 1 (the sum of the prices
must be $\leq n$, the sum of the agents’ budgets), and in this case the cost
condition 3 is redundant, and the all-0 vector forms also an equilibrium with
the same allocation.

We say that a price vector $p$ is normalized if $\min_{i}p_{i}=0$. We will
restrict our attention henceforth to normalized price vectors, without always
mentioning it explicitly.

Our hardness results hold for the following relaxation studied by Vazirani and
Yannakakis [VY21]:

######  Definition 2.3 (Approximate HZ Equilibria).

Given some $\epsilon>0$, a pair $(x,p)$, where
$x=(x_{i,j}:i,j\in[n])\in\mathbb{R}_{\geq 0}^{n\times n}$ and
$p=(p_{i}:i\in[n])\in\mathbb{R}^{n}_{\geq 0}$ (where
$\min_{i\in[n]}p_{i}=0$)666The requirement that $p$ be normalized is important
in the definition because otherwise condition 3 on the cost has no effect: if
$(x,p)$ is any pair that satisfies conditions 1,2,4, then we can always scale
$p$ as above to a vector $p^{\prime}$ where all prices are sufficiently close
to 1 so that condition 3 is also satisfied for $(x,p^{\prime})$., is an
_$\epsilon$ -approximate HZ equilibrium_ of an HZ market $M$ if:

  1. 1.

The total allocation of each good $j\in[n]$ is $1$ unit, i.e.,
$\sum_{i\in[n]}x_{i,j}=1$.

  2. 2.

The total allocation of each agent $i\in[n]$ is $1$ unit, i.e.,
$\sum_{j\in[n]}x_{i,j}=1$.

  3. 3.

The cost of $x_{i}$ is at most $1+\epsilon$ for each $i\in[n]$, i.e.,
$\smash{\sum_{j\in[n]}p_{j}x_{i,j}\leq 1+\epsilon}$.

  4. 4.

The value $\sum_{j\in[n]}u_{i,j}x_{i,j}$ of $x_{i}$ to agent $i$ is at least
$\emph{{value}}_{p}(i)-\epsilon$ for each $i\in[n]$.

An alternative, more relaxed notion of an $\epsilon$-approximate equilibrium,
where condition 1 is also relaxed to $|\sum_{i\in[n]}x_{i,j}-1|\leq\epsilon$
for all goods $j\in[n]$, is polynomially equivalent to the above notion
[VY21]. Thus, it follows that computing an $\epsilon$-approximate equilibrium
under the more relaxed notion is also PPAD-complete.

###  2.2 Threshold Games

Our PPAD hardness results use _threshold games_ , introduced recently by
Papadimitriou and Peng [PP21]. They showed that the problem of finding an
approximate equilibrium in a threshold game is PPAD-complete.

######  Definition 2.4 (Threshold game [PP21]).

A threshold game is defined over a directed graph $H=(V,E)$. Each node $v\in
V$ represents a player with strategy space $x_{v}\in[0,1]$. Let $N_{v}$ be the
set of nodes $u\in V$ with $(u,v)\in E$. Then $x=(x_{v}:v\in V)\in[0,1]^{V}$
is a $\kappa$-_approximate equilibrium_ if every $x_{v}$ satisfies

$\displaystyle x_{v}\in\begin{cases}[0,\kappa]&\sum_{u\in
N_{v}}x_{u}>0.5+\kappa\\\ [1-\kappa,1]&\sum_{u\in N_{v}}x_{u}<0.5-\kappa\\\
[0,1]&\sum_{u\in N_{v}}x_{u}\in[0.5-\kappa,0.5+\kappa]\end{cases}$

######  Theorem 2.5 (Theorem 4.7 of [PP21]).

There is a positive constant $\kappa$ such that the problem of finding a
$\kappa$-approximate equilibrium in a threshold game is PPAD-hard. This holds
even when the in-degree and out-degree of each node is at most $3$ in the
threshold game.

##  3 PPAD-hardness

Our goal in this section is to prove the following theorem:

######  Theorem 3.1.

The problem of finding a $(1/n^{5})$-approximate HZ equilibrium in an HZ
market with $n$ agents and goods is PPAD-hard.

In Appendix A (via a standard padding argument), we give a polynomial-time
reduction from the problem of finding a $(1/n^{5})$-approximate HZ equilibrium
to that of finding a $(1/n^{c})$-approximate HZ equilibrium in an HZ market,
for any positive constant $c$. Theorem 1.1 follows by combining the PPAD
membership result of [VY21].

Our plan is as follows. Let $\epsilon=1/n^{5}$ throughout this section
wherever an HZ market with $n$ agents and goods is concerned. We start with
some basic facts about approximate HZ equilibria in Section 3.1 (mainly about
how to work with approximately optimal bundles for agents). Then we describe
the polynomial-time reduction from threshold games to HZ markets in Section
3.2. Our reduction constructs two types of gadgets, _variable gadgets_ and
_edge gadgets_ , which simulate variables $x_{v}$ and edges $(u,v)$ in a
threshold game, respectively. Using these gadgets, we finish the reduction’s
correctness proof in Section 3.3; the analysis of these two gadgets is
presented afterwards in Section 3.4 and 3.5, respectively.

###  3.1 Basic Facts

Let $M$ be an HZ market with $n$ agents and goods. As it will become clear
later, the HZ market we construct in the reduction satisfies
$\max_{j\in[n]}u_{i,j}=1$ for every agent $i\in[n]$. _Hence we assume this is
the case in every HZ market discussed in the rest of this section._ In all
lemmas of this subsection we assume $(x,p)$ to be an $\epsilon$-approximate HZ
equilibrium of $M$ (and skip it in their statements). Recall that prices are
normalized: $\min_{i}p_{i}=0$.

We give first an upper bound on the sum of prices:

######  Lemma 3.2.

$\sum_{j\in[n]}p_{j}\leq 2n$.

###### Proof.

Since $(x,p)$ is an $\epsilon$-approximate HZ equilibrium, every good must be
sold out and no agent can spend more than $1+\epsilon$. Thus,
$\sum_{j\in[n]}p_{j}\leq n(1+\epsilon)<2n$ using $\epsilon=1/n^{5}$. ∎

Next, we consider an optimal solution $(\alpha_{i}^{*},\mu_{i}^{*})$ to the
dual LP for agent $i$ and prove the following:

######  Lemma 3.3.

$\mu_{i}^{*}\geq 0$ and $\alpha_{i}^{*}\leq 1$ for every $i\in[n]$.

###### Proof.

Let $\ell$ be a good with $p_{\ell}=0$. From the dual LP constraints, we have
$0\leq u_{i,\ell}\leq\alpha_{i}^{*}p_{\ell}+\mu^{*}_{i}=\mu_{i}^{*}.$
Moreover, since all utilities are in $[0,1]$ we have trivially that
$\alpha_{i}^{*}+\mu_{i}^{*}=\textsf{value}_{p}(i)\leq 1$. Therefore, we have
$\alpha_{i}^{*}\leq 1$. ∎

######  Lemma 3.4.

If $\emph{{value}}_{p}(i)\leq 0.9$ then $\alpha_{i}^{*}\geq 1/(20n)$ and
$\sum_{j\in[n]}p_{j}x_{i,j}\geq 1-20n\epsilon$.

###### Proof.

Let $u_{i,\ell}=1$. It follows from Lemma 3.2 that $p_{\ell}\leq 2n$ and thus,

$1=u_{i,\ell}\leq\alpha_{i}^{*}p_{\ell}+\mu_{i}^{*}\leq
2n\alpha_{i}^{*}+\mu_{i}^{*}.$

On the other hand, $\textsf{value}_{p}(i)=\alpha^{*}_{i}+\mu^{*}_{i}\leq 0.9$.
The first part of the lemma follows from adding these two inequalities.

Next, multiplying both sides of the inequalities
$\alpha_{i}^{*}p_{j}+\mu_{i}^{*}\geq u_{i,j}$ by $x_{i,j}$, summing over all
$j\in[n]$, and using $\sum_{j}x_{i,j}=1$, we have

$\sum_{j\in[n]}\alpha_{i}^{*}p_{j}x_{i,j}+\mu_{i}^{*}\geq\sum_{j\in[n]}u_{i,j}x_{i,j}\geq\alpha_{i}^{*}+\mu_{i}^{*}-\epsilon.$

The second part of the lemma then follows from $\alpha_{i}^{*}\geq 1/(20n)$. ∎

Recall that all goods $j$ satisfy
$u_{i,j}\leq\alpha_{i}^{*}p_{j}+\mu_{i}^{*}$. We say a good $j$ is
$\delta$-_suboptimal_ for agent $i$ if
$u_{i,j}+\delta\leq\alpha_{i}^{*}p_{j}+\mu_{i}^{*}$. We show that agent $i$’s
good-bundle, $x_{i}$, cannot contain significant quantities of suboptimal
goods.

######  Lemma 3.5.

For every $i\in[n]$, the total allocation in $x_{i}$ to $\delta$-suboptimal
goods is at most $2\epsilon/\delta$.

###### Proof.

Fix an agent $i\in[n]$. We have $u_{i,j}\leq\alpha_{i}^{*}p_{j}+\mu_{i}^{*}$
for all $j\in[n]$, and $u_{i,j}+\delta\leq\alpha_{i}^{*}p_{j}+\mu_{i}^{*}$ for
$\delta$-suboptimal goods. Let $W$ be the total allocation in $x_{i}$ to
$\delta$-suboptimal goods. Then

$\sum_{j\in[n]}u_{i,j}x_{i,j}+W\delta\leq\alpha_{i}^{*}\sum_{j\in[n]}p_{j}x_{i,j}+\mu_{i}^{*}\sum_{j\in[n]}x_{i,j}.$

Using the definition of $\epsilon$-approximate HZ equilibria, the LHS is at
least

$\textsf{value}_{p}(i)-\epsilon+W\delta=\alpha_{i}^{*}+\mu_{i}^{*}+W\delta-\epsilon$

and the RHS is at most $\alpha_{i}^{*}(1+\epsilon)+\mu_{i}^{*}$. The lemma
follows from $\alpha_{i}^{*}\leq 1$ by Lemma 3.3. ∎

We use some of the lemmas above to obtain following corollaries:

######  Corollary 3.6.

Let $J$ be the set of $j\in[n]$ that are _not_ $\delta$-suboptimal for $i$. If
$\emph{{value}}_{p}(i)\leq 0.9$, then

$\displaystyle 1-2\epsilon/\delta\leq\sum_{j\in J}x_{i,j}\leq
1\quad\text{and}\quad 1-20n\epsilon-\frac{4n\epsilon}{\delta}\leq\sum_{j\in
J}p_{j}x_{i,j}\leq 1+\epsilon.$

###### Proof.

The first part follows directly from Lemma 3.5.

The second part follows from Lemma 3.2, Lemma 3.4, and Lemma 3.5. ∎

######  Corollary 3.7.

Let $J$ be the set of goods $j\in[n]$ with $u_{i,j}>0$. If
$\emph{{value}}_{p}(i)\leq 0.9$, then

$1-20n\epsilon-\frac{1}{n^{2}}\leq\sum_{j\in J}p_{j}x_{i,j}\leq 1+\epsilon.$

###### Proof.

The second inequality clearly holds since $(x,p)$ is an $\epsilon$-approximate
equilibrium. Suppose that the first inequality does not hold. Then by Lemma
3.4, agent $i$ spends more than $1/n^{2}$ on zero-utility goods, hence she
buys at least an amount $1/2n^{3}$ of these, since all prices are at most
$2n$. Consider a new bundle for $i$ obtained by replacing $1/2n^{3}$ of the
zero-utility goods by a good with utility 1. The cost of the new bundle is
still less than 1, i.e. it is a feasible bundle, and the value exceeds that of
the original bundle $x_{i}$ by $1/2n^{3}>\epsilon$, contradicting the fact
that $(x,p)$ is an $\epsilon$-approximate equilibrium. ∎

Finally we include a simple lemma about the optimal value of an agent:

######  Lemma 3.8.

Let $i\in[n]$ and $\ell\in[n]$ with $u_{i,\ell}=1$. Then
$\emph{{value}}_{p}(i)\geq\min(1,1/p_{\ell})$.

###### Proof.

If $p_{\ell}=0$, then agent $i$ can get value $1$ by buying one unit of good
$\ell$ for free.

If $p_{\ell}>0$ then there is another good with zero price and thus, agent $i$
can get value $\min(1,1/p_{\ell})$ by buying $\min(1,1/p_{\ell})$ unit of good
$\ell$ and $1-\min(1,1/p_{\ell})$ unit of a zero price good. ∎

###  3.2 The Construction

Let $\kappa\in(0,1)$ be the positive constant in Theorem 2.5. Recall that our
goal is to give a polynomial-time reduction from the problem of finding a
$\kappa$-approximate equilibrium in a threshold game (with both in-degree and
out-degree at most $3$) to that of finding an $\epsilon$-approximate HZ
equilibrium in an HZ market with $\epsilon=1/n^{5}$.

Let $C$ be a sufficiently large universal constant, and $m=\lceil
C/\kappa\rceil$. Let $H=(V,E)$ be a threshold game with $|V|=N$. (Note that
$N$ is asymptotically large and should be considered as larger than any
function of $m$.) We write $\text{in-deg}(v)$ and $\text{out-deg}(v)\leq 3$ to
denote the in-degree and out-degree of $v\in V$, respectively. We construct an
HZ market $M_{H}$ from $H$ in three steps as described below. This is done by
creating _groups_ of goods and _groups_ of agents, with the guarantee that
agents in the same group have the same utility for any good as each other, and
that goods in the same group yield the same utility to any agent. We say a
group $A_{i}$ of agents have utility $u$ for a group $G_{j}$ of goods if all
agents in $A_{i}$ share the same utility $u$ for all goods in $G_{j}$.
(Intuitively we create a group $A_{i}$ of agents to simulate an agent with
demand and budget $|A_{i}|$ instead of $1$, and a group $G_{j}$ of goods to
simulate a good with a supply of $|G_{j}|$ units in the market. A technical
subtlety though is that in an approximate HZ equilibrium, goods in the same
group may not share exactly the same price and agents in the same group may
not have exactly the same allocation.)

### Step 1: Creating Variable Gadgets

We start with an empty market and create a _variable gadget_ for each node
$v\in V$ to simulate the variable $x_{v}$ in the threshold game $H$. For each
node $v\in V$, the variable gadget of $v$ consists of the following three
groups of goods and one group of agents:

  1. 1.

Create three groups of goods $G_{v,1},G_{v,2}$ and $G_{v,3}$: $G_{v,1}$ has
$m^{10}+S_{u}$ goods, where

$S_{u}:=(24m^{3}+12m)\cdot\text{out-deg}(u)+(24m^{3}+15m)\cdot\text{in-
deg}(u)-3m,$

and $G_{v,2}$ and $G_{v,3}$ both have $2m^{10}$ goods. Let $G_{v}$ denote the
union of $G_{v,1},G_{v,2}$ and $G_{v,3}$.

  2. 2.

Create a group $A_{v}$ of $5m^{10}$ agents. Each agent in $A_{v}$ has the
following utilities for $G_{v}$:

$\frac{1}{2m^{2}-1}\ \text{for}\ G_{v,1},\quad\frac{m^{2}+1}{4m^{2}-2}\
\text{for}\ G_{v,2},\quad 1\ \text{for}\ G_{v,3},$ (1)

and utility $0$ for every other good in the market (including those created
later).

Looking ahead, we will prove (in Lemma 3.10) that in any
$\epsilon$-approximate HZ equilibrium $(x,p)$ of the final HZ market $M_{H}$,
$p(G_{v,1}),p(G_{v,2})$ and $p(G_{v,3})$ must satisfy

$0\leq p(G_{v,1})\lesssim\frac{1}{m^{2}},\quad
p(G_{v,2})\approx\frac{1+p(G_{v,1})}{2}\quad\text{and}\quad p(G_{v,3})\approx
2-p(G_{v,1}),\vspace{0.15cm}$

where $p(G_{v,\ell})$ denotes the minimum price of goods in $G_{v,\ell}$.
Indeed, $p(G_{v,1})$ will be used to simulate the variable $x_{v}$ in the
threshold game $H$ and at the end, we set $x_{v}\approx m^{2}p(G_{v,1})$ for
each $v\in V$ to obtain a $\kappa$-approximate equilibrium of $H$.

### Step 2: Creating Edge Gadgets

Next we create an _edge gadget_ for each edge $e=(u,v)\in E$ to simulate the
action of vertex $u$ sending a contribution $x_{u}$ to the summation at vertex
$v$ in the threshold game $H$ (see definition 2.4). For each (directed) edge
$e=(u,v)\in E$, the edge gadget of $e$ consists of the following multiple
groups of goods and agents (for convenience, we only list goods with positive
utilities for each group of agents; every other good has utility $0$):

  1. 1.

Create a group $G_{e}$ of $32m^{5}$ goods.

  2. 2.

Create a group $A_{e,*}$ of $64m^{5}$ agents. They have utility $1$ for
$G_{e}$.

  3. 3.

Create a group of $48m^{3}$ agents $A_{e,1}$. They have utility $1$ for
$G_{u,3}$ and $1/2$ for $G_{v,1}$.

  4. 4.

Create $m$ groups $A_{e,2,\ell}$, $\ell\in[m]$, each of $6$ agents. They have
$1$ for $G_{e}$ and $\ell/(2m^{3})$ for $G_{v,1}$.

  5. 5.

Create $m$ groups $A_{e,3,\ell}$, $\ell\in[m]$, each of $8$ agents. They have
$1$ for $G_{e}$ and $\ell/(2m^{3})$ for $G_{u,1}$.

  6. 6.

Create $m$ groups $A_{e,4,\ell}$, $\ell\in[2m]$, each of $18$ agents. They
have $1$ for $G_{e}$, $\ell/(2m^{3})$ for $G_{v,1}$,

$\frac{1}{4}+\frac{1}{4m^{2}}+\frac{1}{m^{3}}$

for goods in $G_{u,2}$.

For convenience we write $A_{e}$ to denote the union of groups
$A_{e,1},A_{e,2,\ell},A_{e,3,\ell}$ and $A_{e,4,\ell}$, for all $\ell$.

### Step 3: Adding Dummy Goods

So far we have created

$5m^{10}\cdot|V|+(64m^{5}+48m^{3}+50m)\cdot|E|$ (2)

many agents and

$\sum_{u\in
V}(5m^{10}+S_{u})+32m^{5}\cdot|E|=(5m^{10}-3m)\cdot|V|+(32m^{5}+48m^{3}+27m)\cdot|E|$

many goods. To finish the construction (since the number of goods needs to
match that of agents), we create a group of $3m|V|+(32m^{5}+23m)|E|$ dummy
goods, which have utility $0$ to every agent in the market. This finishes the
construction of $M_{H}$ with $n$ agents and goods, where $n$ is given in (2).
It is clear that $M_{H}$ can be built in polynomial time.

Before moving forward, we record a list of simple properties about $M_{H}$:

######  Fact 3.9.

The HZ market $M_{H}$ satisfies the following properties:

  1. 1.

Every agent in the market has maximum utility $1$;

  2. 2.

For each node $v\in V$, the number of agents outside of $A_{v}$ that have a
positive utility on at least one group of goods in $G_{v}$ is at most
$288m^{3}+258m=O(m^{3})$;

  3. 3.

For each edge $e\in E$, the number of agents outside of $A_{e,^{*}}$ that have
a positive utility on $G_{e}$ is $50m=O(m)$.

###  3.3 Proof of Correctness

Let $\epsilon=1/n^{5}$. We prove three lemmas about variable gadgets in
$M_{H}$ in Section 3.4.

We use $p(G_{i})$ to denote the minimum price of goods in a group $G_{i}$. The
first lemma shows that $p(G_{v,1})$ is between (roughly) $0$ and $1/m^{2}$ and
it determines $p(G_{v,2})$ and $p(G_{v,3})$ (approximately).

######  Lemma 3.10.

Let $(x,p)$ be an $\epsilon$-approximate HZ equilibrium of $M_{H}$. Then
$p(G_{v,1})$ satisfies

$0\leq p(G_{v,1})\leq\frac{1}{m^{2}}+O\left(\frac{1}{m^{6}}\right)$

for every $v\in V$. Moreover, $p(G_{v,2})$ and $p(G_{v,3})$ satisfy

$p(G_{v,2})=\frac{1+p(G_{v,1})}{2}\pm
O\left(\frac{1}{m^{7}}\right)\quad\text{and}\quad p(G_{v,3})=2-p(G_{v,1})\pm
O\left(\frac{1}{m^{7}}\right).$ (3)

We prove Lemma 3.10 in Section 3.4.

We next show that the variable gadget created for each node $v\in V$ is
sensitive to demand from agents outside of $A_{v}$. To state the lemma (and
the next one), we introduce the following notation: Let $G^{*}$ be a subset of
goods (which could be a group or the union of multiple groups of goods) and
$A^{*}$ be a subset of agents in $M_{H}$ (which could be a group or the union
of multiple groups). We let

$x^{+}(G^{*},A^{*})=\sum_{\begin{subarray}{c}i\in A^{*}\\\ j\in G^{*}:\\\
u_{i,j}>0\end{subarray}}x_{i,j},$

i.e., the total allocation of $G^{*}$ to $A^{*}$ but limited to those goods in
$G^{*}$ with positive utilities to each agent in $A^{*}$ only. We also write
$\overline{A}_{v}$ to denote all agents in $M_{H}$ outside of $A_{v}$.

The second lemma (which we also prove in Section 3.4) states that if the total
allocation of $G_{v}$ to agents outside of $A_{v}$ with positive utilities is
either more than $S_{v}+1$ or less than $S_{v}-1$, then $p(G_{v,1})$ must be
at one of the two extreme cases accordingly, i.e., either close to $0$ or
close to $1/m^{2}$.

######  Lemma 3.11.

Let $(x,p)$ be an $\epsilon$-approximate HZ equilibrium of $M_{H}$. Then for
every $v\in V$:

  1. 1.

If $x^{+}(G_{v},\overline{A}_{v})\geq S_{v}+1$, then we have

$p(G_{v,1})=\frac{1}{m^{2}}\pm O\left(\frac{1}{m^{9}}\right);$

  2. 2.

If $x^{+}(G_{v},\overline{A}_{v})\leq S_{v}-1$, then we have $p(G_{v,1})\leq
O(1/n^{2})$.

Finally we prove the following lemma about edge gadgets in $M_{H}$ in Section
3.5:

######  Lemma 3.12.

Let $(x,p)$ be an $\epsilon$-approximate HZ equilibrium of $M_{H}$. For each
$e=(u,v)\in E$,

$x^{+}(G_{u},A_{e})=24m^{3}+12m\pm O(1)\quad\text{and}\quad
x^{+}(G_{v},A_{e})=-6m^{3}p(G_{u,1})+24m^{3}+15m\pm O(1).$

We now use these lemmas to prove Theorem 3.1:

###### Proof of Theorem 3.1 assuming Lemmas 3.10, 3.11 and 3.12.

Let $H=(V,E)$ be a threshold game, and let $(x,p)$ be an
$\epsilon$-approximate HZ equilibrium of $M_{H}$. Let $(x_{v}:v\in V)$ be a
profile for $H$ with

$x_{v}=\min\big{(}1,m^{2}p(G_{v,1})\big{)}$

for each $v\in V$. We prove below that $(x_{v}:v\in V)$ is a
$\kappa$-approximate equilibrium of $H$.

Fix a node $v\in V$. We consider two cases.

  1. 1.

Case $1$: $\sum_{u\in N_{v}}x_{u}>0.5+\kappa$. In this case,
$x^{+}(G_{v},\overline{A}_{v})$ is at most

$\displaystyle\text{out-deg}(v)\cdot\big{(}24m^{3}+12m+O(1)\big{)}+\sum_{u\in
N_{v}}\big{(}24m^{3}+15m-6m^{3}p(G_{u,1})+O(1)\big{)}$ $\displaystyle\hskip
28.45274pt=S_{v}+3m-6m^{3}\sum_{v\in N_{v}}p(G_{u,1})+O(1)<S_{v}-1.$

It follows from Lemma 3.11 that $p(G_{v,1})\leq O(1/n^{2})$ and thus,
$x_{v}\leq O(m^{2}/n^{2})<\kappa$.

  2. 2.

Case $2$: $\sum_{u\in N_{v}}x_{u}<0.5-\kappa$. Using $p(G_{u,1})\leq
1/m^{2}+O(1/m^{9})$, we have

$\sum_{u\in N_{v}}m^{2}p(G_{u,1})<0.5-\kappa+O(1/m^{7}).$

Similarly, $x^{+}(G_{v},\overline{A}_{v})$ is at least

$\displaystyle\text{out-deg}(v)\cdot\big{(}24m^{3}+12m-O(1)\big{)}+\sum_{u\in
N_{v}}\big{(}24m^{3}+15m-6m^{3}p(G_{u,1})-O(1)\big{)}$ $\displaystyle\hskip
28.45274pt=S_{v}+3m-6m^{3}\sum_{u\in N_{v}}p(G_{u,1})-O(1)>S_{v}+1.$

It follows from Lemma 3.11 that $p(G_{v,1})\geq(1/m^{2})-O(1/m^{9})$ and thus,
$x_{v}\geq 1-\kappa$.

This finishes the proof of the theorem. ∎

###  3.4 Analysis of Variable Gadgets

We prove Lemma 3.10 and Lemma 3.11 in this section. We start with some simple
bounds on prices of goods in $G_{e}$ and $G_{v,3}$, $e\in E$ and $v\in V$:

######  Lemma 3.13.

Let $(x,p)$ be an $\epsilon$-approximate HZ equilibrium of $M_{H}$. We have
$p(G_{e})\geq 2(1-2\epsilon)$ for every $e\in E$ and $p(G_{v,3})\geq 5/3$ for
every $v\in V$.

###### Proof.

Fix an $e\in E$. The optimal value of each agent in $A_{e,*}$ is at most
$0.5+\epsilon$; otherwise each of them must receive a bundle with value more
than $0.5$, which implies that each of them gets more than $0.5$ unit of goods
in $G_{e}$, contradicting with the fact that there are $64m^{5}$ many agents
in $A_{e,*}$ but only $32m^{5}$ many goods in $G_{e}$. On the other hand, the
optimal value of each agent in $A_{e,*}$ is at least $\min(1,1/p(G_{e}))$ by
Lemma 3.8 and thus, $p(G_{e})\geq 1/(0.5+\epsilon)>2(1-2\epsilon)$.

Next fix a $v\in V$. With a similar argument, the optimal value of each agent
in $A_{v}$ is at most

$\frac{1}{5m^{10}}\cdot\left(\frac{m^{10}+S_{v}}{2m^{2}-1}+2m^{10}\cdot\frac{m^{2}+1}{4m^{2}-2}+2m^{10}\right)+\epsilon<3/5$

when $m$ is sufficiently large. On the other hand, by Lemma 3.8 the optimal
value of each agent in $A_{v}$ is at least $\min(1,1/p(G_{v,3}))$ and thus,
$p(G_{v,3})\geq 5/3$. ∎

From this we can show that every agent in $M_{H}$ has optimal value at most
$0.9$:

######  Lemma 3.14.

Let $(x,p)$ be an $\epsilon$-approximate HZ equilibrium of $M_{H}$. Then every
agent in $M_{H}$ has optimal value (with respect to $p$) at most $0.9$.

###### Proof.

As shown in the previous lemma, the optimal value of each agent in a group
$A_{v}$ of a variable gadget is at most 3/5, and the optimal value of each
agent in a group $A_{e,*}$ of an edge gadget is at most $0.5+\epsilon$. The
claim for the agents in the groups $A_{e}$ follows from the prices of the
goods in $G_{u,3}$ and $G_{e}$, which are the goods that have utility 1 for
these agents (the other goods have utility 1/2 or less). ∎

This allows us to apply lemmas in Section 3.1. It immediately leads to the
following corollary:

######  Corollary 3.15.

For every group $G_{j}$ of goods, the maximum price in $G_{j}$ is at most
$p(G_{j})+1/n^{2}$.

###### Proof.

Assume for a contradiction that there is a good in $G_{j}$ with price at least
$p(G_{i})+1/n^{2}$. Then for each agent $i$ in the market, we have
$\alpha^{*}_{i}\geq 1/(20n)$ by Lemma 3.4 and thus this good is
$\Omega(1/n^{3})$-suboptimal (by comparing with the good in $G_{j}$ with price
$p(G_{j})$). Hence its allocation to agent $i$ is $O(1/n^{2})$, and the total
allocation of this good in $x$ is $O(1/n)$, a contradiction. ∎

Before proving Lemma 3.10 we show that $p(G_{e})$ is very close to $2$:

######  Lemma 3.16.

For every edge $e\in E$ we have $p(G_{e})=2\pm O(1/m^{4})$.

###### Proof.

We have by Lemma 3.13 that $p(G_{e})\geq 2-O(\epsilon)$. For the upper bound
note that by Lemma 3.13 and Lemma 3.4, goods in $G_{e}$ are
$\Omega(1/n)$-suboptimal to agents with zero utility so their total allocation
to such agents is $O(n^{2}\epsilon)$ by Lemma 3.5. By Fact 3.9 the total
allocation of $G_{e}$ to agents outside $A_{e,*}$ with a positive utility is
$O(m)$ and thus, the rest of $32m^{5}-O(m)$ units of $G_{e}$ are allocated to
agents in $A_{e,*}$. So

$\left(32m^{5}-O(m)\right)p(G_{e})\leq 64m^{5}(1+\epsilon),$

which implies that $p(G_{e})\leq 2+O(1/m^{4})$. This finishes the proof of the
lemma. ∎

We are now ready to prove Lemma 3.10:

Figure 1: The variable gadget.

###### Proof of Lemma 3.10.

Fixing any node $v\in V$, we let $q_{\ell}$ denote $p(G_{v,\ell})$ and
$y_{\ell}$ to denote the total allocation of $G_{v,\ell}$ to agents in $A_{v}$
in $x$, for each $\ell\in\\{1,2,3\\}$. We also write $u_{\ell}$ to denote the
utility of $G_{v,\ell}$ to agents in $A_{v}$ given in (1). We start by showing
that most goods in $G_{v}$ go to $A_{v}$.

######  Claim 3.17.

We have $y_{1}\geq m^{10}-O(m^{3})$ and $y_{2},y_{3}\geq 2m^{10}-O(m^{3})$.

###### Proof.

Let $\alpha^{*}$ and $\mu^{*}$ be an optimal solution to the dual LP of agents
in $A_{v}$. Then $\alpha^{*}q_{\ell}+\mu^{*}\geq u_{\ell}$ for each $\ell$. We
consider the following two cases.

First we consider the case when $\mu^{*}\geq u_{1}/2=\Omega(1/m^{2})$. This
implies that goods outside of $G_{v}$ are $\Omega(1/m^{2})$-suboptimal for
$A_{v}$ and thus, by Lemma 3.5, the total allocation of them to agents in
$A_{v}$ is $O(m^{10})\cdot O(m^{2}\epsilon)<1$ . As a result,
$y_{1}+y_{2}+y_{3}\geq 5m^{10}-1$ from which the claim follows.

Next consider the case when $\mu^{*}<u_{1}/2$. By Lemma 3.3 ($\alpha^{*}\leq
1$) we have $q_{\ell}\geq\Omega(1/m^{2})$ for every $\ell$. This implies that
agents with zero utilities to $G_{v}$ can be allocated only $n\cdot
O(nm^{2}\epsilon)<1$ units of $G_{v}$ given that they are
$\Omega(1/nm^{2})$-suboptimal by Lemma 3.4. On the other hand, by Fact 3.9 the
allocation to agents outside $A_{v}$ with positive utilities for $G_{v}$ is at
most $O(m^{3})$. So all the rest of $G_{v}$ must be allocated to $A_{v}$ and
the claim follows. ∎

Now that we have $y_{\ell}\geq m^{10}-O(m^{3})$ for all $\ell\in\\{1,2,3\\}$,
we proceed to prove (3). Let $(\alpha^{*},\mu^{*})$ denote an optimal solution
to the dual LP for $A_{v}$. By Lemma 3.5 and taking $\delta=20\epsilon$, we
have

$u_{\ell}\leq\alpha^{*}q_{\ell}+\mu^{*}\leq u_{\ell}+\delta,\quad\text{for all
$\ell\in\\{1,2,3\\}$.}$ (4)

If this were not the case (i.e. the second inequality is violated for some
$\ell$), then goods in $G_{v,\ell}$ are $\delta$-suboptimal to $A_{v}$ and
their total allocation to agents in $A_{v}$ can be no more than $5m^{10}\cdot
2\epsilon/\delta=m^{10}/2,$ a contradiction.

Combining (4) and $u_{2}=(3u_{1}+u_{3})/4$, we have

$\alpha^{*}\left(\frac{3q_{1}+q_{3}}{4}\right)+\mu^{*}-\delta\leq\alpha^{*}q_{2}+\mu^{*}\leq\alpha^{*}\left(\frac{3q_{1}+q_{3}}{4}\right)+\mu^{*}+\delta.$

Using $\alpha^{*}\geq 1/(20n)$ from Lemma 3.4, we have

$\displaystyle q_{2}=\frac{3q_{1}+q_{3}}{4}\pm O(n\epsilon).$ (5)

Next, using Corollary 3.7 and Corollary 3.15 we have

$5m^{10}(1-O(1/n^{2}))\leq q_{1}y_{1}+q_{2}y_{2}+q_{3}y_{3}\leq
5m^{10}(1+\epsilon+1/n^{2}).$

Plugging in $y_{1}=m^{10}\pm O(m^{3})$ and $y_{2},y_{3}=2m^{10}\pm O(m^{3})$
and (5), we have $q_{1}+q_{3}=2\pm O(1/m^{7}).$ Together with (5) again we
obtain

$q_{3}=2-q_{1}\pm O(1/m^{7})\quad\text{and}\quad q_{2}=(1+q_{1})/2\pm
O(1/m^{7}).$

Finally we give an upper bound on $q_{1}$. We first note that $q_{1}<q_{3}$;
otherwise goods in $G_{v,1}$ are $\Omega(1)$-suboptimal to agents in $A_{v}$,
contradicting with $y_{1}=m^{10}\pm O(m^{3})$. Using (4) we have

$\mu^{*}\leq\frac{u_{1}q_{3}-u_{3}q_{1}+O(\delta)}{q_{3}-q_{1}}.$

But when $q_{1}\geq 1/m^{2}+1/m^{6}$ (and thus, $q_{3}\leq 2-1/m^{2}$), the
nominator of the RHS is

$u_{1}q_{3}-u_{3}q_{1}\leq\frac{1}{2m^{2}-1}\cdot\left(2-\frac{1}{m^{2}}\right)-1\cdot\left(\frac{1}{m^{2}}+\frac{1}{m^{6}}\right)\leq-\frac{1}{m^{6}}.$

So we have $\mu^{*}<0$, in contradiction with $\mu^{*}\geq 0$ by Lemma 3.3. ∎

Next we prove Lemma 3.11:

###### Proof of Lemma 3.11.

We use the same notation from the proof of the last lemma.

First given that $q_{2}$ and $q_{3}$ are $\Omega(1)$, the total allocation of
$G_{v,2}$ to agents with zero utility on $G_{v,2}$ is at most $n\cdot
O(n\epsilon)$ using Lemma 3.5; the same applies to $G_{v,3}$.

Suppose that $x^{+}(G_{v},\overline{A}_{v})\leq S_{v}-1$. Because $G_{v}$
contains $5m^{10}+S_{v}$ goods while $A_{v}$ contains only $5m^{10}$ agents,
for $G_{v}$ to be fully sold out, the total allocation of $G_{v,1}$ to agents
with zero utility on $G_{v,1}$ must be $1-o_{n}(1)$. This implies that
$q_{1}\leq 1/n^{2}$ since otherwise, the total allocation for $G_{v,1}$ is at
most $n\cdot O(n^{3}\epsilon)=o_{n}(1)$, using $\epsilon=1/n^{5}$.

Next, suppose $x^{+}(G_{v},\overline{A}_{v})\geq S_{v}+1$. Given that there
are $5m^{10}+S_{v}$ goods in $G_{v}$ and $5m^{10}$ agents in $A_{v}$, there
must be an agent in $A_{v}$ who is allocated at least $1/(5m^{10})$-unit of
goods outside of $G_{v}$ (for which it has zero utility). Since such goods are
$\mu^{*}$-suboptimal, we have $\mu^{*}\leq 5m^{10}\epsilon$. On the other
hand, recall (4) with $\delta=20\epsilon$. We have
$\alpha^{*}(q_{1}+q_{3})+2\mu^{*}=u_{1}+u_{3}\pm 2\delta$ and thus,

$\alpha^{*}=\frac{u_{1}+u_{3}}{2}\left(1\pm
O\left(\frac{1}{m^{7}}\right)\right)$

using Lemma 3.10. Then $q_{1}=(u_{1}-\mu^{*}\pm\delta)/\alpha^{*}=1/m^{2}\pm
O(1/m^{9})$. ∎

###  3.5 Analysis of Edge Gadgets

In this subsection we prove Lemma 3.12. Let $(x,p)$ be an
$\epsilon$-approximate HZ equilibrium of $M_{H}$ and $e=(u,v)\in E$ be an edge
in $H$. We work on agents in $A_{e,1},A_{e,2,\ell},A_{e,3,\ell}$ and
$A_{e,4,\ell}$ to understand their allocations of goods with non-zero
utilitites. We start with agents in $A_{e,1}$:

Figure 2: Edge gadget: Agents $A_{e,1}$

######  Lemma 3.18.

The allocation of $G_{u,3}$ and $G_{v,1}$ to each agent in $A_{e,1}$ is given
by

$\frac{1}{2}+\frac{p(G_{u,1})-p(G_{v,1})}{4}+O\left(\frac{1}{m^{4}}\right)\quad\text{and}\quad\frac{1}{2}+\frac{p(G_{v,1})-p(G_{u,1})}{4}+O\left(\frac{1}{m^{4}}\right),$

respectively.

###### Proof.

The dual LP for each agent in $A_{e,1}$ is to minimize $\alpha+\mu$ subject to
the following constraints: $\alpha\geq 0$; $\alpha p_{j}+\mu\geq 1$ for $j\in
G_{u,3}$; $\alpha p_{j}+\mu\geq 1/2$ for $j\in G_{v,1}$; and $\alpha
p_{j}+\mu\geq 0$ for $j\notin G_{u,3}\cup G_{v,1}$. The constraints for the
minimum-priced goods in the groups $G_{u,3}$, $G_{v,1}$ dominate the
constraints for the others goods in the groups (since $\alpha\geq 0$), hence
these constraints are equivalent to

$\alpha\cdot p(G_{u,3})+\mu\geq 1\quad\text{and}\quad\alpha\cdot
p(G_{v,1})+\mu\geq 1/2.$ (6)

The constraint for the good $j$ with price $0$ yields $\mu\geq 0$, and this
subsumes the constraints for all $j\notin G_{u,3}\cup G_{v,1}$. Thus, the dual
LP is to minimize $\alpha+\mu$ subject to $\alpha\geq 0$, $\mu\geq 0$, and (6)
above. The optimal solution $\alpha^{*},\mu^{*}$ satisfies the (6) as
equalities. Thus, solving the dual LP we get

$\alpha^{*}=\frac{1}{2(p(G_{u,3})-p(G_{v,1}))}\approx\frac{1}{4}\quad\text{and}\quad\mu^{*}=\frac{p(G_{u,3})-2p(G_{v,1})}{2(p(G_{u,3})-p(G_{v,1}))}\approx\frac{1}{2}.$

Consider an agent in $A_{e,1}$ and write $x_{u}$ and $x_{v}$ respectively to
denote her allocation of goods from $G_{u,3}$ and $G_{v,1}$. Since every good
that is not in $G_{u,3}\cup G_{v,1}$ is $\mu^{*}$-suboptimal for the agent, it
follows from Corollary 3.6 and Corollary 3.15 that

$x_{u}+x_{v}=1\pm O(\epsilon)\quad\text{and}\quad
p(G_{u,3})x_{u}+p(G_{u,1})x_{v}=1\pm O(1/n^{2}).$

From Lemma 3.10, $p(G_{u,3})=2-p(G_{u,1})\pm O(1/m^{7})$. For ease of
notation, let us use $p_{v}$ to denote $p(G_{v,1})$ and $p_{u}$ for
$p(G_{u,1})$. Solving the above equations for $x_{u}$ and $x_{v}$ gives us

$\displaystyle x_{v}=\frac{1-p_{u}}{2-p_{u}-p_{v}}\pm
O\left(\frac{1}{m^{7}}\right)\quad\text{and}\quad
x_{u}=\frac{1-p_{v}}{2-p_{u}-p_{v}}\pm O\left(\frac{1}{m^{7}}\right).$

Since $p_{u},p_{v}\in[0,1/m^{2}\pm O(1/m^{6})]$, by performing the first order
approximation, we have

$\displaystyle\frac{1-p_{u}}{2-p_{u}-p_{v}}=\frac{(1-p_{u})(2+p_{u}+p_{v})}{(2-p_{u}-p_{v})(2+p_{u}+p_{v})}=\frac{2+p_{v}-p_{u}-p_{u}(p_{u}+p_{v})}{4-(p_{u}+p_{v})^{2}}=\frac{2+p_{v}-p_{u}}{4}\pm
O\left(\frac{1}{m^{4}}\right).$

The result for $x_{u}$ can be shown similarly. ∎

Now we work on agents in $A_{e,2,\ell}$ for each $\ell\in[m]$:

Figure 3: Edge gadget: Agents $A_{e,2,\ell}$ with $\ell\in[m]$.

######  Lemma 3.19.

For each $\ell\in[m]$, the allocation of goods in $G_{v,1}$ to each agent in
$A_{e,2,\ell}$ is $O(m^{4}\epsilon)$ if $\ell/m^{3}\leq p(G_{v,1})-1/m^{4}$
and $0.5\pm O(1/{m^{2}})$ if $\ell/m^{3}\geq p(G_{v,1})+1/m^{4}$.

###### Proof.

The dual LP of each agent in $A_{e,2,\ell}$ is to minimize $\alpha+\mu$
subject to the following constraints: $\alpha\geq 0$; $\mu\geq 0$;
$\alpha\cdot p(G_{e})+\mu\geq 1$; $\alpha\cdot p(G_{v,1})+\mu\geq\ell/2m^{3}$.
(We have simplified the dual LP following similar arguments used at the
beginning of the proof for the previous lemma.) The optimal solution
$(\alpha^{*},\mu^{*})$ now has two cases.

If $p(G_{v,1})\geq\ell/m^{3}+1/m^{4}$, the optimal solution
$(\alpha^{*},\mu^{*})$ is $\alpha^{*}=1/p(G_{e})$ and $\mu^{*}=0$. Thus,

$\alpha^{*}\cdot
p(G_{v,1})+\mu^{*}=\frac{p(G_{v,1})}{p(G_{e})}\geq\frac{\ell}{2m^{3}}+\Omega\left(\frac{1}{m^{4}}\right)$

using Lemma 3.16. So goods in $G_{v,1}$ are $\Omega(1/m^{4})$-suboptimal to
the agent and it follows directly from Lemma 3.5 that the agent is allocated
at most $O(m^{4}\epsilon)$ units of $G_{v,1}$.

If $p(G_{v,1})<\ell/m^{3}-1/m^{4}$, the optimal solution is given by

$\alpha^{*}=\frac{1-\ell/(2m^{3})}{p(G_{e})-p(G_{v,1})}\approx\frac{1}{2}\quad\text{and}\quad\mu^{*}=\frac{(\ell/2m^{3})p(G_{e})-p(G_{v,1})}{p(G_{e})-p(G_{v,1})}\geq\Omega\left(\frac{1}{m^{4}}\right).$

So goods not in $G_{e}\cup G_{v,1}$ are $\mu^{*}$-suboptimal. Let $x_{e}$ and
$x_{v}$ be respectively the allocation of goods in $G_{e}$ and $G_{v,1}$ to
the agent. It follows from Corollary 3.6 and Corollary 3.15 that

$\displaystyle x_{e}+x_{v}$ $\displaystyle=1\pm
O(m^{4}\epsilon)\quad\text{and}\quad p(G_{e})x_{e}+p(G_{v,1})x_{v}=1\pm
O(1/n^{2}).$

Solving the above equations, and recalling $p(G_{e})=2\pm O(1/m^{4})$ and
$p(G_{v,1})=O(1/m^{2})$, we have

$\displaystyle x_{v}=\frac{p(G_{e})-1}{p(G_{e})-p(G_{v,1})}\pm
O\left(\frac{1}{n^{2}}\right)=\frac{2+p(G_{v,1})}{4}\pm
O\left(\frac{1}{m^{4}}\right).$

This finishes the proof of the lemma. ∎

######  Lemma 3.20.

The total allocation of goods in $G_{v,1}$ to all agents in $A_{e,2,\ell}$,
$\ell\in[m]$, is

$3m\big{(}1-m^{2}p(G_{v,1})\big{)}\pm O(1).$

###### Proof.

Let $\ell^{*}=\lfloor m^{3}p(G_{v,1})\rfloor\in[0:m]$. Then for each
$\ell\in[m]$ with $\ell\leq\ell^{*}-1$, the allocation of $G_{v,1}$ to each
agent in $A_{e,2,\ell}$ is $O(m^{4}\epsilon)$; for each $\ell\in[m]$ with
$\ell\geq\ell^{*}+2$, the allocation is $0.5\pm O(1/m^{2})$. For $\ell^{*}$
and $\ell^{*}+1$, the allocation is between $0$ and $1$ trivially.

Since there are 6 agents in each group $A_{e,2,\ell}$, the total allocation to
all agents in all groups is

$6\sum_{\ell\in[\ell^{*}-1]}O(m^{4}\epsilon)+6\sum_{\ell\in[\ell^{*}+2:m]}\left(\frac{1}{2}\pm
O\left(\frac{1}{m^{2}}\right)\right)+O(1)=6\sum_{\ell\in[\ell^{*}+2:m]}\frac{1}{2}\pm
O(1).$

The number of summands in the last expression is

$\max(0,m-\ell^{*}-1)=m\left(1-m^{2}p(G_{v,1})\right)\pm O(1)$

and the lemma follows. ∎

The following lemma for agents in $A_{e,3,\ell}$ can be proved similarly:

######  Lemma 3.21.

The allocation of goods in $G_{u,1}$ to all agents in $A_{e,3,\ell}$,
$\ell\in[m]$, is

$4m\big{(}1-m^{2}p(G_{u,1})\big{)}\pm O(1).$

Finally we work on agents in $A_{e,4,\ell}$, $\ell\in[2m]$:

Figure 4: Edge gadget: Agents $A_{e,4,\ell}$ with $\ell\in[2m]$.

######  Lemma 3.22.

For each $\ell\in[2m]$, we have the following two cases for an agent in
$A_{e,4,\ell}$:

  1. 1.

The allocation of $G_{u,2}$ is $O(m^{3}\epsilon)$ and the allocation of
$G_{v,1}$ is $0.5\pm O(1/m^{2})$, if $\ell$ satisfies

$\frac{\ell}{2m^{3}}\geq\frac{p(G_{v,1})}{2}-\frac{p(G_{u,1})}{3}+\frac{1}{3m^{2}}+\frac{2}{m^{3}}.$
(7)

  2. 2.

The allocation of $G_{v,1}$ is $O(m^{3}\epsilon)$ and the allocation of
$G_{u,2}$ is $2/3\pm O(1/m^{2})$, if $\ell$ satisfies

$\frac{\ell}{2m^{3}}\leq\frac{p(G_{v,1})}{2}-\frac{p(G_{u,1})}{3}+\frac{1}{3m^{2}}.$
(8)

###### Proof.

The dual LP for an agent in $A_{e,4,\ell}$ is to minimize $\alpha+\mu$ subject
to $\alpha\geq 0$, $\mu\geq 0$,

$\alpha\cdot p(G_{e})+\mu\geq 1,\quad\alpha\cdot
p(G_{u,2})+\mu\geq\frac{1}{4}+\frac{1}{4m^{2}}+\frac{1}{m^{3}}\quad\text{and}\quad\alpha\cdot
p(G_{v,1})+\mu\geq\frac{\ell}{2m^{3}}.$ (9)

Geometrically, the feasible space of the LP is a region of the $\alpha-\mu$
plane, bounded from below by a a piecewise linear convex curve whose segments
correspond to (some of) the above constraints. The optimum is achieved at a
vertex of the boundary curve, where the constraints corresponding to the two
adjacent segments are tight. We consider the two cases.

First we consider the case of (7). In this case, the first and third
inequalities of (9) are tight at optimality, and the optimal solution
$(\alpha^{*},\mu^{*})$ is

$\alpha^{*}=\frac{1-(\ell/2m^{3})}{p(G_{e})-p(G_{v,1})}\quad\text{and}\quad\mu^{*}=\frac{(\ell/2m^{3})\cdot
p(G_{e})-p(G_{v,1})}{p(G_{e})-p(G_{v,1})}.$

Using (7) and $p(G_{e})\approx 2$, $p(G_{u,1})\leq 1/m^{2}\pm O(1/m^{6})$, it
is easy to check that $\mu^{*}=\Omega(1/m^{3})$. Therefore, all goods that are
not in $G_{e}\cup G_{v,1}\cup G_{u,2}$ are $\Omega(1/m^{3})$-suboptimal.
Furthermore, also all goods in $G_{u,2}$ are $\Omega(1/m^{3})$-suboptimal,
i.e.,

$\alpha^{*}\cdot
p(G_{u,2})+\mu^{*}-\left(\frac{1}{4}+\frac{1}{4m^{2}}+\frac{1}{m^{3}}\right)\geq\Omega\left(\frac{1}{m^{3}}\right),$

because multiplying the left-hand-side by $p(G_{e})-p(G_{v,1})\approx 2$ we
get

$\displaystyle\frac{1}{2}-\frac{\ell}{4m^{3}}+\frac{p(G_{u,1})}{2}+\frac{\ell}{m^{3}}-p(G_{v,1})-\frac{1}{2}-\frac{1}{2m^{2}}-\frac{2}{m^{3}}+\frac{p(G_{v,1})}{4}\pm
O\left(\frac{1}{m^{4}}\right)$ $\displaystyle\hskip
14.22636pt=\frac{3\ell}{4m^{3}}+\frac{p(G_{u,1})}{2}-\frac{3p(G_{v,1})}{4}-\frac{1}{2m^{2}}-\frac{2}{m^{3}}\pm
O\left(\frac{1}{m^{4}}\right)\geq\Omega\left(\frac{1}{m^{3}}\right).$

So it follows from Lemma 3.5 that the total allocation to the agent (and the
cost) of all goods that are not in $G_{e}$ and $G_{v,1}$ is
$O(m^{3}\epsilon)$.

Using $x_{e}$ and $x_{v}$ to denote the allocation of goods in $G_{e}$ and
$G_{v,1}$ to the agent respectively, it follows from Corollary 3.6 and
Corollary 3.15 that

$\displaystyle x_{e}+x_{v}$ $\displaystyle=1\pm
O(m^{3}\epsilon)\quad\text{and}\quad p(G_{v,1})x_{v}+p(G_{e})x_{e}=1\pm
O(1/n^{2})$

and using $p(G_{e})\approx 2$ and $p(G_{v,1})=O(m^{2})$, one can derive that
$x_{v}=0.5\pm O(1/m^{2})$.

Similarly, one can show that when (8) holds, then the first two inequalities
of (9) are tight at the optimal solution $\alpha^{*},\mu^{*}$. We have again
$\mu^{*}=\Omega(1/m^{3})$, and thus all goods outside $G_{e}\cup G_{u,2}\cup
G_{v,1}$ are $\Omega(1/m^{3})$-suboptimal. Furthermore, in this case all goods
in $G_{v,1}$ are also $\Omega(1/m^{3})$-suboptimal. Hence the total allocation
(and cost) of these goods to the agent is $O(m^{3}\epsilon)$. We can set up
similarly as in the previous case the equations for the allocations
$x_{e},x_{u}$ of the goods in $G_{e}$, $G_{u,2}$ respectively to the agent,
and solve them to get $x_{u}=2/3\pm O(1/m^{2})$. This concludes the proof. ∎

######  Lemma 3.23.

The total allocation of goods in $G_{v,1}$ to agents in $A_{e,4,\ell}$,
$\ell\in[2m]$, is

$18m\left(\frac{2}{3}+\frac{m^{2}}{3}\cdot p(G_{u,1})-\frac{m^{2}}{2}\cdot
p(G_{v,1})\right)+O(1),$

and the total allocation of goods in $G_{u,2}$ to these agents is

$18m\left(\frac{4}{9}-\frac{4m^{2}}{9}\cdot p(G_{u,1})+\frac{2m^{2}}{3}\cdot
p(G_{v,1})\right)+O(1).$

###### Proof.

Let $\ell^{*}$ be chosen as

$\ell^{*}=\left\lfloor m\left(\frac{2}{3}+m^{2}\cdot
p(G_{v,1})-\frac{2m^{2}}{3}\cdot
p(G_{u,1})\right)\right\rfloor\leq\frac{5m}{3}.$

We start with goods in $G_{v,1}$. By Lemma 3.22, the total allocation is $18$
times

$\sum_{\ell\in[\ell^{*}]}O(m^{3}\epsilon)+\sum_{\ell\in[\ell^{*}+6:2m]}\left(0.5\pm
O\left(\frac{1}{m^{2}}\right)\right)+O(1)=\sum_{\ell\in[\ell^{*}+6:2m]}0.5\pm
O(1).$

The number of terms in the last sum is

$2m-m\left(\frac{2}{3}+m^{2}\cdot p(G_{v,1})-\frac{2m^{2}}{3}\cdot
p(G_{u,1})\right)\pm O(1)$

It follows that the total allocation is

$18m\left(\frac{2}{3}+\frac{m^{2}}{3}\cdot p(G_{u,1})-\frac{m^{2}}{2}\cdot
p(G_{v,1})\right)\pm O(1).$

Similarly, the total allocation of goods $G_{u,2}$ is 18 times

$\sum_{\ell\in[\ell^{*}]}\left(\frac{2}{3}\pm
O\left(\frac{1}{m^{2}}\right)\right)+\sum_{\ell\in[\ell^{*}+6:2m]}O(m^{3}\epsilon)+O(1)=\sum_{\ell\in[\ell^{*}]}\frac{2}{3}\pm
O(1).$

The number of terms in the last sum is

$m\left(\frac{2}{3}+m^{2}\cdot p(G_{v,1})-\frac{2m^{2}}{3}\cdot
p(G_{u,1})\right)\pm O(1)$

and the lemma follows. ∎

We are now ready to prove Lemma 3.12:

###### Proof of Lemma 3.12.

Combining Lemma 3.18, Lemma 3.20, Lemma 3.21 and Lemma 3.23, we have the total
allocation of nonzero-utility goods in $G_{v}$ to agents in $A_{e}$ is

$\displaystyle\leavevmode\nobreak\
48m^{3}\left(\frac{1}{2}+\frac{p(G_{v,1})-p(G_{u,1})}{4}\right)+18m\left(\frac{2}{3}+\frac{m^{2}}{3}\cdot
p(G_{u,1})-\frac{m^{2}}{2}\cdot p(G_{v,1})\right)$
$\displaystyle\leavevmode\nobreak\ \hskip 85.35826pt+3m\big{(}1-m^{2}\cdot
p(G_{v,1})\big{)}\pm O(1)$ $\displaystyle\hskip 28.45274pt=-6m^{3}\cdot
p(G_{u,1})+24m^{3}+15m\pm O(1).$

The total allocation of nonzero-utility goods in $G_{u}$ to $A_{e}$ is

$\displaystyle\leavevmode\nobreak\
48m^{3}\left(\frac{1}{2}+\frac{p(G_{u,1})-p(G_{v,1})}{4}\right)+18m\left(\frac{4}{9}-\frac{4m^{2}}{9}\cdot
p(G_{u,1})+\frac{2m^{2}}{3}\cdot p(G_{v,1})\right)$
$\displaystyle\leavevmode\nobreak\ \hskip 113.81102pt+4m\big{(}1-m^{2}\cdot
p(G_{u,1})\big{)}\pm O(1)$ $\displaystyle\hskip 28.45274pt=24m^{3}+12m\pm
O(1).$ (10)

This finishes the proof of the lemma. ∎

##  4 Hardness of Approximating Optimal Social Welfare

In this section we study the problem of approximating the optimal social
welfare (defined as the total utility of all agents) achievable by an HZ
equilibrium. For this purpose we study the following gap problem for a
constant $\rho<1$: the input is an HZ market $M$ together with a parameter SW,
and it is promised that the optimal social welfare achievable by an exact HZ
equilibrium of $M$ is either at least SW or at most $\rho\cdot\textsf{SW}$.
The goal is to tell which case it is. We show that there is no polynomial-time
algorithm for the gap problem when $\rho>175/176$, assuming
$\mathsf{NP}\neq\mathsf{P}$.

######  Theorem 4.1.

Assuming $\mathsf{NP}\neq\mathsf{P}$, for any constant $\epsilon>0$, there is
no polynomial-time algorithm for the gap problem when
$\rho=({175}/{176})+\epsilon$.

###  4.1 Construction

We reduce from $\mathsf{MAX}\leavevmode\nobreak\ 3\mathsf{SAT}$, which is hard
to approximate better than ${7}/{8}$ [Hås01]: Given a $3\mathsf{SAT}$
instance, it is NP-hard to distinguish the case that the formula is
satisfiable from the case that every truth assignment satisfies at most a
fraction $\frac{7}{8}+\epsilon$ of the clauses, for any $\epsilon>0$. Given a
$3\mathsf{SAT}$ instance with $m$ clauses and $n$ variables, we construct the
following HZ market. Throughout the proof, we fix $K=m^{3}$.

#### Creating Variable Gadget

We first introduce the variable gadget. For convenience, we only list non zero
utilities. For each $i\in[n]$

  1. 1.

Create three groups of goods $G_{i,1}$, $G_{i,2}$, $G_{i,3}$, and
$|G_{i,1}|=K$, $|G_{i,2}|=2K$ and $|G_{i,3}|=K$.

  2. 2.

Create two groups of agents $A_{i,1}$, $A_{i,2}$, and
$|A_{i,1}|=|A_{i,2}|=2K$.

  3. 3.

Agents in $A_{i,1}$ have utility $\frac{1}{2K^{2}}$ for $G_{i,1}$,
$\frac{1}{K^{2}}$ for $G_{i,2}$. Agents in $A_{i,2}$ have utility
$\frac{1}{2K^{2}}$ for $G_{i,3}$, $\frac{1}{K^{2}}$ for $G_{i,2}$.

In an (exact) HZ equilibrium, all goods within a group have the same price. We
use $p(G_{i,\ell})$ to denote the price, $\ell\in[3]$.

#### Creating Clause Gadget

We next construct clause gadgets. For each $j\in[m]$,

  1. 1.

Create a group $G_{j}$ of $K$ goods

  2. 2.

Create a group $A_{j,*}$ of $2K$ agents, who have utility $1/K^{2}$ for
$G_{j}$.

  3. 3.

Create an agent $A_{j}$ with utility $1$ for $G_{j}$. It has utility $5/6$ for
$G_{i,1}$ if the $j$-th clause contains $x_{i}$ and utility $5/6$ for
$G_{i,3}$ if the $j$-th clause contains $\overline{x}_{i}$.

#### Adding Dummy Goods

Thus far, we have described $4Kn+Km$ goods and $4Kn+(2K+1)m$ agents. We add
$(K+1)m$ extra dummy goods that have zero utilities for all agents. In a
normalized (exact) HZ equilibrium, these goods have zero price.

###  4.2 Proof of Correctness

We provide the proof of completeness and soundness separately.

#### Completeness

Given a $3\mathsf{SAT}$ instance that has a satisfying assignment, we
construct a HZ equilibrium with social welfare at least
${11}m/{12}-O(1/m^{2})$. Fix a satisfying assignment.

We assign the $j$-th clause to the $\phi(j)$-th variable, if the latter
satisfies the clause. If there are multiple such variables, we choose an
arbitrary one. We set $\ell(j)=1$ if the $j$-th clause contains $x_{\phi(j)}$,
otherwise $\ell(j)=3$. Let $s_{i}$ be the total number of clauses assigned to
the $i$-th variable. The equilibrium prices are as follows.

  1. 1.

The price of dummy goods is $0$.

  2. 2.

The price of $G_{j}$ is $p(G_{j})=\frac{2K+1}{K}$, $j\in[m]$.

  3. 3.

For variable gadget $i\in[n]$, if $x_{i}=1$, then
$(p(G_{i,1}),p(G_{i,3}),p(G_{i,2}))=(0,\frac{8}{5},\frac{4}{5})$, otherwise,
we have $(p(G_{i,1}),p(G_{i,2}),p(G_{i,3}))=(\frac{4}{5},\frac{8}{5},0)$.

Next, we specify the equilibrium allocation.

  1. 1.

Agents of $A_{j,*}$ take $\frac{2K^{2}}{2K+1}$ of $G_{j}$ and
$\frac{2K^{2}+2K}{2K+1}$ of dummy goods, $j\in[m]$.

  2. 2.

Agent $A_{j}$ takes $\frac{K}{2K+1}$ of $G_{j}$ and $\frac{K+1}{2K+1}$ of
$G_{\phi(j),\ell(j)}$, $j\in[m]$.

  3. 3.

If $x_{i}=1$, then agents in $A_{i,1}$ obtain $\frac{5K}{4}$ of $G_{i,2}$,
$\frac{3K}{4}$ of $G_{i,1}$; agents in $A_{i,2}$ obtain $\frac{3K}{4}$ of
$G_{i,2}$, $K$ of $G_{i,3}$, $\frac{K}{4}-s_{j}\cdot\frac{K+1}{2K+1}$ of
$G_{i,1}$ and $s_{j}\cdot\frac{K+1}{2K+1}$ of the dummy good, $i\in[n]$. If
$x_{i}=0$, then we define the allocation symmetrically, switching the groups
of agents $A_{i,1}$ and $A_{i,2}$, and the groups of goods $G_{i,1}$ and
$G_{i,3}$.

One can verify that this is indeed a HZ equilibrium. Agent $A_{j}$ has utility
$\frac{K}{2K+1}+\frac{K+1}{2K+1}\cdot\frac{5}{6}=\frac{11K+5}{12K+6}$, and
hence, the social welfare is at least
$m\cdot\frac{11K+5}{12K+6}\geq\frac{11}{12}m-O(1/m^{2})$.

#### Soundness

Consider any normalized HZ equilibrium $(x,p)$. We first characterize the
equilibrium behaviour of variable gadgets. In an (exact) HZ equilibrium, we
say a variable gadget is vacant if no agents outside of the gadget purchase
goods inside the gadget, and we call other gadgets non-vacant. Loosely
speaking, only non-vacant gadgets are of interest, as vacant gadgets do not
interact with the rest of market and their utility is negligible.

######  Lemma 4.2.

For any $i\in[n]$, suppose the $i$-th variable gadget is non-vacant. Then the
equilibrium price is one of the following three cases.

$\displaystyle p(G_{i,1})=\frac{4}{5}\pm O\left(\frac{1}{m^{2}}\right),\quad
p(G_{i,2})=\frac{8}{5}\pm O\left(\frac{1}{m^{2}}\right),\quad p(G_{i,3})=0\pm
O\left(\frac{1}{m^{2}}\right)$ (11) or $\displaystyle p(G_{i,1})=0\pm
O\left(\frac{1}{m^{2}}\right),\quad p(G_{i,2})=\frac{8}{5}\pm
O\left(\frac{1}{m^{2}}\right),\quad p(G_{i,3})=\frac{4}{5}\pm
O\left(\frac{1}{m^{2}}\right)$ (12) or $\displaystyle
p(G_{i,1})=\frac{2}{3}\pm O\left(\frac{1}{m^{2}}\right),\quad
p(G_{i,2})=\frac{4}{3}\pm O\left(\frac{1}{m^{2}}\right),\quad
p(G_{i,3})=\frac{2}{3}\pm O\left(\frac{1}{m^{2}}\right)$ (13)

###### Proof.

We have $p(G_{i,2})>1$, otherwise $G_{i,2}$ is oversold. Since there are
outside agents that purchase goods inside the gadget, we conclude that one of
the agents in $A_{i,1}$, $A_{i,2}$ must purchase goods outside the gadget,
i.e. those zero-price zero-utility goods. Assume that some agents in $A_{i,1}$
purchase such goods (the other case is symmetric.)

It is easy to see then that $p(G_{i,1})>0$, and therefore, the optimal bundles
of agents in $A_{i,1}$ contain $G_{i,1},G_{i,2}$ and zero-price zero-utility
goods. Hence, $p(G_{i,2})=2p(G_{i,1})$. We further divide into two cases based
on the optimal bundle of $A_{i,2}$.

First, suppose agents in $A_{i,2}$ purchase $G_{i,2}$, $G_{i,3}$ and zero-
price zero-utility goods. Then we have $p(G_{i,2})=2p(G_{i,3})$. Note that
there are at most $m$ agents outside the gadget that have nonzero utility for
$G_{i,1}$ or $G_{i,3}$, and no such agents for $G_{i,2}$. Hence, the agents in
$A_{i,1},A_{i,2}$ buy all the goods in the gadget except for at most $m$ units
of $G_{i,1}$ and $G_{i,3}$. Therefore,

$\displaystyle(K\pm O(m))p(G_{i,1})+2Kp(G_{i,2})+(K\pm O(m))p(G_{i,3})=4K.$

Solving the system of this and the previous two equations yields Eq. (13).

Second, suppose agents in $A_{i,2}$ only buy $G_{i,2}$, $G_{i,3}$. Suppose
$p(G_{i,3})>0$. Then we know agents $A_{i,2}$ buy $K\pm O(m)$ of $G_{i,3}$,
and therefore, $K\pm O(m)$ of $G_{i,2}$. Hence, we have

$\displaystyle(K\pm O(m))p(G_{i,2})+(K\pm O(m))p(G_{i,3})=2K$ and
$\displaystyle(K\pm O(m))p(G_{i,1})+2Kp(G_{i,2})+(K\pm O(m))p(G_{i,3})=4K.$
(14)

These equations, together with $p(G_{i,2})=2p(G_{i,1})$ yield the same
solution, i.e., Eq. (13).

Finally, assume $p(G_{i,3})=0$. Then we only have the constraint Eq. (4.2).
These equations, together with $p(G_{i,2})=2p(G_{i,1})$ yield Eq. (11). The
symmetric case, where some agents of $A_{i,2}$ buy some goods outside the
gadget, yields Eq. (12). ∎

The following lemma follows a similar argument of Lemma 3.16, we omit the
proof

######  Lemma 4.3.

The price of goods $G_{j}$ satisfies $p(G_{j})=2+O({1}/{m^{2}})$, $j\in[m]$.

We are now ready to wrap up the proof of soundness. Given an equilibrium
$(x,p)$ that (approximately) maximizes the social welfare, we look at each
non-vacant variable gadget. Based on the three cases stated in Lemma 4.2, we
extract the $i$-th variable to be $1$ if Eq. (12) holds and $0$ if Eq. (11)
holds. We do nothing for the case of Eq. (13) and those vacant variables
(gadgets).

The total utility of all agents in $A_{i,\ell}$ , $i\in[n],\ell\in[2]$, and
all agents in $A_{j,*}$, $j\in[m]$ is at most $O({1}/{m^{2}})$. We focus on
the utility of agents $A_{j}$, $j\in[m]$. If the $j$-th clause is satisfied,
then one of the $5/6$ utility goods has zero price, and one can see that the
utility is (at most)

$\left(\frac{1}{2}\pm O\left(\frac{1}{m^{2}}\right)\right)\cdot
1+\left(\frac{1}{2}\pm
O\left(\frac{1}{m^{2}}\right)\right)\cdot\frac{5}{6}=\frac{11}{12}\pm
O\left(\frac{1}{m^{2}}\right).$

On the other hand, if the $j$-th clause is not satisfied, we still don’t need
to consider the vacant gadgets (as there is no interactions), and the $5/6$
utility goods have price at least $({2}/{3})\pm O({1}/{m^{2}})$. Hence the
utility is at most

$\left(\frac{1}{4}\pm O\left(\frac{1}{m^{2}}\right)\right)\cdot
1+\left(\frac{3}{4}\pm
O\left(\frac{1}{m^{2}}\right)\right)\cdot\frac{5}{6}=\frac{7}{8}\pm
O\left(\frac{1}{m^{2}}\right).$

Thus, if the truth assignment satisfies at most $(\frac{7}{8}+\epsilon)m$
clauses then the social welfare is at most

$\left(\frac{7}{8}+\epsilon\right)m\cdot\left(\frac{11}{12}+O\left(\frac{1}{m^{2}}\right)\right)+\left(\frac{1}{8}-\epsilon\right)m\cdot\left(\frac{7}{8}+O\left(\frac{1}{m^{2}}\right)\right)+O\left(\frac{1}{m}\right)=\frac{175}{192}m+\frac{1}{24}\epsilon
m+O\left(\frac{1}{m}\right).$

From [Hås01], it is NP-hard to distinguish the case that all clauses can be
satisfied (in which case there is an equilibrium with social welfare
$\frac{11}{12}m-O(1/m^{2})$) from the case that at most
$(\frac{7}{8}+\epsilon)m$ clauses can be satisfied (in which case the maximum
social welfare is at most $\frac{175}{192}m+\frac{1}{24}\epsilon m+O(1/m)$).
The theorem follows.

The construction can be easily modified, if desired, so that all utilities are
in $[0,1]$, and every agent has minimum utility 0 and maximum utility 1.

##  5 Discussion

In this paper we resolved the complexity of computing an approximate
equilibrium in the Hylland-Zeckhauser scheme for one-sided matching markets:
we showed that the problem is PPAD-complete, and this holds even for inverse
polynomial approximation and four-valued utilities. We leave open the
complexity of exact equilibria, in particular whether the problem is FIXP-
complete. Another open question is whether the PPAD-hardness of the
approximation problem holds also for 3-valued utilities.

## References

  * [AJKT17] Saeed Alaei, Pooya Jalaly Khalilabadi, and Eva Tardos.  Computing equilibrium in matching markets.  In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 245–261, 2017.
  * [AS98] Atila Abdulkadiroglou and Tayfun Sonmez.  Random serial dictatorship and the core from random endowments in house allocation problems.  Econometrica, 66(3):689–702, 1998.
  * [BM01] Anna Bogomolnaia and Hervé Moulin.  A new solution to the random assignment problem.  Journal of Economic theory, 100(2):295–328, 2001.
  * [Bud11] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [CDDT09] Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng.  Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 273–282. IEEE, 2009.
  * [CPY17] Xi Chen, Dimitris Paparas, and Mihalis Yannakakis.  The complexity of non-monotone markets.  J. ACM, 64(3):20:1–20:56, 2017.
  * [CT09] Xi Chen and Shang-Hua Teng.  Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria.  In International Symposium on Algorithms and Computation, pages 647–656. Springer, 2009.
  * [DK08] Nikhil R Devanur and Ravi Kannan.  Market equilibria in polynomial time for fixed number of goods or agents.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 45–53. IEEE, 2008.
  * [DPSV08] Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani.  Market equilibrium via a primal–dual algorithm for a convex program.  Journal of the ACM (JACM), 55(5):22, 2008.
  * [EMZ19a] Federico Echenique, Antonio Miralles, and Jun Zhang.  Constrained pseudo-market equilibrium.  arXiv preprint arXiv:1909.05986, 2019.
  * [EMZ19b] Federico Echenique, Antonio Miralles, and Jun Zhang.  Fairness and efficiency for probabilistic allocations with endowments.  arXiv preprint arXiv:1908.04336, 2019.
  * [EY10] Kousha Etessami and Mihalis Yannakakis.  On the complexity of Nash equilibria and other fixed points.  SIAM Journal on Computing, 39(6):2531–2597, 2010.
  * [GMVY17] Jugal Garg, Ruta Mehta, Vijay V Vazirani, and Sadra Yazdanbod.  Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 890–901, 2017.
  * [GTV20] Jugal Garg, Thorben Tröbst, and Vijay V Vazirani.  An arrow-debreu extension of the Hylland-Zeckhauser scheme: Equilibrium existence and algorithms.  arXiv preprint arXiv:2009.10320, 2020.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM (JACM), 48(4):798–859, 2001.
  * [HMPY18] Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan.  A pseudo-market approach to allocation with priorities.  American Economic Journal: Microeconomics, 10(3):272–314, 2018\.
  * [HZ79] Aanund Hylland and Richard Zeckhauser.  The efficient allocation of individuals to positions.  Journal of Political economy, 87(2):293–314, 1979.
  * [Jai07] Kamal Jain.  A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities.  SIAM J. Comput., 37(1):303–318, 2007.
  * [Le17] Phuong Le.  Competitive equilibrium in the random assignment problem.  International Journal of Economic Theory, 13(4):369–385, 2017.
  * [McL18] Andy McLennan.  Efficient disposal equilibria of pseudomarkets.  In Workshop on Game Theory, volume 4, page 8, 2018.
  * [Mou18] Hervé Moulin.  Fair division in the age of internet.  Annual Review of Economics, 2018.
  * [Orl10] James Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proc. 42nd ACM Symp. Theory of Computing, pages 291–300, 2010\.
  * [PP21] Christos Papadimitriou and Binghui Peng.  Public goods games in directed networks.  In Proceedings of the 22nd ACM Conference on Electronic Commerce, 2021.
  * [VY11] V. V. Vazirani and M. Yannakakis.  Market equilibria under separable, piecewise-linear, concave utilities.  Journal of the ACM, 58(3), 2011.
  * [VY21] Vijay V Vazirani and Mihalis Yannakakis.  Computational complexity of the Hylland-Zeckhauser scheme for one-sided matching markets.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.

##  Appendix A Padding

Recall that the goal is to reduce the problem of finding a
$(1/n^{5})$-approximate HZ equilibrium to that of finding a
$(1/n^{c})$-approximate HZ equilibrium, for some constant $c>0$. Let $M$ be an
HZ market with $n$ goods, $n$ agents and utilities $u_{i,j}$. Let $N=n^{5/c}$.
We create a new market $M^{*}$ with $nN$ goods and $nN$ agents. This is done
by replacing each good $j$ in $M$ by a group of $N$ goods $G_{j}$ and
replacing each agent $i$ in $M$ by a group of $N$ agents. Agents in each group
$G_{i}$ have the same utility $u_{i,j}$ for goods in $G_{j}$. Given that $c$
is a constant, $M^{*}$ can be constructed in polynomial time.

Now let $(x^{*},p^{*})$ be an $\epsilon$-approximate HZ equilibrium of $M^{*}$
with

$\epsilon=\frac{1}{(nN)^{c}}\leq\frac{1}{n^{5}}.$

We derive a pair $(x,p)$ for the original market $M$ as follows: set $p_{j}$
to be the minimum price of goods in $G_{j}$; set $x_{i,j}$ to be the total
allocation of goods in $G_{j}$ to agents in $A_{i}$ divided by $N$. We prove
that $(x,p)$ is an $\epsilon$-approximate HZ equilibrium of $M$. The first two
conditions hold trivially by the uniform scaling. For the third condition we
note that the total cost of bundles of $A_{i}$ in $(x^{*},p^{*})$ is at most
$N(1+\epsilon)$. Therefore the cost of the bundle $x_{i}$ of agent $i$ is at
most $1+\epsilon$ because prices of goods can only go down. For the last
property, we note that the utility of agent $i$ from $x_{i}$ is the same as
the total utility of agents in $G_{i}$ divided by $N$. On the other hand, the
LP for agent $i$ (with respect to $p$) is the same as the LP for each agent in
$G_{i}$ (with respect to $p^{*}$), after removing subsumed constraints. So
they have the same optimal value. This finishes the correctness proof of the
reduction.

##  Appendix B Disconnected Equilibria

Figure 5: Market with disconnected equilibria.

We provide a simple example showing that there exists disconnected equilibria
even when the HZ market contains only four agents (i.e., $n=4$) and the
utility is drawn from $\\{0,1/2,1\\}$. The example is indeed the variable
gadget we used in Section 4, we present it here for completeness.

Consider the following HZ market. There are two groups of agents, $A_{1}$ and
$A_{2}$, and there are three groups of goods, $G_{1}$, $G_{2}$ and $G_{3}$.
Let $|A_{1}|=|A_{2}|=2$, $|G_{1}|=|G_{3}|=1$ and $|G_{2}|=2$. Each agent in
$A_{1}$ has utility $1/2$ for goods $G_{1}$, utility $1$ for goods $G_{2}$ and
utility $0$ for goods $G_{3}$. Each agent in $A_{2}$ has utility $0$ for goods
$G_{1}$, utility $1$ for goods $G_{2}$ and utility $1/2$ for goods $G_{3}$.

In any (exact) equilibrium, all goods in the same group must clearly have the
same price, because otherwise the most expensive good in the group will remain
unsold. Let $p=(p_{1},p_{2},p_{3})$ denote an equilibrium price vector of
$G_{1},G_{2},G_{3}$, with $\min_{i}p_{i}=0$. Since both $A_{1}$ and $A_{2}$
have utility $1$ for $G_{2}$, the price $p_{2}>1$, because otherwise $G_{2}$
will be oversold.

######  Claim B.1.

There are three disconnected equilibria in the above HZ market, with
equilibria prices $(0,2,0)$, $(0,8/5,4/5)$ and $(4/5,8/5,0)$ respectively.

###### Proof.

Since goods $G_{1}$ and $G_{3}$ are symmetric, w.l.o.g., we can assume
$p_{1}=0$. The optimal bundle of $A_{1}$ contains exactly goods $G_{1}$ and
$G_{2}$ in this case, and we know agents $A_{1}$ purchase $2/p_{2}$ unit of
goods $G_{2}$ and $2-2/p_{2}$ unit of goods $G_{1}$ in total. We conclude
$p_{2}\leq 2$ since there is at most $1$ unit of goods $G_{1}$.

When $p_{2}=2$, agents $A_{1}$ get $1$ unit of $G_{1}$ and $1$ unit of
$G_{2}$, and therefore, agents $A_{2}$ get $1$ unit of $G_{2}$ and $1$ unit of
$G_{3}$. We have $p_{3}=0$ in this case. Thus, the price vector in this case
is $(0,2,0)$.

On the other hand, when $p_{2}<2$, the optimal bundle of agent $A_{2}$ must
contain all three goods. Hence, we have $p_{2}=2p_{3}$ and $2p_{2}+p_{3}=4$.
This leads to $p_{2}=8/5$ and $p_{3}=4/5$. The equilibrium allocation of
$A_{1}$ equals $(3/4,5/4,0)$ for agents $A_{1}$ and $(1/4,3/4,1)$ for agents
$A_{2}$. The equilibrium price vector in this case is $(0,8/5,4/5)$.
Symmetrically, when $p_{3}=0$, there is an equilibrium price vector
$(4/5,8/5,0)$. ∎

######  Remark B.2.

If we consider also unnormalized prices (i.e. include price vectors with
$\min_{i}p_{i}>0$), the set of equilibrium price vectors consists of three
disjoint regions: $\\{(p,2-p,p)|p\geq 0\\}$, $\\{(1-q,1+3q,1-5q)|0<q\leq
1/5\\}$, and $\\{(1-5q,1+3q,1-q)|0<q\leq 1/5\\}$. The equilibrium allocations
are the same as in the normalized price vectors in the three cases.