| paper | Two-Price Equilibrium |
| authors | Michal Feldman, Galia Shabtai, Aner Wolfenfeld |
| venue | AAAI 2022 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered results concern existence, welfare guarantees, equilibrium correspondences, and structural characterizations. Neither Theorem 8.1 nor Theorem 9.1 asserts polynomial-time solvability, hardness, FPT, or another qualifying computational property, so bit (a) fails regardless of the mirrors' plausibility. Theorem 9.1 nevertheless yields a recognizable continuous computational question.
fails bit a — no named computational result to mirror
The proposed mirror covers the high-multiplicity versions of Theorems 8.1 and 9.1, while leaving the auction correspondence, general combinatorial valuations, heterogeneous items, and the paper's other structural lemmas untreated.
The strongest positive case is narrow but real. The paper contains no named theorem asserting NP-hardness, membership in \(P\), W[1]-hardness, FPT, or another standard complexity classification. Algorithm 1 is constructive, but the paper does not state its running time. Thus I cannot honestly present it as already containing a computational-complexity anchor. Its best anchors are constructive existence and characterization results whose continuous complexity is a natural question.
My lead is Theorem 8.1, proved by the authors (with details deferred to the full version): every market with subadditive symmetric valuations admits a U-\(2\mathrm{PE}\), \((S,\hat p,0)\), of discrepancy at most \(6\). The relevant regime is a large market for identical units—standardized cloud slots, storage units, or production capacity—with many buyers but few demand-curve types. A type \(t\) is the buyer’s complete symmetric valuation curve \(v_t(k)\), including any common restrictions; \(\mu_t\) is the fraction of buyers of that type. Let \(\rho\) be the number of identical item units per buyer. In a finite realization with \(N\) buyers there are \(N\mu_t\) buyers of type \(t\) and \(N\rho\) item units. Thus the continuum records normalized multiplicities, while every individual still receives an integer number of items.
The continuous problem I would attach to Theorem 8.1 is:
\[ \textsc{Low-Discrepancy-2PE}_{\infty}. \]
An instance consists of a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), rational item density \(\rho\), and rational nondecreasing subadditive valuation curves \(v_t:\{0,\ldots,K\}\to\mathbb{Q}_{+}\). Choose masses \(x_{t,k}\ge 0\), where \(x_{t,k}\) is the fraction of type-\(t\) buyers receiving exactly \(k\) items, satisfying
\[ \sum_{k=0}^{K}x_{t,k}=\mu_t \quad\text{and}\quad \sum_{t\in T}\sum_{k=0}^{K}k\,x_{t,k}=\rho. \]
For every occupied positive-quantity cohort \(a=(t,k)\), choose low and high per-item prices \(0\le \check p_a\le\hat p_a\). In the atomless high-multiplicity limit, let \(h=\min_a\hat p_a\). A type-\(t\) buyer in cohort \(a=(t,k)\) must prefer its \(k\)-item bundle to every integer quantity \(\ell\), retaining any \(r\le\min\{k,\ell\}\) of its own items:
\[ v_t(k)-(k-r)\check p_a \;\ge\; v_t(\ell)-(\ell-r)h \]
for every \(\ell\in\{0,\ldots,K\}\) and admissible \(r\). The zero-quantity cohorts satisfy \(v_t(0)\ge v_t(\ell)-\ell h\). The objective is to minimize
\[ D(x,\hat p,\check p) = \frac{\displaystyle \sum_{t,k>0}k\,x_{t,k}(\hat p_{t,k}-\check p_{t,k})} {\displaystyle \sum_{t,k}x_{t,k}v_t(k)}. \]
The theorem-style decision version asks whether a certificate with \(\check p_{t,k}=0\) and \(D\le 6\) exists, and asks for such a certificate.
This is recognizably the authors’ problem: same identical items, same symmetric subadditive valuations, same owner-versus-outsider prices, same market-clearing allocation, same discrepancy objective. It is not merely fractional welfare allocation: \(x_{t,k}\) is a distribution over integer bundles. The natural expectation is Class A. Algorithm 1, Lemma 8.2, and Lemma 8.3 already organize the construction around valuation slopes and “good” quantity blocks, so the number of named buyers should disappear and be replaced by masses of valuation types. Under explicitly tabulated valuation curves, I would expect a procedure whose dependence is on \(\tau\), \(K\), and encoding length, rather than on \(N\). The paper itself does not establish that runtime, so this remains a proposed continuous result, not a claimed theorem.
The cleanest secondary anchor is Theorem 9.1, also proved by the authors: for symmetric valuations, a uniform-price Walrasian equilibrium exists exactly when the allocation is a WE for each valuation’s submodular closure and every assigned quantity lies at an intersection index. Its continuous mirror is:
\[ \textsc{Continuous-WE}_{\infty}. \]
Given \(T,\mu,\rho\), valuation curves \(v_t\), their submodular closures \(\widetilde v_t\), and intersection sets
\[ I_{v_t}=\{k:v_t(k)=\widetilde v_t(k)\}, \]
find a price \(p\ge0\) and masses \(x_{t,k}\) satisfying the same population and supply equations, with
\[ x_{t,k}>0 \;\Longrightarrow\; k\in I_{v_t} \quad\text{and}\quad k\in\arg\max_{\ell} \{\widetilde v_t(\ell)-p\ell\}. \]
This is exactly the high-multiplicity version of buyers choosing integer bundles at a common item price. A type may be split across tied maximizing quantities, which represents many identical buyers rather than fractional items for one buyer. I expect this problem to be in Class A: one can compute the closures and search the finitely many price breakpoints, checking whether \(\rho\) lies in the aggregate demand interval. Again, that complexity statement is mine, not one made by the paper.
The scope is deliberately limited. I am mirroring Theorem 8.1’s low-discrepancy \(2\mathrm{PE}\) construction and Theorem 9.1’s WE characterization. I am not claiming that Proposition 3.5’s auction correspondence, the heterogeneous-item open problem, or every arbitrary combinatorial valuation result has an equally persuasive continuous form.
The weakest point is the absence of a genuine complexity anchor. The paper proves existence, welfare, and structural characterization, not a complexity landscape. Moreover, the atomless \(2\mathrm{PE}\) definition uses the fact that a positive-mass cohort supplies arbitrarily many outside copies in the high-multiplicity limit; the opposing analyst can argue that this changes the finite price-competition environment. My answer is that this is precisely the intended high-multiplicity regime, and the WE mirror avoids even that concern: every individual still chooses an integer bundle, while only the population of indistinguishable buyers is continuous.
The strongest negative point is that this paper supplies no genuine computational anchor. Theorem 8.1 is an existence theorem with a constructive proof, but it gives no running time, input representation, or complexity classification. Theorem 9.1 is a structural characterization, not an algorithmic result. Thus the proposed continuous problems are new questions inspired by the paper, rather than continuous versions of computational results established in it. That is a serious mismatch with ChoCo’s stated purpose.
Theorem 8.1 also does not continuize as cleanly as the proponent suggests. In the finite \(2\mathrm{PE}\), prices belong to individual items. For a deviation from a bundle of size \(k\) to one of size \(\ell\), the cost of acquiring \(\ell-r\) outside items is the sum of the \(\ell-r\) cheapest relevant high prices, not simply \((\ell-r)h\) for \(h=\min_a\hat p_a\). The proposed \(x_{t,k}\) representation forgets the distribution of high prices across owned items. Its constraint is therefore a sufficient condition for equilibrium, not generally an exact aggregate translation.
One can repair this by scaling buyers and items together, imposing a fixed per-buyer demand cap \(K\), and observing that every positive-mass cohort supplies arbitrarily many items at its price in the limit. But that adds a substantial mean-field assumption and changes the object being studied: the exact continuum state must include a joint distribution of buyer types, allocations, and owner-specific prices. The resulting problem is a newly designed equilibrium model, not the high-multiplicity form of the theorem as stated. Moreover, asking whether the discrepancy is at most \(6\) is a universal-yes search problem on the theorem’s promised domain. Optimizing the minimum discrepancy would be more meaningful, but that is an additional research problem rather than a computational mirror supplied by the paper.
Theorem 9.1 is a much stronger anchor for the proponent, and here the negative case is genuinely weak. With finitely many valuation-curve types, integer quantities, and an item density \(\rho\), the proposed continuous Walrasian question is perfectly coherent. A type can be split across tied integer demand levels, while only the population multiplicities become fractional. Submodular closures and the finitely many price breakpoints provide a natural high-multiplicity computation. This is not invalidated by the fact that items remain indivisible, by the use of masses, or by existing high-multiplicity work; those are precisely the right ingredients.
Nor can one object that the answer would probably be easy. A well-posed Class A problem is still a valid ChoCo problem. The best objection is only that the paper’s theorem does not itself formulate this computational task, and that the resulting one-dimensional demand-feasibility problem may be more naturally classified as standard market-equilibrium computation than as continuous computational social choice.
Consequently, I do not think the universal negative claim can honestly be defended. Theorem 8.1 is a weak and imperfect anchor, and the paper lacks the complexity content ChoCo normally wants. But Theorem 9.1 admits a sensible high-multiplicity mirror after a standard, recognizable modelling step. The right verdict is “low priority as a source of computational complexity questions,” not “no worthwhile continuous 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.