| paper | d4-conf-ijcai-2015-0680 |
| 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: Exactly polynomial-time solvable under the original supplies; therefore the requested scheme exists. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a constant number \(m\) of goods, a finite set \(T\) of bidder types with rational masses \(\mu_t\) summing to \(1\), explicitly listed integral bundles \(D_t\) with rational values \(v_t(d)\), and rational per-capita supplies \(b_\ell\), choose masses \(x_{t,d}\ge 0\) to maximize \(\sum_{t\in T}\sum_{d\in D_t}v_t(d)x_{t,d}\), subject to \(\sum_{d\in D_t}x_{t,d}\le\mu_t\) for each \(t\) and \(\sum_{t\in T}\sum_{d\in D_t}d_\ell x_{t,d}\le b_\ell\) for each good \(\ell\).
An atomless population with finitely many complete multi-minded valuation types; \(x_{t,d}\) is the mass of type \(t\) receiving integral bundle \(d\), and the objective is maximum welfare subject to type-mass and per-capita supply constraints.
The mirror covers the multi-minded welfare-allocation core of Theorem 1 under exact per-capita supply constraints. It leaves aside the finite-bidder FPTAS with supply augmentation, the truthful-mechanism guarantee, and the paper’s submodular-bidder result.
My lead is a continuous version of the multi-minded social-welfare allocation problem behind Theorem 1. The theorem, as printed, says: “Multi-unit combinatorial auctions with multi-minded bidders and a constant number of distinct goods admit a truthful FPTAS, that optimizes the social welfare fully, while violating the supplies of goods at most by a factor \((1+\epsilon)\), for any fixed \(\epsilon>0\).” The paper develops the algorithm in Section 3 and presents the result as work from Krysta et al. (2013). The nearby strong NP-hardness claim for allocations that respect supply exactly is unnumbered, so it is useful context, but not an eligible named anchor under the requested rule.
Call the mirror Continuous Multi-Minded Welfare Allocation. There are \(m\) goods, with \(m\) constant, and a finite set \(T\) of bidder types. A type \(t\) is the bidder’s complete multi-minded valuation: a finite demand set \(D_t\) of integer bundles \(d\in\mathbb{Z}_{\ge0}^m\) and a value \(v_t(d)>0\) for each demanded bundle. The input gives rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and rational per-capita supplies \(b_\ell\). For each type and demanded bundle, choose \(x_{t,d}\ge0\), the mass of type \(t\) assigned that bundle. The question is to maximize
\[
\sum_{t\in T}\sum_{d\in D_t}v_t(d)x_{t,d}
\]
subject to
\[
\sum_{d\in D_t}x_{t,d}\le\mu_t \quad(t\in T),\qquad
\sum_{t\in T}\sum_{d\in D_t}d_\ell x_{t,d}\le b_\ell \quad(\ell\in[m]).
\]
The solution is the allocation masses \(x\). Each buyer still receives an integral bundle; it is the mass of a type assigned to each option that may be fractional. Because the paper’s multi-minded valuations are monotone, assigning a superset of a demanded bundle cannot improve welfare over assigning that bundle itself, so these variables capture the relevant choices.
A plausible regime is a large procurement or licensing market with a fixed number of product categories and many similar institutional buyers. Buyers might share a type because they have the same standardized purchasing options, budgets, and valuation schedule. There could be thousands of buyers but only a modest number \(\tau=|T|\) of distinct schedules. In a growing cohort, supply can scale with the number of participating organizations, making per-capita supply a natural input. The exact repeated schedules and scaling are substantive assumptions, but they describe an instance regime rather than claiming every auction has this form.
This problem is an LP with a number of variables linear in the explicitly listed demand alternatives, so with rational input it is solvable in polynomial time. I expect Class A: the continuous allocation question is tractable. The mirror covers Theorem 1’s welfare-optimization core and its multi-minded setting; it does not claim to reproduce the theorem’s supply-augmented FPTAS for finite bidders. The paper’s finite exact-supply hardness makes the contrast worthwhile: the continuum permits splitting a large type cohort across its discrete bundle choices, removing the integer assignment constraint at the cohort level.
The weakest point is that Theorem 1 is also a truthful mechanism result, while this mirror asks for its computed allocation problem. I would not claim that truthfulness automatically carries over to an atomless population; that needs its own strategic model. The most useful follow-up questions are whether continuous solutions can be rounded for finite high-multiplicity instances with small welfare loss, how the loss depends on type counts and \(\tau\), and whether a meaningful truthful mechanism can be defined for this population model.
The best objection is that the proposed LP does not, as written, mirror Theorem 1’s distinctive result. The theorem gives a truthful auction mechanism for bidders who privately report valuations; the mirror takes the type masses and valuations as input and returns a welfare-maximizing allocation. That is a planner’s problem, with no payment rule or truthfulness claim. In an atomless population, one person’s report has zero effect on aggregate welfare and the supply constraints, so the paper’s finite-bidder VCG argument cannot simply be carried over.
That is a real gap in the proposed account, but it does not defeat the stronger mirror. For the stated LP, dual variables give prices \(p_\ell\) for goods and \(\lambda_t\) for type capacity. Every positively allocated bundle \(d\) satisfies \(v_t(d)=\lambda_t+p\cdot d\); thus it is a utility-maximizing bundle at prices \(p\), with feasible rationing among ties. An individual in an atomless population cannot change those prices by misreporting, and a fixed price menu makes truthful choice of bundle weakly dominant. This suggests a continuous truthful mechanism may be available alongside the welfare LP, rather than the strategic question being fundamentally lost.
The institutional-buyer scenario also needs repeated valuation schedules and supplies that scale with the cohort. Those are substantive assumptions, but the problem’s types can include complete valuation schedules, so they do not rule out a sensible high-multiplicity regime. Fractional mass assigned among integral bundles is a natural population model here.
So the honest negative case is weak. The exact LP is not yet a mirror of the theorem’s truthful mechanism, but the gap looks repairable, and the continuous welfare question remains well-posed. Under the programme’s standard, I cannot make the case that this anchor fails.
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.