d4-conf-atal-2011-0148 (d4-conf-atal-2011-0148)

Given existing alternatives \(C\), one new alternative \(y\), a target \(c\in C\), and a rational distribution \(\mu\) over rankings of \(C\), can the mass of each ranking type be split among its full-ranking extensions to \(C\cup\{y\}\) so that \(c\) is a Maximin co-winner? The unique-winner version asks whether \(c\) can be the sole winner.

Given a nonempty set \(C\) of \(m\) existing alternatives, a target \(c\in C\), and exactly one new alternative \(y\notin C\), let \(A=C\cup\{y\}\).
A society is given by its support: \(\tau\) distinct strict rankings \(R_i\) of \(C\), each with positive binary rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
An extension assigns nonnegative real masses \(x_{i,R}\) to strict rankings \(R\) of \(A\) whose restriction to \(C\) is \(R_i\), with \(\sum_{R:R|_C=R_i}x_{i,R}=\mu_i\); there are no further restrictions on inserting \(y\).
Use Maximin with pairwise support masses: \(N(a,b)=\sum_{i,R:a\succ_R b}x_{i,R}\) and \(s(a)=\min_{b\in A\setminus\{a\}}N(a,b)\). All score maximizers are co-winners, with no tie-breaking.
The co-winner decision problem asks whether an extension satisfies \(s(c)\ge s(a)\) for every \(a\ne c\); the unique-winner decision problem requires \(s(c)>s(a)\) for every \(a\ne c\).

For each of these two decision problems, is it in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite unweighted electorates, both problems are \(\mathrm{NP}\)-complete even with exactly one new alternative ([Xia–Lang–Monnot](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R75.pdf)). No result settling exactly the divisible-mass problems above was located in the literature search.

1. Result. Both the co-winner and the unique-winner decision problems are in \(\mathrm{P}\). Each can be decided using at most \(m\) rational linear programs of polynomial encoding length.

The key is that any successful extension can be replaced by one in which \(c\) attains its original Maximin score.

2. Scores and an exact representation of extensions. First suppose \(m\ge 2\). For distinct \(a,b\in C\), define the fixed original supports and scores by
\[ \]
\(p_{ab}=\sum_{i:\,a\succ_{R_i}b}\mu_i,\qquad b_a=\min_{b\in C\setminus\{a\}}p_{ab},\qquad \rho=b_c.\)

For an extension, write \(q_a=N(a,y)\). Since old pairwise supports remain unchanged and total mass is one,
\(s(a)=\min\{b_a,q_a\}\) for every \(a\in C\), and
\(s(y)=\min_{a\in C}(1-q_a)=1-\max_{a\in C}q_a.\)

There are exactly \(m+1\) extensions of each ranking \(R_i\): insert \(y\) after its first \(k\) alternatives, where \(k\in\{0,\ldots,m\}\). Let \(x_{ik}\) denote the mass assigned to that insertion. The extension conditions are exactly

\(x_{ik}\ge 0,\qquad \sum_{k=0}^{m}x_{ik}=\mu_i\quad\text{for every }i.\)

If \(r_i(a)\in\{1,\ldots,m\}\) is the position of \(a\) in \(R_i\), then \(a\) precedes \(y\) precisely when \(k\ge r_i(a)\). Consequently,

\(q_a(x)=\sum_{i=1}^{\tau}\sum_{k=r_i(a)}^{m}x_{ik}.\)

Thus every \(q_a\) is linear in \(\tau(m+1)\) variables, and this formulation describes exactly the allowed extensions.

3. Normalization lemma. Suppose \(\rho<1\). If an extension makes \(c\) a co-winner, then some extension makes \(c\) a co-winner with score exactly \(\rho\). The same statement holds for a unique winner.

*Proof.* Let \(t=s(c)\le\rho\) in a successful extension. If \(t=\rho\), nothing needs changing. Suppose \(t<\rho\). Then \(q_c=t\), because \(t=\min\{\rho,q_c\}\).

Let \(E_{\mathrm{last}}\) be the extension placing \(y\) last throughout the society. Mix the successful extension with \(E_{\mathrm{last}}\), using proportion

\(\lambda=\dfrac{\rho-t}{1-t}.\)

Because \(t<\rho<1\), we have \(0<\lambda<1\). This mixture is an allowed extension: for each original ranking, both extensions assign total mass \(\mu_i\), so their convex combination does too.

The resulting supports satisfy

\(q'_a=(1-\lambda)q_a+\lambda\quad\text{for every }a\in C,\)

and hence \(q'_c=(1-\lambda)t+\lambda=\rho\). Therefore \(s'(c)=\rho\). Also,

\(s'(y)=1-\max_a q'_a=(1-\lambda)s(y).\)

For the co-winner case, fix \(a\in C\setminus\{c\}\). Its original extended score satisfies \(\min\{b_a,q_a\}\le t\).

• If \(b_a\le t\), then \(s'(a)\le b_a\le t<\rho\).
• If \(b_a>t\), then \(q_a\le t\), so \(q'_a\le(1-\lambda)t+\lambda=\rho\), giving \(s'(a)\le\rho\).

Moreover, \(s'(y)=(1-\lambda)s(y)\le t<\rho\). Thus \(c\) remains a co-winner.

For the unique-winner case, \(\min\{b_a,q_a\}<t\).

• If \(b_a<t\), then \(s'(a)\le b_a<t<\rho\).
• Otherwise \(q_a<t\), and \(1-\lambda>0\) gives \(q'_a<(1-\lambda)t+\lambda=\rho\).

Finally, \(s'(y)\le s(y)<t<\rho\). Thus \(c\) remains the unique winner. This proves the lemma.

4. Co-winner algorithm. Assume \(\rho<1\), and define

\(D_{\mathrm{co}}=\{a\in C\setminus\{c\}:b_a>\rho\}.\)

For each \(d\in C\), test feasibility of the following linear program:

• \(x_{ik}\ge 0\) and \(\sum_{k=0}^{m}x_{ik}=\mu_i\) for every \(i\);
• \(q_c(x)\ge\rho\);
• \(q_a(x)\le\rho\) for every \(a\in D_{\mathrm{co}}\);
• \(q_d(x)\ge1-\rho\).

Return YES if at least one of these \(m\) programs is feasible.

*Correctness.* A feasible solution gives \(s(c)=\rho\). Every old rival outside \(D_{\mathrm{co}}\) has \(s(a)\le b_a\le\rho\); every rival inside it has \(s(a)\le q_a\le\rho\). Furthermore,

\(s(y)=1-\max_a q_a\le1-q_d\le\rho.\)

Therefore \(c\) is a co-winner.

Conversely, if a successful extension exists, the normalization lemma supplies one with \(s(c)=\rho\). Every \(a\in D_{\mathrm{co}}\) must then satisfy \(q_a\le\rho\), since \(b_a>\rho\). Also, \(s(y)\le\rho\) implies \(\max_a q_a\ge1-\rho\). Because \(C\) is finite and nonempty, some \(d\in C\) witnesses this inequality. That normalized extension is feasible for the program indexed by \(d\).

5. Unique-winner algorithm. Assume \(\rho<1\), and define

\(D_{\mathrm{uni}}=\{a\in C\setminus\{c\}:b_a\ge\rho\}.\)

For each \(d\in C\), maximize a variable \(\varepsilon\) subject to:

• \(x_{ik}\ge0\) and \(\sum_{k=0}^{m}x_{ik}=\mu_i\) for every \(i\);
• \(0\le\varepsilon\le1\);
• \(q_c(x)\ge\rho\);
• \(q_a(x)\le\rho-\varepsilon\) for every \(a\in D_{\mathrm{uni}}\);
• \(q_d(x)\ge1-\rho+\varepsilon\).

Return YES if at least one program is feasible with optimum strictly positive.

*Correctness.* If \(\varepsilon>0\), then \(s(c)=\rho\). A rival outside \(D_{\mathrm{uni}}\) has \(s(a)\le b_a<\rho\); one inside it has \(s(a)\le q_a\le\rho-\varepsilon<\rho\). Also,

\(s(y)\le1-q_d\le\rho-\varepsilon<\rho.\)

Thus \(c\) is the unique winner.

Conversely, normalize any successful extension to score \(\rho\). Every \(a\in D_{\mathrm{uni}}\) must satisfy \(q_a<\rho\). Since \(s(y)<\rho\), some \(d\in C\) satisfies \(q_d>1-\rho\). The finitely many quantities

\(\rho-q_a\quad(a\in D_{\mathrm{uni}}),\qquad q_d-(1-\rho)\)

are all positive. Choosing \(\varepsilon\) to be their minimum together with \(1\) yields a feasible solution with \(\varepsilon>0\).

The feasible region is closed and bounded: each \(x_{ik}\) lies between \(0\) and \(\mu_i\), and \(\varepsilon\in[0,1]\). Hence every feasible program attains its maximum. Testing the exact optimum’s sign handles strict inequalities without assuming any predetermined numerical tolerance.

6. Boundary cases and running time. If \(m=1\), placing \(y\) below \(c\) gives \(s(c)=1\) and \(s(y)=0\), so both answers are YES.

For \(m\ge2\), if \(\rho=1\), then \(p_{ca}=1\) for every old rival \(a\), and therefore \(p_{ac}=0\). Placing \(y\) last gives \(c\) score \(1\) and every other alternative score \(0\). Again both answers are YES. If \(\rho=0\), unique winning is impossible because all scores are nonnegative; the co-winner algorithm still applies.

For the remaining instances, preprocessing computes all \(p_{ab}\) and \(b_a\) using \(O(\tau m^2)\) rational additions and comparisons. Their bit lengths are \(O(L)\): a common denominator can be taken as the product of the input denominators, whose binary length is \(O(L)\).

Each linear program has \(O(\tau m)\) variables and \(O(\tau+m)\) constraints besides nonnegativity. Its matrix coefficients belong to \(\{-1,0,1\}\), and its right-hand sides have \(O(L)\) bits. A dense encoding therefore has length

\(B=O\bigl(\tau m(\tau+m)+mL\bigr).\)

We use the standard polynomial bit complexity theorem for rational linear programming, including exact feasibility and optimization. See [Megiddo, *On the complexity of linear programming*](https://theory.stanford.edu/~megiddo/pdf/wcongres_4.0.a.pdf).

Writing \(P_{\mathrm{LP}}\) for a fixed polynomial bound for an exact rational LP algorithm, each decision problem takes

\(O(\tau m^2L^2)+mP_{\mathrm{LP}}(B)\)

bit operations, including construction of the programs. In particular, the running time is \((m\tau+L)^{O(1)}\).

The finite-electorate hardness result in [Xia–Lang–Monnot, Theorem 4](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R75.pdf) does not conflict with this conclusion: the normalization step uses divisible mass, and the linear programs impose no integrality constraints.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The argument establishes that both divisible-mass decision problems are in \(\mathrm{P}\). I found no mathematical errors or substantive gaps.

• Original scores and extension variables are correct.

For \(m\ge2\), the quantities \(p_{ab}\), \(b_a\), and \(\rho=b_c\) are well-defined. Old pairwise supports are unchanged by inserting \(y\), so
\[ s(a)=\min\{b_a,q_a\},\qquad s(y)=1-\max_{a\in C}q_a. \]
The second identity uses strict rankings and total mass one, which give \(N(y,a)=1-N(a,y)\).

Every extension of a particular \(R_i\) is uniquely determined by one of its \(m+1\) insertion positions. Thus the nonnegative variables \(x_{ik}\), with row sums \(\mu_i\), describe exactly the extensions permitted by the task. The condition \(k\ge r_i(a)\) correctly identifies when \(a\) precedes \(y\). The formula for \(q_a(x)\) is consequently exact.

• The normalization lemma is valid for both winner notions.

In a successful extension, \(t=s(c)\le\rho\). When \(t<\rho\), the score identity forces \(q_c=t\). Under the lemma’s assumption \(\rho<1\),
\[ 0<\lambda=\frac{\rho-t}{1-t}<1. \]
The denominator is positive, and mixing preserves every prescribed original-ranking mass.

Placing \(y\) last gives \(q_a=1\) for every old alternative. Therefore the stated affine transformation of all \(q_a\) is correct, and
\[ (1-\lambda)t+\lambda=\rho. \]
Since the transformation is increasing, its maximum transforms in the same way; hence \(s'(y)=(1-\lambda)s(y)\).

For co-winning, the two cases \(b_a\le t\) and \(b_a>t\) exhaust all old rivals. In the second case, the original winning inequality forces \(q_a\le t\), giving the required transformed bound.

For unique winning, the cases \(b_a<t\) and \(b_a\ge t\) likewise exhaust all possibilities. In the latter case, \(q_a<t\), and \(1-\lambda>0\) preserves strictness. The bounds for \(y\) are valid because all scores are nonnegative.

No integrality assumption enters this argument. Its use of arbitrary convex mixing is authorized by the divisible-mass model.

• The co-winner LPs are necessary and sufficient.

The constraint \(q_c\ge\rho\) ensures \(s(c)=\rho\). Rivals with \(b_a\le\rho\) need no further constraint; rivals with \(b_a>\rho\) must satisfy \(q_a\le\rho\). This is exactly the definition and treatment of \(D_{\mathrm{co}}\).

The remaining requirement is
\[ s(y)\le\rho\quad\Longleftrightarrow\quad\max_{a\in C}q_a\ge1-\rho. \]
Enumerating \(d\in C\) expresses this finite disjunction correctly. The normalization lemma supplies the converse implication from an arbitrary successful extension. Both directions are established.

• The unique-winner LPs handle strict inequalities correctly.

The threshold \(b_a\ge\rho\) in \(D_{\mathrm{uni}}\) is correct: an old rival whose original score equals \(\rho\) must also have its support against \(y\) strictly below \(\rho\).

A feasible point with \(\varepsilon>0\) gives strict defeat of every constrained old rival and of \(y\). Every unconstrained old rival already has \(b_a<\rho\).

Conversely, a normalized unique-winning extension supplies strictly positive margins for every member of \(D_{\mathrm{uni}}\) and for at least one witness \(d\). Taking their minimum together with \(1\) gives a positive feasible \(\varepsilon\). This remains valid when \(D_{\mathrm{uni}}\) is empty: the witness margin is still present.

The feasible region is closed and bounded as stated. Thus a feasible optimization problem attains its maximum, and exact comparison of that maximum with zero correctly decides strict feasibility.

• The boundary cases are complete.

For \(m=1\), placing \(y\) below \(c\) gives scores \(1\) and \(0\).

For \(m\ge2\) and \(\rho=1\), every \(p_{ca}=1\). Strict rankings give \(p_{ac}=0\), so every old rival has score zero. Placing \(y\) last also gives \(s(y)=0\).

For \(\rho=0\), unique winning is impossible because \(s(c)=0\) and every competing score is nonnegative. The co-winner formulation remains valid. There is no unhandled empty minimum: \(b_a\) is only defined after assuming \(m\ge2\).

• The encoding and running-time claims are valid.

A product of the input denominators has binary length \(O(L)\). Supports, original scores, and LP right-hand sides therefore have \(O(L)\)-bit rational representations.

The variable and constraint counts are correct. In the dense encoding bound
\[ B=O\bigl(\tau m(\tau+m)+mL\bigr), \]
the original masses contribute only their total encoding length \(O(L)\); the derived thresholds occur in \(O(m)\) constraints. No omitted factor of \(\tau L\) is required.

The invoked rational-LP theorem applies: the programs have explicit rational data of polynomial encoding length, and the optimization programs have bounded feasible regions. Exact feasibility and optimization are covered by the cited survey’s discussion of polynomial bit complexity and recovery of exact optimal solutions. [Megiddo, Sections 3 and 7](https://theory.stanford.edu/~megiddo/pdf/wcongres_4.0.a.pdf).

The preprocessing bound \(O(\tau m^2L^2)\) is a valid conservative bound for exact rational arithmetic. With at most \(m\) LP calls, the claimed running time is polynomial in \(m,\tau,L\).

• The comparison with finite-electorate hardness is accurate.

The cited Theorem 4 states NP-completeness for both finite-electorate winner notions with one new alternative. The present proof uses divisible mass and imposes no integrality constraints, so it does not contradict that theorem. [Xia–Lang–Monnot, Theorem 4](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R75.pdf).

Actionable feedback: No repair or additional clarification is needed to verify the conclusion.

⟨structured verdict parsed — rendered above⟩