| paper | d4-conf-ijcai-2016-0566 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results establish mechanism properties and a design impossibility, but none asserts an algorithm, complexity bound, computational formulation used by a solver, or hardness result. The proposed mass-core feasibility question is a plausible extension of core selection under uncertain availability, but it cannot provide the required computational anchor from this paper.
fails bit a — no named computational result to mirror
The proposed mirror concerns ex-post core feasibility and contingent payments; it leaves the strategyproofness and expected individual-rationality results, the ex-ante core, and the equilibrium comparisons outside its scope.
The paper has no numbered result classifying an underlying problem as polynomial-time solvable, NP-hard, or similar. Its strongest nearby anchor is Theorem 3, proved in this paper: with uncertain goods availability, no mechanism is both budget balanced and ex-post core-selecting. The proof considers two bidders and two goods, and shows that for each possible allocation rule there is an availability distribution and realization that make the ex-post core empty, for any of the paper’s ex-post information sets. That is a design-impossibility result, not a computational-complexity result, so it falls short of the programme’s preferred anchor criterion.
Still, it suggests a credible population mirror. Imagine repeated spectrum or hotspot-capacity markets serving large cohorts of similar buyers. A type \(t\) is a complete bidder description: in the paper’s single-minded domain, a desired bundle \(S_t\), value \(v_t\), and any other bidder-specific attributes relevant to allocation or payment. Its mass \(\mu_t\) is the fraction of the cohort with that description. The regime is many buyers and relatively few distinct types. Goods capacity \(q_j\) scales with cohort size, so the market retains meaningful per-capita supply; that co-modification belongs to the mirror. The paper’s uncertain, possibly correlated availability remains a source of uncertainty in the auction, not the continuized object.
I would make Mass-Core Feasibility with Uncertain Availability the lead question. An instance gives finite goods \(G\), finite type support \(T\) of size \(\tau\), rational masses \(\mu_t\) summing to one, per-capita capacities \(q_j\), seller costs, a finite rational joint distribution over bundle availabilities, and the set of realized availabilities observed when payments are computed. A solution consists of an allocation \(y_t\in[0,\mu_t]\), assigning mass \(y_t\) of type \(t\) its bundle, and a payment per served unit of each type for every possible observation. The allocation must maximize expected social welfare subject to the scaled capacity constraints.
The payments must be budget balanced, give each served agent nonnegative utility after availability is realized, and satisfy the ex-post core constraint for every coalition of type mass. More precisely, a coalition may include any amount of served mass up to \(y_t\) and unserved mass up to \(\mu_t-y_t\) for each type. Given the observed availabilities, let \(W(\kappa)\) be the coalition’s maximum expected surplus from reallocating its mass, using the paper’s conditional-expectation convention and the same capacity limits. The core condition requires current seller net revenue plus the coalition’s current utility to be at least \(W(\kappa)\), for every such coalition. The output is a feasible allocation and payment schedule, or a certificate that none exists.
This is recognizable as the authors’ problem: it preserves efficient combinatorial allocation, uncertain bundle availability, contingent payments, individual rationality, budget balance, and blocking coalitions. The continuous question asks whether the core-selection difficulty changes when the bidders are interchangeable within finitely many complete types. It covers Theorem 3’s ex-post core impossibility question. The paper’s equilibrium comparisons and its VCG properties are outside this mirror.
For the per-instance feasibility problem, I would initially expect Class A. With finite type support, the allocation is an LP, and each coalition’s best deviation is also an LP. The infinitely many mass-coalition constraints may admit a convex-optimization separation procedure. Establishing that procedure, its running time in \(m,\tau,L\), and the availability-support size is the computational work to hand a prover. This predicts tractable checking and selection when a core outcome exists; it does not predict that every instance has one. In particular, whether atomlessness removes Theorem 3’s empty-core phenomenon, or whether common availability shocks preserve a counterexample, is a further question.
The paper’s result is proved here, and the theorem’s tiny witness gives the mirror a useful boundary to investigate. But it does not establish the continuous claim: an atomless population permits fractional allocation across members of a type, which can change the core constraints substantially.
That is the weakest point in the case, alongside the anchor mismatch. The original LLG equilibrium example has only three bidders, and Theorem 3 is not a complexity classification. The positive case is therefore for a well-motivated continuous research question grounded in the paper’s core-design problem, not a claim that the paper already supplies the programme’s usual computational anchor.
The proponent has one anchor: Theorem 3. It is a substantial design impossibility, but it does not classify the complexity of a computational problem. It asks whether a mechanism can guarantee budget balance and ex-post core selection across the domain. The paper gives no algorithmic input-output problem, complexity bound, or reduction for that question. Its computational contribution is the approximate Bayes-Nash analysis, which studies three asymmetric bidder roles with privately drawn values; it does not establish a complexity result for solving those games.
A market with many standardized spectrum or hotspot buyers is plausible, and scaling supply with the population would make mass a meaningful quantity. That supports the general high-multiplicity regime. The paper’s LLG equilibrium benchmark, though, has two local bidders and one global bidder, each with a private value. Since a complete type includes that value, exact-type grouping of such buyers generally makes the support grow with the population. Replacing the value draws with a finite set of repeated valuation tiers could yield a useful large-market equilibrium problem, but it changes the benchmark and introduces a new equilibrium model rather than continuizing a computational result established in the paper.
“Mass-Core Feasibility” is the proponent’s strongest repair, and it is coherent as a research question. Its mismatch with Theorem 3 is in the question being asked: the theorem concerns whether a mechanism can guarantee the property across a domain, while the proposed problem fixes a welfare-maximizing allocation and asks whether that particular instance admits a contingent payment schedule satisfying constraints for every fractional coalition. The latter could matter for implementation, but it is a new per-instance optimization problem. The proposed LP and separation route is a hypothesis about that problem, not something the paper’s result itself calls for. This objection concerns the connection to the paper’s computational contribution, not what the continuous answer would be.
That is the strongest negative case I can make. It defeats Theorem 3 as a computational anchor, and the paper’s small equilibrium study supplies no stronger named complexity result. It does not establish that no worthwhile mirror exists: a mass-core feasibility study or a large-market equilibrium analysis could be valuable extensions, especially for standardized buyers. The universal “no scenario” claim is therefore weaker than the claim that this paper lacks a strong computational anchor.
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.