Some results on approximating the minimax solution in approval voting (d4-conf-atal-2007-0132)

Given \(q\) candidates, committee size \(k\), a finite approval-type set \(T\subseteq\{0,1\}^q\), and a rational distribution \(\mu\) over \(T\), output an integral committee \(S\subseteq[q]\) with \(|S|=k\) satisfying \(R_\mu(S)\le 3\min_{|S'|=k}R_\mu(S')\), where \(R_\mu(S)=\max_{\mu_b>0}H(S,b)\).

Let \(m=q\ge 1\) be the number of candidates and let \(1\le k\le m\) be an input integer. Approval types are arbitrary vectors in \(\{0,1\}^m\), including the empty approval set.
A society is given by its support: a nonempty list \(T\) of \(\tau\) distinct types with positive binary rational masses \(\mu_b\), satisfying \(\sum_{b\in T}\mu_b=1\). Here \(\tau\) is the support size, not the number of possible approval types; \(L\) is the total input bit length.
For an integral committee \(S\subseteq\{1,\ldots,m\}\), let \(H(S,b)\) denote the standard Hamming distance between its incidence vector and \(b\). Define \(R_\mu(S)=\max_{b\in T}H(S,b)\) and \(\mathrm{OPT}_\mu=\min_{|S'|=k}R_\mu(S')\). Any committee meeting the requested bound is acceptable; no tie-breaking rule is imposed.

Does this problem admit an algorithm running in \(\operatorname{poly}(m,\tau,L)\) that outputs an integral committee \(S\) with \(|S|=k\) and \(R_\mu(S)\le 3\mathrm{OPT}_\mu\), or is obtaining this approximation NP-hard?

The discrete problem admits a polynomial-time factor-\(3\) approximation ([LeGrand–Markakis–Mehta](https://comsoc-community.org/assets/proceedings/comsoc-2006/LeGrand.pdf)) and a polynomial-time factor-\(2\) approximation ([Caragiannis–Kalaitzis–Markakis](https://ojs.aaai.org/index.php/AAAI/article/download/7615/7476)).
The stated support model has exactly the same objective and feasible committees as discrete minimax approval voting on the listed types; consequently, these verified results already settle the requested approximation question. No open target remains under these definitions.

Answer and reduction to the discrete model

Yes: a polynomial-time factor-\(3\) approximation exists.

For every committee \(S\), the objective \(R_\mu(S)=\max_{b\in T}H(S,b)\) depends only on the listed types, not their masses. Form a discrete election with one voter for each \(b\in T\). Its feasible committees and the objective value of every committee are exactly those of the given instance. This construction uses \(\tau\) voters; no expansion of rational masses is necessary.

Algorithm

Use the algorithm of [LeGrand–Markakis–Mehta, Theorem 2](https://comsoc-community.org/assets/proceedings/comsoc-2006/LeGrand.pdf):

Choose the first listed type \(b_0\), and let \(A=\{i:b_{0,i}=1\}\).

• If \(|A|\ge k\), output any \(k\)-element subset \(S\subseteq A\).
• If \(|A|<k\), output \(S=A\cup B\), where \(B\subseteq\{1,\ldots,m\}\setminus A\) has size \(k-|A|\).

Both choices are possible because \(k\le m\). They give \(|S|=k\) and \(H(S,b_0)=\bigl||A|-k\bigr|\).

Proof of the guarantee

An optimal committee \(S^\star\) exists because the feasible family is finite and nonempty. Write \(r=\mathrm{OPT}_\mu\).

For every committee \(C\) of size \(k\),
\(H(C,b_0)=|C\setminus A|+|A\setminus C|\ge\bigl||A|-k\bigr|\):
the sum of two nonnegative numbers is at least the absolute value of their difference.

Consequently, \(H(S,b_0)\le H(S^\star,b_0)\le r\). For every \(b\in T\), the Hamming triangle inequality gives
\(H(S,b)\le H(S,b_0)+H(b_0,S^\star)+H(S^\star,b)\le 3r\).
Taking the maximum proves \(R_\mu(S)\le 3\mathrm{OPT}_\mu\).

This argument also covers \(r=0\) and empty approval types.

Running time and conclusion

Choose added or removed candidates in increasing index order. Construction requires a scan of \(m\) coordinates. Including input parsing and binary counter operations, the running time is \(O(L+m\log(m+1))\), hence polynomial in \(m,\tau,L\).

The stronger polynomial-time factor-\(2\) result is also stated in [Caragiannis–Kalaitzis–Markakis, Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/7615/7476), whose model explicitly permits empty ballots. The direct proof above already completely settles the requested factor-\(3\) question.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover fully resolves the requested approximation question. The algorithm outputs an integral committee of the required size in polynomial time, and the factor-\(3\) guarantee is correct. No major or minor mathematical issues were found.

Step-by-step verification

• Reduction to the discrete model.

The objective takes the maximum over the listed support types; the masses never enter its definition. Giving each listed type one voter therefore preserves every feasible committee, every objective value, and the optimum. The construction uses exactly \(\tau\) voters, regardless of the denominators of the masses.

• Algorithm and feasibility.

Nonempty support guarantees that the first type \(b_0\) exists. If \(|A|\ge k\), a \(k\)-element subset of \(A\) exists. If \(|A|<k\), the complement has enough candidates because
\[ m-|A|\ge k-|A|. \]
Both branches produce an integral committee of size exactly \(k\). The claimed distance
\[ H(S,b_0)=\bigl||A|-k\bigr| \]
is correct: the algorithm changes only the excess approved coordinates or the missing unapproved coordinates.

• Optimality relative to the selected type.

For every size-\(k\) committee \(C\), the set differences satisfy
\[ |C\setminus A|-|A\setminus C|=k-|A|. \]
Thus the stated inequality follows from the sum of two nonnegative quantities being at least the absolute value of their difference. Consequently, the constructed committee minimizes distance to \(b_0\) among feasible committees. Applying this comparison to \(S^\star\) is justified.

• Approximation guarantee.

The feasible family is finite and nonempty, so an optimal committee exists. Because \(b_0\in T\), its distance to \(S^\star\) is at most \(r\). For each \(b\in T\), the displayed triangle-inequality chain bounds all three terms by \(r\). Taking the maximum therefore proves the requested guarantee. There is no division by \(r\), so the proof also applies when \(r=0\).

• Edge cases and running time.

Empty approval types cause no difficulty in either the construction or the inequalities. The cases \(m=1\), \(k=m\), and \(\tau=1\) are covered. Scanning coordinates and manipulating counters and output indices of \(O(\log(m+1))\) bits supports the stated construction bound. Reading or skipping the encoded input costs \(O(L)\); no rational arithmetic or mass expansion is needed. Input validity is promised by the task.

• Citations and hypotheses.

[LeGrand–Markakis–Mehta, Theorem 2](https://comsoc-community.org/assets/proceedings/comsoc-2006/LeGrand.pdf) states the factor-\(3\) guarantee for precisely the ballot-completion algorithm described. Its binary-ballot and fixed-size committee hypotheses match the reduced instance. [Caragiannis–Kalaitzis–Markakis, Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/7615/7476) states the factor-\(2\) guarantee, and that paper explicitly permits empty approval sets. The supplementary citation is accurate; the submitted direct proof already establishes the requested result independently.

Actionable feedback

No repair or additional clarification is needed. The polynomial classification concerns obtaining the requested approximation, not computing an exact optimum.

⟨structured verdict parsed — rendered above⟩