Answer: The worst-case approximation ratio is \(R=+\infty\), both in general and when \(m=\tau=3\), all project pairs conflict, and \(T=\{\{1\},\{2\},\{3\}\}\).
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThere exist instances of the PB game ⟨P, V, β, cost⟩such that the ratio of the optimal social wel- fare to the welfare of the Modified UG algorithm is unbounded. Specifically, for some family of instances parameterized by n = |V|, we have lim n→∞ P i∈V ui(Wopt) P i∈V ui(Wgreedy}) = ∞.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite project set, rational positive project costs, a rational budget, pairwise project conflicts, and a rational distribution \(\mu\) over approval types, does Modified UG have a finite worst-case approximation ratio for maximizing \(\operatorname{SW}_{\mu}(W)=\sum_t\mu_t|t\cap W|\)? Here \(W\) is an integral feasible project set, and Modified UG scans projects in descending order of \(\sum_{t:p\in t}\mu_t/\operatorname{cost}(p)\), adding each when feasible. In particular, does the ratio remain unbounded with three projects, all pairs conflicting, and support on three singleton approval types?
Let \(P=\{1,\ldots,m\}\), with \(m\geq1\), positive binary-rational costs \(c_p\), positive binary-rational budget \(B\), and a simple undirected conflict graph \(G\) on \(P\). An integral allocation \(W\subseteq P\) is feasible if it is independent in \(G\) and \(\sum_{p\in W}c_p\leq B\).
A society is given by its support: a list \(T\subseteq2^P\) of \(\tau\geq1\) approval types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval types. Let \(L\) be the total input bit length; express any running times in \(m,\tau,L\).
Define \(\operatorname{SW}_{\mu}(W)=\sum_{t\in T}\mu_t|t\cap W|\). Modified UG starts with the empty allocation, scans every project once in nonincreasing order of \(\bigl(\sum_{t\in T:p\in t}\mu_t\bigr)/c_p\), breaks ties by increasing project index, and adds a project precisely when the resulting allocation is feasible.
Let \(W_G\) be its output and \(\operatorname{OPT}_{\mu}=\max_{W\text{ feasible}}\operatorname{SW}_{\mu}(W)\). Define its worst-case approximation ratio as \(R=\sup_{\operatorname{OPT}_{\mu}>0}\operatorname{OPT}_{\mu}/\operatorname{SW}_{\mu}(W_G)\), interpreting a zero denominator as \(+\infty\).
Is \(R\) finite, or is it unbounded? Does the same dichotomy yield a finite or unbounded ratio when \(m=\tau=3\), all project pairs conflict, and \(T=\{\{1\},\{2\},\{3\}\}\)?
For finite approval electorates, Modified UG has an unbounded approximation ratio, already with three mutually conflicting projects and singleton approvals. [Damle and Faltings](https://arxiv.org/html/2508.06060v1#A3.SS1)
No result settling this exact distributional approximation question was identified in the literature search.
The worst-case ratio is \(R=+\infty\), both in general and under the stated restriction \(m=\tau=3\). The following family proves this using strictly positive dyadic rational masses and costs.
\(P=\{1,2,3\}\), \(G=K_3\), \(B=1\), and \(T=\{\{1\},\{2\},\{3\}\}\). Choose
\[
\]
\(c_1=\varepsilon,\qquad c_2=c_3=1,\)
\(\mu_{\{1\}}=\varepsilon,\qquad \mu_{\{2\}}=\frac12,\qquad \mu_{\{3\}}=\frac12-\varepsilon.\)
Since \(0<\varepsilon\leq\frac14\), all costs and masses are strictly positive binary rationals. The masses sum to \(1\), so the support size is exactly \(\tau=3\). Every singleton is affordable. Because every project pair conflicts, the feasible allocations are precisely \(\varnothing,\{1\},\{2\},\{3\}\).
\(\frac{\mu_{\{1\}}}{c_1}=1,\qquad \frac{\mu_{\{2\}}}{c_2}=\frac12,\qquad \frac{\mu_{\{3\}}}{c_3}=\frac12-\varepsilon.\)
These densities are strictly decreasing, so Modified UG scans projects in the order \(1,2,3\), independently of its tie-breaking rule. It accepts project \(1\), which is affordable. It then rejects both remaining projects because each conflicts with project \(1\). Thus
\(W_G=\{1\},\qquad \operatorname{SW}_{\mu}(W_G)=\varepsilon.\)
The welfare of a singleton \(\{p\}\) is exactly \(\mu_{\{p\}}\). Among the four feasible allocations, \(\{2\}\) has the largest welfare: its value is \(\frac12\), whereas the others have values \(0,\varepsilon,\frac12-\varepsilon\). Consequently,
\(\operatorname{OPT}_{\mu}=\frac12,\qquad \frac{\operatorname{OPT}_{\mu}}{\operatorname{SW}_{\mu}(W_G)}=\frac{1}{2\varepsilon}=2^{k-1}.\)
For every finite positive bound \(C\), an integer \(k\geq2\) can be chosen with \(2^{k-1}>C\). Hence the restricted class already has unbounded ratio. Since that class is contained in the general class, the general ratio is also unbounded. Throughout this family, \(m=\tau=3\); only the numerical input length grows, with \(L=\Theta(k)\) under standard binary rational encoding.
This explains why the finite-electorate obstruction in [Damle and Faltings, Appendix C.1](https://arxiv.org/html/2508.06060v1#A3.SS1) carries over to rational distributions. The explicit construction above verifies the conclusion directly under every hypothesis of this question.
⟨structured verdict parsed — rendered above⟩
The output proves both requested conclusions: the general worst-case ratio is unbounded, and it remains unbounded under the exact restriction \(m=\tau=3\). No mathematical gaps or false steps were found.
The parameter range \(k\geq2\) gives \(0<\varepsilon=2^{-k}\leq\frac14\). Consequently, every specified cost and mass is a strictly positive dyadic rational, including \(\mu_{\{3\}}=\frac12-\varepsilon\geq\frac14\). The masses sum exactly to \(1\). The three approval types are distinct and have positive masses, so the support size is exactly \(\tau=3\).
With \(B=1\), each singleton is affordable, including the two projects whose costs equal the budget. The complete conflict graph excludes every allocation containing two or more projects. Thus the stated list of four feasible allocations is exhaustive.
Singleton approvals make each project's approval mass exactly its corresponding type mass. The three computed densities are correct and satisfy
\(1>\frac12>\frac12-\varepsilon\).
Hence the scan order is uniquely determined, with no dependence on tie-breaking.
Project \(1\) is accepted because its singleton is feasible. Each subsequent project conflicts with the accepted project, so both are rejected. The claimed output \(W_G=\{1\}\) and welfare \(\operatorname{SW}_{\mu}(W_G)=\varepsilon\) follow directly from the specified algorithm.
The welfare values listed for all four feasible allocations are correct. Since \(\varepsilon\leq\frac14<\frac12\) and \(\varepsilon>0\), project \(2\) has strictly greater welfare than either other singleton. Therefore \(\operatorname{OPT}_{\mu}=\frac12>0\).
The denominator is strictly positive throughout the family, and the ratio calculation
\(\operatorname{OPT}_{\mu}/\operatorname{SW}_{\mu}(W_G)=1/(2\varepsilon)=2^{k-1}\)
is exact. The argument does not rely on the zero-denominator convention.
The quantified statement about every finite positive bound is sufficient to establish an infinite supremum. Every instance in the family satisfies the restricted question. Since these instances also belong to the general class, the conclusion transfers to that class.
Keeping \(m=\tau=3\) while allowing numerical input length to grow is permitted by the task. The claim \(L=\Theta(k)\) is correct under conventional explicit binary numerator/denominator or finite binary-expansion encodings. No algorithmic running time is claimed, so no running-time requirement remains unmet.
The normalization argument is sound: a common denominator gives positive integral voter counts whose sum is \(D\). Welfare and all project densities scale by the same positive factor, preserving comparisons, ties, the scan order, feasibility decisions, and welfare ratios.
The cited [Appendix C.1](https://arxiv.org/html/2508.06060v1#A3.SS1) does present a finite-electorate unboundedness construction with three mutually conflicting projects and singleton approvals. The submitted distributional construction establishes the target independently, so its correctness does not depend on importing the cited proof.
Repair feedback: No additional mathematical clarification or repair is needed. This establishes an approximation-ratio result; it does not establish a computational complexity classification.
⟨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.