| paper | d4-conf-aaai-2015-0766 |
| 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: Polynomial-time solvable in the total explicit-table binary input length; the ordinary and strengthened allocation families describe exactly the same type-uniform core price set as absence of blocking coalitions. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1 (Weakly Stronger Core Constraints)
statement extracted from the paper’s text layer
Given a finite item set \(G\), finitely many bidder types \(T\) with rational masses \(\mu_t\), explicit bundle-value menus \(v_t(S)\), and rational per-capita supplies \(b_g\), what is the complexity of computing a welfare-maximizing allocation and minimum-payment type-uniform prices \(p_t\) whose outcome has no blocking measurable coalition? Does the continuous allocation-based formulation that omits payments of nonconflicting incumbent mass preserve exactly the same core price set?
Types encode all bidder attributes used by the auction; each type has mass \(\mu_t\), and each assigned bundle \(S\subseteq G\) remains indivisible. Allocation variables \(x_{t,S}\ge 0\) obey \(\sum_S x_{t,S}\le\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}\le b_g\). After maximizing welfare, choose type-uniform winner prices \(p_t\) minimizing \(\sum_t w_t p_t\), where \(w_t\) is the winning mass of type \(t\); separation searches over coalition submasses and feasible reallocations for a blocker. With explicit bundle menus, these allocation and blocking checks are linear programs.
The proposed LP removes the paper’s finite integer winner-determination bottleneck by allowing mass to split, and it does not establish that Theorem 1’s conflict-based strengthening remains equivalent at the mass level.
fatal: False
The mirror covers core-price computation and the role of Theorem 1’s allocation-based constraints in that computation. It leaves the finite CATS experiments, their speedups, and the paper’s specific CCG iteration behavior unaddressed.
The strongest mirror I see is a type-mass core-pricing problem for a replicated combinatorial auction. The regime would be a large auction for standardized equipment or spectrum lots: perhaps tens of thousands of regional operators or branches, but only dozens of distinct valuation templates. Each type captures everything the auction uses about a bidder, including its reported valuation and any relevant budget or pricing class. The society is a distribution \(\mu\) over those types. Item supplies scale with the cohort, so \(b_g\) is the supply of item \(g\) per unit of population. That co-modification keeps the auction meaningful as the population grows.
The named anchor is Theorem 1 (Weakly Stronger Core Constraints), proved in this paper. It states that constraint sets (C2) and (C3) describe the same core. For every allocation \(X\), (C2) requires
\[
\sum_{j\in W\setminus C(X)}p_j
\ge V(X)-V_{C(X)}(\operatorname{wd}(N)).
\]
Constraint (C3) uses the same right-hand side but sums only over \(W_X\setminus C(X)\), where \(W_X\) is the set of incumbent winners whose allocations conflict with \(X\). Thus it drops payments from winners who could keep their allocations alongside \(X\). The theorem proves that these stronger constraints preserve exactly the same core: (C3) implies (C2) because it has fewer nonnegative payment terms; in the other direction, the (C2) constraint for \(X\) combined with the incumbent allocation of non-conflicting winners implies the (C3) constraint for \(X\). The paper uses this structural result in developing its core-constraint-generation methods.
The paper does not give a numbered theorem classifying a problem as NP-hard or polynomial-time solvable, so I would not present Theorem 1 as one. It is a formulation result used by the computation—the kind of anchor allowed here. My mirror concerns the underlying computation it helps with:
Type-Mass Core Pricing. An instance gives item types \(G\), rational per-capita supplies \(b_g\), and finitely many bidder types \(t\), with rational masses \(\mu_t\) summing to one. Each type has an explicitly represented valuation over bundles, such as a finite bid menu. A feasible allocation is a collection of masses \(x_{t,S}\): the mass of type \(t\) receiving the integral bundle \(S\). It must satisfy
\[
\sum_S x_{t,S}\le \mu_t,\qquad
\sum_{t,S:\,g\in S}x_{t,S}\le b_g.
\]
The variables describe fractions of people assigned bundles; each individual still receives an integral bundle. First choose a welfare-maximizing allocation. Then find nonnegative, type-uniform winner prices \(p_t\) that put the outcome in the core and minimize total payments,
\[
\min \sum_t w_t p_t,\qquad
w_t=\sum_{S\ne\varnothing}x_{t,S}.
\]
A solution is an optimal price vector, or a certificate that no core price vector exists under the type-uniform pricing restriction. Core stability requires that no measurable coalition can reallocate the goods among its members, subject to the same supply limits, and improve on its current value while raising more revenue than the incumbent winners outside the coalition.
I expect this explicit-menu version to be Class A. A coalition can select any submass from each current type-and-bundle cell. For a proposed price vector, the most-blocking-coalition check then chooses those submasses and a new allocation for them. Both choices are continuous mass variables with linear capacity constraints, so the check is an LP. The efficient allocation is an LP as well. That gives a separation route for optimizing over the core-price constraints, even though there can be infinitely many measurable coalitions. This is where the programme’s continuous-optimization toolbox applies: the population relaxation turns coalition selection and allocation into mass-flow variables. The result is polynomial in the explicit valuation-menu size, the number of types, and the rational input length; it is not a claim about every succinct valuation representation.
The mirror covers the paper’s core-price computation and the structural role of Theorem 1. It does not claim to reproduce the paper’s experimental speedups on finite CATS instances. A further question is whether the theorem’s conflict-based strengthening has a clean polynomial-size version when winners and conflicts are fractional masses. Others follow naturally: when are type-uniform core prices guaranteed to exist, what finer type information is needed if they do not, and how does this continuous solution approximate a large finite auction?
The weakest point is the market change: per-capita item supply and a common price for winners of the same type are substantive modelling choices, and the theorem itself does not prove that its finite conflict argument carries over unchanged. The case survives because the mirror keeps the paper’s central object—core payments against blocking coalitions—and asks the corresponding computational question for a plausible high-multiplicity auction regime.
The strongest case against is that the proposed anchor is not a computational result in the sense ChoCo is trying to map. Theorem 1 proves that two finite-auction descriptions define the same core; it says nothing about the complexity of computing prices. The paper’s algorithmic contribution is instead its CCG speedups, reported experimentally. The AAAI record describes those as constraint-generation techniques and experimental gains, not a complexity classification. ([AAAI paper](https://ojs.aaai.org/index.php/AAAI/article/view/9289))
The proponent’s best model—a replicated procurement or advertising market, with per-capita supplies and finitely many complete bidder types—is coherent. If bid menus are explicit, welfare allocation is a configuration LP. For a fixed price vector, a blocking-coalition check can also be written as an LP by choosing mass from current type-and-bundle cells and reallocating it. That gives a plausible polynomial-time Class A question. But the tractability comes from making assignment and coalition membership divisible. It does not mirror the paper’s finite CCG bottleneck, where each iteration solves an integer winner-determination problem. And the proposed LP does not itself establish a continuous counterpart of Theorem 1’s conflict-based strengthening.
Keeping the paper’s fixed inventory instead does not rescue the match: with a normalized population, the share receiving bundles tends to zero. Scaling inventory avoids that degeneration, as the proponent suggests, but changes the setting into a replicated-capacity market. That change is allowed by the programme, so it is not a fatal objection; it does mean the theorem’s individual-winner conflict argument needs a new mass-level formulation rather than carrying over as stated. Under explicit menus, the resulting core-pricing problem still looks like an ordinary LP application, while any harder compact-bid version would depend on a representation issue the proposed mirror deliberately excludes.
So this is a real weakness in the case for, but not a decisive refutation of the mirror. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists: the type-mass pricing problem is sensible, and its tractability could be a useful result under ChoCo’s goals. The negative case is strongest on the mismatch between the named theorem and the computational question, and weakest precisely where the programme permits a new, tractable high-multiplicity problem to count as worthwhile.
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.