| paper | One-Sided Matching Markets with Endowments: Equilibria and Algorithms |
| authors | — |
| venue | AAMAS 2022 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 23
statement extracted from the paper’s text layer
Given rational \(\mu\in\mathbb{Q}^{\tau}\), type utilities \(u_t\in\{0,1\}^{G}\), type endowments \(e_t\), aggregate supplies \(s_g=\sum_t\mu_t e_{tg}\), and rational \(\epsilon\in(0,1)\), compute prices \(p\), type budgets \(b_t\), and unit bundles \(x_t\) such that \(\sum_t\mu_t x_{tg}=s_g\), each \(x_t\) is a cheapest utility-maximizing bundle at budget \(b_t\), and \( (1-\epsilon)p\cdot e_t\le b_t\le\epsilon+p\cdot e_t \) for every type \(t\).
A finite-type Arrow–Debreu/HZ market with mass \(\mu_t\), type utility \(u_t\), type endowment \(e_t\), aggregate good supply \(s\), type budgets \(b_t\), per-unit allocations \(x_t\), common prices \(p\), weighted market clearing, and typewise best responses.
Replacing \(n\) named goods and endowment vectors by finitely many categories \(G\) with capacities \(s_g\) requires a new rational-capacity lifting of the price-raising and flow proof, so Theorem 23 alone does not establish runtime polynomial in \(\tau\) rather than the clone count.
fatal: False
The mirror directly covers Theorem 23 and poses type-weighted analogues of Theorem 24 and Proposition 13; it leaves arbitrary cardinal-utility ADHZ, exact nonexistence results, and standalone equilibrium properties as separate questions.
The strongest honest case is a finite-type, high-multiplicity mirror of the paper’s dichotomous or bi-valued market—not a claim that every ADHZ instance becomes continuous or tractable.
The natural regime is a large school district or university housing market. There are many students or residents, but only a moderate number of complete types. A type \(t\) records both the cardinal utility vector \(u_t\) over good categories and the initial endowment vector \(e_t\). Thus two agents are the same type exactly when the paper’s problem treats them identically. Let \(\mu_t\) be the fraction of the population of type \(t\), and let \(G\) be a finite set of good categories with aggregate supply \(s_g=\sum_t\mu_t e_{tg}\). A realistic regime might have millions of agents but only tens or hundreds of \((u_t,e_t)\)-types and good categories.
The fractional allocation in the paper is not itself the continuization; it is already part of HZ and ADHZ. The new continuous object is the population distribution \(\mu\). For each type, \(x_{tg}\) means the bundle received by one unit of type-\(t\) mass, while \(\mu_t x_{tg}\) is the aggregate mass assigned to good \(g\).
My lead anchor is Theorem 23, proved in this paper. It states that an \(\epsilon\)-approximate ADHZ equilibrium for rational \(\epsilon\in(0,1)\) under dichotomous utilities can be computed in time polynomial in \(1/\epsilon\) and \(n\), which the authors call a fully polynomial-time approximation scheme.
The corresponding problem should be called Continuum \(\epsilon\)-ADHZ Equilibrium. Its input is a finite rational type distribution \(\mu\), rational endowments \(e_t\), dichotomous utilities \(u_t\in\{0,1\}^{G}\), and rational \(\epsilon\in(0,1)\). The task is to output type-level allocations \(x_t\), prices \(p\), and type budgets \(b_t\) satisfying:
\(x_t\) is a unit bundle, so \(\sum_g x_{tg}=1\);
the market clears in aggregate, so \(\sum_t\mu_t x_{tg}=s_g\) for every good \(g\);
\(x_t\) is a cheapest utility-maximizing bundle for type \(t\) at budget \(b_t\), namely it maximizes \(u_t\cdot y\) over unit bundles with \(p\cdot y\le b_t\), and among bundles attaining that utility it minimizes price;
and the approximate endowment-budget relation holds for every type:
\((1-\epsilon)p\cdot e_t\le b_t\le \epsilon+p\cdot e_t\).
This is recognizably the authors’ problem. It retains endowments, prices, budget feasibility, cheapest utility-maximizing bundles, and exact fractional market clearing. Only the sums over named agents have become weighted sums over types.
I expect this problem to be tractable, with running time polynomial in \(\tau=|T|\), \(|G|\), the input bit length, and \(1/\epsilon\), independent of the expanded population size. The proof of Theorem 23 proceeds through Theorem 21, price classes, and max-flow computations. In the type-compressed version, repeated agents become capacity-\(\mu_t\) nodes and repeated goods become capacity-\(s_g\) nodes. The relevant matching, min-cut, and flow computations remain polynomial with rational capacities. The price-raising process should depend on the number of distinct goods or price classes, not on the number of represented individuals.
This also respects the paper’s own reason for introducing approximation. Proposition 12, proved here, gives a dichotomous ADHZ market with no exact equilibrium. Its five-agent example can simply be represented by five positive-mass types, so exact continuum ADHZ equilibrium is not automatically rescued by aggregation. The continuous question therefore quite properly uses the paper’s \(\epsilon\)-approximate notion. Theorems 15, 16, and 19 suggest that the resulting type-level solution retains approximate individual rationality, equal-type envy-freeness, approximate weak-core stability, and existence.
A second, genuinely distinct anchor is Theorem 24, also proved here. It gives a rational convex program for HZ equilibrium under dichotomous utilities and shows that its optimal solutions correspond to HZ equilibria.
Its continuous counterpart is Type-Compressed HZ-RCP. Given rational masses \(\mu_t\), good supplies \(s_g\), and dichotomous utilities \(u_t\), let \(z_{tg}\) be the total mass of type \(t\) assigned to good \(g\). Solve
\[ \max_{z\ge0} \sum_{t:\mu_t>0} \mu_t\log\left( \frac{1}{\mu_t}\sum_g u_{tg}z_{tg} \right) \]
subject to \(\sum_g z_{tg}\le\mu_t\) for every type \(t\), and \(\sum_t z_{tg}\le s_g\) for every good \(g\). An optimal solution is extended to a full fractional matching, and its dual good variables are returned as equilibrium prices.
This is not merely a fractional-outcome reformulation. The coefficients \(\mu_t\) are the population itself, and the program has no individual-agent list. The KKT argument in Theorem 24 should carry over to these weighted constraints. I therefore expect an exact rational convex-program formulation and polynomial-time solvability for this dichotomous type-compressed problem. Further questions include whether the rational denominator guarantees remain polynomial in the encoding of \(\mu\), and whether a comparable convex program exists for ADHZ with endowments rather than for HZ alone.
The paper’s only useful hardness-side anchor is Proposition 13, proved here. It reduces HZ to ADHZ by giving every agent an equal share of every good and shows that equilibria correspond after rescaling prices. The paper itself cites the PPAD-completeness of computing HZ equilibria from [10] and [35]; that hardness is not proved in this paper.
The corresponding boundary problem is Equal-Endowment Continuum ADHZ: every type has the same endowment \(e_t=s\), prices are normalized by \(p\cdot s=1\), and the task is to compute an exact equilibrium satisfying the HZ best-response and market-clearing conditions. In the unrestricted type-support regime, I expect hardness to transfer from HZ. This is a Class B mirror: the continuous population representation does not destroy combinatorics encoded in the utility matrix over goods. It is not evidence of continuum-specific hardness, and it does not show hardness when \(\tau\) is fixed or very small.
The weakest point is that the weighted compression is not proved in the paper. Theorem 23’s algorithm is stated for an explicitly listed population, and one must still establish carefully that every step—especially the price-raising and vertex-cover stages—admits the required rational-capacity version. The scenario can also fail if students own genuinely idiosyncratic named seats or have individual cardinal utilities; then \(\tau\) and the number of goods may be close to the population size, and the mirror loses its high-multiplicity force.
Subject to that limitation, the positive case is strong: the paper’s equilibrium problem has a natural population-level input, a credible school-choice or housing regime with \(N\gg\tau\), a precise \(\epsilon\)-ADHZ computational question, and a plausible polynomial-time continuum analogue anchored directly in Theorem 23. Theorem 24 supplies an independent convex-program formulation, while Proposition 13 identifies the honest boundary where hardness survives.
The strongest negative is a modelling objection, but it does not survive the proponent’s best repair.
In the paper’s actual ADHZ model, \(G\) is a set of named goods with \(|A|=|G|=n\), and an agent’s endowment is a vector over those named goods. In a housing interpretation, two students who prefer the same room types but initially own different rooms are not the same type: their endowment vectors differ. Thus, if named goods are retained, a population of \(N\) agents still comes with \(N\) goods and \(N\)-dimensional endowment vectors. The claimed regime \(N\gg\tau\) does not yield a fixed finite market description.
The proponent’s formulation avoids this by replacing named rooms or seats with good categories of aggregate supply \(s_g\). That is plausible, but it is not merely continuizing the population. It also changes the market from one unit of each named good and a fractional perfect matching into a capacitated exchange market with repeated goods and category-level endowments. Theorem 23 does not establish that its vertex-cover, price-raising, and flow arguments remain polynomial in the number of types and categories rather than in the expanded multiplicities. Rational capacities may well permit such a lift, but that is a new theorem, not a consequence of the paper’s FPTAS.
The same objection weakens Theorem 24 as an independent anchor. The proposed weighted program is essentially the clone-expansion identity: if \(\mu_t=a_t/D\), it corresponds to repeating type \(t\) \(a_t\) times and supplying \(D s_g\) copies of each category. That is mathematically legitimate, but it is a weighted-capacity reformulation of the HZ program, not a population-level result about ADHZ with endowments. A separate proof is needed that its dual variables still produce the required typewise budget relations and equilibrium prices. The paper itself supplies no such proof.
Proposition 13 is weaker still. It is a reduction between HZ and ADHZ, not a complexity theorem, and the PPAD-hardness cited by the paper belongs to earlier work. Its hard HZ instances may use essentially one utility vector per agent. Then \(\tau\) grows with the population, so they do not demonstrate hardness in the high-multiplicity regime. Conversely, restricting to small \(\tau\) removes the only supplied hardness transfer. The proposed “boundary problem” is therefore a reasonable open parameterized question, but not evidence that the paper already supports a continuum hardness mirror.
That is the best negative case: the literal model has no robust fixed-type population limit, while the repaired model is a new capacitated market whose algorithmic claims remain to be proved. But I cannot honestly push this to the requested universal conclusion. Repeated school seats, room categories, or cohort-level endowments are natural high-multiplicity scenarios; weighted flows and the weighted HZ convex program are technically credible; and none of the programme’s permitted objections—identity dependence, vacuity, or prior continuous completion—applies. Theorem 23’s repaired mirror therefore survives. The negative verdict should be a demand for precise re-modelling and a lifting proof, not a claim that no worthwhile continuous mirror exists.
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.