| paper | d4-conf-wine-2021-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: \(R^*(H)=H\) for every fixed binary rational \(H>1\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
For even \(N\), let \(N/2\) suppliers occupy each role \(r\in\{A,B}\), each with cost \(1\) or \(H\), and let \(\mu_N(b)\) be the normalized distribution over role-cost types induced by report profile \(b\). The only outcomes select all of \(A\) or all of \(B\), at integrated cost \(\mathrm{SC}_{\mu_N}(x^r)=\sum_{c\in{1,H}}\mu_{N,r,c}c\)\). Determine \(R^*(H)=\inf_{(M_N)}\limsup_{N\to\infty,\,N\text{ even}}\sup_b \mathrm{SC}_{\mu_N(b)}(M_N(b))/\mathrm{OPT}(\mu_N(b))\), where each \(M_N\) is an individual-agent OSP mechanism on the finite grid and \(\mathrm{OPT}\) selects the lower-cost cohort; is \(R^*(H)=H\)?
A society is a distribution \(\mu\) over the four role-cost types \({A,B}\times{1,H}\), with each role having mass \(1/2\). Choose one whole cohort and minimize its integrated cost, while requiring each mechanism in the approximating sequence to be OSP for individual suppliers.
A native atomless protocol could have a different approximation ratio because an individual report is no longer pivotal; the proposed question covers finite-grid limits, a scope restriction the proponent acknowledges.
fatal: False
Covers Theorem 10’s social-cost lower bound for two mutually exclusive outcomes in the fixed-cost-ratio limit; it leaves the paper’s other approximation results and general set systems untouched.
The strongest honest case is narrow: a high-multiplicity version of the paper’s obvious-strategyproof procurement problem, anchored on its social-cost lower bound. The paper does not prove an NP-hardness or running-time result. Its relevant computational result is an unconditional approximation barrier.
Theorem 10 (proved here) says that for every \(\rho\ge 1\), there is a set system with exactly two feasible solutions and four agents such that no two-way greedy algorithm achieves a \(\rho\)-approximation to minimum social cost. Corollary 3, also proved here, identifies the bridge to incentives: in binary allocation problems, a mechanism is OSP exactly when its algorithm is an all-monotone, interleaving two-way greedy algorithm. Together, these results make Theorem 10 a lower bound for OSP mechanisms in that setting.
A concrete mirror is Mass-limit Two-option OSP Procurement. There are two large, mutually exclusive supplier cohorts, \(A\) and \(B\), and the feasible outcomes are to hire all of \(A\) or all of \(B\). Each supplier has private cost \(1\) or \(H>1\); their complete problem type is their cohort and cost. The society is the distribution \(\mu\) over the four types \(\{A,B\}\times\{1,H\}\), with each cohort having mass \(1/2\). The decision remains binary: choose \(x^A\) or \(x^B\), where \(x^r\) selects the whole cohort \(r\). Social cost is the integral of selected costs; for example, \(\mathrm{SC}_\mu(x^A)=\mu_{A,1}+H\mu_{A,H}\).
To retain the paper’s individual-level incentive notion, define an admissible continuous mechanism as a limit of finite OSP mechanisms on equal-mass grids: each grid has \(N/2\) agents in each cohort, each agent has mass \(1/N\), and OSP must hold at every finite \(N\). The problem is to determine the best worst-case approximation ratio \(R^*(H)\) achievable by such a mechanism family over all reported type distributions, and to produce either a family attaining that ratio or a matching lower bound. This gives a concrete target for a prover, while making explicit how the continuum protocol is defined.
The paper’s proof supports the expected answer. Its two-block construction uses cohort sizes \(s\) and \(k\) and endpoint costs with ratio \(H\). Taking \(s=k=N/2\), the proof rules out a \(\rho\)-approximation when
\[
H>\max\left\{\frac{\rho k-1}{k-1},\frac{\rho(k-1)}{k-\rho}\right\}.
\]
For fixed \(\rho\), the right side tends to \(\rho\) as \(N\) grows. Thus the scaled construction points to a limiting lower bound of \(H\). A mechanism that always chooses \(A\) is OSP and has ratio at most \(H\), so the proposed limit is \(R^*(H)=H\). This is a transfer of an approximation barrier to the grid-limit setting—not an NP-hardness claim.
The regime is plausible for choosing between two all-or-nothing production or procurement cohorts: many suppliers, few distinct cost-and-role types, and a society represented by their mass fractions. Even with many agents, the support remains at most four types. The authors should recognize the mirror: it keeps their binary allocation problem, social-cost objective, and OSP constraint, while changing the population representation.
The weakest point is the passage from finite protocols to a fluid protocol. The lower bound relies on mechanisms that query individual agents; an atomless population has no first individual of positive mass. A more permissive continuous-time or simultaneous protocol might escape the grid-limit bound. The all-or-nothing, two-cohort scenario is also deliberately restrictive. So I would expect the barrier to transfer under the stated limit definition, but the result would not settle what happens for every native notion of continuous OSP mechanism.
The proposed cohorts are a plausible high-multiplicity regime: suppliers can share a role and cost type, and the support stays small. So the objection is not that these agents cannot sensibly be grouped. It is that the paper’s central object—OSP—depends on how individuals are queried and on how one individual’s report can affect the outcome.
In an atomless version, one supplier’s report does not change the cohort’s cost mass or the choice between hiring all of \(A\) and all of \(B\). If the mechanism takes the distribution \(\mu\) as its input, it can compare the two aggregate costs, but it is no longer eliciting private types through the paper’s extensive-form mechanism. If it elicits reports from individuals, a single report has no effect on the aggregate outcome, so the individual OSP constraint loses the pivotality that makes the paper’s characterization meaningful. A protocol that instead asks a whole cohort to report its mass treats that cohort as a strategic bloc, changing the paper’s independent-agent model.
The proposed equal-mass-grid definition preserves OSP at each finite \(N\), but its mechanism still queries individual suppliers. The limit \(R^*(H)\) is therefore a limit of finite-agent approximation guarantees, not an algorithm operating on the continuous input \(\mu\). It retains \(N\) in the strategic protocol, while the distribution has only four possible types. Grouping agents by type does not remove that gap: it compresses the instance, not the sequence of individual decisions required by OSP.
Theorem 10 is the strongest anchor, and Corollary 3 explains its OSP connection. But Theorem 10 bounds the approximation quality imposed by incentive constraints; it gives no computational-complexity barrier, pricing problem, or algorithmic running-time result. That makes it a weaker fit for ChoCo’s complexity landscape. The finite-grid limit could be a legitimate asymptotic study, but it does not supply the promised continuous computational model.
A continuous model with strategic cohorts or coalition reports might be worth studying. It would need a new account of who acts, what they know, and what OSP means for a mass report. That is a different mechanism-design problem, rather than a continuous-population mirror of this paper’s individual-agent results.
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.