| paper | d4-conf-atal-2015-0226 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable exactly: a feasible allocation attaining \(\mathrm{OPT}\) can be computed in time polynomial in \(m,\tau,D,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given goods \(U\), \(\tau\) normalized monotone submodular valuation types \(v_t:2^U\to\mathbb{Q}_{\ge 0}\), rational masses \(\mu_t\ge 0\) summing to \(1\), and per-capita supplies \(q_e\ge 0\), choose fractions \(x_{t,S}\ge 0\) of each type assigned each integral bundle \(S\subseteq U\), with \(\sum_{S\subseteq U}x_{t,S}=1\) for each \(t\) and \(\sum_t\mu_t\sum_{S\ni e}x_{t,S}\le q_e\) for each good \(e\). Compute the maximum per-capita welfare \(\sum_t\mu_t\sum_{S\subseteq U}x_{t,S}v_t(S)\), with complexity measured in \(m=|U|\), \(\tau\), the rational bit length, and the valuation-description length.
A distribution over \(\tau\) bidder types with masses \(\mu_t\); each type’s mass is distributed among whole bundles, while per-capita capacities \(q_e\) scale with the population. Maximize expected welfare over those bundle assignments.
The hard instances use bidder-specific valuation families to carry combinatorial information, and the case does not show that this structure or its approximation threshold persists with moderate support and scaled supplies.
fatal: False
The mirror covers Theorem 9’s welfare-maximization clause; it leaves aside the payment-computation result and the paper’s truthfulness, verification, and mechanism-characterization results.
My lead is a high-multiplicity version of submodular combinatorial-auction welfare maximization. The anchor is Theorem 9, proved in this paper using a hardness result cited from Dobzinski and Vondrák (2013). It says there is a setting of combinatorial auctions with submodular bidders where finding a welfare-maximizing allocation is NP-hard to approximate within \(2e/(2e-1)-\epsilon\), for every \(\epsilon>0\), while computing payments for Algorithm 2 is polynomial-time. In the hard setting, each bidder’s valuation is specified using a family of \(g\) subsets of the goods, each of size \(s\), where \(g\) and \(s\) are fixed constants; that restriction makes the bidder domains polynomial in the number of goods. The hardness rests on the welfare-maximization part of the theorem.
Here is the continuous problem I would put to a prover, called High-Multiplicity Submodular Welfare. The goods are \(U\), with \(|U|=m\). An instance gives \(\tau\) types of bidder, each a complete, succinctly represented normalized monotone submodular valuation \(v_t:2^U\to\mathbb Q_{\ge0}\), and rational masses \(\mu_t\ge0\) summing to \(1\). It also gives a per-capita supply \(q_e\in[0,1]\) for each good \(e\in U\). For every type \(t\) and bundle \(S\subseteq U\), choose \(x_{t,S}\ge0\), the fraction of type \(t\) receiving the integral bundle \(S\). Require
\[
\sum_{S\subseteq U}x_{t,S}=1\quad\text{for every }t,
\qquad
\sum_t\mu_t\sum_{S\ni e}x_{t,S}\le q_e\quad\text{for every }e.
\]
The task is to return a feasible allocation maximizing per-capita welfare
\[
\sum_t\mu_t\sum_{S\subseteq U}x_{t,S}v_t(S).
\]
Thus mass is a fraction of actual agents, and \(x_{t,S}\) describes a distribution over whole bundles for those agents. The instance size and running time should be stated in \(m,\tau\), the rational bit length, and the valuation-description length.
A plausible regime is a large procurement platform or licensing system with many standardized operators whose valuations for bundles of license categories fall into relatively few profiles. Recurring license capacity scales with the size of the operator population. With \(N\) operators, the mass \(\mu_t\) represents roughly \(N\mu_t\) operators of type \(t\), while \(q_e\) represents roughly \(Nq_e\) copies of category \(e\). This puts \(N\) well above \(\tau\) without pretending that any operator receives a fractional bundle. The mirror retains the paper’s goods, submodular valuations, feasible bundles, and welfare objective; it continuizes the population and makes the supply scaling needed for that population explicit.
I expect the general succinct-input problem to be Class C, though the paper’s particular hard family is the key case to investigate. The continuous formulation is an LP with exponentially many bundle variables. Its dual pricing task, for a type \(t\), is to maximize \(v_t(S)-\sum_{e\in S}p_e\) over bundles \(S\). Efficient pricing for the paper’s fixed-\(g\), fixed-\(s\) valuation family could make the continuous problem tractable and show that its discrete welfare hardness dissolves. For general succinct submodular valuations, that pricing task is itself a serious source of hardness, even when \(\tau=1\). Theorem 9’s approximation threshold does not by itself prove hardness for this continuous problem: mass can split across bundle choices, so its discrete reduction may lose force. The questions are whether the theorem’s valuation family admits efficient pricing, what approximation guarantees survive in the continuous problem, and whether solutions yield useful additive approximations for finite replicated auctions.
The scope here is the welfare-maximization clause of Theorem 9. It does not mirror the payment computation or the truthfulness and verification requirements. The weakest point is the replicated-supply assumption: the original theorem has a fixed set of goods, while this mirror scales category supply with the population. That is a deliberate co-modification to make a large population of bundle-receiving agents feasible. The authors should recognize the underlying welfare problem, but may judge that supply regime to be a meaningful variant rather than their own problem.
The strongest objection is that Theorem 9’s hard instances do not establish the high-multiplicity regime the proposed mirror needs. Its bidders’ valuations are built from different families \(S_i\), which carry the instance’s combinatorial information. The fact that each bidder has a polynomial-size declaration domain does not mean that many bidders share one valuation type. Replicating such an instance leaves the support size at roughly the original number of distinct bidders; grouping them into fewer types risks discarding the data behind the hardness result.
There is also a real mismatch in the resources. With \(N\) bidders and the paper’s fixed, single-copy goods, normalized per-capita supply is \(1/N\) per good. For a fixed finite set of types and bounded valuations, only \(O(1/N)\) mass can receive a nonempty bundle, so per-capita welfare tends to zero. Keeping welfare nontrivial requires scaling each good’s supply with \(N\). That is a coherent co-modification, and the programme explicitly permits it, but it moves from Theorem 9’s partition of a fixed set of goods to a replicated-capacity auction. The theorem does not show that its hard family remains hard, or even retains its relevant structure, in that regime.
Those objections weaken the claim that this is a mirror of Theorem 9’s result. They do not defeat the stronger version of the proposal. A market with many standardized operators, a small number of valuation profiles, and recurring license capacity is plausible. Its welfare problem over type masses and integral bundles is well-posed. The fact that it becomes a configuration LP with a potentially hard pricing problem is a research question, not a reason to reject it. Nor is bidder identity an objection to this welfare-only formulation: identical valuation types can be grouped when the objective and constraints use only those types.
The paper’s more distinctive mechanism results are harder to carry over: verification and truthfulness concern a named bidder’s unilateral report, and a type-level mass alone does not encode that individual incentive constraint. Theorem 6’s payment hardness, for example, already applies with two bidders and two goods, so it offers no population-multiplicity explanation for its difficulty. But the proponent explicitly chose the welfare clause of Theorem 9 as the anchor, and one good mirror is enough.
So the best negative case is that the proposed model’s link to the paper’s hard instance is unproven and requires a substantial resource-scaling assumption. It is not an honest basis for claiming that no worthwhile continuous mirror exists. The negative case is weak against the plausible replicated-market scenario.
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.