| paper | Computing Competitive Equilibria with Mixed Manna |
| authors | J. Garg, Patricia C. McGlaughlin |
| venue | ATAL 2020 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Computing one exact equilibrium is polynomial-time solvable for every fixed \(m\), in \(\tau^{O(m)}\operatorname{poly}(L)\) time. Computing the specified representation of all equilibria is polynomial-time solvable for \(m=1,2\); for every fixed \(m\ge3\), that representation need not exist because equilibrium prices can form a continuum. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given \(m\) item classes with rational per-capita supplies \(q_j\), a finite set \(T\) of complete linear-utility types, and rational masses \(\mu_t\) summing to \(1\), compute a competitive equilibrium for a negative mixed-manna market with type-level allocation masses \(z_{tj}\), \(\sum_t z_{tj}=q_j\), representative bundles \(a_{tj}=z_{tj}/\mu_t\), prices \(p_j\), per-capita virtual budget \(-1\), and conditions \(\sum_j p_j a_{tj}=-1\) and \(a_t\in\arg\max_{y\ge0}\{\sum_j u_{tj}y_j:\sum_j p_jy_j\le-1\}\) for every \(\mu_t>0\). For fixed \(m\), determine whether one equilibrium, or a finite cell-and-polytope representation of all equilibria, can be computed in time polynomial in \(\tau=|T|\) and the input encoding length.
A nonatomic mixed-manna market with finite complete utility types \(T\), masses \(\mu\), per-capita supplies \(q\), per-capita virtual budgets \(-1\), type-level allocation variables \(z\), representative bundles \(a_t=z_t/\mu_t\), and prices \(p\); the computational objective is to compute a competitive equilibrium, with fixed \(m\) as the tractability parameter.
The mirror may add no computational mechanism beyond replacing repeated agents by mass capacities, making it a succinct high-multiplicity compression rather than a new continuum phenomenon; this limits novelty but does not invalidate the well-posed question.
fatal: False
It mirrors Theorem 3.2's algorithmic branches over positive, null, and fixed-\(m\) or fixed-\(n\) mixed-manna markets, with the strongest formulation using fixed \(m\) and variable type count \(\tau\). It does not resolve the unrestricted negative case or separately mirror the paper's structural lemmas and fairness guarantees.
The strongest positive case is the negative-instance branch of the paper’s Theorem 3.2, proved in this paper. The theorem states in full:
If a mixed-manna instance is positive or null, its unique competitive equilibrium in utilities can be computed in polynomial time. If it is negative, all competitive equilibria can be computed in polynomial time when either the number of agents or the number of items is constant.
The paper contains no named NP-hardness result; indeed, it explicitly leaves the unrestricted negative case open. Thus this is an algorithmic, Class-A mirror rather than a hardness-dissolution test.
My lead mirror is Continuous Mixed-Manna Competitive-Equilibrium Enumeration.
Take a fixed set \(M\) of \(m\) item classes, with rational per-capita supplies \(q_j\). The society has a finite set \(T\) of complete utility types. A type \(t\) consists of its entire linear utility vector \(u_t=(u_{tj})_{j\in M}\), together with any entitlement information if such information is part of the instance. The society is a rational distribution \(\mu\), where \(\mu_t\) is the mass of type \(t\), \(\sum_t\mu_t=1\). The intended regime is a very large nonatomic population, perhaps millions of workers or platform users, belonging to a modest number \(\tau=|T|\) of recurring preference/contract cohorts.
Let \(z_{tj}\) be the total amount of item \(j\) assigned to type \(t\), so
\[ \sum_{t\in T} z_{tj}=q_j. \]
For \(\mu_t>0\), the representative bundle of type \(t\) is
\[ a_{tj}=\frac{z_{tj}}{\mu_t}. \]
In the negative regime, every unit of population has virtual budget \(-1\), so type \(t\) has aggregate budget \(-\mu_t\). A continuous competitive equilibrium is a price vector \(p\) and allocation \(z\) such that, for every type \(t\),
\[ \sum_{j\in M}p_j a_{tj}=-1 \]
and \(a_t\) solves
\[ \max_{y\ge 0}\ \sum_{j\in M}u_{tj}y_j \qquad\text{subject to}\qquad \sum_{j\in M}p_jy_j\le -1. \]
The requested output is a complete exact description of all such equilibria, represented cell-by-cell: each feasible price cell, its equilibrium price vector, and the corresponding allocation polytope. A weaker version asks only for one equilibrium.
This is genuinely a population continuization. The items remain the paper’s divisible mixed manna; what becomes continuous is the society assigning and receiving it. A finite instance with \(n_t\) agents of type \(t\) maps to \(\mu_t=n_t/n\). Conversely, a rational distribution can be expanded into a high-multiplicity finite market. The per-capita supplies \(q_j\) make the market scale explicit; the paper’s unit-supply convention is recovered by choosing the corresponding normalized \(q_j\).
The mirror is particularly plausible for the negative branch. The paper’s algorithm does not use agent names: it compares utility-per-price ratios, constructs the utility-per-buck graph, determines prices within connected components, and then solves a flow problem. In the continuous version, duplicate agents collapse into one type vertex. The flow capacities become \(\mu_t\) for type budgets, \(-p_jq_j\) for bad supplies, and \(p_jq_j\) for good supplies. The paper’s price arrangement becomes the arrangement of
\[ p_j=0 \]
and
\[ u_{tj}p_{j'}-u_{tj'}p_j=0 \]
over types \(t\) and item pairs \(j,j'\). With \(m\) fixed, there are \(O(\tau m^2)\) hyperplanes in an \(m\)-dimensional space, hence polynomially many cells in \(\tau\). Each cell fixes every type’s maximum-bang-per-buck goods, minimum-pain-per-buck bads, and the relevant flow network. This strongly suggests an exact algorithm polynomial in \(\tau\) and the input encoding length for fixed \(m\), with the same XP-in-\(m\) flavour as the paper’s \(O((nm^2)^m)\) enumeration.
The authors should recognize this as their problem rather than a tractable caricature. It preserves linear utilities, divisible goods and bads, virtual budgets, individual optimality, market clearing, negative instances, and the non-convex, potentially disconnected equilibrium set. The only replacement is that repeated identical utility rows are represented by their mass. That is precisely the high-multiplicity interpretation of their finite model, not an objection to it. In the positive branch, the finite Nash-product objective would naturally become the weighted continuum objective
\[ \sum_{t\in T}\mu_t\log u_t, \]
the logarithm of a weighted geometric mean, which is also the expected high-multiplicity limit.
The expected classification is therefore Class A for fixed \(m\): the continuous negative-instance problem should inherit the paper’s cell-decomposition and max-flow method, now with type masses. The unrestricted-\(m\) problem remains open. Further questions include whether the dependence on \(m\) can be improved from XP to FPT, whether an uncountable type space admits an oracle or convex-analytic formulation, how equilibrium selection should be performed when many equilibria remain, and whether heterogeneous entitlements or separable piecewise-linear concave utilities preserve the reduction.
The weakest point is that this mirror may look algorithmically close to a weighted restatement of the paper’s fixed-item algorithm. That limits the claim of conceptual novelty. But it does not make the question illegitimate: it asks for the exact high-multiplicity competitive-equilibrium problem, with complexity measured in the number of distinct types rather than named agents, and it retains the paper’s genuinely difficult negative-market geometry.
The only eligible anchor is Theorem 3.2, and it is weaker as a basis for continuization than the proponent suggests. It gives a polynomial algorithm only when the number of agents or items is constant; it gives no unrestricted complexity classification or hardness result.
More importantly, the proposed negative-instance mirror is an exact quotient of the finite algorithm, not a population-continuum problem in which mass changes the computational object. If several agents share utility type \(t\), averaging their equilibrium bundles gives a representative bundle \(a_t\). Because utilities, budgets, and feasibility are linear, this averaging is reversible: any representative allocation can be distributed identically among the clones. Thus the continuous and finite high-multiplicity equilibria correspond exactly.
The algorithm confirms how little the population axis contributes. The price cells are determined by
\[ p_j=0 \quad\text{and}\quad u_{tj}p_{j'}-u_{tj'}p_j=0, \]
so their combinatorics depend only on the utility types and items. The masses \(\mu_t\) merely replace repeated unit capacities by aggregate capacities. They do not create a new separation problem, convex formulation, pricing phenomenon, or source of tractability. With fixed \(m\), the mirror is simply the paper’s existing fixed-item algorithm after duplicate rows have been compressed. With fixed \(\tau\), it is the same observation applied to the paper’s fixed-agent algorithm, replacing \(n\) by the number of distinct rows.
The stronger unrestricted mirror does not rescue the case. If \(m\) and \(\tau\) are both variable, every finite instance embeds by giving each agent its own type, so the continuous notation adds no computational leverage. If \(\tau\) is fixed, the resulting polynomiality is already explained by the paper’s constant-agent proof and measures succinct input encoding rather than a new continuous-population mechanism. The positive and null branches behave identically: the weighted Nash objective and feasibility LP are just the finite programs with repeated rows aggregated.
There is also a gap between the claim and the stated theorem. The paper’s cell enumeration does not by itself establish a polynomial-size exact representation of every equilibrium polytope, and “compute all equilibria” may require outputting a positive-dimensional family. A one-equilibrium version avoids that issue but is correspondingly just a weighted flow computation.
This is the strongest negative case: the mirror is mathematically sound but scientifically thin. It compresses repeated agents; it does not make population mass an active computational object. However, the objection is not airtight under ChoCo’s stated rules. High-multiplicity fair division is explicitly admissible, and the fixed-\(\tau\), variable-\(m\) formulation is a legitimate succinct-input problem with a plausible polynomial algorithm. If any exact high-multiplicity computational question counts as worthwhile, Theorem 3.2 survives; the honest negative verdict can establish only “thin and derivative,” not “no worthwhile mirror in any scenario.”
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.