Answer: Polynomial-time solvable
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe set of alternatives Ct chosen by Algorithm 4 at round t is exactly the set of alternatives that can be chosen at round t by Algorithm 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
At round \(t\), given a finite alternative set \(A_t\), a rational distribution \(\mu\) over observable types \(\theta\), and for each type a common accrued utility \(u_\theta\) and current valuation vector \(v^t_\theta\), compute the exact set \(C_t^\infty\) of alternatives \(a\) for which there exist \(x_\theta\in(0,1]\) and \(y_\theta\in\mathbb{R}\) for zero-utility types such that \(a\) maximizes \(\sum_{u_\theta>0}\mu_\theta v^t_\theta(b)/u_\theta+\sum_{u_\theta=0}\mu_\theta(x_\theta/\varepsilon+y_\theta)v^t_\theta(b)\) over \(b\in A_t\), equivalently by testing unboundedness of the grouped LP for each \(a\).
At a fixed round \(t\), let \(A_t\) be an explicitly listed, nonempty set of \(m\) alternatives. A society is given by its support: a list \(\Theta\) of \(\tau\) types with positive binary rational masses \(\mu_\theta\), where \(\sum_{\theta\in\Theta}\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a common accrued utility before this round \(u_\theta\in\mathbb Z_{\ge0}\) and current valuations \(v^t_\theta(b)\in\mathbb Z_{\ge0}\) for every \(b\in A_t\), all encoded in binary. Let \(L\) be the total input bit length and \(Z=\{\theta:u_\theta=0\}\).
For each \(\theta\in Z\), choose real numbers \(x_\theta\in(0,1]\) and \(y_\theta\in\mathbb R\), common to the entire type. Define \(S_{x,y}(b)=\sum_{\theta\notin Z}\mu_\theta v^t_\theta(b)/u_\theta+\sum_{\theta\in Z}\mu_\theta(x_\theta/\varepsilon+y_\theta)v^t_\theta(b)\).
The formal infinitesimal \(\varepsilon\) orders these scores lexicographically: compare the coefficient of \(\varepsilon^{-1}\) first, then the constant coefficient. Define \(C_t^\infty=\{a\in A_t:\exists(x,y)\ \forall b\in A_t,\ S_{x,y}(a)\ge S_{x,y}(b)\}\). Tied maximizers are included; empty sums are zero.
Is computing the exact set \(C_t^\infty\) possible in polynomial time in \(m,\tau,L\), or is deciding membership \(a\in C_t^\infty\) NP-hard?
For finitely many individual agents, the entire analogous proportional-fair choice set is computable in polynomial time by one LP unboundedness test per alternative; this equals the set obtainable by the infinitesimal weights above ([verified full version](https://www.rupertfreeman.com/fair_social_choice_full.pdf)).
No prior result settling this exact distribution-over-types problem was located in the search.
The exact set \(C_t^\infty\) is computable in polynomial time in \(m,\tau,L\). For each alternative, membership reduces to one rational LP feasibility test with at most \(2\tau\) variables.
The finite-agent unboundedness formulation appears in Algorithm 4 and Theorem 2 of the [cited full version](https://www.rupertfreeman.com/fair_social_choice_full.pdf). The proof below establishes the result directly for the given type-level definition, without expanding rational masses into individual agents.
Fix \(a\in A_t\), and let \(k=|Z|\). For each \(b\in A_t\), define the vector \(d_b\in\mathbb Q^k\) and constant \(c_b\in\mathbb Q\) by
\(\displaystyle d_{b,\theta}=\mu_\theta\bigl(v^t_\theta(a)-v^t_\theta(b)\bigr)\qquad(\theta\in Z),\)
\(\displaystyle c_b=\sum_{\theta\notin Z}\frac{\mu_\theta}{u_\theta}\bigl(v^t_\theta(a)-v^t_\theta(b)\bigr).\)
Every denominator \(u_\theta\) in this sum is positive, by the definition of \(Z\).
For any permitted vectors \(x,y\), the score difference is
\(\displaystyle S_{x,y}(a)-S_{x,y}(b)=\frac{d_b\cdot x}{\varepsilon}+c_b+d_b\cdot y.\)
Consequently, \(a\in C_t^\infty\) precisely when there exist \(x\in(0,1]^k\) and \(y\in\mathbb R^k\) such that, for every \(b\),
\(\displaystyle d_b\cdot x\ge 0,\qquad d_b\cdot x=0\ \Longrightarrow\ c_b+d_b\cdot y\ge 0.\)
If \(k=0\), these conditions reduce to \(c_b\ge 0\) for every \(b\). This case is decided by exact rational comparisons. Henceforth assume \(k>0\).
For the fixed alternative \(a\), consider the following system in unrestricted real vectors \(h,q\in\mathbb R^k\):
\(\displaystyle h_\theta\ge 1\qquad\text{for every }\theta\in Z,\)
\(\displaystyle d_b\cdot h\ge 0\qquad\text{for every }b\in A_t,\)
\(\displaystyle c_b+d_b\cdot q\ge 0\qquad\text{for every }b\in A_t.\)
This is a rational linear feasibility problem with \(2k\) variables and \(k+2m\) inequalities.
Claim. This system is feasible if and only if \(a\in C_t^\infty\).
Suppose \(x,y\) witness \(a\in C_t^\infty\). Since \(Z\) is finite and every coordinate of \(x\) is positive,
\(\displaystyle \eta=\min_{\theta\in Z}x_\theta>0.\)
Set \(h=x/\eta\). Then \(h_\theta\ge 1\), and \(d_b\cdot h\ge 0\) for every \(b\).
To construct \(q\), write
\(\displaystyle \alpha_b=d_b\cdot x,\qquad \beta_b=c_b+d_b\cdot y.\)
The lexicographic conditions give \(\alpha_b\ge 0\) and, whenever \(\alpha_b=0\), also \(\beta_b\ge 0\).
Choose the finite real number
\(\displaystyle K=\max\left(\{0\}\cup\left\{-\frac{\beta_b}{\alpha_b}:b\in A_t,\ \alpha_b>0\right\}\right),\)
and set \(q=y+Kx\). For every alternative \(b\),
\(\displaystyle c_b+d_b\cdot q=\beta_b+K\alpha_b.\)
If \(\alpha_b=0\), this equals \(\beta_b\ge 0\). If \(\alpha_b>0\), the definition of \(K\) makes it nonnegative. Thus all inequalities of the LP hold.
This step uses the explicit finiteness of \(A_t\): a single finite \(K\) handles all comparisons.
Conversely, suppose \(h,q\) satisfy the LP. Define
\(\displaystyle H=\max_{\theta\in Z}h_\theta,\qquad x=h/H,\qquad y=q.\)
Because every \(h_\theta\ge 1\), we have \(H\ge 1\) and \(0<x_\theta\le 1\).
For each \(b\),
\(\displaystyle d_b\cdot x=\frac{d_b\cdot h}{H}\ge 0.\)
If this is positive, the leading coefficient makes \(S_{x,y}(a)>S_{x,y}(b)\). If it is zero, the LP gives
\(\displaystyle c_b+d_b\cdot y=c_b+d_b\cdot q\ge 0.\)
Therefore \(S_{x,y}(a)\ge S_{x,y}(b)\) lexicographically for every \(b\), including equality where appropriate. These vectors witness \(a\in C_t^\infty\), completing the equivalence.
All coefficients are computable exactly with polynomially many bit operations.
To check their sizes explicitly, write each input mass as \(\mu_\theta=p_\theta/r_\theta\). Each coordinate \(d_{b,\theta}\) is formed from one rational mass and one difference of binary integers, so its encoding length is polynomial in \(L\).
For \(c_b\), a common denominator is
\(\displaystyle Q=\prod_{\theta\notin Z}r_\theta u_\theta,\)
with empty product equal to \(1\). Its bit length is bounded by the sum of the bit lengths of these input factors, hence is \(O(L)\). After bringing the summands to this denominator, their integer numerators and their sum also have polynomial bit length. Thus the entire LP has encoding length polynomial in \(m,\tau,L\).
We apply the standard polynomial-time feasibility theorem for rational linear programming: a finite system of rational linear inequalities can be decided in time polynomial in its encoding length. Its hypotheses hold here; no boundedness assumption is required, and all inequalities are non-strict.
For every explicitly listed \(a\), either perform the direct comparisons when \(Z\) is empty or solve the LP above. Collect exactly those alternatives that pass. There are \(m\) tests, each of polynomial size, so this computes the exact set \(C_t^\infty\) in polynomial time.
Every variable is indexed by a type. The constructions therefore respect the requirement that weights be common to the entire type, regardless of the binary-encoded masses.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct. The LP equivalence is rigorous, and the encoding argument establishes polynomial running time for the explicitly listed support. No major or minor mathematical issues were found.
The definitions of \(d_b\) and \(c_b\) correctly give
\[
S_{x,y}(a)-S_{x,y}(b)=\frac{d_b\cdot x}{\varepsilon}+c_b+d_b\cdot y.
\]
Every denominator appearing in \(c_b\) is positive: the task assumes nonnegative accrued utilities, and \(\theta\notin Z\) means \(u_\theta\ne0\).
The stated membership conditions are exactly the lexicographic comparison rule. A negative leading coefficient loses regardless of the constant coefficient; a positive leading coefficient wins; a zero leading coefficient requires a nonnegative constant coefficient. Non-strict inequalities correctly include ties.
When \(k=0\), the permitted vectors are empty, and membership reduces to the stated comparisons \(c_b\ge0\). This case is handled correctly.
The proposed system has \(2k\) real variables and \(k+2m\) non-strict rational inequalities, as claimed. Both vectors are unrestricted except for their displayed constraints.
Although the constraints on \(q\) require nonnegative constant expressions for every alternative, this strengthening is justified by the forward implication below.
Because \(k>0\) is finite and every coordinate of \(x\) is positive, \(\eta=\min_{\theta\in Z}x_\theta\) exists and is strictly positive. Consequently, \(h=x/\eta\) satisfies both \(h_\theta\ge1\) and \(d_b\cdot h\ge0\).
The construction of \(K\) is valid:
For \(q=y+Kx\), the identity
\[
c_b+d_b\cdot q=\beta_b+K\alpha_b
\]
is correct. When \(\alpha_b=0\), membership already gives \(\beta_b\ge0\). When \(\alpha_b>0\), the defining bound on \(K\) gives the required nonnegativity.
The same \(q\) works simultaneously for every alternative. No rationality or polynomial-size requirement on these particular witness vectors is needed for this logical implication.
Since every \(h_\theta\ge1\), the finite maximum \(H\) is positive. Thus \(x=h/H\) satisfies \(0<x_\theta\le1\).
Positive rescaling preserves the sign and zero status of each \(d_b\cdot h\). A positive leading coefficient wins lexicographically; a zero leading coefficient is accompanied by the nonnegative constant expression supplied by the \(q\)-constraints. Taking \(y=q\) therefore gives a valid membership witness.
All constructed coordinates remain indexed by types, so the requirement of common weights within each type is respected.
The coefficient-size argument is sound. Each valuation difference has polynomial bit length, and multiplication by its input rational mass preserves a polynomial bound.
For \(c_b\), the displayed product \(Q\) is a valid common denominator. Its bit length is bounded by the total bit length of the denominator and accrued-utility factors, hence by \(O(L)\). The corresponding numerators and their finite sum also have polynomial bit length. Computing these quantities uses polynomially many operations on polynomial-size integers.
The invoked rational LP feasibility theorem is stated sufficiently precisely for this application: finite rational systems of non-strict linear inequalities admit feasibility decisions in time polynomial in their encoding length. The constructed systems satisfy those hypotheses; bounded feasible regions are unnecessary.
Performing one such test for each of the \(m\) explicitly listed alternatives therefore computes the exact set in polynomial time. No expansion of binary rational masses into individual agents occurs.
The attribution to Algorithm 4 and Theorem 2 matches the [cited full version](https://www.rupertfreeman.com/fair_social_choice_full.pdf). That reference is contextual; the type-level argument does not depend on applying its finite-agent theorem.
The write-up also handles self-comparisons, identical valuation vectors, zero valuations, absent positive leading comparisons, and ties through its existing formulas. None creates an undefined quantity or an omitted case.
No additional clarification or repair is 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.