May 31, 2026
In this paper, we investigate the computational hardness of finding fractional allocations to unit-demand players using competitive equilibria from equal incomes (CEEI), where we allow a small constant error in players’ response to market prices (also known as an approximate Hylland-Zeckhauser equilibrium). We show that assuming the \(\mathbf{(\varepsilon,\delta)}\)-\(\mathrm{\small Gcircuit}\) problem is PPAD-hard (the “PCP for PPAD" conjecture), finding an approximate HZ equilibrium is also PPAD-hard. This result provides additional motivation for trying to prove the PCP for PPAD conjecture as a tool for obtaining robust computational hardness results about markets. Further, we introduce a natural restriction on approximate HZ equilibria, where players’ bundles may still only be approximately optimal given the prices, but may not contain positive-price items for which the player has zero utility. We show unconditionally that there exists a constant \(\varepsilon\) such that finding a restricted \(\varepsilon\)-HZ equilibrium is PPAD-hard.
In this paper we focus on allocating \(n\) divisible goods to \(n\) unit-demand players. A canonical application is assigning students to schools: each student receives a probability distribution over schools, which is then sampled using a lottery. Each student’s utility is their expected utility over the lottery.
Formally, there are \(n\) players and \(n\) items. Each player \(i\) has utility \(u_{ij}\ge 0\) for item \(j\). A valid allocation \(\{X_{ij}\}_{i\in[n],j\in[n]}\) satisfies capacity constraints and unit-demand constraints: \[\forall i,j~X_{ij}\ge0;~~~~~~~\forall j~\sum_{i} X_{ij}=1; ~~~~~~\forall i~\sum_{j} X_{ij}=1\] The utility of player \(i\) under such an allocation is \[U_i(X)=\sum_j u_{ij}\cdot X_{ij}\]
In a setting with money, this allocation problem leads to a unit-demand auction, which is very well understood [1], [2]. The auction’s VCG prices can be easily computed by a linear program. Moreover, there is a natural tatonnement dynamics that converges to those prices [3].
In the setting without money, a natural approach is to use a token currency to produce an allocation. Such an allocation is called a competitive equilibrium from equal incomes (CEEI) or a Hylland-Zeckhauser (HZ) equilibrium [4].
Formally, an allocation \(\{X_{ij}\}\) is supported by an HZ equilibrium if there are item prices \(P_j\ge 0\) such that when faced with these prices and a budget constraint each player picks their bundle \(X_i\) to maximize expected utility:
\[\label{eq:HZ1} \forall i~X_i \in \mathop{\mathrm{arg\,max}}_y\left\{ \sum_j u_{ij} \cdot y_j ~:~\sum_j y_j =1 \text{ and }\sum_{j} P_j \cdot y_j\le 1\right\}\tag{1}\]
Pseudo-market based approaches are not the only way to solve allocation problems without money. There is a rich literature on combinatorial allocation mechanisms such as random serial dictatorship, top trading cycles, and probabilistic serial [5]–[7]. The pseudo-market based approach has several important benefits. Firstly, it incorporates cardinal utility information, which is invariably lost when considering ranking-based mechanisms. Secondly, it is not hard to see that any CEEI outcome is guaranteed to be Pareto optimal (PO)5 and (ex-ante) envy-free (EF) — these are simple consequences of market efficiency.
While an allocation being PO+EF does not generally imply that it is supported by a CEEI, additional “coalition envy-free" conditions imply CEEI [8]. This means that pseudo-market-based equilibria are a natural notion of fairness and efficiency for allocation problems. Moreover, there is a generic reduction that shows that, computationally, the problem of finding a CEEI equilibrium is not more difficult than the problem of”only" finding an allocation that is Pareto-optimal and envy free [9].
Finally, as compared to combinatorial approaches, it is much easier to extend market-based approaches to allocation problems to obtain market-based approaches to much more general coordination problems.
Perhaps the main reason for pseudo-market-based mechanisms not being more widely adopted is that computing equilibrium prices is computationally difficult. While allocation with money can be solved efficiently using simple demand queries, no such algorithm is known for the pseudo-market setting.
Existence of HZ equilibria is proved using a fixed-point argument, which only give exponential-time algorithms for finding a solution. After decades of unsuccessful attempts to find a more efficient algorithm, it was finally shown that the problem of finding such an equilibrium is PPAD-hard [10].
The problem of fair and efficient allocation is important both in theory and in practice. Hence, the main takeaway from the negative result is that one needs to find a relaxation of the equilibrium notion to make it computationally tractable. For example, there are at least two natural ways of getting around the PPAD-hardness of finding Nash equilibria: (1) relaxing the equilibrium notion giving rise to an \(\varepsilon\)-equilibrium; (2) relaxing the information structure of the game, giving rise to correlated equilibria. The first approach leads to a notion that can be computed in quasi-polynomial time [11]. The second – to a notion that can be computed efficiently using a linear program, or, more importantly using repeated play [12].
Both approaches to getting around the computational hardness of Nash equilibria suggest natural approaches to getting around the computational hardness of CEEI. In this paper we focus on the first approach, specifically for allocation problems, giving rise to the following main question:
Main Problem. Can an \(\varepsilon\)-HZ equilibrium be computed efficiently?
Note that – for now – we do not give a precise definition of an \(\varepsilon\)-relaxation notion, as definition details may affect the answer.
The main result of [10] shows that computing an HZ equilibrium is PPAD-hard. It also shows that for a sufficiently small \(\varepsilon\) it is PPAD-hard to find an \(\varepsilon\)-approximate HZ equilibrium where all constraints are satisfied up to \(\varepsilon\). The result is a direct extension of the exact result: when \(\varepsilon\) is sufficiently small, errors are negligible, even when accumulated over the entire market. Thus the reduction from a PPAD-hard fixed-point problem to finding an HZ equilibrium is not affected by such errors.
What happens when \(\varepsilon\) is not negligible, such as when it is a small constant \(\varepsilon=\Theta(1)\)? It depends on the precise definition of an \(\varepsilon\)-HZ equilibrium.
The goal of this section is to explain the different flavors of \(\varepsilon\)-fixed point conjectures/theorems. There are several versions of approximate fixed point problems. Some of these are known to be PPAD-hard, although not the ones needed to prove hardness results for approximate market (or pseudo-market) equilibria.
A particularly useful PPAD-complete problem is that of generalized circuits (or \(\mathrm{\small Gcircuit}\)). One constructs a circuit with gates and wires connecting to input and output nodes. The circuit is allowed to have loops (thus, gates can be thought of as constraints on the nodes). The goal of the \(\mathrm{\small Gcircuit}\) problem is to find a fixed point in \([0,1]^V\), where \(V\) is the number of nodes. Note that as long as the gates’ functions are continuous, Brouwer’s Fixed Point Theorem guarantees that a fixed point exists. To avoid complications with real numbers, one should consider approximate gates. It turns out that this is sufficient for application to computational complexity in game theory. Informally:
The \(\mathbf{\varepsilon}\)-\(\mathrm{\small Gcircuit}\) problem: assign a value from \([0,1]\) to every node such that the value of each gate output is within an additive \(\varepsilon\) from the value prescribed by the gate computing it.
\(\varepsilon\)-\(\mathrm{\small Gcircuit}\) was introduced by [13] as an intermediate problem to show \((1/poly(n))\)-approximate 2-Nash is PPAD-hard. They showed that \((1/poly(n))\)-\(\mathrm{\small Gcircuit}\) is PPAD-complete by a reduction from a discrete Brouwer problem6. Subsequent work by [14] improved this result and showed that \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) is PPAD-complete for some constant \(\varepsilon>0\) even for generalized circuits of fan-out 2. [14]’s result on \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) is used to show constant inapproximability of other problems [15]–[19]. In an effort to nail down the constant \(\varepsilon\) in the inapproximability results, [20] introduced the Pure-Circuit problem, which can be thought of as taking \(\varepsilon\to 1\) for \(\varepsilon\)-\(\mathrm{\small Gcircuit}\), and used it to further tighten results on the hardness of computing Nash equilibria. By a reduction from the Pure-Circuit problem, [20] showed that \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) is PPAD-complete for all \(\varepsilon< 0.1\).
The \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem was initially proposed by [21]. There are some nuances in how exactly the problem should be defined, but the version we will use is a direct relaxation of the \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) problem, where gates have fan-out \(\le 2\), and a \(\delta\)-fraction of gates is allowed to behave arbitrarily:
The \(\mathbf{(\varepsilon,\delta)}\)-\(\mathrm{\small Gcircuit}\) problem: assign a value from \([0,1]\) to every node such that for all but a \(\delta\)-fraction of gates, the value of the gates’ output is within an additive \(\varepsilon\) from the value prescribed based on its inputs.
As a relaxed version of the PPAD-complete \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) problem, the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem is also in PPAD. [21] conjectured that it is PPAD-complete. This is referred to as the PCP for PPAD conjecture, since \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) can be interpreted as a PCP formulation of the \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) problem. They showed that this conjecture implies finding prices and income assignment for the course allocation problem with low market clearing error and near-optimal Gini index is PPAD-complete. Interestingly, the original \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) problem was used to show unconditionally that there exists \(\beta>0\) such that the closely related solution concept \((\alpha^*,\beta)\)-A-CEEI (as defined in [22]) is PPAD-complete where \(\alpha^*\) is a known function of input.7
Our main goal is to tighten the link between (hardness of) approximate market equilibria and well-established conjectures around fixed point computations.
As a secondary goal, we contribute to establishing the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem as the “right" problem to reduce from when establishing the hardness of market equilibria. This should encourage more work on settling the complexity of this problem. We expect either resolution to be beneficial for our understanding of the hardness of approximate market equilibria: If it turns out to be computationally difficult (thus establishing”PCP for PPAD"), then the likely consequence is that hardness of exact market equilibria will translate into hardness of approximate market equilibria – as it does in the present paper. On the other hand, a surprising efficient algorithm for the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) will likely translate into new algorithms for approximate market equilibria (such as approximate HZ equilibria) – perhaps even leading to new efficient dynamic mechanisms.
All our results deal with the computational hardness of computing approximate HZ equilibria for allocating goods without money. As in other “approximate" settings (such as approximate Nash Equilibria), the approximation refers to the extent to which each player best responds to market prices. An allocation \(X\) is supported by an approximate \(\varepsilon\)-HZ equilibrium with prices \(P\) if budget and optimality conditions 1 hold up to \(\varepsilon\): \[\begin{align} &\forall i~\sum_j P_j X_{ij} \le 1+\varepsilon; \nonumber \\ &\forall i~\sum_{j} u_{ij} \cdot X_{ij} \geq \max_y\left\{ \sum_j u_{ij} \cdot y_j ~:~\sum_j y_j =1 \text{ and }\sum_{j} P_j \cdot y_j\le 1\right\}-\varepsilon. \label{eq:HZ2} \end{align}\tag{2}\]
Our first result is on the hardness of computing an \(\varepsilon\)-HZ equilibrium. We show that there is a polynomial time reduction from the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem to the problem of computing an \(\varepsilon\)-HZ:
Theorem 1 (restated). For any positive constant \((\varepsilon,\delta)\), there is a polynomial-time reduction from the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem to the problem of computing an \(\varepsilon'\)-HZ for some other constant \(\varepsilon'\).
Assuming the PCP for PPAD conjecture, this implies that computing an approximately CEEI solution for unit-demand allocation is PPAD-hard. Even without this conjecture, it ties the problem of finding approximate equilibria to a well-stated open problem in approximate fixed-point computation.
Our second result aims to prove that \(\varepsilon\)-HZ equilibria are difficult to compute without relying on new conjectures. Since even high-precision equilibria computation is in PPAD, the best hardness result we can hope for is PPAD hardness. To this end, we introduce a new notion of an approximate HZ equilibrium with restriction (Definition 9). Informally, an allocation is an \(\varepsilon\)-RHZ if (1) each agent chooses a feasible bundle that maximizes their utility up to an additive \(\varepsilon\) using a relaxed budget of up to \(1+\varepsilon\); and (2) no agent ever chooses any positive-price items for which they have \(0\) utility. In other words, in addition to condition 2 we require that \[\label{eq:HZ3} \forall i,j~~u_{ij}=0 \land P_j>0 \Rightarrow X_{ij}=0.\tag{3}\] Consider a market where each player only considers a subset of items (for example, a student may only be interested in a school in their neighborhood, or in a course in their major). Intuitively, restriction 3 says that while a player may not respond optimally to a given vector of prices, they will never even consider items outside of their demand set, and thus we need not consider solutions supporting such responses.
Note that without such a restriction, any solution that removes an \(O(\varepsilon)\)-fraction of the goods from the market can be implemented as an \(\varepsilon\)-HZ solution (by having each player use \(\varepsilon\)-fraction of its budget to buy and burn these items). The restriction aims to curtail such arbitrary “long range" effects within the market.
It turns out that with condition 3 the problem of finding \(\varepsilon\)-RHZ becomes PPAD-complete:
Theorem 2. Finding an \(\varepsilon\)-\(\textit{RHZ}\) with restriction is PPAD-hard for some constant \(\varepsilon>0\).
Technically, the proof of Theorem 2 is very similar to the hardness proof for polynomially-small \(\varepsilon\) in [10]. (We defer the proof of this theorem to Appendix 5.) Our main contribution in this result is a conceptual one: introducing a natural restriction for a market-based equilibrium that makes constant-approximation PPAD-hard. We believe that such a restriction will be useful in other market-based scenarios where the goal is to allow players to approximately-best-respond to the market without creating new arbitrary demands.
While finding a PO+EF allocation is shown to be PPAD-hard by [9] by a reduction from \(1/poly(n)\)-HZ, one might wonder if a relaxed notion of PO+EF is still hard.
****Open Problem** 1**. Is there a constant \(\varepsilon>0\) for which it is PPAD hard to find an \(\varepsilon\)-relaxed Pareto Optimal + Envy Free allocation? That is, every player experiences at most \(\varepsilon\) envy, and there is no Pareto improvement in which everyone is at least as well off, and aggregate welfare increases by at least \(\varepsilon\cdot n\)?
Note that the problem above is strictly stronger than hardness of \(\varepsilon\)-HZ for a constant \(\varepsilon>0\). Therefore, a more reasonable conjecture would be to look for a reduction from the PCP for PPAD problem:
****Open Problem** 2**. Are there constants \(\varepsilon,\delta,\varepsilon'>0\) for which there is a polynomial time reduction from the \(\mathbf{(\varepsilon,\delta)}\)-\(\mathrm{\small Gcircuit}\) problem to the problem of finding an \(\varepsilon'\)-relaxed Pareto Optimal + Envy Free allocation?
A one-sided allocation problem consists of \(n\) unit-demand agents and \(n\) divisible goods, each of which has unit supply. We use \(u_{ij}\) to denote agent \(i\)’s utility for one unit of good \(j\). The HZ scheme is a market-based approach for allocating goods to agents. More specifically, in an HZ market, each agent is given one unit of “fake” currency with no value outside of the market that they can use to buy the goods. An \(\varepsilon\)-HZ equilibrium consists of an allocation \(x \in \RR^{n \times n}_{\geq 0}\) and item prices \(p \in\RR^n_{\geq 0}\) that satisfy the following conditions. For all agents \(i\), we use \(x_i\) to denote her allocation.
Definition 1 (\(\varepsilon\)-HZ, [4], [10]). Given \(\varepsilon>0\), a pair \((x,p)\), where \(x\in \RR^{n\times n}_{\geq 0}\) and \(p\in \RR^{n}_{\geq 0}\) is an \(\varepsilon\)-approximate HZ equilibrium of an HZ market \(M\) if:
Unit supply: \(\sum_{i\in [n]}x_{ij}=1, \forall j\)
Unit demand: \(\sum_{j\in [n]}x_{ij}=1, \forall i\)
Normalized prices: \(\min_{j\in [n]}p_j=0\)
Budget is approximately 1: \(\sum_{j\in [n]}p_j x_{ij}\leq 1+\varepsilon, \forall i\)
Bundle is approximately optimal: \(\sum_{j\in [n]}u_{ij}x_{ij}\geq val_p(i)-\varepsilon, \forall i\)
where \(val_p(i) = \max_{y\geq 0}\left\{ \sum_{j\in [n]} u_{ij} y_j ~:~\sum_{j\in [n]} y_j =1 \text{ and }\sum_{j\in [n]} p_j y_j\le 1\right\}\) is the value of the best affordable bundle for agent \(i\) under unit demand.
[10] observed that the normalization of prices is necessary since HZ equilibria are invariant to the following transformation of the prices: let \((x,p)\) be an HZ equilibrium. Then for any \(0<r\leq \min\{1/(1-p_j)\mid p_j<1\}\), we can rescale the prices \(p\) to \(p'\) where \(p'_j-1=r(p_j-1)\) and \((x,p')\) is also an HZ equilibrium. If we do not normalize the prices, then condition 4 can be trivially satisfied by transforming the prices so that all prices are close to 1. With this observation, they require the normalization in condition (3) that the minimum item price is 0. We also follow this convention.
Next we introduce the generalized circuits problem and its relaxation to \((\varepsilon,\delta)\)-Gcircuit.
Definition 2 (Generalized circuits, [13]). A generalized circuit* \(S\) is a pair \((V, \mathcal{T})\), where \(V\) is a set of nodes and \(\mathcal{T}\) is a collection of gates. Every gate \(T \in \mathcal{T}\) is a 5-tuple \(T = G(\zeta\mid v_1,v_2\mid v)\), in which \(G\in\{G_\zeta, G_{\times\zeta}, G_=, G_+, G_-, G_<, G_{\lor}, G_{\land}, G_{\lnot}\}\) is the type of the gate; \(\zeta \in \mathbb{R} \cup \{nil\}\) is an (optional) real parameter; \(v_1, v_2 \in V \cup \{nil\}\) are the first and second input nodes of the gate (one or both of them may be missing); and \(v \in V\) is the output node; no two distinct gates have the same output node.*
Definition 3 ([21], \((\varepsilon,\delta)\)-Gcircuit). Given a generalized circuit \(S = (V,\mathcal{T})\), we say that an assignment \(x: V \to [0,1]\) \((\varepsilon, \delta)\)-approximately satisfies* \(S\) if for all but a \(\delta\)-fraction of the gates, \(x\) satisfies the corresponding constraints in Table 1.*
| Gate | Constraint |
|---|---|
| \(G_\zeta(\alpha \parallel a)\) | \(\mathbf{x}[a] = \alpha \pm \varepsilon\) |
| \(G_{\times\zeta}(\alpha \mid a \mid b)\) | \(\mathbf{x}[b] = \alpha \cdot \mathbf{x}[a] \pm \varepsilon\) |
| \(G_=(\mid a \mid b)\) | \(\mathbf{x}[b] = \mathbf{x}[a] \pm \varepsilon\) |
| \(G_+( \mid a,b \mid c)\) | \(\mathbf{x}[c] = \min(\mathbf{x}[a] + \mathbf{x}[b], 1) \pm \varepsilon\) |
| \(G_-( \mid a,b \mid c)\) | \(\mathbf{x}[c] = \max(\mathbf{x}[a] - \mathbf{x}[b], 0) \pm \varepsilon\) |
| \(G_<(\mid a,b \mid c)\) | \(\mathbf{x}[c] = \begin{cases} 1 \pm \varepsilon& \text{if } \mathbf{x}[a] < \mathbf{x}[b] - \varepsilon 0 \pm \varepsilon& \text{if } \mathbf{x}[a] > \mathbf{x}[b] + \varepsilon \end{cases}\) |
| \(G_{\lor}(\mid a,b \mid c)\) | \(\mathbf{x}[c] = \begin{cases} 1 \pm \varepsilon& \text{if } \mathbf{x}[a] = 1 \pm \varepsilon\text{ or } \mathbf{x}[b] = 1 \pm \varepsilon 0 \pm \varepsilon& \text{if } \mathbf{x}[a] = 0 \pm \varepsilon\text{ and } \mathbf{x}[b] = 0 \pm \varepsilon \end{cases}\) |
| \(G_{\land}(\mid a,b \mid c)\) | \(\mathbf{x}[c] = \begin{cases} 1 \pm \varepsilon& \text{if } \mathbf{x}[a] = 1 \pm \varepsilon\text{ and } \mathbf{x}[b] = 1 \pm \varepsilon 0 \pm \varepsilon& \text{if } \mathbf{x}[a] = 0 \pm \varepsilon\text{ or } \mathbf{x}[b] = 0 \pm \varepsilon \end{cases}\) |
| \(G_{\lnot}(\mid a \mid b)\) | \(\mathbf{x}[b] = \begin{cases} 1 \pm \varepsilon& \text{if } \mathbf{x}[a] = 0 \pm \varepsilon 0 \pm \varepsilon& \text{if } \mathbf{x}[a] = 1 \pm \varepsilon \end{cases}\) |
[21] conjectured the generalized circuit problem is PPAD-hard to approximate even allowing some constant fraction of the gates to be corrupted. They showed that this conjecture implies computational hardness for computing Nash Equilibria and CEEIs. We show in this paper that this conjecture also implies computing an \(\varepsilon\)-approximate HZ equilibrium is PPAD-hard for some constant \(\varepsilon>0\).
There exist constants \(\varepsilon,\delta>0\) such that \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) is PPAD-hard.
Now we are ready to state our main theorem of this section.
Theorem 1. Assuming Conjecture \(\ref{conj:gcircuit}\), finding an \(\varepsilon\)-HZ equilibrium is PPAD-hard for some constant \(\varepsilon>0\).
We show this by a reduction from the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem to an intermediate problem called \((\kappa, \delta')\)-\(\mathrm{\small Threshold}\) problem and then a reduction from the threshold problem to the \(\varepsilon'\)-HZ problem. The \((\kappa,\delta)\)-\(\mathrm{\small Threshold}\) problem is a relaxation of the Threshold game in [17]. It only requires approximate satisfaction of a large fraction of the gates.
Definition 4 (\((\kappa,\delta)\)-Threshold). Given a threshold game defined on the directed graph \(H=(V,E)\) and threshold \(t\), a strategy profile \(x=(x_u)_{u\in V}\in [0,1]^{|V|}\) is an \((\kappa, \delta)\)-equilibrium of the threshold game if for at least \((1-\delta)\)-fraction of the vertices, we have \[\begin{align} x_v = \begin{cases} [0,\kappa] &\sum_{u\in N_v}x_u>t+\kappa\\ [1-\kappa,1] &\sum_{u\in N_v}x_u<t-\kappa\\ [0,1] &\sum_{u\in N_v}x_u\in [t-\kappa, t+\kappa].\\ \end{cases} \end{align}\] where \(N_v\) is the set of vertices \(u\) with incoming edges \((u,v)\in E\) to vertex \(v\).
Lemma 1. Assuming Conjecture [conj:gcircuit], \((\kappa,\delta)\)-\(\mathrm{\small Threshold}\) is PPAD-hard for some \(\kappa, \delta>0\) and directed graph \(H\) with bounded in-degree and out-degree.
Proof. Conjecture [conj:gcircuit] says that \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) is PPAD-hard, so it suffices to show a reduction from \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) to \((\kappa,\delta')\)-\(\mathrm{\small Threshold}\). [17] give a reduction from \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) to \(\kappa\)-\(\mathrm{\small Threshold}\). Their proof uses an alternative but equivalent formulation of the generalized circuit problem. The alternative gates are shown in Table 2. Consider an instance of the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem \((V,\mathcal{T})\). Without loss of generality, we can assume the generalized circuit has fan-out bounded by some constant (see Appendix 4 for a detailed reduction). Let \(n=|\mathcal{T}|\) be the number of gates. Then we can construct an instance of the threshold game \(H(V,\mathcal{T}),t=1/2\) using the gadget construction in [17], which uses a subgraph consisting of a constant number of vertices to simulate each gate in the generalized circuit. The constructed directed graph \(H\) has in-degree and out-degree bounded by some constant and the number of vertices in the graph is \(c_2 n\) for some constant \(c_2\). Let \((x_v)_{v\in V(H)}\) be an \((\kappa,\delta')\)-equilibrium of the threshold game. Then only \(\delta'\)-fraction of the vertices are not satisfied. We delete any gate in the generalized circuit instance whose gadget in \(H\) has at least one unsatisfied vertex. Since each unsatisfied vertex of \(V(H)\) appears in at most one gate gadget (it is either a vertex added to simulate some gate or a vertex in \(V\) that is the output node of the gate), we will delete at most \(c_2n\delta'\) gates. Thus there are \((1-c_2\delta')n\) gates whose constraints are \(\varepsilon\)-approximately satisfied by \((x_v)_{v\in V(H)}\). Set \(c_2\delta'<\delta\), then the result follows. ◻
| Gate | Constraint |
|---|---|
| \(G_{\frac{1}{2}}(v)\) | \(x[v] = \frac{1}{2} \pm \varepsilon\) |
| \(G_{\times \frac{1}{2}}(\vert v_1 \vert v)\) | \(x[v] = \frac{1}{2} \cdot x[v_1] \pm \varepsilon\) |
| \(G_=(\vert v_1 \vert v)\) | \(x[v] = x[v_1] \pm \varepsilon\) |
| \(G_+(\vert v_1, v_2 \vert v)\) | \(x[v] = \min\{x[v_1] + x[v_2], \frac{1}{2}\} \pm \varepsilon\) |
| \(G_-(\vert v_1, v_2 \vert v)\) | \(x[v] = \max\{x[v_1] - x[v_2], 0\} \pm \varepsilon\) |
| \(G_{<}(\vert v_1, v_2 \vert v)\) | \(x[v] = \left\{ \begin{array}{ll} \frac{1}{2} \pm \varepsilon& \text{if } x[v_1] < x[v_2] - \varepsilon 0 \pm \varepsilon& \text{if } x[v_1] > x[v_2] + \varepsilon \end{array}\right.\) |
| \(G_{\land}(\vert v_1, v_2 \vert v)\) | \(x[v] = \left\{ \begin{array}{ll} \frac{1}{2} \pm \varepsilon& \text{if } x[v_1] = \frac{1}{2} \pm \varepsilon\land x[v_2] = \frac{1}{2} \pm \varepsilon 0 \pm \varepsilon& \text{if } x[v_1] = 0 \pm \varepsilon\lor x[v_2] = 0 \pm \varepsilon \end{array}\right.\) |
| \(G_{\lor}(\vert v_1, v_2 \vert v)\) | \(x[v] = \left\{ \begin{array}{ll} 1 \pm \varepsilon& \text{if } x[v_1] = \frac{1}{2} \pm \varepsilon\lor x[v_2] = \frac{1}{2} \pm \varepsilon 0 \pm \varepsilon& \text{if } x[v_1] = 0 \pm \varepsilon\land x[v_2] = 0 \pm \varepsilon \end{array}\right.\) |
| \(G_{\lnot}(\vert v_1 \vert v)\) | \(x[v] = \left\{ \begin{array}{ll} \frac{1}{2} \pm \varepsilon& \text{if } x[v_1] = 0 \pm \varepsilon 0 \pm \varepsilon& \text{if } x[v_1] = \frac{1}{2} \pm \varepsilon \end{array}\right.\) |
For any constant \(\kappa>0\), [10] reduced the \(\kappa\)-\(\mathrm{\small Threshold}\) problem with bounded in-degree/out-degree to \((1/n^c)\)-HZ where \(n\) is the number of goods/agents in the HZ market, which is polynomial in the number of vertices in the threshold game and \(1/\kappa\). In contrast, we show that \((\kappa,\delta)\)-\(\mathrm{\small Threshold}\) with bounded in-degree/out-degree can be reduced to \(\varepsilon\)-HZ where \(\varepsilon\) is just a constant, thereby showing a stronger hardness of approximation result under Conjecture [conj:gcircuit]. Without loss of generality, we assume the \((\kappa,\delta)\)-\(\mathrm{\small Threshold}\) problem uses a threshold of \(t=1/2\), which is derived from the reduction in the proof of Lemma 1.
The HZ market we construct is the same as in [10]. We restate it here for completion. Let \(m=\lceil C/\kappa\rceil\), where \(C\) is a large constant. Let \(M_H\) be an HZ market consisting of the following groups of agents and goods: for each vertex \(v\in V\), we construct a group of agents \(A_v\) (\(5m^{10}\)), and three groups of goods \(G_{v,1}\) (\(m^{10}+S_v\)), \(G_{v,2}\) (\(2m^{10}\)), \(G_{v,3}\) (\(2m^{10}\)), where the quantity of each group is indicated in the parentheses and \[\begin{align} S_v = (24m^3+12m)\cdot \text{out-deg}(v)+(24m^3+15m)\cdot \text{in-deg}(v)-3m; \end{align}\] For each edge \(e\in E\), we construct five groups of agents \(A_{e,*}(64m^5)\), \(A_{e,1}(48m^3)\), \(A_{e,2,\ell}\) (6 for each \(\ell\in [m]\)), \(A_{e,3,\ell}\) (8 for each \(\ell\in [m]\)), \(A_{e,4,\ell}\) (18 for each \(\ell\in [2m]\)) and a group of goods \(G_e\) (\(32m^5\)). We also add a group of dummy goods \(G_D\) (\(3m|V|+(32m^5+23m)|E|\)) to make the number of agents and goods the same. Let \(A\) be the set of all agents created and \(G\) be the set of all goods created. Let \(n\) be the total number agents/goods in the market, then \(n=|A|=|G|=5m^{10}|V|+(64m^5+48m^3+50m)|E|\). Let \(G_v = G_{v,1}\cup G_{v,2}\cup G_{v,3}\), and \[\textstyle A_e = A_{e,1} \cup \bigcup_{\ell\in[m]} A_{e,2,\ell} \cup \bigcup_{\ell\in[m]} A_{e,3,\ell} \cup \bigcup_{\ell\in[2m]} A_{e,4,\ell}.\] Then \(|G_v|=5m^{10}+S_v\) and \(|A_e|=O(m^3)\). The utilities of the different groups of agents are as follows: \[\begin{align} &A_v: 1 \text{ for }G_{v,3}, \frac{m^2+1}{4m^2-2} \text{ for }G_{v,2}, \frac{1}{2m^2-1} \text{ for }G_{v,1} \\ &A_{e,*}: 1 \text{ for }G_e\\ &A_{e,1}: 1 \text{ for }G_{u,3}, \frac{1}{2}\text{ for }G_{v,1}\\ &A_{e,2,\ell}: 1 \text{ for }G_e, \frac{\ell}{2m^3}\text{ for }G_{v,1}\\ &A_{e,3,\ell}: 1 \text{ for }G_e, \frac{\ell}{2m^3}\text{ for }G_{u,1}\\ &A_{e,4,\ell}: 1 \text{ for }G_e,\frac{\ell}{2m^3}\text{ for }G_{v,1}, \frac{1}{4}+\frac{1}{4m^2}+\frac{1}{m^3}\text{ for }G_{u,2}.\\ \end{align}\] Observe that each agent has a favorite good of utility 1, which is either \(G_e\) for some edge \(e\) or \(G_{v,3}\) for some vertex \(v\).
Note that \(n\leq 6m^{10}|V|\) for \(C\) large enough since the threshold graph \(H\) has bounded degree and thus \(|E|=O(|V|)\). Consider an \(\varepsilon\)-HZ equilibrium \((x,p)\), where \(\varepsilon\) will be set later. Let \(p(G_e)\) and \(\bar{p}(G_e)\) denote the minimum and maximum prices of any good in \(G_e\) (i.e. identical copies of goods in \(G_e\) can have different prices). Similarly we define the minimum and maximum prices for groups of goods \(G_{v,1}, G_{v,2}, G_{v,3}\).
Similar to [10], we will rely on reasoning about the individual optimization LP and its dual defined as follows:
Definition 5 (Individual Optimization LP). \[\begin{align} \max &\sum_{j\in [n]}u_{ij}x_{ij}\\ s.t. &\sum_{j\in [n]}p_j x_{ij}\leq 1\\ &\sum_{j\in [n]}x_{ij}=1\\ & x_{ij}\geq 0, \forall j\in [n] \end{align}\]
Definition 6 (Dual of Individual Optimization LP). \[\begin{align} \min &\alpha_i+\mu_i\nonumber\\ s.t. & \alpha_i p_j+\mu_i\geq u_{ij}, \forall j\in [n] \label{eq:dual-constraint} \\ & \alpha_i\geq 0 \nonumber \end{align}\qquad{(1)}\]
Let \(\alpha_i, \mu_i\) be an optimal solution to the dual LP of each agent \(i\) in \(M_H\). Let \(val_p(i)\) denote the optimal value of both of these LPs. This is the maximum utility agent \(i\) can get subject to the non-relaxed budget of 1 and prices \(p\) from the \(\varepsilon\)-HZ equilibrium.
Definition 7 (\(\delta\)-suboptimal goods [10]). A good \(j\) is called \(\delta\)-suboptimal for agent \(i\) if \(\alpha_i p_j+\mu_i\geq u_{ij}+\delta\).
We state a few observations that are still true in the current setting.
Lemma 2 ([10], Lemma 3.5). For agent \(i\), the total allocation in \(x_i\) to \(\delta\)-suboptimal goods is at most \(2\varepsilon/\delta\).
Lemma 3. \[\begin{align} &\mu_i\geq 0\\ &p(G_e)\geq 2(1-2\varepsilon)\\ &p(G_{v,3})\geq 5/3\\ &\alpha_i+\mu_i=val_p(i)\leq 0.9, \forall i\in A \end{align}\]
Proof. Follows from Lemma 3.3, Lemma 3.13 and Lemma 3.14 in [10] as their proof still applies when \(\varepsilon\) is a small constant. ◻
In what follows, we will keep a counter of bad groups of goods whose minimum prices or allocation does not behave nicely in equilibrium: either the price is too high or a lot of the goods from that group are allocated to agents with 0 utility. We will denote such groups of goods by \(B_G\subset V\cup E\) (the vertex goods indexed by \(v\) and edge goods indexed by \(e\). (Note that we do not differentiate between the groups of goods \(G_{v,1}\), \(G_{v,2}\), and \(G_{v,3}\) for the same vertex nor the groups of agents for the same edge.)
Definition 8. We say an agent is bad* if it has positive utility for any vertex goods or edge goods in \(B_G\).*
We first show that there cannot be too many vertex goods \(G_{v,3}\) or edge goods \(G_e\) with a high price. We focus on these two groups of goods because every agent’s favorite good is either \(G_{v,3}\) or \(G_e\). In what follows, we set the price ceiling to be \(f(m)=m^{20}\) and add any groups of goods exceeding this ceiling to the bad goods. We also set \(\varepsilon= 1/f(m)^2 = 1/m^{40}\).
Lemma 4. Let \(k_v\) be the fraction of vertices \(v\) such that \(p(G_{v,3})\geq f(m)\). Let \(k_e\) be the fraction of edges \(e\) such that \(p(G_e)\geq f(m)\). If \(f(m)=m^{20}\), then \(k_v,k_e\leq O\left(\frac{m^5}{f(m)}\right)=O\left(\frac{1}{m^{15}}\right)\).
Proof. Since every agent can spend at most \((1+\varepsilon)\), and there are \(2m^{10}\) goods in \(G_{v,3}\) for every \(v\) and \(32m^5\) goods in \(G_e\) for every \(e\), we have \[\begin{align} &2m^{10}|V|k_vf(m)\leq n(1+\varepsilon) \leq 6m^{10}|V|(1+\varepsilon)\\ &32m^{5}|E|k_ef(m)\leq n(1+\varepsilon)\leq 6m^{10}|E|(1+\varepsilon).\\ \end{align}\] The result then follows since \(\varepsilon<1\). ◻
Let \(B^1_G\) denote the set of vertices \(v\) of or edges \(e\) such that \(p(G_{v,3})\geq f(m)\) or \(p(G_{e})\geq f(m)\). Then any good labeled with vertices or edges in \(B^{1}_G\) is bad. Let \(B^{1}_A\) be bad agents who have positive utility for any good in \(B^1_G\).
Lemma 5. \[\begin{align} &|B_{A}^{1}| = O\left(\frac{m^5}{f(m)}n\right); \\ & \text{For } i\in A\setminus B_{A}^{1}, \alpha_i=\Omega\left(\frac{1}{f(m)}\right) \end{align}\]
Proof. To calculate the number of bad agents, we have \[\begin{align} |B^{1}_A|&\leq 5m^{10}|V|k_v+(64m^5+O(m^3))|E|k_e\\ &\leq (5m^{10}|V|+(64m^5+O(m^3))|E|)O\left(\frac{m^5}{f(m)}\right) = O\left(\frac{m^5}{f(m)}n\right). \end{align}\] For \(i\in A\setminus B_{A}^{1}\), without loss of generality, we can assume \(i\)’s favorite good is \(G_e\). Since any agent gets utility 1 from their favorite item, we have \[\begin{align} &\alpha_i p(G_e) +\mu_i\geq 1\\ & \alpha_i + \mu_i = val_p(i)\\ \implies &\alpha_i \geq \frac{1-val_p(i)}{p(G_e)-1}\geq \frac{0.1}{f(m)-1} = \Omega\left(\frac{1}{f(m)}\right) \end{align}\] where we use the fact that \(val_p(i)\leq 0.9\) and \(p(G_e), p(G_{v,3})>1\) from Lemma 3. ◻
Let \(g_i\) denote the amount of budget that an agent wastes with respect to the non-relaxed budget of 1, i.e. not spend or spend on goods with 0-utility or on goods with a higher price than the minimum price of its group. More formally, we say \[\begin{align} g_i = 1-\sum_{j:u_{ij}>0} x_{ij}p(G_j) \end{align}\] where \(G_j\) denote the group that a good \(j\) belongs to and \(p(G_j)\) is the minimum price of this group. Note that \(g_i\) might be negative since each agent might spend up to \(1+\varepsilon\).
We show that \(g_i\) is subconstant in \(m\) with the right choice of \(\varepsilon\) for any agent not in \(B_{A}^{1}\). The intuition is that any such agent can always purchase their favorite item with a bounded price and they do not already have their favorite item in full capacity (since their favorite item is under-supplied), implying their allocation would not be approximately optimal if they waste a lot of their budget.
Lemma 6. For \(i\in A\setminus B_{A}^{1}\), \[g_i\leq g(1/m)\] where \(g(1/m) = O(1/f(m))\).
Proof. Since \(\alpha_i+\mu_i\leq 0.9\) for all agent \(i\) by Lemma 3, we know that each agent is allocated \(\leq 0.9\) unit of their favorite item. Thus by unit-demand, they must be allocated \(\geq 0.1\) unit of items that give them utility at most 1/2 since any agent’s second favorite item provides them with utility at most 1/2. With a budget of \(g_i\leq 1\), they can swap \(g_i/f(m)<0.1\) unit of their current allocation with their favorite good for a per-unit gain of \(1/2\) in utility. Since \((x,p)\) is \(\varepsilon\)-HZ, we have \[\frac{g_i}{f(m)}\frac{1}{2}\leq \varepsilon\implies g_i\leq 2\varepsilon f(m)=O\left(\frac{1}{f(m)}\right)\] since \(\varepsilon= \frac{1}{f(m)^2}\). ◻
Corollary 1. \(i\in A\setminus B_{A}^{1}\), \[\begin{align} \sum_{j:u_{ij}>0} x_{ij}p(G_j) = 1\pm O(1/m^{20}) \end{align}\]
Proof. Follows from budget constraint \(1+\varepsilon=1+1/m^{40}\) and Lemma 6. ◻
Let \(x^{0}(G_j, A_k)\) denote the total allocation of goods in \(G_j\) to agents in \(A_k\) such that the allocation gives 0 utility to the agents. Since we know \(p(G_e)\) is bounded from below, we can bound the sum of allocations of \(G_e\) to 0-utility agents over all edges \(e\).
Lemma 7. \[\bigcup_{e\in E} x^{0}(G_e, A) = O\left(\frac{m^5}{f(m)}\right)n.\]
Proof. \[\begin{align} \bigcup_{e\in E}x^{0}(G_e,A) &\leq \bigcup_{e\in E}x^{0}(G_e,B_A^{1}) + \bigcup_{e\in E}x^{0}(G_e,A\setminus B_A^{1})\\ &\leq |B_{A}^{1}|+ (|A|-|B_{A}^{1}|)\frac{g(1/m)}{2-O(\varepsilon)}\\ &= O\left(\frac{m^5}{f(m)}\right)n + \left(1-O\left(\frac{m^5}{f(m)}\right)\right)n\frac{O(1/f(m))}{2-O(\varepsilon)}\\ &= O\left(\frac{m^5}{f(m)}\right)n \end{align}\] since \(\varepsilon= 1/f(m)^2\). The second inequality follows from Lemma 6 and Lemma 3. ◻
Similarly, we can bound the allocation of \(G_v\) goods to 0-utility agents if the price of the goods are bounded from below.
Lemma 8. Fix any \(\ell\in [3]\), then \[\bigcup_{v: p(G_{v,\ell})\geq 1/m^4} x^{0}(G_{v,\ell},A)= O\left(\frac{m^5}{f(m)}\right)n.\]
Proof. \[\begin{align} \bigcup_{v: p(G_{v,\ell})\geq 1/m^4}x^{0}(G_{v,\ell},A) &\leq \bigcup_{v: p(G_{v,\ell})\geq 1/m^4}x^{0}(G_{v,\ell},B_A^{1}) + \bigcup_{v: p(G_{v,\ell})\geq 1/m^4}x^{0}(G_{v,\ell},A\setminus B_A^{1})\\ &\leq |B_{A}^{1}|+ (|A|-|B_{A}^{1}|)\frac{g(1/m)}{1/m^4}\\ &= O\left(\frac{m^5}{f(m)}\right)n + \left(1-O\left(\frac{m^5}{f(m)}\right)\right)n\frac{O(1/f(m))}{1/m^4}\\ &= O\left(\frac{m^5}{f(m)}\right)n, \end{align}\] where the second inequality follows from Lemma 6. ◻
Lemma 9. Let \(k_{e}^{0}\) be the fraction of edges \(e\) where \(x^{0}(G_e,A)>1/m\). Then \(k_{e}^{0}\leq O\left(\frac{m^{16}}{f(m)}\right)=O\left(\frac{1}{m^4}\right)\).
Proof. \[\begin{align} &\bigcup_{e\in E}x^{0}(G_e, A) = O\left(\frac{m^5}{f(m)}\right)n\leq O\left(\frac{m^5}{f(m)}\right)6m^{10}|E|\\ & \bigcup_{e\in E}x^{0}(G_e, A)> \frac{1}{m}|E|k_{e}^{0}\\ &\implies k_{e}^{0} \leq O\left(\frac{m^{16}}{f(m)}\right) \end{align}\] ◻
Let \(B^2_G\) denote the set of edges \(e\) such that \(x^{0}(G_e,A)>1/m\).
Lemma 10. For any \(\ell\in [3]\), let \(k_{v,\ell}^{0}\) be the fraction of vertices \(v\) where \(p(G_{v,\ell})\geq 1/m^4\) and \(x^{0}(G_{v,\ell},A)>1/m\). Then \(k_{v,\ell}^{0}\leq O\left(\frac{m^{16}}{f(m)}\right)=O\left(\frac{1}{m^4}\right)\).
Proof. \[\begin{align} &\bigcup_{v: p(G_{v,\ell})\geq 1/m^4} x^{0}(G_{v,\ell},A)= O\left(\frac{m^5}{f(m)}\right)n\leq O\left(\frac{m^5}{f(m)}\right)6m^{10}|V|\\ & \bigcup_{v: p(G_{v,\ell})\geq 1/m^4} x^{0}(G_{v,\ell},A)> \frac{1}{m}|V|k_{v,\ell}^{0}\\ &\implies k_{v,\ell}^{0} \leq O\left(\frac{m^{16}}{f(m)}\right) \end{align}\] ◻
Let \(B^3_G\) denote the set of vertices \(v\) such that \(p(G_{v,\ell})\geq 1/m^4\) and \(x^{0}(G_{v,\ell},A)>1/m\) for some \(\ell\in [3]\).
The upper bound on allocation of goods to 0-utility agents makes sure that the price of groups of goods behave like they do in a local market. Let \(x^{+}(G_j, A_k)\) denote the total amount of goods in group \(G_j\) that is assigned to agents in group \(A_k\) such that the assignment gives positive utility to the agents.
Lemma 11. For \(e\notin B_G^{2}\), \(p(G_e) = 2\pm O(1/m^4)\).
Proof. Since \(e\notin B_G^2\), we have \(x^{0}(G_e,A)\leq 1/m\). Then \(x^{+}(G_e,A) = x(G_e,A_e\setminus A_{e,1})\geq 32m^5-1/m\). By budget constraint, we have \[\begin{align} p(G_e)\leq \frac{(64m^5+50m)(1+\varepsilon)}{32m^5-1/m} = 2+O(1/m^4) \end{align}\] The claim then follows from Lemma 3. ◻
Let \(y_{\ell}(v) = x(G_{v,\ell}, A_v)\) for any \(\ell\in [3]\). Let \(q_{\ell}(v) = p(G_{v,\ell})\). We might use \(y_{\ell}\) and \(q_{\ell}\) when \(v\) is clear from context. Let \(u_{\ell}\) denote the utility \(A_v\) has for \(G_{v,\ell}\). We rederive a few lemmas regarding the allocation and prices of vertex goods for a subset of vertices.
Lemma 12. For \(v\notin B_G^3\), we have \(y_1\geq m^{10}-O(m^3)\), \(y_2,y_3\geq 2m^{10}-O(m^3)\).
Proof. (Adapted from proof of Claim 3.17 in [10]). Since \(v\notin B_G^3\), we have \(q_\ell<1/m^4\) or \(x^{0}(G_{v,\ell},A)\leq 1/m\) for every \(\ell\in [3]\). Let \(\alpha,\mu\) be an optimal solution to the dual LP for agents in \(A_v\).
Case 1: \(\mu\geq u_1/2=\Omega(1/m^2)\). Then any good that \(A_v\) has 0 utility for is \(\mu\)-suboptimal for them. Thus the total allocation of \(A_v\) to \(\overline{G_v}\) (i.e. not \(G_v\) goods) is bounded by \(5m^{10} * \frac{2\varepsilon}{\Omega(1/m^2)} = O(m^{12})\varepsilon<1\) by Lemma 2 and \(\varepsilon=1/m^{40}\). Thus \(y_1+y_2+y_3\geq 5m^{10}-1\). Since \(y_1\leq |G_{v,1}|=m^{10}+S_v=m^{10}+\Theta(m^3)\) and \(y_2,y_3\leq 2m^{10}\), we have \(y_1\geq m^{10}-1\) and \(y_2,y_3\geq 2m^{10}-O(m^3)\).
Case 2: \(\mu < u_1/2\). For \(\ell\in [3]\), since \(\alpha q_\ell+\mu\geq u_\ell\geq u_1\), we have \(\alpha q_\ell\geq u_1/2\). By Lemma 3, \(\alpha<1\), thus \(q_\ell\geq \frac{u_1}{2\alpha}\geq \frac{u_1}{2}=\Omega(1/m^2)>1/m^4\) for all \(\ell\in [3]\). Thus by \(v\notin B_G^3\), we have \(x^{0}(G_{v,\ell},A)\leq 1/m\) for all \(\ell\in [3]\), which implies \(x^{0}(G_{v},A)\leq O(1/m)\). Since \(G_{v}\) only gives positive utility to \(A_v\) agents and \(A_e\) agents where \(e=(u,v)\) or \(e=(v,k)\) for some \(u\) and \(k\), and there are \(\Theta(m^3)\) such \(A_e\) agents (the in-degree and out-degree of \(H\) are bounded), the total allocation of \(G_v\) to \(A_v\) is \(y_1+y_2+y_3\geq 5m^{10}+S_v-O(m^3)-O(1/m)\geq 5m^{10}-O(m^3)\). Thus \(y_1\geq m^{10}-O(m^3)\) and \(y_2,y_3\geq 2m^{10}-O(m^3)\).
◻
Lemma 13. For all \(v\notin B_{G}^1\cup B_{G}^3\), \[\begin{align} & 0\leq p(G_{v,1})\leq \frac{1}{m^2} + O\left(\frac{1}{m^6}\right)\\ & p(G_{v,2})=\frac{1+p(G_{v,1})}{2}\pm O\left(\frac{1}{m^7}\right)\\ & p(G_{v,3})=2-p(G_{v,1})\pm O\left(\frac{1}{m^7}\right) \end{align}\] and for any \(\ell\in [3]\), \(G_{v,\ell}\) is at most \(\delta\)-suboptimal for any agent in \(A_v\) for \(\delta=20\varepsilon\).
Proof. (Adapted from proof of Lemma 3.10 in [10]). Fix \(v\notin B_{G}^1\cup B_{G}^3\). Let \(\alpha,\mu\) be an optimal solution to the dual LP for agents in \(A_v\). Since \(A_v\subset A\setminus B_A^1\), \(\alpha\geq \Omega(1/f(m))\) by Lemma 5. Since \(v\notin B_{G}^3\), Lemma 12 applies.
First we note that if for any \(\ell\in [3]\), \(G_{v,\ell}\) is \(\delta\)-suboptimal for \(A_v\), then we can assign at most \(2\varepsilon/\delta\) of \(G_{v,\ell}\) per agent in \(A_v\) by Lemma 2. Since we have to assign \(y_\ell\geq m^{10}-O(m^3)\) in total by Lemma 12, we need \[\begin{align} &5m^{10}2\varepsilon/\delta\geq m^{10}-O(m^3)\implies \delta\leq 10\varepsilon+O(\varepsilon/m^7)<20\varepsilon. \end{align}\] for \(m\) large enough. Thus \(G_{v,\ell}\) cannot be \(20\varepsilon\)-suboptimal for \(A_v\) for any \(\ell\in [3]\). Let \(\delta=20\varepsilon\). This implies \[\label{ineq:32constraint-bdd-eps-delta} u_{\ell}\leq \alpha q_\ell +\mu \leq u_\ell+\delta, \forall \ell\in [3].\tag{4}\] Since utilities are designed so that \(u_2=(3u_1+u_3)/4\), we have \[\begin{align} &\alpha\left(\frac{3q_1+q_3}{4}\right)+\mu-\delta\leq u_2\leq \alpha q_2+\mu\leq u_2+\delta\leq \alpha\left(\frac{3q_1+q_3}{4}\right)+\mu+\delta\\ \implies & q_2=\left(\frac{3q_1+q_3}{4}\right) \pm O\left(\frac{\delta}{\alpha}\right) =\left(\frac{3q_1+q_3}{4}\right) \pm O\left(\frac{1}{m^9}\right) \end{align}\] The last line uses the fact that \(O(\delta/\alpha)=O(\varepsilon f(m)) = O(1/m^9)\) since \(\alpha\geq \Omega(1/f(m))\), \(\varepsilon= 1/f(m)^2\) and \(f(m)=m^{20}\). Now, we can use the total payment of agents in \(A_v\) to bound \(q_1,q_2, q_3\). Since \(A_v\subset A\setminus B_A^1\), by Corollary 1 we have \[\begin{align} \label{eq:32good-Av-payment} &q_1y_1 + q_2y_2 + q_3y_3 = 5m^{10}(1\pm O(1/m^{20}))\\ &\implies q_1y_1+\left(\left(\frac{3q_1+q_3}{4}\right) \pm O(1/m^9)\right)y_2 + q_3y_3 = 5m^{10}(1\pm O(1/m^{20})) \end{align}\tag{5}\] where \(f(m)=m^{20}\).
By Lemma 12 we conclude that \[\begin{align} &q_2=\frac{1+q_1}{2}\pm O\left(\frac{1}{m^7}\right)\\ & q_3=2-q_1\pm O\left(\frac{1}{m^7}\right)\label{eqn:q1q3-eps-delta}. \end{align}\tag{6}\] Now it remains to bound \(q_1\). We first observe that \(q_1<q_3\) since if not, then we have \[\begin{align} \alpha q_1+\mu\geq \alpha q_3+\mu\geq u_3=1. \end{align}\] Since \(u_1 = \Theta(1/m^2)\), \(G_{v,1}\) is \((1-\Theta(1/m^2))\)-suboptimal for \(A_v\), a contradiction to \(\delta = 20\varepsilon\). Thus \(q_1< q_3\). By 4 , since \(q_1,q_3\geq 0\), we have \[\begin{align} &q_3*u_{1}\leq q_3(\alpha q_1 +\mu) \leq q_3(u_1+\delta) \\ &q_1*u_{3}\leq q_1(\alpha q_3 +\mu) \leq q_1(u_3+\delta)\\ &\implies\mu\leq \frac{u_1q_3-u_3q_1+q_3\delta}{q_3-q_1} =\frac{u_1q_3-u_3q_1+O(\delta)}{q_3-q_1}. \end{align}\] since \(q_3\leq 3\) by 6 . Note that the denominator is positive. Suppose \(q_1\geq 1/m^2+1/m^6\), then \(q_3\leq 2-1/m^2\) by 6 . Then \(u_1q_3-u_3q_1\leq -1/m^6\). Since \(\delta=20\varepsilon=O(1/m^{40})\), the numerator is negative. Thus \(\mu<0\), a contradiction to \(\mu\geq 0\) by Lemma 3. Thus \[q_1<1/m^2+1/m^6.\] ◻
Lemma 14. For any \(v\notin B_G^1\cup B_G^3\),
If \(x^{+}(G_v, \overline{A_v})\geq S_v+1\), then \(p(G_{v,1})=1/m^2\pm O(1/m^9)\)
If \(x^{+}(G_v, \overline{A_v})\leq S_v-1\), then \(p(G_{v,1})\leq \kappa/m^2\).
Proof. (Adapted from proof of Lemma 3.11 in [10]).
Case 1: \(x^{+}(G_v, \overline{A_v})\geq S_v+1\). Since there are \(5m^{10}+S_v\) goods in \(G_v\), we can allocate at most \(5m^{10}-1\) goods to \(A_v\), so there exists an agent in \(A_v\) who is allocated at least \(1/5m^{10}\) units of goods outside of \(G_v\). Let \(\alpha, \mu\) be an optimal solution to the dual of LP of this agent. Since this agent has 0 utility for these goods, they are \(\mu\)-suboptimal, which means \(1/5m^{10}\leq 2\varepsilon/\mu\), so \(\mu=O(m^{10}\varepsilon)\). By Lemma 13, 4 and 6 , we have \[\begin{align} &\alpha(q_1+q_3)+2\mu =u_1+u_3+ O(\delta)\nonumber\\ \implies & \alpha = \frac{u_1+u_3+O(\varepsilon)-2*O(m^{10}\varepsilon)}{q_1+q_3}\nonumber\\ \implies & \alpha = \frac{u_1+u_3}{2}(1\pm O(1/m^7))\geq \frac{1}{2}(1\pm O(1/m^7))\label{eq:case1-eps-delta} \end{align}\tag{7}\] since \(\delta=20\varepsilon\) and \(\varepsilon= 1/m^{40}\). Again by 4 , we have \[\begin{align} q_1 &=\frac{u_1-\mu+O(\delta)}{\alpha}\\ &=\frac{u_1}{\alpha}+\frac{-O(m^{10}\varepsilon)+O(\varepsilon)}{\alpha}\\ &=\frac{u_1}{\alpha}\pm O(1/m^{10})\text{ by \ref{eq:case1-eps-delta}}\\ &=\frac{u_1}{\frac{u_1+u_3}{2}(1\pm O(1/m^7))}\pm O(1/m^{10})\text{ by \ref{eq:case1-eps-delta}}\\ &=1/m^2\pm O(1/m^9). \end{align}\]
Case 2: \(x^{+}(G_v, \overline{A_v})\leq S_v-1\). Then \[\begin{align} x^0(G_v,\overline{A_v})+x(G_v, A_v)\geq 5m^{10}+1 \implies x^0(G_v,\overline{A_v})\geq 1 \end{align}\] since \(x(G_v, A_v)\leq |A_v|=5m^{10}\). This implies \(x^0(G_{v,1},\overline{A_v})+x^0(G_{v,2},\overline{A_v})+x^0(G_{v,3},\overline{A_v})\geq 1\). Since \(v\notin B_G^3\), it must be the case that either \(p(G_{v,\ell})<1/m^4\) or \(x^0(G_{v,\ell}, A)\leq 1/m\) for all \(\ell\in [3]\). Since \(p(G_{v,\ell})>1/m^4\) for \(\ell=2,3\) by Lemma 13, it must be the case that \[p(G_{v,1})\leq \frac{1}{m^4}\leq \frac{1}{m^3}\frac{\kappa}{C}\leq \frac{\kappa}{m^2}\] where \(m=\lceil \frac{C}{\kappa}\rceil\).
◻
Lemma 15. Consider any \(e=(u,v)\in E\) such that \(e\notin B_{G}^1\cup B_G^2\) and \(u,v\notin B_{G}^1\cup B_G^3\), then \[\begin{align} &x^{+}(G_u, A_e)=24m^3+12m\pm O(1)\\ &x^{+}(G_v, A_e)=24m^3+15m-6m^3p(G_{u,1})\pm O(1)\\ \end{align}\]
Proof. The proof of Lemma 15 is nearly identical to the proof of Lemma 3.12 in [10], so we only highlight the modifications that need to be made. At a high level, the proof of Lemma 3.12 in [10] characterizes the optimal dual solution \((\alpha, \mu)\) for each agent and then applies their bounds on the allocations to each agent and prices. Thus, the only modifications that need to be made are to use our bounds on the allocations and prices when they use theirs. We provide a mapping from their results to ours below so that this substitution is easier.
| [10] | Here |
|---|---|
| Lemma 3.5 | Lemma 2 |
| Corollaries 3.6 + 3.15 | Lemma 2 + Corollary 1 (requires \(e\notin B_G^1\)) |
| Lemma 3.10 | Lemma 13 (requires \(u,v\notin B_G^1\cup B_G^3\)) |
| Lemma 3.16 | Lemma 11 (requires \(e\notin B_G^2\)) |
A careful reader may realize that whenever [10] obtains a bound up to error \(O(m^6\varepsilon)\), this error is \(O(1/\mathrm{poly}(n))\) for them since \(\varepsilon= O(1/\mathrm{poly}(n))\) in their setting. Meanwhile, for us, \(O(m^6\varepsilon) = O(1/m^{34})\) since we chose \(\varepsilon = O(1/m^{40})\). Nonetheless, this additional amount of error does not quantitatively affect the proof. ◻
Lemma 16. Let \(\Delta\) be the fraction of \(v\in V\) s.t. \(v\notin B_G^1\cup B_G^3\) and for any edge \((u,v)\in E\) and \((v,w)\in E\), we have \(u,w\notin B_G^1\cup B_G^3\) and \((u,v),(v,w)\notin B_G^1\cup B_G^2\). Then \(\Delta\geq 1-O(1/m^4)\).
Proof. By definition of \(B_G^1\), \(B_G^2\), and \(B_G^3\), we have \[\begin{align} &|B_G^1|\leq k_v|V|+k_e|E|\\ &|B_G^2|\leq k_e^0|E|\\ &|B_G^3|\leq k_{v,\ell}^0*3|V|\\ \end{align}\] Thus \[\begin{align} &\Delta|V|\geq |V|-(|B_G^1|+|B_G^3|)-6(|B_G^1|+|B_G^3|)-6(|B_G^1|+|B_G^2|)\\ &\geq |V|-O(|B_G^1|)-O(|B_G^2|)-O(|B_G^3|)\\ &=|V|-|V|O(k_v+k_e+k_e^0+k_{v,\ell}^0)\\ &= |V|-|V|(O(1/m^{15})+O(1/m^{15})+O(1/m^4)+O(1/m^4)) \\ &= |V|(1-O(1/m^4)) \end{align}\] where we use the fact that \(|E|=O(|V|)\). Here we first remove the bad vertices from \(B_G^1\) and \(B_G^3\) themselves and then we remove any vertex destroyed by any of its bad neighbors (each bad vertex can destroy up to a constant number of vertices since the degree of \(H\) is bounded) and finally remove any vertex destroyed by any of its incident bad edges (each bad edge can destroy two vertices). Here we crucially rely on the fact that \(H\) has bounded in-degree and out-degree. ◻
Now we are ready to show the core Lemma.
Lemma 17. There is a polynomial-time reduction from \((\kappa,\delta)\)-\(\mathrm{\small Threshold}\) game to \(\varepsilon\)-HZ.
Proof. (Adapted from proof of Theorem 3.1 in [10].)
The proof relies on Lemma 13 (requires \(u,v\notin B_G^1\cup B_G^3\)), Lemma 14 (requires \(v\notin B_G^1\cup B_G^3\)), and Lemma 15 (requires \(e\notin B_G^1\cup B_G^2\)).
For any instance of the threshold game \(H=(V,E)\) where the in-degree and out-degree are bounded and the threshold is \(1/2\), we can create the HZ market \(M_H\) as described before. Let \((x,p)\) be an \(\varepsilon\)-HZ of \(M_H\) where \(\varepsilon=\frac{1}{m^{40}} = \frac{1}{{\lceil C/\kappa\rceil}^{40}}\) for some large constant \(C\). Let \(x_v=\min (1,m^2p(G_{v,1}))\in [0,1]\). Then we claim that \(x=(x_v)_{v\in V}\) is a \((\kappa,\delta)\)-approximate equilibrium of \(H\).
Consider only the fraction of \(v\in V\) s.t. \(v\notin B_G^1\cup B_G^3\) and for any edge \((u,v)\in E\) and \((v,w)\in E\), we have \(u,w\notin B_G^1\cup B_G^3\) and \((u,v),(v,w)\notin B_G^1\cup B_G^2\). Denote this set of vertices by \(S\). Then by Lemma 16, we only removed at most \(O(1/m^4)=c'/m^4\) fraction of the vertices for some constant \(c'\geq 1\). Since \(m=\lceil C/\kappa\rceil\) for some constant \(C\). We can choose \(C>c'/\delta\) so that \(c'/m^4 \leq \kappa^4\delta^4/c'^3<\delta\) since \(0<\kappa,\delta<1\). Thus for any \(v\in S\), Lemma 13, Lemma 14, and Lemma 15 apply. It remains to be shown that for any vertex \(v\in S\), the threshold condition holds.
Case 1: \(\sum_{u\in N_v}x_u>0.5+\kappa\). By definition of \(x_u\), we have \(x_u\leq m^2 p(G_{u,1})\). This implies \(p(G_{u,1})\geq x_u/m^2\implies \sum_{u\in N_v}p(G_{u,1})\geq \sum_{u\in N_v}x_u/m^2>(1/m^2)(0.5+\kappa)\). Then by Lemma 15, we have \[\begin{align} x^{+} (G_v, \overline{A_v}) &= \sum_{v\in e} x^{+}(G_v, A_e)\\ &\leq \text{out-deg}(v)\cdot (24m^3+12m+ O(1)) +\sum_{u\in N_v} (24m^3+15m-6m^3p(G_{u,1})+ O(1))\\ &= S_v+3m-6m^3\sum_{u\in N_v}p(G_{u,1})+O(1)\\ &\leq S_v+3m-6m^3(1/m^2)(0.5+\kappa)+O(1)\\ &= S_v-6m\kappa + O(1) <S_v-1. \end{align}\] since \(m=\lceil C/\kappa\rceil\) and we can choose the \(C\) to be larger than the \(O(1)\) term. Then by Lemma 14, we have \(p(G_{v,1})\leq \kappa/m^2\), which implies \(x_{v}\leq \kappa\), as desired.
Case 2: \(\sum_{u\in N_v}x_u<0.5-\kappa\). By Lemma 13, we have \(p(G_{u,1})\leq 1/m^2+O(1/m^6)\). Thus \[\begin{align} &m^2p(G_{u,1})\leq 1+O(1/m^4)\\ &\implies x_u = \min(1,m^2p(G_{u,1})) \geq m^2p(G_{u,1})-O(1/m^4)\\ &\implies p(G_{u,1})\leq x_u/m^2+O(1/m^6)\\ &\implies \sum_{u\in N_v}p(G_{u,1})\leq \sum_{u\in N_v}x_u/m^2+O(1/m^6)<(1/m^2)(0.5-\kappa+O(1/m^4)) \end{align}\] by bounded in-degree. Then by Lemma 15, we have \[\begin{align} x^{+}(G_v, \overline{A_v})&\geq \text{out-deg}(v)\cdot (24m^3+12m- O(1)) +\sum_{u\in N_v} (24m^3+15m-6m^3p(G_{u,1})-O(1))\\ &= S_v+3m-6m^3\sum_{u\in N_v}p(G_{u,1})-O(1)\\ &\geq S_v+3m-6m^3(1/m^2)(0.5-\kappa+O(1/m^4))-O(1)\\ &= S_v+6m\kappa -O(1/m^3)- O(1) > S_v+1. \end{align}\] Thus by Lemma 14, \(p(G_{v,1})\geq 1/m^2-O(1/m^9)\), which means \(x_v\geq 1-O(1/m^7)\geq 1-\kappa\), as desired.
◻
The authors would like to thank Aviad Rubinstein of Stanford University for discussions about the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem. This research is in part supported by National Science Foundation Alan T. Waterman award grant 1933331.
By definition of a generalized circuit, each gate has a fan-in of at most 2, i.e. it takes inputs from at most two nodes in the circuit. However, each gate can have an unbounded fan-out, i.e. the output node of the gate can have a wire connecting to many gates in the circuit, serving as one of their input values. We will show below that it is without loss of generality to consider only the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problems with a constant fan-out.
Proof. Given an instance of the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) Problem \(S = (V,\mathcal{T})\) for some constant \(\varepsilon, \delta>0\), we show a reduction to an instance of \((\varepsilon',\delta')\)-\(\mathrm{\small Gcircuit}\) Problem \(S'\) with constant fan-out \(10/\delta\) and \(\varepsilon'=\varepsilon, \delta' = \delta/10\). Let \(n=|\mathcal{T}|\) be the number of gates in \(S\). Consider the set of gates \(L\) that have a fan-out \(\geq 10/\delta\). Since each gate in \(S\) has a fan-in of at most 2, and each wire either connects a node to a gate or a gate to its unique output node, there are at most \(3n\) wires in \(S\) and at most \(2n\) wires contribute to the fan-in. Thus there are at most \(2n/(10/\delta)=\delta n/5\) gates in \(L\). We construct \(S'\) as follows: copy the gates and wires in \(S\). For each gate \(T\in L\), let \(a\) be the output node of \(T\) and let \(T_1,\dots, T_k\) denote the gates that the output of \(T\) provides inputs into. We remove all the wires connecting the output node of \(T\) to each gate \(T_i\) for \(i\in [k]\) and add a constant 0 gate that provides input to these \(T_i\) gates (Note: 0 is a valid input to any gate). More formally, for each \(T_i\) gate, we construct a constant \(G(0||a_i)\) gate whose output node \(a_i\) should satisfy \(x[a_i]=0\pm \varepsilon\). Then we modify \(T_i = G(|a,b|c)\) to \(T_i' = G(|a_i,b|c)\). Now the new instance \(S'\) has fan-out at most \(10/\delta\). Consider an \((\varepsilon'=\varepsilon,\delta'=\delta/10)\)-approximate solution \(x'\) to the new instance \(S'\) (an \(\varepsilon\)-approximate solution exists to any generalized circuit instance even without the \(\delta\) slack). Then we can construct a solution \(x\) to \(S\) as follows: for each gate \(T\in L\) whose output node is \(a\), we let \(x[a]=0\). If \(x'[a]\neq 0\), we declare the gate \(T\) corrupted. Now, for each gate \(T_1,\dots, T_k\) that gets input from \(T\), we check if the \(x'[a_i]=0\). If not, we declare \(T_i\) corrupted. For any gate not in \(L\) and does not receive input from a gate in \(L\), it is corrupted in \(S\) if and only if it is corrupted in \(S'\) since they get the same input values and output values. Since \(x'\) is an \((\varepsilon, \delta/10)\)-approximate solution to \(S'\), and we added at most \(n\) gates, there are at most \(2n(\delta/10)=\delta n/5\) corrupted gates in \(S'\). Thus the total number of corrupted gates in \(S\) induced by \(x\) is at most \(\delta n/5 + |L|\leq 2\delta n/5<\delta n\). For any uncorrupted gates, it satisfies the gate to an additive error of \(\varepsilon\). Thus \(x\) is indeed a \((\varepsilon,\delta)\)-approximate solution to \(S\).
The reduction shows that we can use a solution to the \((\varepsilon,\delta/10)\)-\(\mathrm{\small Gcircuit}\) problem with fan-out \(10/\delta\) to solve the problem of \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) with unbounded fan-out. Thus the former problem is at least as hard as the latter problem. From there, we can further reduce the \((\varepsilon,\delta/10)\)-\(\mathrm{\small Gcircuit}\) problem with fan-out \(10/\delta\) to the \((\varepsilon'',\delta'')\)-\(\mathrm{\small Gcircuit}\) problem for some constant \(\varepsilon'',\delta''>0\) with fan-out at most 2 using the same construction as in [14]. ◻
[14] gives a reduction to constant fan-out for \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) by constructing a binary tree of logical gates to copy an output value. This reduction does not directly apply to the \((\varepsilon,\delta)\)-\(\mathrm{\small Gcircuit}\) problem with unbounded fan-out because a single corrupted gate at the top levels of the binary tree can affect \(O(n)\) copied values at the leaves.
Definition 9 (Approximate HZ Equilibria with Restriction). Given \(\varepsilon>0\), a pair \((x,p)\), where \(x\in \RR^{n\times n}_{\geq 0}\) and \(p\in \RR^{n}_{\geq 0}\) is an \(\varepsilon\)-approximate HZ equilibrium with restriction (\(\varepsilon\)-\(\textit{RHZ}\)) of an HZ market \(M\) if:
Unit supply: \(\sum_{i\in [n]}x_{ij}=1, \forall j\)
Unit demand: \(\sum_{j\in [n]}x_{ij}=1, \forall i\)
Normalized prices: \(\min_{j\in [n]}p_j=0\)
Budget is approximately 1: \(\sum_{j\in [n]}p_j x_{ij}\leq 1+\varepsilon, \forall i\)
Bundle is approximately optimal: \(\sum_{j\in [n]}u_{ij}x_{ij}\geq val_p(i)-\varepsilon, \forall i\), where \(val_p(i)\) is the value of the best affordable bundle for agent \(i\) under unit demand.
Do not buy positive-price, 0-utility goods: \(\sum_{j\in [n], u_{ij}=0}p_j x_{ij}=0, \forall i\)
This definition is stricter than the definition in [10] in that we additionally require condition 6—no zero utility goods are purchased with positive prices. This additional requirement allows us to derive a stronger inapproximability result shown below in 2.
Lemma 18. An \(\varepsilon\)-\(\textit{RHZ}\) exists for any \(\varepsilon\geq 0\).
Proof. Since an HZ equilibrium exists when each individual purchases their cheapest best affordable bundle [4], and any such HZ equilibrium (after normalizing the minimum price to 0) satisfies the conditions 1-6 (in particular, it satisfies condition 6 since the cheapest best bundle will never buy positive-price, 0-utility goods), we conclude that an \(\varepsilon\)-approximate HZ Equilibrium exists even when \(\varepsilon=0\). ◻
Theorem 2. Finding an \(\varepsilon\)-\(\textit{RHZ}\) with restriction is PPAD-hard for some constant \(\varepsilon>0\).
We follow the same outline of proof as [10]. but modify the lemmas therein to obtain the hardness result for \(\varepsilon\) as a constant, instead of \(1/poly(n)\), for the restricted version.
Similar to [10], we reduce from the problem of finding a \(\kappa\)-approximate equilibrium for the threshold game \(H=(V,E)\). To make the proof self-contained, we repeat the setup of [10] here.
Definition 10 (Threshold game [17]). A threshold game is defined on a directed graph \(H=(V,E)\) and a threshold \(t\) (\(0<t<1\)). The vertices of the graph represent players with strategy space \(x_v\in [0,1]\). A strategy profile \(x=(x_u)_{u\in V}\in [0,1]^{|V|}\) is an \(\kappa\)-approximate equilibrium (\(\kappa<t<1-\kappa\)) if it satisfies \[\begin{align} x_v = \begin{cases} [0,\kappa] &\sum_{u\in N_v}x_u>t+\kappa\\ [1-\kappa,1] &\sum_{u\in N_v}x_u<t-\kappa\\ [0,1] &\sum_{u\in N_v}x_u\in [t-\kappa, t+\kappa]\\ \end{cases} \end{align}\] where \(N_v\) is the set of vertices with incoming edges \((u,v)\in E\) to vertex \(v\). Intuitively, each vertex needs to behave like an indicator of whether the incoming flows exceed a certain threshold, and can act arbitrarily near the threshold.
[17] showed that there exists a constant \(\kappa\) such that the problem of finding \(\kappa\)-approximate equilibrium in a threshold game is PPAD-hard, and the hardness already holds when in-degree and out-degree of each vertex is bounded by some constant. Therefore we assume \(H\) has bounded in-degree and out-degree. Additionally, the threshold is set to \(1/2\) in their reduction, so we will also set \(t=1/2\).
We use the same construction of an HZ market \(M_H\) as in [10], which is formally stated in Section 3. Let \((x,p)\) be an \(\varepsilon\)-\(\textit{RHZ}\) of this market \(M_H\), where we set \(\varepsilon= 1/m^{20}\). Let \(\alpha_i, \mu_i\) be the optimal solutions for the dual program 6 for each agent \(i\). Let \(val_p(i)\) denote the optimal value of both of these LPs using prices \(p\) from the \(\varepsilon\)-RHZ.
First we make the simple observation that the dummy goods must have price 0.
Lemma 19. \(p(G_D)=\bar{p}(G_D)=0\)
Proof. If any dummy good has positive price, no agent will buy it, so there is zero demand for the dummy good, contradicting that \((x,p)\) is an \(\varepsilon\)-\(\textit{RHZ}\). This also shows that any \(\varepsilon\)-equilibrium for this market that satisfies condition 1,2,4-6 automatically satisfies condition 3, that \(\min_j p_j=0\). ◻
Next we show that the prices of some goods in the market are bounded by some constants. This will be helpful for us to bound \(\alpha_i\) in the dual of individual optimization LP. (We will later show that actually all goods are bounded by some constants.) Let \(e=(u,v)\) unless indicated otherwise.
Lemma 20. \[\begin{align} p(G_e)&\leq 2+O(1/m^4)\\ p(G_{v,3})&\leq 5/2+O(1/m^7) \end{align}\]
**Proof.* First we observe that any good in \(G_e\) must have positive prices, i.e. \(p(G_e)>0\) since otherwise each agent \(A_{e,*}\) will buy at least \((1-\varepsilon)\) unit of \(G_e\). However, there are \(64m^5\) agents in \(A_{e,*}\) but only \(32m^5\) goods in \(G_e\), demand is greater than supply, a contradiction. Thus the prices of \(G_e\) is positive. This also implies that only agents with positive utility for them will be assigned these goods. Since all goods in \(G_e\) need to be sold, and can be sold only to agents in \(A_{e,*}, A_{e,2,\ell}, A_{e,3,\ell}, A_{e,4,\ell}\) who have positive utility for it, where each of them has a budget of \(1+\varepsilon\), therefore we have \[p(G_e)\leq \frac{(64m^5 + 50m)(1+\varepsilon)}{32m^5} = 2+O(1/m^4).\]*
Similarly, \(G_{v,3}\) have positive prices and therefore can only be sold to agents in \(A_v\) and \(A_{e,1}\) where \(e=(v,k)\) for some \(k\) (there can only be a constant number of such edges since the out-degree of each vertex is bounded). Thus by market clearance, we have \[p(G_{v,3})\leq \frac{(5m^{10} + \Theta(48m^3))(1+\varepsilon)}{2m^{10}} = 5/2 + O(1/m^7).\] ◻
We also have the following lower bounds for prices of \(G_e\) and \(G_{v,3}\).
Lemma 21 ([10], Lemma 3.13). \[\begin{align} &p(G_e)\geq 2(1-2\varepsilon)\\ &p(G_{v,3})\geq 5/3 \end{align}\]
Corollary 2. \(\forall e\in E, p(G_e)=2\pm O(1/m^4)\)
Lemma 22. Each agent \(i\) in \(M_H\) has optimal value \(val_p(i)\leq 0.9\). More precisely, \(val_p(A_v)<0.6\), \(val_p(A_{e,*})\leq 0.5+\varepsilon\), and \(val_p(A_e)\leq 0.8\).
Proof. Proof of Lemma 3.13 in [10] gives \(val_p(A_v)<0.6\) and \(val_p(A_{e,*})\leq 0.5+\varepsilon\). We verify the claim for \(A_e\) agents (adapted from proof of Lemma 3.14 in [10] for constant \(\varepsilon\)). Note that only \(G_e\) and \(G_{u,3}\) goods give them utility 1, and the other goods give them utility at most 1/2. But \(G_e\) and \(G_{u,3}\) are expensive as shown in Lemma 21 and the utility they can get from them (subject to budget 1 because we are looking at the LP, not their real budget) is at most \(\max\{1/2(1-2\varepsilon), 3/5\} = 0.6\) when \(\varepsilon\) is a sufficiently small constant. Thus \(val_p(A_e)\leq 0.6+0.4*0.5= 0.8\). ◻
Now we are ready to bound \(\alpha_i\) and \(\mu_i\) for any agent \(i\). (The bound is tighter than [10], Lemma 3.3 because we utilize the fact that the prices of all goods in the market are bounded by some constant.)
Lemma 23. \[\begin{align} &\mu_i\geq 0\\ & 1/20 \leq \alpha_i\leq 0.9 \end{align}\]
Proof. (Adapted from proof of Lemma 3.3 in [10]). We have \(\mu\geq 0\) because there exists a good \(\ell\) with \(p_\ell=0\) such as the dummy goods and the corresponding dual constraint ?? implies \(\mu\geq 0\). Then \(\alpha_i\leq \alpha_i+\mu_i=val_p(i)\leq 0.9\). Now, since every agent \(i\) has a utility 1 good, which is either \(G_{e}\) or \(G_{v,3}\) for some \(e\in E, v\in V\), and we know their minimum prices are at most 3 by Lemma 20. Thus by ?? , we have \(\alpha_i*3+\mu_i\geq 1\) and \(\alpha_i+\mu_i=val_p(i)\leq 0.9\), which yields \(\alpha_i\geq 1/20\). ◻
Lemma 24. For all groups of goods \(G_j\), \(\bar{p}(G_j)\leq p(G_j)+\Theta(1/m^9)\).
Proof. By way of contradiction, suppose there exists a good in \(G_j\) with price \(\bar{p}(G_j)\geq p(G_j)+\Theta(1/m^9)>0\). Then this good can only be assigned to agents with positive utility for it. We note that any good has at most \(\Theta(m^{10})\) agents who have positive utility for it. We also have for any such agent \(i\), \(\alpha_i\bar{p}(G_j)+\mu_i\geq u_{ij}\) and \(\alpha_i p(G_j)+\mu_i\geq u_{ij}\). By our assumption and the fact that \(\alpha_i\geq 1/20\) by Lemma 23, we know that this good is \(1/20*\Theta(1/m^9)\)-suboptimal. By Lemma 2, we conclude the total allocation of this good can be at most \(\Theta(m^{10})*\frac{2\varepsilon}{(1/20)\Theta(1/m^9)} = 40\varepsilon*\Theta(m^{19}) = \Theta(1/m)<1\) since \(\varepsilon=1/m^{20}\), a contradiction. ◻
Note that this bound on the maximum price of each group is weaker than Corollary 3.15 in [10], since we only assume \(\varepsilon\) is a constant rather than polynomially small in \(n\).
For simplicity of notation, let \(y_1,y_2,y_3\) denote the allocation of \(G_{v,1}, G_{v,2}, G_{v,3}\) to \(A_v\) respectively, \(u_1,u_2,u_3\) be the corresponding utilities, and \(q_1,q_2,q_3\) be the respective minimum prices of each group. Recall that \(u_1=\frac{1}{2m^2-1}, u_2=\frac{m^2+1}{4m^2-2}, u_3=1\).
Lemma 25. \[\begin{align} &y_1\geq m^{10}-O(m^3)\\ & y_2, y_3\geq 2m^{10}-O(m^3) \end{align}\]
Proof. (Adapted from proof of Claim 3.17 in [10], for constant \(\varepsilon\)). Let \(\alpha,\mu\) be an optimal solution to the dual LP for agents in \(A_v\).
Case 1: \(\mu\geq u_1/2=\Omega(1/m^2)\). Then any good that \(A_v\) has 0 utility for is \(\mu\)-suboptimal for them. Thus the total allocation of \(A_v\) to \(\overline{G_v}\) (i.e. not \(G_v\) goods) is bounded by \(5m^{10} * \frac{2\varepsilon}{\Omega(1/m^2)} = O(m^{12})\varepsilon<1\) since \(\varepsilon\leq 1/m^{20}\). Thus \(y_1+y_2+y_3\geq 5m^{10}-1\). Since \(y_1\leq |G_{v,1}|=m^{10}+S_v=m^{10}+\Theta(m^3)\) and \(y_2,y_3\leq 2m^{10}\), we have \(y_1\geq m^{10}-1\) and \(y_2,y_3\geq 2m^{10}-O(m^3)\).
Case 2: \(\mu < u_1/2\). Consider the dual of LP for \(A_v\) agents. For \(\ell\in [3]\), since \(\alpha q_\ell+\mu\geq u_\ell\geq u_1\), we have \(\alpha q_\ell\geq u_1/2\). By Lemma 23 \(\alpha<1\), thus \(q_\ell\geq \frac{u_1}{2\alpha}\geq \frac{u_1}{2}=\Omega(1/m^2)>0\). Thus \(G_{v,\ell}\) can only be allocated to positive utility agents, which are \(A_v\) and \(A_e\) agents where \(e=(u,v)\) or \(e=(v,k)\) for some \(u\) and \(k\). There are \(\Theta(m^3)\) such \(A_e\) agents since the in-degree or out-degree of \(H\) is bounded by a constant. Thus the total allocation of \(G_v\) to \(A_v\) is \(y_1+y_2+y_3\geq 5m^{10}+S_v-\Theta(m^3)\geq 5m^{10}-\Theta(m^3)\). Thus \(y_1\geq m^{10}-O(m^3)\) and \(y_2,y_3\geq 2m^{10}-O(m^3)\).
◻
We can also bound each agent’s payment. Note that by our definition of \(\textit{RHZ}\), all payment is toward positive-utility goods. For what follows, we use \(p_j\) to denote the price of an individual good \(j\), not the minimum price of the groups of goods that \(j\) belongs to.
Lemma 26. For any agent \(i\), \[\begin{align} \sum_{j\in [n]}p_j x_{ij} = \sum_{j\in [n], u_{ij}>0}p_j x_{ij}= 1\pm O(\varepsilon) \end{align}\]
Proof. By ?? , we have \[\begin{align} &\alpha_ip_j+\mu_i\geq u_{ij}\\ \implies & \sum_{j\in [n]}\alpha_ip_jx_{ij} +\sum_{j\in[n]}\mu_i x_{ij}\geq \sum_{j\in [n]}u_{ij}x_{ij} \geq val_p(i)-\varepsilon\\ \implies &\alpha_i\sum_{j\in [n]}p_jx_{ij}+\mu_i\geq \alpha_i+\mu_i-\varepsilon\\ \implies & \sum_{j\in [n]}p_j x_{ij}\geq 1-\frac{\varepsilon}{\alpha_i}\\ \end{align}\] Then using \(\alpha_i\geq 1/20\) in Lemma 23, we get \[\begin{align} \sum_{j\in [n]}p_j x_{ij}\geq 1-20\varepsilon. \end{align}\] Budget constraint gives the upper bound \(\sum_{j\in [n]}p_j x_{ij}\leq 1+\varepsilon\). ◻
Now we are ready to prove the following lemma.
Lemma 27. For all \(v\in V\), \[\begin{align} & 0\leq p(G_{v,1})\leq \frac{1}{m^2} + O\left(\frac{1}{m^6}\right)\\ & p(G_{v,2})=\frac{1+p(G_{v,1})}{2}\pm O\left(\frac{1}{m^7}\right)\\ & p(G_{v,3})=2-p(G_{v,1})\pm O\left(\frac{1}{m^7}\right) \end{align}\] and for any \(\ell\in [3]\), \(G_{v,\ell}\) is at most \(\delta\)-suboptimal for any agent in \(A_v\) for \(\delta=20\varepsilon\).
Proof. (Adapted from proof of Lemma 3.10 in [10]). First we note that if for any \(\ell\in [3]\), \(G_{v,\ell}\) is \(\delta\)-suboptimal for \(A_v\), then we can assign at most \(2\varepsilon/\delta\) per agent in \(A_v\) by Lemma 2. Since we have to assign \(y_\ell\geq m^{10}-O(m^3)\) in total by Lemma 25, we need \[\begin{align} &5m^{10}2\varepsilon/\delta\geq m^{10}-O(m^3)\implies \delta\leq 10\varepsilon+O(\varepsilon/m^7)<20\varepsilon. \end{align}\] for \(m\) large enough. Thus \(G_{v,\ell}\) cannot be \(20\varepsilon\)-suboptimal for \(A_v\) for any \(\ell\in [3]\). Let \(\delta=20\varepsilon\). This implies \[\label{ineq:32constraint-bdd} u_{\ell}\leq \alpha q_\ell +\mu \leq u_\ell+\delta, \forall \ell\in [3].\tag{8}\] Since utilities are designed so that \(u_2=(3u_1+u_3)/4\), it follows that \[\begin{align} &\alpha\left(\frac{3q_1+q_3}{4}\right)+\mu-\delta\leq u_2\leq \alpha q_2+\mu\leq u_2+\delta\leq \alpha\left(\frac{3q_1+q_3}{4}\right)+\mu+\delta\\ \implies & q_2=\left(\frac{3q_1+q_3}{4}\right) \pm O\left(\frac{\delta}{\alpha}\right)\\ \implies & q_2=\left(\frac{3q_1+q_3}{4}\right) \pm O(\varepsilon) \end{align}\] since \(\alpha\geq 1/20\) by Lemma 23. Now, we can use the total payment of agents in \(A_v\) to bound \(q_1,q_2, q_3\). We know that \(q_\ell\) is the minimum price of a good in \(G_{v,\ell}\), and that by Lemma 24, any good \(j\) in \(G_{v,\ell}\) has price \(p_j=q_\ell +O(1/m^9)\). On the other hand, the payment of each agent in \(A_v\) is \(1\pm O(\varepsilon)\) by Lemma 26. Thus we have \[\begin{align} &(q_1+O(1/m^9))y_1+(q_2+O(1/m^9))y_2 + (q_3+O(1/m^9))y_3 = 5m^{10}(1\pm O(\varepsilon))\\ \implies & (q_1+O(1/m^9))y_1+\left(\left(\frac{3q_1+q_3}{4}\right) \pm O(\varepsilon)+O(1/m^9)\right)y_2 + (q_3+O(1/m^9))y_3 = 5m^{10}(1\pm O(\varepsilon)). \end{align}\] By Lemma 25 and \(\varepsilon=1/m^{20}\), we conclude that \[\begin{align} &q_2=\frac{1+q_1}{2}\pm O\left(\frac{1}{m^7}\right)\\ & q_3=2-q_1\pm O\left(\frac{1}{m^7}\right)\label{eqn:q1q3}. \end{align}\tag{9}\] Now it remains to bound \(q_1\). We first observe that \(q_1<q_3\) since if not, then we have \[\begin{align} \alpha q_1+\mu\geq \alpha q_3+\mu\geq u_3=1. \end{align}\] Since \(u_1 = \Theta(1/m^2)\), \(G_{v,1}\) is \((1-\Theta(1/m^2))\)-suboptimal for \(A_v\). Thus by Lemma 2, the total allocation of \(G_{v,1}\) to \(A_v\) is \(y_1\leq 5m^{10}2\varepsilon/(1-\Theta(1/m^2))<1\), a contradiction to Lemma 25. Thus \(q_1< q_3\). By 8 , since \(q_1,q_3\geq 0\), we have \[\begin{align} &q_3*u_{1}\leq q_3(\alpha q_1 +\mu) \leq q_3(u_1+\delta) \\ &q_1*u_{3}\leq q_1(\alpha q_3 +\mu) \leq q_1(u_3+\delta)\\ &\implies\mu\leq \frac{u_1q_3-u_3q_1+q_3\delta}{q_3-q_1} =\frac{u_1q_3-u_3q_1+O(\delta)}{q_3-q_1}. \end{align}\] since \(q_3\leq 3\) by 9 . Note that the denominator is positive. Suppose \(q_1\geq 1/m^2+1/m^6\), then \(q_3\leq 2-1/m^2\) by 9 . Then \(u_1q_3-u_3q_1\leq -1/m^6\). Since \(\delta=20\varepsilon=O(1/m^{20})\), the numerator is negative. Thus \(\mu<0\), a contradiction to \(\mu\geq 0\) by Lemma 23. Thus \[q_1<1/m^2+1/m^6.\] ◻
Let \(x^{+}(G_j, A_k)\) denote the total amount of goods in group \(G_j\) that is assigned to agents in group \(A_k\) such that the assignment gives positive utility to the agents. The following lemma proves a stricter bound than Lemma 3.11 in [10] because of our restriction on the equilibrium.
Lemma 28. For any \(v\in V\),
If \(x^{+}(G_v, \overline{A_v})\geq S_v+1\), then \(p(G_{v,1})=1/m^2\pm O(1/m^9)\)
If \(x^{+}(G_v, \overline{A_v})\leq S_v-1\), then \(p(G_{v,1})=0\).
Proof. (Adapted from proof of Lemma 3.11 in [10]). By Lemma 27, we know that both \(G_{v,2}\) and \(G_{v,3}\) have positive prices, so no agent with 0 utility for them will be allocated these goods.
Case 1: \(x^{+}(G_v, \overline{A_v})\geq S_v+1\). This means the assignment of \(G_{v}\) to agents with positive utility outside of \(A_v\) is at least \(S_v+1\). Since there are \(5m^{10}+S_v\) goods in \(G_v\), we must allocate at most \(5m^{10}-1\) goods to \(A_v\), so there exists an agent in \(A_v\) who is allocated at least \(1/5m^{10}\) units of goods outside of \(G_v\). Let \(\alpha, \mu\) be an optimal solution to the dual of LP of this agent. Since this agent has 0 utility for these goods, they are \(\mu\)-suboptimal, which means \(1/5m^{10}\leq 2\varepsilon/\mu\), so \(\mu=O(m^{10}\varepsilon)\). By Lemma 27, 8 and 9 , we have \[\begin{align} &\alpha(q_1+q_3)+2\mu =u_1+u_3+ O(\delta)\nonumber\\ \implies & \alpha = \frac{u_1+u_3+O(\varepsilon)-2*O(m^{10}\varepsilon)}{q_1+q_3}\nonumber\\ \implies & \alpha = \frac{u_1+u_3}{2}(1\pm O(1/m^7))\label{eq:case1} \end{align}\tag{10}\] since \(\varepsilon= 1/m^{20}\). Again by 8 , we have \[\begin{align} q_1 &=\frac{u_1-\mu+O(\delta)}{\alpha}\\ &=\frac{u_1}{\alpha}+\frac{-O(m^{10}\varepsilon)+O(\varepsilon)}{\alpha}\\ &=\frac{u_1}{\alpha}\pm O(1/m^{10})\\ &=\frac{u_1}{\frac{u_1+u_3}{2}(1\pm O(1/m^7))}\pm O(1/m^{10})\text{ by \ref{eq:case1}}\\ &=1/m^2\pm O(1/m^9). \end{align}\]
Case 2: \(x^{+}(G_v, \overline{A_v})\leq S_v-1\). This means the assignment of \(G_{v}\) to agents with positive utility outside of \(A_v\) is at most \(S_v-1\). Since there are \(5m^{10}+S_v\) goods in \(G_v\), we must assign at least \(5m^{10}+1\) goods to \(A_v\) and agent with 0 utility outside of \(A_v\). Since there are at most \(5m^{10}\) agents in \(A_v\), there is at least one agent with 0 utility for goods in \(G_v\) who gets assigned some good in \(G_v\). This good cannot be \(G_{v,2},G_{v,3}\) since they have positive prices, so this agent must be assigned some good in \(G_{v,1}\) with price 0, so \(p(G_{v,1})=0\).
◻
Lemma 29. \[\begin{align} &x^{+}(G_u, A_e)=24m^3+12m\pm O(1)\\ &x^{+}(G_v, A_e)=24m^3+15m-6m^3p(G_{u,1})\pm O(1)\\ \end{align}\]
Proof. Like Lemma 15, the proof of Lemma 29 is nearly identical to the proof of Lemma 3.12 in [10]. The only modifications that need to be made are to use our bounds on the allocations and prices when they use theirs. We again provide a mapping from their results to ours below so that this substitution is easier.
| [10] | Here |
|---|---|
| Lemma 3.5 | Lemma 2 |
| Corollaries 3.6 + 3.15 | Lemmas 2 + 26 + 24 |
| Lemma 3.10 | Lemma 27 |
| Lemma 3.16 | Lemma 26 |
As before, if we choose \(\varepsilon = O(1/m^{20})\), then the fact that \(O(m^6\varepsilon) = O(1/m^{14})\) for us, while \(O(m^6\varepsilon) = O(1/\mathrm{poly}(n))\) for them, does not quantitatively affect the proof. ◻
Then the proof of Theorem 2 follows from Lemma 27, Lemma 28, and Lemma 29 as in [10]. We add the proof here for completion.
Proof. (Adapted from proof of Theorem 3.1 in [10]. The only change is we apply a tighter bound from Lemma 28 to get \(p(G_{v,1})=0\) for Case 1 instead.)
For any instance of the threshold game \(H=(V,E)\) where the in-degree and out-degree are bounded by some constant and the threshold is \(1/2\), we can set \(m=\lceil C/\kappa\rceil\) and create the HZ market \(M_H\) as described before. Let \((x,p)\) be an \(\varepsilon\)-\(\textit{RHZ}\) of \(M_H\) where \(\varepsilon=\frac{1}{m^{20}} = \frac{1}{{\lceil C/\kappa\rceil}^{20}}\). Let \(x_v=\min (1,m^2p(G_{v,1}))\in [0,1]\). Then we claim that \(x=(x_v)_{v\in V}\) is a \(\kappa\)-approximate equilibrium of \(H\).
Case 1: \(\sum_{u\in N_v}x_u>0.5+\kappa\). By definition of \(x_u\), we have \(x_u\leq m^2 p(G_{u,1})\). This implies \(p(G_{u,1})\geq x_u/m^2\implies \sum_{u\in N_v}p(G_{u,1})\geq \sum_{u\in N_v}x_u/m^2>(1/m^2)(0.5+\kappa)\). Then by Lemma 29, we have \[\begin{align} x^{+}(G_v, \overline{A_v})&\leq \text{out-deg}(v)\cdot (24m^3+12m+ O(1)) +\sum_{u\in N_v} (24m^3+15m-6m^3p(G_{u,1})+ O(1))\\ &= S_v+3m-6m^3\sum_{u\in N_v}p(G_{u,1})+O(1)\\ &\leq S_v+3m-6m^3(1/m^2)(0.5+\kappa)+O(1)\\ &= S_v-6m\kappa + O(1) <S_v-1. \end{align}\] since \(m\kappa \geq C\) for some large constant \(C\) and we can choose the \(C\) to be larger than the \(O(1)\) term. Then by Lemma 28, we have \(p(G_{v,1})=0\), which implies \(x_{v}=0\), as desired.
Case 2: \(\sum_{u\in N_v}x_u<0.5-\kappa\). By Lemma 27, we have \(p(G_{u,1})\leq 1/m^2+O(1/m^6)\). Thus \[\begin{align} &m^2p(G_{u,1})\leq 1+O(1/m^4)\\ &\implies x_u = \min(1,m^2p(G_{u,1})) \geq m^2p(G_{u,1})-O(1/m^4)\\ &\implies p(G_{u,1})\leq x_u/m^2+O(1/m^6)\\ &\implies \sum_{u\in N_v}p(G_{u,1})\leq \sum_{u\in N_v}x_u/m^2+O(1/m^6)<(1/m^2)(0.5-\kappa+O(1/m^4)) \end{align}\] by bounded in-degree. Then by Lemma 29, we have \[\begin{align} x^{+}(G_v, \overline{A_v})&\geq \text{out-deg}(v)\cdot (24m^3+12m- O(1)) +\sum_{u\in N_v}(24m^3+15m-6m^3p(G_{u,1})-O(1))\\ &= S_v+3m-6m^3\sum_{u\in N_v}p(G_{u,1})-O(1)\\ &\geq S_v+3m-6m^3(1/m^2)(0.5-\kappa+O(1/m^4))-O(1)\\ &= S_v+6m\kappa -O(1/m^3)- O(1) \geq S_v+C> S_v+1. \end{align}\] Thus by Lemma 28, \(p(G_{v,1})\geq 1/m^2-O(1/m^9)\), which means \(x_v\geq 1-O(1/m^7)\geq 1-\kappa\), as desired.
◻
Princeton University↩︎
Princeton University↩︎
Princeton University↩︎
Stanford University↩︎
Provided that each player chooses the cheapest bundle that gives them the same maximum utility↩︎
The \(\varepsilon\)-\(\mathrm{\small Gcircuit}\) problem can be reduced to finding an approximate fixed point of a given continuous map from \([0,1]^n\rightarrow[0,1]^n\), and thus is in PPAD.↩︎
The equilibrium concept \((\alpha,\beta)\)-approximate CEEI (or A-CEEI) was first proposed by [22] to solve the allocation problem of indivisible goods without money where each agent is given a fake budget of \(B_i\) (which can be unequal) and items are priced so that when each agent chooses their favorite integral bundle of items, market clears with a small clearing error \(\alpha\), and the inequality in agents’ budgets is bounded by \(\beta\). However, this is not to be confused with the approximate CEEI (or approximate HZ equilibrium) defined in our setting, where items are divisible and each agent has unit-demand (alternatively, the allocation can be thought of as bundles of probability shares of different indivisible items). We note that although our main result also connects the conjecture to the computational hardness of an approximate-CEEI (i.e. an approximate HZ), our fractional setting makes the reduction much more difficult as each item can now be allocated to many agents, each getting a tiny fraction and it is harder to reason about prices and allocations in any equilibrium.↩︎