d4-conf-ecai-2024-0193 (d4-conf-ecai-2024-0193)

Given candidates \(C\), committee size \(k\), ballot size \(l\), and disjoint approval parties \(P_i\) with rational masses \(\mu_i\) summing to \(1\), let \(q_i=\lfloor k\mu_i\rfloor\) and assume \(l\le q_i\le |P_i|\). Each party allocates its mass among ballots \(B\in\binom{C}{l}\), with \(x_{i,B}\ge0\) and \(\sum_B x_{i,B}=\mu_i\); candidate \(c\) receives vote mass \(\sum_i\sum_{B\ni c}x_{i,B}\). The winning committees are the size-\(k\) sets with maximum total vote mass, and party \(i\)'s utility is its minimum number of candidates in any winning committee. Does the profile that chooses \(X_i\subseteq P_i\) with \(|X_i|=q_i\) and distributes type \(i\)'s mass uniformly over the \(l\)-subsets of \(X_i\) form an ε-Nash equilibrium against arbitrary unilateral mass reallocations, where \(\epsilon=k-\sum_i q_i\)?

Let \(C\) be an explicitly listed candidate set with \(m=|C|\), and let \(1\le l\le k\le m\) be integers.
A society is given by its support: \(\tau\) pairwise disjoint approval types \(P_i\subseteq C\), each with positive mass \(\mu_i\) encoded as a binary rational, with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible approval types; let \(L\) be the total input bit length.
Set \(q_i=\lfloor k\mu_i\rfloor\), require \(l\le q_i\le |P_i|\), and include explicitly chosen sets \(X_i\subseteq P_i\) with \(|X_i|=q_i\) in the input. Candidates outside all approval types are allowed.
Party \(i\)'s strategy is any allocation \(x_{i,B}\in\mathbb R_{\ge0}\) over \(B\in\binom{C}{l}\), with \(\sum_Bx_{i,B}=\mu_i\); ballots may include candidates outside \(P_i\).
For a profile \(x\), define \(s_x(c)=\sum_i\sum_{B\ni c}x_{i,B}\), let \(\mathcal W(x)\) contain all size-\(k\) committees maximizing \(\sum_{c\in W}s_x(c)\), and define \(U_i(x)=\min_{W\in\mathcal W(x)}|W\cap P_i|\).
The designated profile \(x^*\) assigns \(x^*_{i,B}=\mu_i/\binom{q_i}{l}\) when \(B\subseteq X_i\), and zero otherwise; this formula specifies the profile without enumerating its ballots.
Put \(\epsilon=k-\sum_iq_i\). The decision problem asks whether \(U_i(x^*)\ge U_i(x^*_{-i},x'_i)-\epsilon\) for every party and every feasible unilateral allocation \(x'_i\), including when \(\epsilon=0\).

Is deciding whether the designated profile is an \(\epsilon\)-Nash equilibrium in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L,k,l\).

For finite electorates, evenly spread lower-quota strategies are claimed to be \(\epsilon\)-Nash equilibria, with \(\epsilon=k-\sum_i\lfloor kn_i/n\rfloor\), under the corresponding quota and party-size conditions. [Source](https://arxiv.org/html/2407.17973v1).
No result settling this exact continuous decision problem was located.

Result

The problem is in \(\mathrm{P}\). Every instance satisfying the stated hypotheses is a yes-instance, including when \(\epsilon=0\).

In fact, writing \(p_i=|P_i|\), we prove the exact formulas
\[ U_i(x^*)=\max\{q_i,k-m+p_i\}, \qquad \max_{x'_i}U_i(x^*_{-i},x'_i)=\min\{p_i,q_i+\epsilon\}. \]

1. Scores at the designated profile

Set \(Q=\sum_jq_j=k-\epsilon\). Because \(q_j\le k\mu_j\) and \(\sum_j\mu_j=1\), we have \(Q\le k\), hence \(\epsilon\ge0\).

For each \(c\in X_j\), counting the size-\(l\) subsets containing \(c\) gives
\[ s_{x^*}(c) =\mu_j\frac{\binom{q_j-1}{l-1}}{\binom{q_j}{l}} =\frac{l\mu_j}{q_j} \ge\frac{l}{k}>0. \]
Disjointness of the approval types ensures that other parties contribute nothing to this score. Every candidate outside \(\bigcup_jX_j\) has score zero.

We will repeatedly use the following exchange property: if \(W\) maximizes committee score, \(c\in W\), and \(d\notin W\), then \(s(c)\ge s(d)\). Otherwise, replacing \(c\) by \(d\) strictly increases the committee score.

Since exactly \(Q\le k\) candidates have positive scores, every winning committee contains all of them. Its remaining \(\epsilon\) members can be any zero-score candidates. Consequently,
\[ U_i(x^*)\ge q_i. \]

For completeness, the exact utility follows by counting available zero-score candidates outside \(P_i\). Their number is
\[ Z_i=m-p_i-(Q-q_i). \]
Among the \(\epsilon\) additional committee members, the minimum possible number from \(P_i\) is \(\max\{0,\epsilon-Z_i\}\). All such extensions are winning committees, so
\[ U_i(x^*) =q_i+\max\{0,\epsilon-Z_i\} =\max\{q_i,k-m+p_i\}. \]

2. A bound for every unilateral deviation

Fix a party \(i\) and an arbitrary feasible allocation \(x'_i\), allowing ballots outside \(P_i\). Write \(x'=(x^*_{-i},x'_i)\), and define
\[ D_i=\bigcup_{j\ne i}X_j, \qquad R_i=|D_i|=Q-q_i=k-\epsilon-q_i. \]
The sets are disjoint, and \(D_i\cap P_i=\varnothing\).

Every \(d\in D_i\) retains its original opponent contribution. The deviator adds only nonnegative scores, so
\[ s_{x'}(d)\ge\frac{l}{k}. \]

Meanwhile, opponents contribute nothing to candidates in \(P_i\). Therefore their total score satisfies
\[ \sum_{c\in P_i}s_{x'}(c) =\sum_{B\in\binom{C}{l}}|B\cap P_i|x'_{i,B} \le l\sum_Bx'_{i,B} =l\mu_i <\frac{l(q_i+1)}{k}. \]
The strict inequality follows from \(k\mu_i<q_i+1\).

Suppose a winning committee \(W\) contained
\[ t=|W\cap P_i|\ge q_i+\epsilon+1. \]
Then
\[ |W\setminus P_i|=k-t\le R_i-1. \]
Thus some \(d\in D_i\) is omitted from \(W\). By the exchange property, every \(c\in W\cap P_i\) satisfies
\[ s_{x'}(c)\ge s_{x'}(d)\ge\frac{l}{k}. \]
It follows that
\[ \sum_{c\in P_i}s_{x'}(c) \ge\frac{tl}{k} \ge\frac{l(q_i+1)}{k}, \]
contradicting the score-budget inequality.

Hence every winning committee after every unilateral deviation satisfies
\[ |W\cap P_i|\le q_i+\epsilon. \]
In particular,
\[ U_i(x^*_{-i},x'_i)\le q_i+\epsilon. \]

Combining this with \(U_i(x^*)\ge q_i\) proves
\[ U_i(x^*)\ge U_i(x^*_{-i},x'_i)-\epsilon \]
for every party and every feasible deviation. This argument also applies when \(\epsilon=0\).

3. The deviation bound is attainable

Let
\[ r_i=\min\{p_i,q_i+\epsilon\}. \]
Since \(p_i\ge q_i\ge l\), we have \(r_i\ge l\). Choose \(Y_i\subseteq P_i\) with \(|Y_i|=r_i\), and distribute mass \(\mu_i\) uniformly over its size-\(l\) subsets.

The positive-score candidates are exactly \(Y_i\cup D_i\), whose number satisfies
\[ r_i+R_i\le(q_i+\epsilon)+(k-\epsilon-q_i)=k. \]
Every winning committee therefore contains \(Y_i\), giving utility at least \(r_i\). The preceding bound and the elementary bound \(U_i\le p_i\) give utility at most \(r_i\). Thus
\[ \max_{x'_i}U_i(x^*_{-i},x'_i)=r_i. \]
This construction specifies the allocation without enumerating its ballots.

4. Decision algorithm and running time

On the promised input domain, the algorithm simply returns yes. Its decision time is \(O(1)\); reading the entire input takes \(O(L)\).

If malformed inputs must also be rejected, a straightforward validator checks the candidate lists, disjointness, rational masses, normalization, quotas, and designated sets. Using schoolbook exact integer arithmetic gives a conservative \(O(L^3+m+\tau)\) bit-operation bound. Here \(k,l\le m\), their binary encodings are included in \(L\), and no enumeration of \(\binom{m}{l}\) ballots or \(\binom{m}{k}\) committees is required.

The finite-electorate analogue is stated in [Theorem 14 of the cited paper](https://arxiv.org/html/2407.17973v1#S7). The proof above independently establishes the exact continuous statement, including unrestricted unilateral ballots and \(\epsilon=0\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the assigned continuous decision problem correctly. Every valid instance is a yes-instance, including when \(\epsilon=0\). Both claimed exact utility formulas are established. I found no major or minor mathematical issues.

Step-by-step verification

1. Designated profile and its scores

The designated allocation is feasible: \(q_j\ge l\ge1\), so \(\binom{q_j}{l}\) is positive, and assigning mass \(\mu_j/\binom{q_j}{l}\) to each of these ballots gives total mass \(\mu_j\).

The deduction
\(Q=\sum_jq_j\le k\sum_j\mu_j=k\)
is valid, so \(\epsilon=k-Q\ge0\).

For \(c\in X_j\), the ballot count and binomial ratio are correct:
\[ \frac{\binom{q_j-1}{l-1}}{\binom{q_j}{l}}=\frac{l}{q_j}. \]
Consequently, \(s_{x^*}(c)=l\mu_j/q_j\ge l/k>0\). Disjointness ensures no other party contributes to this candidate. All candidates outside the designated sets receive zero.

The exchange property is correctly stated and justified. Since there are exactly \(Q\le k\) positive-score candidates, every maximizing committee must contain them all. Any extension by \(\epsilon\) zero-score candidates is maximizing. Such extensions exist because \(m-Q\ge k-Q=\epsilon\).

The count
\(Z_i=m-p_i-(Q-q_i)\)
correctly removes the opponents’ positive-score candidates from the candidates outside \(P_i\). Therefore the minimum number of additional members from \(P_i\) is \(\max\{0,\epsilon-Z_i\}\). The resulting simplification to
\[ U_i(x^*)=\max\{q_i,k-m+p_i\} \]
is correct.

2. Universal bound on deviations

The argument fixes an arbitrary party and an arbitrary feasible deviation, so its quantifiers match the task.

The opponent set \(D_i\) has size
\(R_i=Q-q_i=k-\epsilon-q_i\)
and is disjoint from \(P_i\). Every candidate in \(D_i\) retains score at least \(l/k\), regardless of the deviator’s ballots, because all added contributions are nonnegative.

Opponents contribute nothing to \(P_i\). The score-budget identity and bound are valid:
\[ \sum_{c\in P_i}s_{x'}(c) =\sum_B|B\cap P_i|x'_{i,B} \le l\mu_i <\frac{l(q_i+1)}{k}. \]
The strict inequality follows exactly from \(q_i=\lfloor k\mu_i\rfloor\). It remains strict when \(k\mu_i\) is integral.

If a maximizing committee contains \(t\ge q_i+\epsilon+1\) members of \(P_i\), then
\(k-t\le R_i-1\).
Thus it cannot contain all \(R_i\) opponent candidates. The exchange property implies that every selected member of \(P_i\) has score at least \(l/k\). Their combined score then contradicts the strict budget bound.

The degenerate case \(R_i=0\) creates no gap: the hypothesized committee would require \(k-t\le-1\), which is impossible.

The conclusion applies to every maximizing committee, so it establishes the claimed bound on the minimum utility despite adversarial tie handling:
\[ U_i(x^*_{-i},x'_i)\le q_i+\epsilon. \]

Combining this with \(U_i(x^*)\ge q_i\) proves the required equilibrium inequality for every party and every deviation. No step assumes \(\epsilon>0\).

3. Attainment of the deviation bound

The chosen size \(r_i=\min\{p_i,q_i+\epsilon\}\) satisfies \(l\le r_i\le p_i\), so the proposed set and uniform allocation are feasible.

Every candidate in \(Y_i\) receives positive score, and the positive-score candidates are exactly \(Y_i\cup D_i\). These sets are disjoint, and their total size is at most \(k\). Hence every maximizing committee contains \(Y_i\), giving minimum utility at least \(r_i\).

The previously established universal bound, together with \(U_i\le p_i\), gives the matching upper bound. Thus
\[ \max_{x'_i}U_i(x^*_{-i},x'_i)=\min\{p_i,q_i+\epsilon\} \]
is proved. The explicit construction also justifies writing a maximum rather than merely a supremum.

4. Algorithm and complexity

On the promised domain, returning yes without inspecting the input is a valid constant-time decision algorithm. The distinction between \(O(1)\) decision time and \(O(L)\) time to read the input is appropriate.

The optional validation bound \(O(L^3+m+\tau)\) is conservative and consistent with schoolbook exact arithmetic. Rational normalization and quota calculations involve integers of bit length bounded by the total encoding length; explicit candidate and set checks also fit within this bound.

The running-time statement addresses all requested parameters: \(k,l\le m\), their encodings contribute to \(L\), and neither ballots nor committees need enumeration.

5. External citation

The cited [Theorem 14](https://arxiv.org/html/2407.17973v1#S7) does state the finite-electorate equilibrium claim with the indicated quota conditions and value of \(\epsilon\). The prover uses this as context, not as an unverified theorem application establishing the continuous result.

Repair feedback

No mathematical repair or additional clarification is required. The proof establishes the claimed result for unrestricted unilateral ballots, candidates outside all approval types, and adversarial selection among maximizing committees.

⟨structured verdict parsed — rendered above⟩