| paper | d4-conf-wine-2015-0006 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable: singleton packages support an equilibrium attaining \(W=\mathrm{OPT}\), computable in time \(\operatorname{poly}(K,\tau,L)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite type set \(T\) of size \(\tau\), rational masses \(\mu_t>0\) summing to \(1\), rational per-capita supply \(0<\lambda\le K\), and explicit rational monotone valuation tables \(v_t:\{0,\ldots,K\}\to\mathbb{Q}_{\ge0}\), find a competitive bundling equilibrium in time polynomial in \(K,\tau,L\), where \(L\) is the input bit length. A bundle has an integral size \(j\in\{1,\ldots,K\}\), mass \(q_j\), and price \(p_j\), with \(\sum_j jq_j=\lambda\). Each type’s mass may split across integral package-choice vectors \(z\in\mathbb{Z}_{\ge0}^K\) with \(\sum_j jz_j\le K\); every positive-mass choice must maximize \(v_t(\sum_j jz_j)-\sum_jp_jz_j\), and the assignment must clear each package type. The equilibrium welfare should be at least an \(1/O(\log(2+\min\{K,\tau\}))\) fraction of \(\mathrm{OPT}\), the maximum of \(\sum_{t,k}y_{t,k}v_t(k)\) over \(y_{t,k}\ge0\) satisfying \(\sum_k y_{t,k}=\mu_t\) and \(\sum_{t,k}ky_{t,k}=\lambda\).
An atomless price-taking population with finite rational type masses \(\mu_t\), integral bundles for each person, and per-capita supply \(\lambda\). Bundle sizes and individual choices stay integral; package supply and type-level assignments may be fractional.
The proposed mirror does not specify an encoding for \(v_t(k)\) or the representation of equilibrium prices and mass assignments, so its polynomial-time claim needs a concrete input/output model.
fatal: False
The mirror covers the multi-unit welfare guarantee of Theorem 4.1. It leaves the heterogeneous-good welfare results, budget-additive results, revenue guarantees, and LP-relation results aside; Theorem 4.3’s lower-bound analogue is not established.
Strictly, the paper gives no numbered NP-hardness, P, W[1]-hardness, or FPT result. Its strongest named computationally relevant anchors are the constructive welfare guarantee in Theorem 4.1 and the matching equilibrium-quality lower bound in Theorem 4.3. Both are proved here. Theorem 4.1’s proof uses earlier tools, and Remark 4.2 describes the corresponding demand-query algorithm; neither theorem is a standard complexity classification.
My lead is Theorem 4.3. It proves that for every market with \(n=m\) identical goods, there are subadditive valuations for which every competitive bundling equilibrium achieves only a \(1/\Omega(\log m)\) fraction of optimal welfare. In the construction, consumer \(i\ge2\) is unit-demand with value \(1/i\) for any nonempty bundle. Consumer \(1\) values every nonempty proper subset at \(1+\varepsilon\), and the grand bundle at \(2+2\varepsilon\). The optimum gives one item to each consumer, with welfare on the order of \(\log m\); every competitive bundling equilibrium gives all items to consumer \(1\), with welfare \(2+2\varepsilon\). Theorem 4.1, proved here as well, supplies the other half of the picture: every \(n\)-consumer, \(m\)-item multi-unit market has a competitive bundling equilibrium with welfare at least an \(O(\log\mu)\)-approximation to optimum, where \(\mu=\min\{m,n\}\). Its proof is constructive; Remark 4.2 gives a polynomial demand-query procedure and a value-query version after preprocessing.
Here is the mirror I would put to a prover: Mass Multi-Unit Bundling Welfare. Take an atomless population of mass \(1\), with finite type support \(T\), rational type masses \(\mu_t>0\) summing to \(1\), and a supply \(\lambda\) of identical indivisible units per capita. Each type \(t\) has a nondecreasing valuation \(v_t(k)\) for receiving \(k\) units, for \(0\le k\le K\). A bundling offers packages of integer sizes \(j\le K\), with mass \(q_j\) of packages at price \(p_j\), and \(\sum_j j q_j=\lambda\). A type may choose any feasible collection \(z\) of offered packages, valuing it at \(v_t(\sum_j jz_j)-\sum_j p_jz_j\). An equilibrium is a distribution of the population over utility-maximizing package choices that allocates every package: if \(a_{t,z}\) is the mass of type \(t\) assigned choice \(z\), then \(\sum_z a_{t,z}=\mu_t\) and \(\sum_{t,z}a_{t,z}z_j=q_j\). Each person still receives an integral bundle; only the type-level allocation is fractional.
The benchmark is the maximum welfare over mass allocations of integral quantities \(k\le K\) using total supply \(\lambda\), without the equilibrium restriction. The requested output is an equilibrium with high welfare relative to that benchmark. The Theorem 4.1 question is whether every such instance admits a constructive \(O(\log(2+\min\{K,\tau\}))\)-approximation, where \(\tau=|T|\). The Theorem 4.3 question is whether there is a family in which every mass equilibrium loses a factor \(\Omega(\log K)\).
For the latter, a natural stress test has \(\lambda=1\), \(K\) types each of mass \(1/K\), and \(K\) as the parameter. Type \(1\) has \(v_1(0)=0\), \(v_1(k)=1+\varepsilon\) for \(1\le k<K\), and \(v_1(K)=2+2\varepsilon\); each type \(i\ge2\) has \(v_i(0)=0\) and \(v_i(k)=1/i\) for \(k\ge1\). The unrestricted allocation giving each type one unit has welfare \((H_K+\varepsilon)/K\), while assigning \(K\) units to the type-\(1\) cohort gives welfare \((2+2\varepsilon)/K\). The question is whether every mass competitive bundling equilibrium in this family remains logarithmically worse than the unrestricted optimum.
I expect the upper-bound question to be tractable, by adapting the paper’s constructive bundling argument to type masses. I expect the stress-test lower bound to survive as an equilibrium-quality barrier—the analogue of a transferred lower bound—but it needs a proof: continuum cohorts can split across bundles, so Theorem 4.3 does not itself establish the result. This is a plausible mirror because it preserves the paper’s central object: indivisible homogeneous goods, bundled supply, anonymous prices, profit-maximizing consumers, and market clearance. The population becomes the continuous object; the fractional quantities are averages over types, not fractional bundles for individuals.
The mirror covers only the multi-unit welfare results in Theorems 4.1 and 4.3. It does not try to continuize the paper’s revenue results or its heterogeneous-good settings. Its weakest point is that the lower-bound witness uses \(K\) distinct valuation types, with masses \(1/K\), and a deliberately sharp complementarity in one type. Each type is a continuum-sized cohort, but the witness does not have fixed or especially small support as \(K\) grows. Also, the special valuation may be hard to motivate in some markets. Those are real limits; they make the lower-bound transfer a question to prove, not a conclusion to assume.
The strongest case against is a scope objection. Theorem 4.1 and Theorem 4.3 give welfare guarantees for competitive bundling equilibria: one proves an \(O(\log \mu)\) bound, the other a matching \(\Omega(\log \mu)\) obstruction. The latter is an equilibrium-quality lower bound, not a computational hardness result. The former is constructive, and the paper gives polynomial demand-query procedures for its multi-unit setting. So the proposed mirrors chiefly ask how welfare guarantees change in an atomless market. That is a natural market-design question, but it does not by itself fill ChoCo’s stated gap in complexity and algorithms.
Theorem 4.3 is the weaker anchor. Its discrete construction has one consumer at each of \(K\) distinct values. Replacing those consumers by types of mass \(1/K\) creates a new equilibrium model in which each cohort can split across utility-maximizing choices. The discrete proof’s argument about which consumers receive bundles does not transfer directly. The proposed logarithmic lower bound therefore needs its own proof. That uncertainty weakens the claim that this theorem supplies a transferred lower-bound mirror; it does not make the continuous question uninteresting.
The best version of Theorem 4.1’s mirror would specify rational type masses, integral bundles for each person, per-capita supply, and an algorithmic model for valuations, input size, and output prices and allocations. That is coherent: a large market with repeated buyer types is a sensible high-multiplicity regime, and fractional type-level allocations are an allowed consequence of continuizing the population. But once those details are supplied, the result is a high-multiplicity extension of a constructive welfare theorem. The paper offers no reason to expect that extension to reveal the kind of complexity boundary ChoCo is meant to chart.
That is a case for lower priority, not for the universal claim that no worthwhile mirror exists. I see no honest identity, multiplicity, or degeneration objection: repeated valuation types are plausible, and the proposed scaling avoids vanishing per-capita supply. The upper-bound mirror in particular survives the objections above. The negative case is therefore weak; a careful computational formulation could make this paper a worthwhile mirror, even though its headline theorems are welfare bounds rather than complexity classifications.
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.