| paper | d4-conf-atal-2006-0163 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even with all incumbent values equal to \(1\) and positive dyadic masses summing to \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite item set \(I\), a rational distribution \(\mu\) over positive-valued single-minded incumbent bid types \(t=(B_t,v_t)\), and two explicit colluders, can the colluders win all items with zero VCG payment?
Incumbent bidders are represented by their type distribution \(\mu\), with each supported type indicating an available bid \(B_t\). Items remain indivisible, and the two colluders remain explicit entrants who choose their bids. The question depends on the supported bundles: whether \(I\) can be partitioned into \(T_1,T_2\) so every supported \(B_t\) intersects both parts.
The anchors cover zero-payment collusion in free-disposal forward auctions and maximum-payment collusion in reverse auctions. The mirror leaves the revenue examples, self-enforcing collusion conditions, non-free-disposal auctions, and exchanges aside.
The strongest honest mirror is a high-multiplicity VCG collusion problem: many incumbent bidders share a small set of complete bid types, while a small cartel enters and chooses its bids. A type is a single-minded report \(t=(B_t,v_t)\) in a forward auction, or \(t=(B_t,c_t)\) in a reverse auction: the bundle and its value or cost, since those are the features that determine the bidder’s role in these results. The incumbent society is a rational distribution \(\mu\) over those types, with support size \(\tau\). It can represent \(N\gg\tau\) individual bidders by taking \(N\mu_t\) identical copies of each type, for a sufficiently large \(N\) that makes those counts integral. Items remain indivisible; the population is the continuous object.
The paper’s colluders are additional bidders, so I keep their actions explicit rather than folding them into the incumbent distribution. That preserves the paper’s question: given the other bids, can entrants manipulate the VCG outcome? The recurring-procurement regime is a large pool of suppliers or buyers competing over standardized lots, with many agents sharing the same bundle and valuation or cost. This is plausible when firms have common schedules or capacity classes, and it has \(N\) large relative to \(\tau\).
My lead is Forward Mass-Society Zero-Payment Collusion Feasibility, anchored in Theorem 3. The theorem says that DIVIDE-SUBSETS is NP-complete even when \(n=2\): given an item set \(I\) and a family \(\mathcal R\) of subsets, decide whether \(I\) can be partitioned into \(n\) parts so that no member of \(\mathcal R\) is contained in any part. The paper proves this by identifying the problem with Hypergraph-2-Colorability and citing its NP-completeness in [7].
The mirror’s instance is a finite item set \(I\) and a rational mass distribution \(\mu\) over positive-valued single-minded bid types \(t=(B_t,v_t)\), with support size \(\tau\). It asks whether two colluders can win all items for zero VCG payment against this incumbent society. A solution is a partition \(I=T_1\dot\cup T_2\) such that every supported bid bundle meets both parts; equivalently, no \(B_t\) is contained in either part. By the paper’s Theorem 1, this partition is exactly the condition for the colluders to secure all items at zero cost. They can report sufficiently high values on their assigned parts, and the condition ensures either colluder’s removal leaves the other’s allocation undisturbed by any positive noncolluder bid. Theorem 3’s hard instance embeds directly: make each \(S_i\in\mathcal R\) a positive bid type and give the types uniform positive masses. Thus I expect Class B, hardness transfers. The combinatorics are in the item bundles, and the reduction already works with two colluders.
A second mirror covers reverse auctions. Reverse Mass-Society Maximum-Payment Feasibility is anchored in Theorem 6. The theorem says CRITICAL-PARTITION is NP-complete even with \(n=2\), under a restriction where a partition is a solution exactly when no complement \(I\setminus T_i\) contains all items of any bid. In the general problem, the input is an item set, bids \((S_i,v_i)\), and \(n\); the cost \(c(T)\) is the minimum cost of a set of bids covering \(T\), and the question is whether \(I\) can be partitioned into \(n\) parts with \(c(T_i)=c(I)\). The paper proves hardness here with a reduction from NAESAT and gives membership for the stated restriction.
For the mass version, \(\mu\) is a distribution over supplier types \(t=(B_t,c_t)\) with nonnegative rational costs. Let \(C_\mu(U)\) be the least cost of supported bid types whose bundles cover \(U\), and set \(N=C_\mu(I)\), assuming the incumbent bids can cover \(I\). The question is whether two colluders can each receive a VCG payment of \(N\). A witness is a partition \(I=T_1\dot\cup T_2\) with \(C_\mu(T_i)=N\) for each part. The paper’s Theorem 4 characterizes exactly this payment condition. Duplicate suppliers of a supported type do not change these covering costs, so the NP-hard restricted instances embed by assigning positive rational mass to their bid types. This is again Class B.
These anchors cover VCG collusion feasibility in free-disposal forward auctions and reverse auctions. They do not claim to mirror all the paper’s revenue guarantees, the self-enforcing reverse-auction condition, non-free-disposal auctions, or exchanges. The direct questions they generate are whether the problems admit algorithms parameterized by \(m\) or \(\tau\), and whether masses matter for less extreme goals such as approximate payments or self-enforcing collusion. The latter is especially useful: in these anchors, every positive mass gives the same feasibility condition, so one should test where changing prevalence begins to change the answer.
The weakest point is that the mass distribution describes the incumbent bidders while the coalition remains two atomic entrants; their share of the total population tends to zero as \(N\) grows. If the mirror required every strategic actor to be atomless, the VCG pivot question could change substantially. I think this mirror survives because the paper itself fixes incumbent bids and studies the effect of added colluders. It is a faithful high-multiplicity version of that problem, and its main conclusion is a meaningful boundary result: in these cases, continuously describing bidder prevalence does not remove hardness rooted in the item structure.
The strongest objection is that both anchors depend on atomic bids and their individual VCG externalities, while the proposed continuum describes population by mass. In these auctions, a bid is accepted or rejected as a whole, and a bidder’s payment depends on what changes when that particular bid is removed. An atomless type has no such individual: removing measure zero leaves the society unchanged. If mass contributes linearly to welfare, an individual’s VCG externality tends to zero with its mass. The proposed mirrors need a way to preserve the paper’s pivotal bidders while making the population continuous.
For Theorem 3, a large pool of firms with repeated single-minded bids is plausible, but repetitions do not give the masses a role in the partition condition. With finitely many indivisible items, two identical bids compete for the same bundle, so extra copies do not add another useful allocation option. The condition in Theorem 1 depends on which positive bid bundles exist, not how prevalent each is. Treating \(\mu_t v_t\) as a type’s aggregate value would make the type a single bloc with a different valuation; allowing a fraction of the type to win would change the all-or-nothing allocation problem. Either route changes the object whose complexity Theorem 3 establishes.
For Theorem 6, the reverse-auction version has the same fault. If a type means a unit supplier offering a fixed bundle at a fixed cost, then one available supplier of that type already supplies the bid option used in the cover condition; repeating it does not make a fractional population relevant. If instead mass scales the quantity supplied and its cost, covering an item set becomes a divisible-supply problem, and removing one supplier no longer gives the paper’s payment criterion. That may be a sensible procurement model, but it is a different problem from asking whether each of two individual colluders can receive the payment characterized by Theorem 4.
A stronger rescue would scale the market with the population: more items or lots, and suppliers whose capacities grow with mass. But the paper’s collusion results concern a finite set of indivisible items and discrete entrants. Making entrants atomless removes their individual pivot effect; treating each colluding cohort as one strategic bloc changes “each colluder’s payment” into a group-level question. Keeping a finite cartel against an atomless incumbent crowd is possible as a hybrid model, but with fixed finite goods the crowd’s mass does not act like a collection of additional indivisible bids. A model that gives it meaningful supply requires the scaling and allocation changes just described.
So the case against these anchors is that they do not yet identify a population-continuous version of the paper’s computational problem: the discrete bid options and individual pivots do the work, while population masses either drop out or force a different allocation and payment model. This is not an airtight case against every continuous auction model. A scaled, cohort-based procurement model could be worthwhile in its own right, and the hybrid cartel setting may deserve study. The weakness is that ruling those out would require more than showing the direct mirrors lose the paper’s atomic VCG structure.
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.