d4-conf-aaai-2010-0094

The strongest mirror is the paper’s Theorem 3, proved here: the LP based algorithm for \(k\)-minimax approval has approximation ratio at most \(2\). It solves a natural fractional relaxation and returns the \(k\) candidates with largest fractional values. The paper also shows that this relaxation has integrality gap \(2\), so it cannot yield a better guarantee without changing the relaxation. I would not use the paper’s unnumbered statement that exact \(k\)-minimax approval is NP-hard as an anchor; the theorem provides a named computational result.

Continuous \(k\)-Minimax Approval, 2-Approximation. An instance consists of \(m\) candidates, a committee size \(k\), and a finite support \(\mathcal S\) of approval sets with positive rational masses \(\mu_S\) summing to \(1\). A feasible solution is a size-\(k\) committee \(K\). Its loss is
\[ D_\mu(K)=\operatorname*{ess\,sup}_{S\sim\mu} d_H(K,S) =\max_{S\in\mathcal S} d_H(K,S). \]
The task is to return \(K\) with \(D_\mu(K)\le 2\operatorname{OPT}_\mu\), where \(\operatorname{OPT}_\mu=\min_{|K|=k}D_\mu(K)\).

The theorem’s LP has a variable \(x_a\in[0,1]\) for each candidate, a variable \(q\ge0\), the constraint \(\sum_a x_a=k\), and, for each supported approval set \(S\), the constraint
\[ q+2\sum_{a\in S}x_a\ge k+|S|. \]
It minimizes \(q\), then rounds by taking the \(k\) largest \(x_a\). Repeated voters with the same approval set give identical constraints, so the continuous instance has only \(\tau=|\mathcal S|\) voter constraints. The expected classification is tractable as a 2-approximation: the theorem’s algorithm and guarantee carry over directly, with running time polynomial in \(m,\tau\), and the input bit length \(L\).

A plausible regime is a large professional association electing a committee from a fixed candidate slate. Many members cast identical approval ballots: for example, hundreds of thousands of members but only a few dozen supported ballot types. A type is an approval set; its mass is the fraction of members who cast it. The paper’s worst-voter objective becomes the essential supremum over the population. If \(\mu_S=n_S/n\) for a finite election, the objective is exactly the same maximum over ballots that occur. The authors should recognize this as their problem: it preserves the committee size, feasible outcomes, Hamming distance, and worst-case objective.

My weakest point is that the masses do not affect the objective beyond whether they are positive. A type with tiny positive mass can determine the result just as much as the majority type. That is faithful to a rule minimizing the distance of the worst-off voter, but it means this mirror does not gain tractability from averaging the population; the theorem already handles the corresponding finite support. It is a credible continuous formulation of their approximation result, not evidence that exact \(k\)-minimax approval becomes easy.

The further questions are whether exact optimization remains hard for this support based formulation, whether approximation ratios better than \(2\) are achievable by another method, and how the guarantees depend on \(m\), \(\tau\), and \(L\). I would keep the scope to Theorem 3. The paper’s strategyproofness results are weaker anchors for an atomless population: an individual has zero mass, so individual manipulation can become vacuous unless the strategic model is changed.