| paper | Bundling equilibrium in combinatorial auctions |
| authors | R. Holzman, Noa E. Kfir-Dahav, Dov Monderer, Moshe Tennenholtz |
| venue | GEB 2004 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: in \(\mathrm P\), with bit running time \(\bigl[L+(m+\tau)\tau 2^m+(k+\tau)\tau 2^k\bigr]^{O(1)}=L^{O(1)}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given item kinds \(A\), a partition \(\pi\), rational valuation types \(v_t:2^A\to\mathbb{Q}_{\ge 0}\), masses \(\mu_t\) summing to \(1\), per-capita supplies \(\rho_a\), and threshold \(q\), optimize mass allocations \(x_{t,B}\) with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B\ni a}x_{t,B}\le\rho_a\), compare unrestricted welfare \(S^\star\) with \(\Sigma_\pi\)-restricted welfare \(S^\pi\), and decide whether \(S^\star/S^\pi\ge q\).
A high-multiplicity many-copy combinatorial-auction welfare model: \(\mu_t\) is type mass, \(x_{t,B}\) is mass receiving integral bundle \(B\), \(\rho_a\) is supply per unit mass, and the objective compares unrestricted allocation welfare with welfare restricted to \(B\in\Sigma_\pi\).
The proposed \(\rho_a\)-capacity model changes Theorem 2's one-copy integer incidence constraints into weighted or fractional mass capacities, so whether the exact intersecting-family characterization survives remains open.
fatal: False
The mirror covers the welfare ratio in Theorem 2 and asks whether the bounds and tight constructions in Theorems 3 and 4 persist; it leaves Theorem 1's unilateral equilibrium characterization, seller revenue, and other strategic results aside.
The positive case is real but narrow: it is strongest for the paper’s Section 5 analysis of surplus loss under partition-based bundling, not for its equilibrium characterization in Section 4.
The paper contains no named NP-hardness, polynomial-time, FPT, or similar complexity theorem. Its strongest computationally relevant anchor is therefore Theorem 2, proved in this paper. If “computational anchor” is interpreted literally as requiring a complexity classification, this paper has no qualifying anchor. Under the programme’s broader allowance for a theorem that computes or characterizes an underlying optimization problem, Theorem 2 is a defensible anchor.
A natural high-multiplicity setting is a many-copy combinatorial-auction market. There are \(m\) item kinds \(A=\{a_1,\ldots,a_m\}\), with many buyers but only \(\tau\) distinct valuation types. A type is a complete rational valuation \(v_t:2^A\to\mathbb{Q}_{\ge 0}\), satisfying \(v_t(\emptyset)=0\), free disposal, and all the other information relevant to the auction. The society is a rational distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\), where \(\mu_t\) is the fraction of buyers of type \(t\).
Continuization requires item supply to scale as well. Let \(\rho_a\) be the number of copies of item kind \(a\) per unit population. This is the minimal co-modification needed to avoid a population of buyers competing for a fixed finite set of goods. Every individual unit of mass still receives an integral bundle \(B\subseteq A\); only the mass of a type assigned to different bundles is fractional. Thus this is not fractionalizing an individual’s bundle.
For a fixed partition \(\pi=\{A_1,\ldots,A_k\}\), let \(\Sigma_\pi\) be the family of unions of its parts. A mass allocation is a vector \(x_{t,B}\ge 0\), where \(x_{t,B}\) is the mass of type \(t\) receiving bundle \(B\), satisfying
\[ \sum_{B\subseteq A}x_{t,B}=\mu_t \]
and
\[ \sum_{t}\sum_{B\ni a}x_{t,B}\le \rho_a \]
for every item \(a\). Define
\[ S^\star(\mu,\rho)= \max_x\sum_{t,B}v_t(B)x_{t,B}, \]
and define \(S^\pi(\mu,\rho)\) by imposing \(x_{t,B}=0\) whenever \(B\notin\Sigma_\pi\). The continuous problem I would hand to a prover is:
Continuous Partition-Equilibrium Surplus Ratio \(\mathrm{CPESR}_\infty\). Given \(A\), \(\pi\), a finite valuation-type list, rational masses \(\mu\), rational per-capita supplies \(\rho\), and a rational threshold \(q\), compute \(S^\star/S^\pi\), or decide whether \(S^\star\ge qS^\pi\), returning optimal mass allocations for both sides.
This is recognisably the paper’s problem. The unrestricted optimum is the socially optimal VC allocation, while \(S^\pi\) is exactly the surplus generated when buyers use the partition-based bundling equilibrium \(f^\pi\). The communication parameter remains the paper’s \(|\Sigma_\pi|=2^k\); it has not been replaced by an unrelated communication model.
The high-multiplicity dictionary is exact. If \(\mu_t=n_t/N\) and \(\rho_a=q_a/N\), clearing denominators produces \(n_t\) buyers of type \(t\) and \(q_a\) copies of item \(a\). Conversely, a large market with repeated valuation types normalizes to such a pair \((\mu,\rho)\). The intended regime is \(N\gg\tau\). The paper’s single-minded valuations \(w_B\) become large cohorts of buyers demanding bundle \(B\), so the witnesses used in its proofs survive naturally.
The anchor is Theorem 2, proved here. The paper defines
\[ r_\pi=\sup_{n\ge 1,\;v\ne 0}\frac{S_{\max}(v)}{S_\pi(v)}. \]
It then proves that, for every partition \(\pi=\{A_1,\ldots,A_k\}\),
\[ r_\pi=\max s(\Delta), \]
where \(\Delta=(H_i)_{i=1}^s\) is a family, repetitions allowed, of subsets of \(\{1,\ldots,k\}\) such that every two members intersect,
\[ H_i\cap H_j\ne\emptyset, \]
and each index \(\ell\) occurs in at most \(|A_\ell|\) members:
\[ \bigl|\{i:\ell\in H_i\}\bigr|\le |A_\ell|. \]
The continuous analogue is the worst-case envelope of \(\mathrm{CPESR}_\infty\) over rational societies and per-capita supplies. Its central question is whether the same intersecting-family characterization survives when cohorts and item copies become masses. This is a genuine computational question: the allocation side is a configuration LP, while the universal worst-case envelope is an incidence optimization over the partition.
For a fixed finite type list with explicit bundle values, I expect \(\mathrm{CPESR}_\infty\) to be Class A. Both \(S^\star\) and \(S^\pi\) are linear programs. With succinct valuation representations, the unrestricted pricing problem has the form
\[ \max_{B\subseteq A}\left(v_t(B)-\sum_{a\in B}p_a\right), \]
and the partition-restricted version optimizes over \(B\in\Sigma_\pi\). Thus the continuous model exposes exactly the sort of pricing question central to the ChoCo programme. Whether those pricing problems are polynomial depends on the valuation language; the paper itself explicitly leaves concise bidding languages outside its scope.
The paper’s Theorem 3, also proved here, supports the same mirror: if \(\beta(\pi)=\max_i|A_i|\), then
\[ r_\pi\le \beta(\pi)\,\varphi(k), \qquad \varphi(k)=\max_{j=1,\ldots,k}\min\{j,k/j\}. \]
Theorem 4 gives tight cases: if \(k=q^2+q+1\), every part has size \(q+1\), and \(q=0\), \(q=1\), or \(q=p^\ell\), then
\[ r_\pi=k. \]
In the continuous model these become further questions about whether the same upper bounds and projective-plane witnesses survive fractional cohort allocation. The combinatorics live in the goods and the partition, not in the number of named buyers, so I would expect the worst-case envelope to be Class B-facing: any hardness in the intersecting-family or partition-design problem should survive continuization. A genuinely larger value caused by fractional many-copy allocations would instead be a meaningful Class C boundary result.
This mirror deliberately covers only the paper’s surplus/communication tradeoff: Theorem 2 and its quantitative consequences in Theorems 3 and 4. I would not claim to mirror Theorem 1 directly. Its statement concerns unilateral ex post deviations by named buyers. In an atomless population, one buyer has zero mass, so unilateral strategic influence can become vacuous. A cohort-deviation or positive-mass incentive notion would be an extension, not a direct mirror.
The weakest point is therefore clear: scaling goods into per-capita supplies and allowing cohort mass to split across integral bundles moves beyond the paper’s literal single-copy auction. An opponent can reasonably call this a many-copy extension rather than a direct restatement. The case survives because the modification is forced by a genuine continuum population, preserves the paper’s valuation, allocation, \(\Sigma_\pi\), and surplus objects, and has an exact rational-clone interpretation. It is not a new story pasted onto the paper; it is the high-multiplicity version of the paper’s own central welfare comparison.
The negative case should begin more strongly than the proponent’s case does: under the programme’s strict anchoring rule, this paper has no qualifying computational anchor. It contains no theorem about polynomial time, NP-hardness, approximation, parameterized complexity, or an algorithm. Theorem 1 is an equilibrium characterization; Theorems 2–4 are extremal combinatorial and distortion results. The paper’s “communication complexity” is merely the number \( |\Sigma| \) of reported bundle values, not a computational-complexity classification. Thus \(\mathrm{CPESR}_\infty\) is not a continuization of a computational result; it is a new computational problem invented around a welfare bound.
Even under the programme’s broader allowance for optimization characterizations, Theorem 2 is a poor population mirror. The paper has one copy of each good. Consequently, every allocation gives nonempty bundles to at most \(m\) buyers, regardless of how large \(n\) is. Indeed, the paper itself observes that the supremum defining \(r_\pi\) is attained for some \(n\le m\). Increasing the number of buyers therefore produces no richer population object for this result: with bounded valuations, normalized welfare vanishes as \(n\to\infty\), while the welfare ratio is determined by a finite set of at most \(m\) served buyers. The high-multiplicity regime is not where Theorem 2 lives.
The proponent’s repair is to scale the inventory with the population. That is a sensible model of a different market, but it is not forced by continuizing the population in this paper. The paper’s goods are a finite scarce set; nothing relates their supply to the number of buyers. Scaling them creates a many-copy combinatorial auction and changes the resource constraints that generate the theorem.
This also breaks the claimed direct passage from Theorem 2. The bound
\[ \bigl|\{i:\ell\in H_i\}\bigr|\le |A_\ell| \]
comes from having exactly one copy of every good in \(A_\ell\). In the proposed model it becomes a capacity constraint involving the newly introduced supply density, such as
\[ \sum_{i:\ell\in H_i} z_i \le \sum_{a\in A_\ell}\rho_a . \]
The integer family of repeated sets is then replaced by a weighted or fractional incidence problem. That may be an interesting new theorem, but it is not Theorem 2 in continuous form. The rational-clone dictionary only relates the new many-copy model to new finite many-copy auctions; it does not provide a high-multiplicity limit of the paper’s one-copy auction.
There is a second semantic break. In an atomless population, an individual buyer has zero influence, so the unilateral ex post equilibrium that motivates \(S_\pi\) loses its strategic content. If deviations by positive-mass cohorts are introduced, that is a new coalition or nonatomic-game concept, not the paper’s equilibrium. Without such a concept, \(S^\pi\) is simply the optimum under a restricted bundle family; calling it surplus “generated by the bundling equilibrium” is no longer justified.
The proposed configuration LP does not repair this. With valuation tables explicitly supplied, both unrestricted and partition-restricted welfare problems are ordinary finite LPs whose input already contains the exponentially many bundle values. With succinct valuations, the pricing problem depends entirely on a bidding language that the paper explicitly leaves outside its scope. Either way, the computational question comes from added representation choices, not from a named computational question in the paper.
Theorems 3 and 4 do not provide independent anchors. They are bounds and tight examples for the same \(r_\pi\) already covered by Theorem 2. Their projective-plane witnesses are combinatorics of the finite goods and partition. Replacing buyers by masses either makes the witnesses irrelevant under fixed inventory or turns them into a new fractional design problem under scaled inventory. The latter could be worthwhile, but it would be a new many-copy/fractional extension rather than a continuous mirror of those theorems.
The honest weakness of this negative case is that the many-copy extension is not absurd. A separate paper on type-homogeneous combinatorial-auction markets with per-capita supplies could expose interesting LP and pricing complexity. But that is precisely the problem: the proposed mirror changes the inventory regime, drops the equilibrium concept, and adds a valuation representation absent from the source. On the paper as written, there is no named computational result whose population continuization the programme can study.
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.