Answer: Polynomial-time solvable.
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn every line-up election, an outcome without reasonable dissatisfaction is guaranteed to exist.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), positions \(P\), and a rational distribution \(\mu\) over approval sets \(A_t\subseteq C\times P\), where \(S(c,p)=\sum_{t:(c,p)\in A_t}\mu_t\), can one compute an injective line-up with no reasonably dissatisfied pair under \(S\)?
Let \(C\) contain \(m\) candidates and \(P\) contain \(q\) positions, with \(1\leq q\leq m\).
A society is given by its support: the list of the \(\tau\) distinct approval types \(A_t\subseteq C\times P\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). The support size \(\tau\) counts listed types, not possible types; let \(L\) be the total input bit length.
Define \(S(c,p)=\sum_{t:(c,p)\in A_t}\mu_t\). A line-up is an injective map \(\pi:P\to C\); write \(\pi_p=\pi(p)\), and let \(\pi(c)\) denote the assigned position of an assigned candidate.
A pair \((c,p)\in C\times P\) is reasonably dissatisfied precisely when \(S(c,p)>S(\pi_p,p)\) and either \(c\notin\pi(P)\), or \(c\in\pi(P)\) and \(S(c,p)>S(c,\pi(c))\). Equal scores do not cause dissatisfaction; any qualifying line-up may be returned.
Is computing a line-up without reasonably dissatisfied pairs solvable in polynomial time in \(m,q,\tau,L\), or is this search problem NP-hard?
For explicitly given rational score matrices, a reasonably satisfying line-up always exists and is computable in polynomial time ([verified source](https://arxiv.org/pdf/2007.04960)).
That result already covers the aggregated rational scores defined here; consequently, the stated continuous question is covered by the known result rather than being an open target.
The search problem is solvable in polynomial time in \(m,q,\tau,L\). A greedy algorithm always produces a line-up without reasonably dissatisfied pairs.
This is the max-first rule in the [cited paper](https://arxiv.org/pdf/2007.04960), Sections 4–5. The following proof establishes correctness directly for the stated support representation, including its bit complexity.
Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers given in binary. Define \(D=\prod_{t=1}^{\tau}b_t\) and \(n_t=a_t(D/b_t)\). Then \(n_t=D\mu_t\) is an integer.
For each pair \((c,p)\), compute
\(W(c,p)=\sum_{t:(c,p)\in A_t}n_t\).
Thus \(W(c,p)=D S(c,p)\). Since \(D\) is positive, every strict comparison or equality between scores is preserved.
The binary length of \(D\) is at most \(1+\sum_t\log_2 b_t\), hence is \(O(L+1)\). Moreover, positivity and normalization give \(\sum_t n_t=D\), so \(0\leq W(c,p)\leq D\). Consequently, all these integers have \(O(L+1)\) bits.
Their computation uses polynomial-time integer arithmetic and a scan of the explicitly listed approval types. No expansion of the masses into individual voters is needed.
Initially, every candidate and every position is available. Repeat the following operation until all positions are filled:
Before iteration \(k\), exactly \(k-1\) candidates and positions have been removed. There are therefore \(m-k+1\) available candidates and \(q-k+1\) available positions. For \(1\leq k\leq q\), both quantities are positive because \(m\geq q\).
Thus every iteration is possible, and after exactly \(q\) iterations the assignments define an injective map \(\pi:P\to C\).
Fix any pair \((c,p)\). Consider the iteration in which position \(p\) receives its final candidate \(\pi_p\).
Case 1: Candidate \(c\) was available immediately before that iteration.
The pair \((c,p)\) was eligible for selection. By maximality of the selected pair,
\(W(\pi_p,p)\geq W(c,p)\).
Therefore \(S(\pi_p,p)\geq S(c,p)\), and the first strict inequality required for dissatisfaction fails.
Case 2: Candidate \(c\) was already unavailable.
Then \(c\) was assigned in an earlier iteration to its final position \(\pi(c)\). Position \(p\) was still available at that earlier iteration, because it was assigned later. Hence \((c,p)\) was eligible when the algorithm selected \((c,\pi(c))\). Maximality gives
\(W(c,\pi(c))\geq W(c,p)\).
Therefore \(S(c,\pi(c))\geq S(c,p)\), and the second strict inequality required for dissatisfaction fails.
These cases exhaust all possibilities. In particular, a candidate unassigned in the final line-up is always covered by Case 1. Thus no pair is reasonably dissatisfied. The proof permits arbitrary tie-breaking.
Once the integer score table is constructed, each iteration scans at most \(mq\) pairs. The construction therefore uses at most \(mq^2\) comparisons of integers with \(O(L+1)\) bits.
Score aggregation and greedy selection both take polynomial time in \(m,q,\tau,L\). This proves existence and polynomial-time computability for every input satisfying the premises.
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the assigned problem. The greedy construction is correct, its arithmetic has polynomial bit complexity, and no major or minor issues were found.
Each denominator \(b_t\) is positive, so \(D=\prod_{t=1}^{\tau}b_t\) is positive and divisible by every \(b_t\). Consequently, \(n_t=a_t(D/b_t)=D\mu_t\) is an integer. The identity \(W(c,p)=DS(c,p)\) follows directly from the definitions, and multiplication by positive \(D\) preserves every relevant strict inequality and equality.
The claimed bit bound is correct: the binary length of \(D\) is at most \(1+\sum_t\log_2 b_t\), which is \(O(L+1)\). Normalization gives \(\sum_t n_t=D\). Positivity then implies \(0\leq W(c,p)\leq D\), so intermediate score sums also have polynomial bit length. Forming the product, performing exact divisions, and scanning the listed approval types require polynomial time. No enumeration of unlisted types or expansion into individual voters occurs.
Before iteration \(k\), the available sets have sizes \(m-k+1\) and \(q-k+1\). Both are positive for \(1\leq k\leq q\), using the stipulated \(m\geq q\). Thus a maximizing pair exists at every iteration. Removing its candidate and position prevents repeated assignments, and exactly \(q\) iterations fill every position. The result is an injective map with the required domain.
If candidate \(c\) is available when position \(p\) is filled, then \((c,p)\) is among the pairs over which the algorithm maximizes. Therefore \(W(\pi_p,p)\geq W(c,p)\), and hence \(S(\pi_p,p)\geq S(c,p)\). This negates the first required strict inequality, regardless of whether \(c\) is assigned later.
An unavailable candidate must have been assigned earlier, since assignment is the only operation removing candidates. At that earlier iteration, position \(p\) was still available. Thus \((c,p)\) competed with the selected pair \((c,\pi(c))\), giving \(W(c,\pi(c))\geq W(c,p)\). The corresponding score inequality negates the second required strict inequality. Here \(\pi(c)\) is well-defined because this case guarantees that \(c\) is assigned.
The cases exhaust all candidates. A finally unassigned candidate remains available throughout and therefore falls under Case 1.
Both arguments establish weak inequalities, which suffice because dissatisfaction requires strict inequalities. Arbitrary tie-breaking is therefore valid. The argument also covers zero scores, all scores tied, \(q=1\), \(q=m\), and pairs already assigned in the final line-up. None requires an additional assumption.
There are \(q\) iterations, each scanning at most \(mq\) pairs, so the stated bound of \(mq^2\) comparisons holds. Each comparison involves \(O(L+1)\)-bit integers. Together with polynomial-time aggregation, this establishes the requested polynomial dependence on \(m,q,\tau,L\).
Section 4 of the [cited paper](https://arxiv.org/pdf/2007.04960) defines max-first by selecting a highest-scoring remaining candidate-position pair; Section 5 states its reasonable-satisfaction guarantee. The attribution is accurate. Moreover, the submitted proof establishes that guarantee directly, so its correctness does not depend on an unstated external theorem.
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.