Answer: \(R^*(H)=H\) for every fixed binary rational \(H>1\).
Theorem 10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any ρ ≥1, there exists a set system such that no two-way greedy algorithm returns a ρ-approximation to the optimal social cost, even if there are only two feasible solutions and four agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\)?
Fix a binary rational \(H>1\), independent of population size. There are \(m=2\) public roles, \(A\) and \(B\). For every even \(N\ge4\), each role contains \(N/2\) individually identified suppliers, each with private cost in \(\{1,H\}\).
A society is represented by its support: the list of \(\tau\) role-cost types with positive mass, each mass a binary rational. Here \(\tau\le4\) is the support size, and \(L\) is the total input bit length; masses sum to \(1\), with mass \(1/2\) in each role. State any running times in \(m,\tau,L,N\).
For a report profile \(b\in\{1,H\}^N\), define \(\mu_{N,r,c}(b)=N^{-1}|\{i:r_i=r,\ b_i=c\}|\). The only feasible allocations are \(x^A\) and \(x^B\), selecting every supplier in the indicated role. Define \(\mathrm{SC}_{\mu}(x^r)=\sum_{c\in\{1,H\}}\mu_{r,c}c\) and \(\mathrm{OPT}(\mu)=\min_{r\in\{A,B\}}\mathrm{SC}_{\mu}(x^r)\).
An admissible \(M_N\) is a deterministic finite extensive-form mechanism: each query partitions one supplier's currently compatible cost domain, and each leaf specifies a feasible allocation and real payments. Supplier \(i\)'s utility is \(p_i-t_i x_i\); payments have no sign, budget, or individual-rationality restrictions.
OSP means that at every query to supplier \(i\), for any two compatible profiles \((t_i,b_{-i})\) and \((d_i,b'_{-i})\) taking different branches, \(p_i(t_i,b_{-i})-t_i x_i(t_i,b_{-i})\ge p_i(d_i,b'_{-i})-t_i x_i(d_i,b'_{-i})\). Mechanisms know \(N,H\) and roles, but learn costs only through individual queries; the realized mass distribution is not supplied to them. No anonymity or computational restriction is imposed.
Define \(R^*(H)=\inf_{(M_N)}\limsup_{N\to\infty,\ N\text{ even}}\sup_{b\in\{1,H\}^N}\mathrm{SC}_{\mu_N(b)}(M_N(b))/\mathrm{OPT}(\mu_N(b))\), where the infimum ranges over admissible OSP mechanism sequences and \(M_N(b)\) denotes their allocation.
Determine \(R^*(H)\): is \(R^*(H)=H\) for every binary rational \(H>1\), or can it be strictly smaller?
For discrete set-system procurement, deterministic OSP mechanisms have no uniform constant approximation as population size and cost domains vary. A later full version gives, for two disjoint equal-size feasible cohorts, impossibility of every ratio \(\rho<N/2\) for suitable cost domains ([Ferraioli–Penna–Ventre](https://kclpure.kcl.ac.uk/portal/files/344119035/2waygreedy-OSP.pdf)).
No result settling this fixed-\(H\), normalized-grid asymptotic question was located.
Result
For every fixed binary rational \(H>1\),
\(\boxed{R^*(H)=H}\).
More precisely, writing \(n=N/2\), every admissible deterministic OSP mechanism satisfies
\[
\sup_b\frac{\mathrm{SC}_{\mu_N(b)}(M_N(b))}{\mathrm{OPT}(\mu_N(b))}
\ge \frac{nH}{n+H-1}.
\]
Below, all displayed mathematics uses the requested inline delimiters.
1. A consequence of the OSP inequalities
Consider a query separating supplier \(i\)'s compatible costs \(1\) and \(H\). There cannot exist two profiles compatible with this query such that:
Indeed, let \(P=p_i(b^\ell)\) and \(Q=p_i(b^h)\). Applying OSP with true cost \(1\), truthful profile \(b^\ell\), and alternative profile \(b^h\), gives
\(P\ge Q-1\).
Applying OSP in the reverse direction, with true cost \(H\), gives
\(Q-H\ge P\).
Consequently,
\(Q-H\ge P\ge Q-1\),
which implies \(H\le1\), a contradiction. This argument permits arbitrary real payments.
Thus, at such a query, at least one of the following statements holds:
Because the only feasible allocations select an entire role, either statement fixes the allocation throughout the corresponding report branch.
2. A finite-population lower bound
Fix an admissible OSP mechanism \(M_N\), and let \(n=N/2\).
If the mechanism never makes an informative query, every profile follows the same history and receives the same allocation. Giving all suppliers in the selected role cost \(H\), and all suppliers in the other role cost \(1\), produces ratio \(H\).
Otherwise, consider its first informative query. All profiles reach this node: preceding queries, if any, have not distinguished any costs. The queried supplier \(i\) therefore has compatible domain \(\{1,H\}\), and every other supplier's cost remains unrestricted.
Let \(R\) be \(i\)'s role and \(S\) the other role. By Section 1, at least one of the following cases applies.
Case I: Every profile with \(b_i=1\) selects role \(R\).
Choose a profile with \(b_i=1\), all other suppliers in \(R\) having cost \(H\), and every supplier in \(S\) having cost \(1\). The mechanism selects \(R\), and
\(\mathrm{SC}_{\mu_N(b)}(x^R)=[1+(n-1)H]/N\),
whereas
\(\mathrm{SC}_{\mu_N(b)}(x^S)=n/N\).
Since \(1+(n-1)H>n\), the optimal allocation is \(x^S\). The resulting ratio is
\(a_n=[1+(n-1)H]/n=H-(H-1)/n\).
Case II: Every profile with \(b_i=H\) selects role \(S\).
Choose a profile with \(b_i=H\), all other suppliers in \(R\) having cost \(1\), and every supplier in \(S\) having cost \(H\). The mechanism selects \(S\), and
\(\mathrm{SC}_{\mu_N(b)}(x^S)=nH/N\),
whereas
\(\mathrm{SC}_{\mu_N(b)}(x^R)=[H+n-1]/N\).
The difference between the corresponding unnormalized costs is
\(nH-(H+n-1)=(n-1)(H-1)>0\).
Hence the optimal allocation is \(x^R\), and the ratio is
\(c_n=nH/(n+H-1)\).
Finally,
\(a_n-c_n=(n-1)(H-1)^2/[n(n+H-1)]>0\).
Therefore, in either case,
\(\displaystyle \sup_b\frac{\mathrm{SC}_{\mu_N(b)}(M_N(b))}{\mathrm{OPT}(\mu_N(b))}\ge\frac{nH}{n+H-1}=\frac{NH}{N+2(H-1)}\).
These witnesses use only three positive role-cost masses, namely \(1/N\), \((n-1)/N\), and \(1/2\). Thus the lower bound already holds on the normalized grid with support size \(\tau=3\).
3. Matching upper bound and asymptotic conclusion
For every report profile and either role \(r\), the role's mass is \(1/2\) and its suppliers' costs lie in \(\{1,H\}\). Therefore
\(1/2\le\mathrm{SC}_{\mu_N(b)}(x^r)\le H/2\).
It follows that every feasible allocation has approximation ratio at most \(H\).
An admissible OSP sequence exists: for every \(N\), use a mechanism with no queries, always select \(A\), and pay every supplier zero. OSP is vacuous for this mechanism, and its worst-case ratio is exactly \(H\).
For any admissible OSP sequence, define
\(q_N=\sup_b\mathrm{SC}_{\mu_N(b)}(M_N(b))/\mathrm{OPT}(\mu_N(b))\).
The preceding bounds give
\(\displaystyle \frac{NH}{N+2(H-1)}\le q_N\le H\).
Because \(H\) is fixed independently of \(N\), the lower bound tends to \(H\). Hence \(q_N\) converges to \(H\) along even population sizes for every admissible OSP sequence. Taking the infimum of their limit superiors proves
\(\boxed{R^*(H)=H}\).
4. Running time
With \(m=2\) and \(H\) fixed, the attaining mechanism makes zero cost queries and specifies its selected role in \(O(1)\) time. Explicitly outputting all allocation entries and zero payments takes \(O(N)\) time. Both bounds are independent of the society's support size \(\tau\) and input length \(L\); the mechanism does not receive the society's masses.
⟨structured verdict parsed — rendered above⟩
The claimed result is proved. The OSP implication, finite-population lower bound, and limiting argument are valid under the stated mechanism model. No mathematical gaps or false statements were found.
The proof addresses precisely the fixed-\(H\) question defining \(R^*(H)\). It applies to arbitrary deterministic finite extensive-form mechanisms satisfying the given OSP inequalities, without assuming anonymity, computational efficiency, restricted payments, or knowledge of the realized masses.
Using the first informative query is legitimate. Before that query, no supplier’s two possible costs have been separated. Since the mechanism is deterministic and obtains costs only through individual queries, every report profile reaches the same node. Consequently, all suppliers’ costs remain unrestricted there.
If there is no informative query, every profile reaches the same leaf and receives the same allocation. The stated adversarial profile then gives ratio exactly \(H\).
Suppose two profiles compatible with the same query have the asserted outcomes: supplier \(i\) is unselected when reporting \(1\), and selected when reporting \(H\).
Writing their payments as \(P\) and \(Q\), respectively, the two applications of the stipulated OSP condition give exactly
\[
P\ge Q-1,\qquad Q-H\ge P.
\]
Thus \(Q-H\ge Q-1\), contradicting \(H>1\). Both profiles take different branches, so the hypotheses of the OSP inequalities are satisfied.
The resulting dichotomy is logically correct. If there exists an unselected compatible profile with report \(1\), there can be no selected compatible profile with report \(H\). Otherwise, every compatible profile with report \(1\) selects \(i\).
Because the feasible allocations select entire roles, selection of \(i\) forces allocation \(x^R\), while nonselection forces allocation \(x^S\). Accordingly, one entire report branch has the allocation claimed in the proof. Arbitrary real payments do not affect this conclusion.
Here \(n=N/2\ge2\), so every strict inequality using \(n-1>0\) is justified.
In Case I, the selected role has unnormalized cost \(1+(n-1)H\), and the other role has cost \(n\). Their difference is \((n-1)(H-1)>0\). The claimed ratio
\[
a_n=H-\frac{H-1}{n}
\]
is correct.
In Case II, the selected role has unnormalized cost \(nH\), and the other role has cost \(H+n-1\). The displayed difference \((n-1)(H-1)\) is correct and positive. The claimed ratio
\[
c_n=\frac{nH}{n+H-1}
\]
is therefore correct.
The comparison also checks:
\[
a_n-c_n=\frac{(n-1)(H-1)^2}{n(n+H-1)}>0.
\]
Hence either branch condition supplies a profile with ratio at least \(c_n\). The cases need not be mutually exclusive; their exhaustiveness suffices.
The mechanism with no informative queries also satisfies this lower bound, since its ratio is \(H\ge c_n\). Substituting \(n=N/2\) correctly gives
\[
c_n=\frac{NH}{N+2(H-1)}.
\]
Both constructed profiles have exactly three positive role-cost masses: \(1/N\), \((n-1)/N\), and \(1/2\). These sum to \(1\), give each role mass \(1/2\), and correspond to actual profiles with individually identified suppliers. Thus the support-size claim is valid.
Each role has mass \(1/2\), and every cost lies between \(1\) and \(H\). Therefore each feasible social cost lies between \(1/2\) and \(H/2\), establishing the universal ratio bound \(H\).
The proposed constant-allocation mechanism is admissible: it has a single leaf, selects a feasible role, and assigns permitted real payments. With no queries, OSP is vacuous. Its worst-case ratio is exactly \(H\).
For every admissible mechanism sequence, the bounds
\[
\frac{NH}{N+2(H-1)}\le q_N\le H
\]
hold at every even \(N\ge4\). Because \(H\) is fixed, the lower bound converges to \(H\). The conclusion that every such sequence has \(q_N\to H\) follows directly.
The infimum over sequences is therefore handled correctly. The argument neither exchanges incompatible quantifiers nor assumes that the same adversarial profile works for different mechanisms.
The running-time statements are appropriate for the specified attaining mechanism: choosing a fixed role requires \(O(1)\) time, while explicitly producing \(N\) allocation entries and payments requires \(O(N)\) time. Independence from \(\tau\) and \(L\) is justified because the mechanism does not receive the society representation.
The established result is an optimal asymptotic approximation guarantee under OSP. It does not assert a polynomial-time exact solution or a computational hardness classification. Accordingly, the requested continuous-status label is other.
No repairs or additional clarification are needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.