| paper | d4-conf-sagt-2020-0011 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
For \(\epsilon>0\), admissible \(m,k\) with \(k\mid m\), and \(\rho>1-\frac{1}{2k}\), consider societies with \(\tau=m/k\) complete submodular valuation types, each of mass \(\mu_t=1/\tau\), and per-capita supply \(b_j=1/\tau\) for each of \(m\) item categories. Each unit of mass must receive an integral bundle \(S\subseteq M\), while the allocation variables \(x_{t,S}\) may be fractional and satisfy \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:\,j\in S}x_{t,S}\le b_j\). Given value-oracle access to each \(v_t\), and restricting to instances with a unique optimum unchanged after any submass \(\delta\) of a type is split off and its value for one item is inflated by the paper’s \((2-\epsilon)\)-perturbation, must every algorithm use at least \(\binom{m}{k}\) queries in the worst case to return a feasible allocation with welfare at least \(\rho\) times optimal?
A configuration allocation over type masses: \(x_{t,S}\) is the mass of type \(t\) receiving integral bundle \(S\), feasibility respects per-capita supplies \(b_j\), and welfare is \(\sum_{t,S}x_{t,S}v_t(S)\). Stability applies when a submass \(\delta\) is split off and one item value is inflated.
Theorem 2 does not establish that the split-mass stability promise holds for its hard instances or that fractional assignments preserve the value-query lower bound.
fatal: False
The mirror covers Theorem 2’s value-query lower bound for stable submodular welfare approximation; it leaves the paper’s algorithm, equilibrium, mechanism-design, and price-of-anarchy results aside.
My lead is Continuous Stable CA Welfare Approximation, a high multiplicity version of the paper’s social welfare problem. The setting is a large procurement market for standardized resource lots: there are \(m\) item categories and many buyers, but only \(\tau\) distinct purchasing types. A type is a complete valuation function over bundles, with all other relevant buyer properties held fixed. Think of many branches or firms following the same purchasing template. The number \(N\) of buyers can be much larger than \(\tau\).
Normalize the population to mass \(1\). The instance gives rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and rational per capita supply \(b_j\) for each item \(j\). Let \(x_{t,S}\) be the mass of type \(t\) assigned the integral bundle \(S\subseteq M\). Feasibility and welfare are
\[ \sum_{S\subseteq M}x_{t,S}=\mu_t,\qquad \sum_{t,S:\,j\in S}x_{t,S}\le b_j,\qquad x_{t,S}\ge 0, \]
\[ W(x)=\sum_{t,S}x_{t,S}v_t(S). \]
Thus each individual receives an integral bundle, while a type’s mass can be split across bundles. The algorithm gets value-oracle access to each \(v_t\) and must return a feasible allocation \(x\) with the requested welfare guarantee. This is the population analogue of the auction’s underlying allocation problem; the computational question is about welfare approximation, not about an encoding.
My anchor is Theorem 2, proved in this paper. It says that for every \(\epsilon>0\), there is a submodular \((2-\epsilon)\)-stable valuation profile such that, for every integer \(k\ge 1\), approximating its optimal allocation within any factor greater than \(1-\frac{1}{2k}\) requires at least \(\binom{m}{k}\) value queries. This is a value-oracle lower bound, not an NP-hardness result. Its hard instances hide a bundle \(O\) among the \(k\)-item subsets: discovering \(O\) is what lets the allocation beat the value achieved by assigning other bundles of size \(k\).
The continuous problem I would hand to a prover is: for fixed \(\epsilon>0\), integer \(k\mid m\), and target ratio \(\rho>1-\frac{1}{2k}\), determine whether every value-query algorithm for Continuous Stable CA Welfare Approximation needs at least \(\binom{m}{k}\) queries in the worst case on \((2-\epsilon)\)-stable instances with \(\tau=m/k\). In the corresponding regime, take equal masses \(\mu_t=1/\tau\) and per capita supplies \(b_j=1/\tau\). If each type is repeated \(R\) times, then \(N=R\tau\): population size can grow while the number of valuation types stays fixed for that instance. These masses and capacities are the normalized form of the paper’s \(m/k\)-bidder construction.
For stability in this population model, I would require that the unique optimal aggregate allocation remains unchanged if any mass \(\delta\) of one type is split off and its per capita valuation for one item is inflated by the paper’s rule,
\(v'_t(S)=v_t(S)+(\gamma-1)v_t(S\cap\{j\})\). The optimal plan is compared after merging the split type labels back together. This makes perturbation stability meaningful for a population: perturbing one named buyer of zero mass would have no effect on the aggregate problem.
I expect hardness to transfer in the value-oracle sense. The concealed structure is in the bundle universe and the valuation functions, not in the number of copies of each type; repeating buyers does not reveal the hidden bundles. A direct proof still has to show that allowing fractional type mass across integral bundles does not evade the query lower bound. Further questions are whether the lower bound survives that fractional allocation, whether stronger access such as demand queries changes it, and whether the apparent boundary near stability factor \(2\) persists in the population model.
The weakest point is the adaptation of the stability promise and of the lower-bound construction. Theorem 2 perturbs named bidders and studies discrete allocations; it does not prove the stated result for cohort masses and fractional aggregate plans. The population version also assumes supply scales with market size, which suits recurring or replicated lots but may not fit a one-off auction of a fixed scarce stock. Still, this is a focused weakness: the proposed mirror preserves the paper’s welfare objective, bundle valuations, and stability idea, and puts its hidden-bundle hardness question directly into a high multiplicity regime. I would limit the mirror to Theorem 2’s welfare result; this does not attempt to continuize the paper’s mechanism-design, equilibrium, or price-of-anarchy results.
The strongest objection to this anchor is that Theorem 2 is about indivisible allocations to named bidders, while the proposed mirror is a configuration LP: each type’s mass can be split across bundles. The paper’s argument that an algorithm must discover each hidden bundle \(O_i\) does not establish a lower bound for that LP. Fractional assignments may change what can be achieved without finding every \(O_i\), and the paper’s bidderwise stability promise does not establish stability when an arbitrary mass \(\delta\) is split off as a new type. The proposed query lower bound therefore needs a new proof.
There is also a gap in the scenario. In the construction, each of the \(\tau=m/k\) types is built around a particular hidden bundle. Repeating each type \(R\) times creates many agents, but does not make those adversarial valuation types more representative of a recurring procurement market. The hard part remains hidden in the valuation oracles. That weakens the case for this particular example as a motivating application.
Neither point defeats the better mirror, though. A population of firms sharing complete purchasing templates is a sensible high-multiplicity regime, and the configuration-LP question is well-posed. Whether fractional mass assignments erase the lower bound is precisely a computational question worth asking; a different answer from the discrete theorem would be a meaningful result. The paper also plainly has named computational results, so absence of an anchor is not available as an objection.
I can’t make an honest universal case that this paper has no worthwhile continuous mirror. The strongest negative case is that the proposed transfer from Theorem 2 is unproved and its motivating scenario is thin. Those are reasons to be cautious about this anchor, but they do not rule out the mirror—the central uncertainty they identify is itself worth studying.
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.