| paper | d4-conf-atal-2018-0348 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Nonexistence can occupy an open set of positive Lebesgue measure. For fixed \(m=3\), equilibrium existence and exact equilibrium construction are polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.1
Fix \(J=\{1,2,3\}\), rational per-capita supplies \(q_j\in(0,1]\), type masses \(\mu_t>0\) summing to \(1\), and complete monotonically increasing rankings \(\succ_t\) over \(2^J\). For almost every budget vector \(b\in\mathbb{R}_{>0}^{|T|}\), can one compute positive prices \(p_j\) and assignment masses \(x_{t,S}\geq 0\) such that \(\sum_S x_{t,S}=\mu_t\), \(\sum_{t,S:j\in S}x_{t,S}=q_j\), and \(x_{t,S}>0\) only when \(S\) is a most-preferred bundle among those satisfying \(\sum_{j\in S}p_j\leq b_t\)?
A nonatomic Fisher market with three indivisible good categories and per-capita supplies \(q_j\). Each type \(t\) has mass \(\mu_t\), a shared monotone bundle ranking, and a per-person budget \(b_t\); variables \(x_{t,S}\) assign mass to integral bundles \(S\), while prices clear supplies and make every assigned bundle affordable and utility maximizing.
Covers the constructive three-good CE result after replacing each finite good with scalable category supply and individuals with mass types; leaves the paper’s fairness analysis, other goods and chores results, and the picking-sequence game as a strategic object untouched.
The strongest positive case is a three-good high-multiplicity Fisher market. The paper’s closest named computational anchor is Theorem 5.1, proved in this paper. It says that with three goods, for almost every income vector and every profile of monotonically increasing preferences, a competitive equilibrium exists and can be found by Algorithm 1. The paper notes that the existence result was known earlier; its contribution here is a simpler constructive proof and algorithm. This is an algorithmic anchor, though the paper does not give a running-time classification such as membership in P or NP-hardness. [Theorem 5.1](https://arxiv.org/html/1705.04212)
Here is the mirror I would put to a prover: Three-Good Mass CE Search. There are three good categories \(J=\{1,2,3\}\), with per-capita supplies \(q_j\), and a finite support \(T\) of \(\tau\) consumer types. Type \(t\) has population mass \(\mu_t\), where \(\sum_t\mu_t=1\), a monotonically increasing complete ranking \(\succ_t\) over the eight bundles \(S\subseteq J\), and a per-person budget \(b_t>0\). A type is complete in the high-multiplicity sense: its members share both the ranking and the budget.
The task is to decide whether there are positive prices \(p_j\) and masses \(x_{t,S}\geq 0\) such that \(\sum_S x_{t,S}=\mu_t\) for each type, \(\sum_{t,S:j\in S}x_{t,S}=q_j\) for each good, and every bundle assigned positive mass to type \(t\) is a most-preferred bundle that type can afford. A solution is the prices and assignment masses; each person receives an integral bundle. The \(x_{t,S}\) are fractions of a cohort assigned to different bundles, not fractional bundles for individuals. The exact search problem takes rational \(\mu,q,b\) as input and asks for an equilibrium or a “no” answer. Its associated generic-income question is whether, for fixed \(\mu,q\), and preference types, equilibria exist for Lebesgue-almost every budget vector \(b\in\mathbb{R}_{>0}^{\tau}\).
A plausible regime is a large university cohort choosing among seats in three course categories, with capacities scaling with enrollment. Many students share the same bundle ranking and credit budget, so \(N\) students can be represented by \(\tau\ll N\) types and their masses. A seat remains indivisible for each student; the capacities and cohort sizes scale together. This is the paper’s CE demand-and-price question applied to a population with repeated types.
I expect the fixed-three-good search problem to be tractable. There are only eight bundles per type, and affordability changes across the three-dimensional price space at boundaries \(p(S)=b_t\). These boundaries form an arrangement of \(O(\tau)\) hyperplanes. Within each cell or face, every type’s affordable and demanded bundles are fixed; whether the type masses can clear supply is then a linear feasibility problem in the \(x_{t,S}\). This suggests an exact algorithm polynomial in \(\tau\) and the input bit length \(L\) for fixed \(m=3\). With \(m\) variable, the corresponding question is complexity in \(m,\tau,L\). This is a proposed route and classification, not a result proved by the paper.
The mirror covers the constructive, three-good CE result, not the paper’s fairness-property analysis or its picking-sequence game as a strategic object. It does not continuize the outcome: only the population is continuous. A useful next question is whether the almost-all-incomes guarantee survives for arbitrary rational type masses and per-capita supplies. Another is where it breaks as \(m\) grows, including whether the paper’s four-good nonexistence examples persist in the scaled-supply setting. Those are existence boundaries, not computational hardness results, so I would not present them as hardness anchors.
My weakest point is that Theorem 5.1 concerns three indivisible goods in a finite market, while the mirror scales each good category’s supply with the population. That co-modification is needed to give a large cohort a meaningful allocation, but it means the theorem does not transfer directly. Splitting a type’s mass across bundles is also feasible only when those bundles are all demanded at the same prices. The paper’s algorithm has no stated complexity bound either. The case for the mirror is that its core question remains recognizable—find prices and a market-clearing allocation of individually integral bundles—and the extra work is precisely to determine what the finite result becomes in a genuine high-multiplicity regime.
The proponent has one real anchor: Theorem 5.1 gives an algorithm for finding a CE with three goods. But it is a finite-market existence result for three distinct indivisible items, not a complexity result with a specified input representation or running time. That makes it a thin foundation for a computational mirror.
Keeping the three original items while taking population mass to a continuum makes their supply vanish per capita; allocations of those items then disappear from the population-level description. The proponent’s stronger repair—scale each good’s supply with the population—avoids that degeneration, but changes the market into one with repeated category goods and cohort masses. That is a plausible question in its own right, and the paper’s authors might recognize it. Still, it is not obtained simply by aggregating the paper’s agents.
For the proposed fixed-three-category search problem, the computational challenge also looks limited: the eight bundles give \(O(\tau)\) affordability boundaries \(p(S)=b_t\) in three-dimensional price space. Enumerating the arrangement’s \(O(\tau^3)\) faces fixes each type’s demanded bundles; an LP can then check whether assignment masses clear supply. This suggests a direct polynomial-time method in \(\tau\) and the input bit length. A more ambitious version with the number of goods variable may be worthwhile, but Theorem 5.1’s three-good result does little to anchor its complexity.
So the strongest negative is that this theorem does not establish a compelling complexity mirror: the literal limit degenerates, while the nondegenerate repair is a different market with a routine fixed-dimension search. That case is honest but not decisive. The repaired model is sensible, and I cannot rule out a worthwhile mirror on the evidence here.
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.