| paper | Price of Anarchy in a Double-Sided Critical Distribution System |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finite buyer types \(B\) and seller types \(S\) with rational masses \(\mu_b,\nu_s\), per-agent Good supplies \(q_s\), demands \(d_b\), initial Rights \(r_b^0\), Right capacities, and fixed Good- and Right-bid/ask parameters, choose aggregate Good flows \(x_{bs}\ge0\) and non-self Right flows \(y_{ab}\ge0\), with \(y_{bb}=0\), maximizing \(G=\sum_{b\in B}\sum_{s\in S}x_{bs}\), subject to \(\sum_bx_{bs}\le\nu_sq_s\), \(\sum_sx_{bs}\le\mu_bd_b\), mass-scaled Right capacities, \(\mu_br_b^0-\sum_ay_{ba}+\sum_ay_{ab}\ge G_b\), \(\sum_ay_{ab}\le G_b\), and the average-price constraints \(\sum_sa_s^Gx_{bs}\le p_b^GG_b\) and \(\sum_aa_a^Ry_{ab}\le p_b^RH_b\), where \(G_b=\sum_sx_{bs}\) and \(H_b=\sum_ay_{ab}\).
A fixed one-market high-multiplicity double auction with buyer types \(b\) and seller types \(s\), masses \(\mu_b,\nu_s\), mass-scaled capacities, aggregate Good flows \(x_{bs}\), aggregate Right flows \(y_{ab}\), and an objective maximizing cleared Good under the paper's Right-coupling and average-price constraints.
The mirror is an exact quotient of a fixed bid profile and does not model the paper's evolving strategies, equilibrium, or Price of Anarchy; faithfully treating those may require histories as types and destroy the compression.
fatal: False
The mirror covers the divisible one-market maximum-clearing results in Theorems 1 and 2, with Theorem 2 as the strongest anchor. It leaves untouched the repeated-crisis dynamics, strategic equilibrium in Definition 3, reinforcement-learning approximation, frustration and Price of Anarchy, empirical results, and the indivisible branch of Theorem 1.
The strongest honest positive case is narrow but real: this paper supports a Class-A continuous mirror of its one-market clearing problem. Theorem 2 is my lead anchor, with Theorem 1 as a closely related companion. I would not claim a continuous theorem about the paper’s learned equilibria or empirical Price of Anarchy: those are not named computational results.
The appropriate regime is a crisis-distribution market with many hospitals, clinics, warehouses, or regional suppliers, but only a small number of recurring complete trader types. A buyer type includes everything relevant to clearing: its demand, money and Good holdings, initial Rights, desired quantities, and Good- and Right-bid parameters. A seller type includes its Good supply and asking price. Thus two hospitals belong to the same type only if the mechanism treats them identically in all these respects. If there are \(N\) traders but only \(\tau\) such profiles, with \(N\gg\tau\), the population can be represented by rational masses \(\mu_b\) and \(\nu_s\). Aggregate demand and supply are then mass-scaled quantities such as \(\mu_b d_b\) and \(\nu_s q_s\). This is a plausible setting for repeated cohorts of similarly sized hospitals and distributors, rather than for a seven-agent bespoke market.
The finite/high-multiplicity bridge is clean here. Clearing denominators in the masses produces a market with repeated clones of each type. Conversely, aggregating a finite repeated-type market gives the mass instance. Because the paper already makes Good divisible and Rights real-valued, splitting aggregate trades is not an artificial fractionalization of an indivisible outcome. The continuous object is the population distribution and its mass-weighted clearing capacities.
My lead problem is Continuous Crisdis Average-Bid Maximum Clearing, mirroring Theorem 2, which states: “Maximum clearing allocation with average bids can be found efficiently using a linear program.” This theorem is proved in the paper; the conference version gives a proof sketch and refers to the full version for details.
An instance has finite buyer types \(B\), seller types \(S\), rational masses \(\mu_b,\nu_s\), seller Good supplies \(q_s\) and asking prices \(a_s^G\), buyer Good demands \(d_b\) and maximum average prices \(p_b^G\), and analogous Right-selling and Right-buying data. Let \(x_{bs}\ge0\) be the aggregate Good transferred from seller type \(s\) to buyer type \(b\), and let \(y_{ab}\ge0\) be the aggregate Right transferred from buyer type \(a\) to buyer type \(b\), with \(y_{bb}=0\). Define
\[ g_b=\sum_{s\in S}x_{bs},\qquad h_b=\sum_{a\in B}y_{ab},\qquad \ell_b=\sum_{a\in B}y_{ba}. \]
The allocation must satisfy Good supply and demand,
\[ \sum_{b\in B}x_{bs}\le \nu_s q_s,\qquad g_b\le \mu_b d_b, \]
Right-selling and Right-buying capacities,
\[ \ell_b\le \mu_b r_b^{\mathrm{sell}},\qquad h_b\le \mu_b r_b^{\mathrm{buy}}, \]
and the Crisdis Right constraint. If \(r_b^0\) is the initial Right allocation per buyer of type \(b\), then
\[ \mu_b r_b^0-\ell_b+h_b\ge g_b, \qquad h_b\le g_b. \]
The first inequality says that a buyer must finish with at least as many Rights as Goods; the second encodes the paper’s condition that Rights are not bought without an equal amount of Good. For every buyer type \(b\), average-price feasibility is
\[ \sum_{s\in S} a_s^G x_{bs} \le p_b^G g_b \]
and
\[ \sum_{a\in B} a_a^R y_{ab} \le p_b^R h_b. \]
The question is to maximize total cleared Good,
\[ \max \sum_{b\in B} g_b. \]
A solution is the complete rational flow vector \((x,y)\) satisfying these constraints. This is a linear program with \(O(|B||S|+|B|^2)\) variables, hence plausibly solvable in time polynomial in the number of types and the input bit length. Its expected classification is Class A.
This is recognizably the authors’ problem. The paper’s average-price mechanism already defines clearing by linear average-price inequalities; the mirror only replaces repeated individual traders by mass-weighted type capacities. It does not replace strategic bidding by a planner’s unrelated objective, nor does it change the market’s Good-Right coupling. The fact that the original paper’s Good is divisible is helpful, but is not itself the continuization claim.
The companion anchor is Continuous Crisdis Absolute Maximum Clearing, mirroring Theorem 1, which states: “Maximum clearing allocation can be found efficiently using a reduction to the Max Flow problem.” This is also proved in the paper, with details deferred to the full version.
The instance is the same, except that Good and Right trades are allowed only on type-level compatibility edges:
\[ x_{bs}=0 \quad\text{unless}\quad a_s^G\le p_b^G, \]
and
\[ y_{ab}=0 \quad\text{unless}\quad a_a^R\le p_b^R \quad\text{and}\quad a\ne b. \]
The question is again to maximize \(\sum_b g_b\), subject to the supply, demand, Right, and equal-quantity constraints above. The type-level capacities are simply the original vertex weights multiplied by type mass. Thus the paper’s combined max-flow construction becomes a network on type vertices with rational capacities. Its expected classification is also Class A, with a polynomial-time max-flow algorithm in \(|B|+|S|\) and the encoding length.
I would claim only the divisible-Good branch directly. Theorem 1’s additional statement for indivisible Good would require a separate repeated-inventory and integrality argument; it should not be smuggled into the continuous claim.
These mirrors cover the paper’s two named theoretical results and deliberately exclude its reinforcement-learning algorithm, NashConv experiments, repeated-crisis dynamics, and empirical PoA curves. Natural follow-up problems are whether contested-garment Rights can be computed directly from type masses; whether a finite-horizon typed crisis admits an efficiently computable optimal policy; how to define a non-vacuous type-level equilibrium; and whether the resulting continuous frustration converges to finite-clone PoA with a rounding guarantee.
The weakest point is that the paper’s main scientific object is arguably the strategic repeated crisis, whereas these mirrors freeze the bids and study only the clearing subproblem. If every hospital has an idiosyncratic bid, ask, budget, or state, then \(\tau\) approaches \(N\) and the high-multiplicity benefit disappears. There is also a proof obligation that aggregate average-price trades can always be disaggregated into per-agent trades without violating individual constraints. Identical types and divisible quantities make that plausible by proportional splitting, but it should be proved. So this is not a mirror of the whole paper; it is a strong, author-recognizable continuous mirror of its two explicit polynomial clearing results, with Theorem 2 as the best anchor.
The strongest negative case is that the proponent’s two anchors are valid aggregations, but not worthwhile continuizations of this paper’s computational object.
Theorem 1 and Theorem 2 concern a fixed, already-realized one-market bid profile. Once the offers, prices, supplies, demands, and Rights are fixed, traders enter only as capacities, weights, and compatibility edges. Replacing identical vertices by one vertex with multiplied capacity is therefore an exact quotient of an ordinary flow or LP instance. It applies equally to ten traders and to a billion traders; it does not identify a population-dependent computational phenomenon. The “continuous society” is functioning only as compressed input notation.
The average-price mirror is especially vulnerable on this point. Theorem 2 does not compute strategic behaviour, equilibrium, or even the offers themselves. It computes the best allocation after the strategic part has already been supplied. In the paper, however, offers are generated by policies \(\pi_s\) and \(\pi_b\) that depend on individual holdings, demands, observed offers, money, Good, Rights, and previous markets. Those quantities are not merely attributes of a static buyer or seller type; they are evolving states and actions.
A faithful continuization of the strategic model must therefore put histories, inventories, policies, and observations into the type description. Then the type space is generally not a fixed finite set: distinct histories or policies create distinct types, and in the paper’s continuously sampled experimental domain the number of distinct types is almost surely the number of traders. If instead one imposes anonymous Markov policies and aggregates all same-looking traders, one obtains a new price-taking mean-field market, not the paper’s game. Its equilibrium and its Price of Anarchy need not correspond to Definition 3 or \((\mathrm{PoA})\).
The claimed aggregate LP also relies on a stronger assumption than the proponent acknowledges. Proportional splitting disaggregates a type-level solution only when agents are identical in every relevant current state and face anonymous constraints. If agents merely share a bid or an asking price while differing in money, inventories, Rights, demands, or continuation values, a pooled average-price inequality can be feasible even though no individual allocation is. Restoring complete types repairs exactness, but then the hoped-for multiplicity compression disappears. The same issue affects the absolute-price max-flow mirror of Theorem 1.
There is a further continuum degeneration in the strategic version. Under a nonatomic population, one trader’s deviation has zero effect on aggregate supply, Rights, prices, or clearing. The unilateral-deviation condition defining the paper’s equilibrium consequently becomes a price-taking condition. To preserve the strategic effect of an individual deviation, one must retain atomic agents or explicitly model finite clone blocks; that gives an atomic large-market model rather than the proposed continuum.
This does not yield an airtight universal rejection. A deliberately constructed market of many genuinely identical hospitals and suppliers, with bids fixed exogenously for one clearing round, does admit the proposed mass-scaled flow and LP. Theorem 2 is therefore a legitimate, if modest, Class-A high-multiplicity mirror. The honest negative conclusion is narrower: the paper offers no strong continuous mirror of its main contribution—the repeated strategic crisis and its PoA—and its two named clearing results support only a routine weighted-flow reformulation. Claiming that no worthwhile mirror exists in any scenario would overstate the case.
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.