| paper | d4-conf-wine-2014-0040 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: A PTAS exists: for every fixed \(\epsilon\in(0,1)\), a committee with \(D_\mu(W)\le(1+\epsilon)\mathrm{OPT}_\mu\) can be computed in time polynomial in \(m,\tau,L\), with \(k\) part of the input. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a finite approval-type support \(\mathcal{A}\subseteq 2^C\) with positive binary-rational masses \(\mu_A\) summing to \(1\), and fixed \(\epsilon\in(0,1)\), compute a committee \(W\subseteq C\) with \(|W|=k\) such that \(D_\mu(W)\le(1+\epsilon)\min_{|U|=k}D_\mu(U)\), where \(D_\mu(W)=\max_{A\in\mathcal{A}}|W\triangle A|\).
Represent society by a distribution \(\mu\) over complete approval-set types; choose an integral size-\(k\) committee minimizing maximum individual symmetric-difference dissatisfaction over positive-mass types.
Covers Theorem 1’s PTAS for minimax committee selection over supported approval types; leaves exact-optimization complexity, strategyproofness, and the paper’s suggested intermediate objectives unresolved.
The strongest honest mirror is a high-multiplicity version of Minimax Approval Voting, anchored by Theorem 1, proved in this paper. The theorem says that for every fixed \(\epsilon\in(0,1)\), given \(n\) approval votes over \(m\) candidates and a committee size \(k\), the authors compute a committee of exactly \(k\) candidates whose maximum Hamming distance from any vote is at most \((1+\epsilon)\mathrm{OPT}\), in time polynomial in \(n\) and \(m\). Here \(\mathrm{OPT}\) is the minimum, over all size-\(k\) committees, of that maximum distance.
My lead mirror is Continuous-Support Minimax Approval Voting PTAS. An instance consists of a candidate set \(C\), a committee size \(k\), and a finite list of approval types \(A\subseteq C\), each with a positive binary-rational mass \(\mu_A\), where the masses sum to \(1\). The type is the voter’s complete approval set; its mass is the fraction of society holding that type. For a committee \(W\subseteq C\) with \(|W|=k\), define its worst dissatisfaction as
\[
D_\mu(W)=\max_{A:\,\mu_A>0}|W\triangle A|.
\]
The question is: for any fixed \(\epsilon\in(0,1)\), compute such a committee \(W\) with \(D_\mu(W)\le(1+\epsilon)\min_{|U|=k}D_\mu(U)\). The solution remains an integral, fixed-size committee; only the society is represented continuously.
A plausible regime is a very large association or electorate choosing a small committee, where many members cast the same approval ballot: for example, millions of people but only hundreds or thousands of distinct approval types. Identical approval sets make members indistinguishable for this problem, so grouping them is faithful to the original question. The PTAS applies to the list of \(\tau\) positive-mass types, with running time polynomial in \(m,\tau,L\) for fixed \(\epsilon\), where \(L\) is the mass encoding length. The masses matter as population shares in the model, though the worst-voter objective depends only on which types have positive mass.
I expect the anchored approximation question to be tractable (Class A): apply Theorem 1 to one representative ballot per supported type. Repeating a ballot any number of times changes neither the optimum nor the worst-voter objective. The paper’s introduction also says that exact MAV is NP-hard, citing LeGrand [6]; that claim is not a numbered result proved here, so I do not use it as an anchor. It does give useful context: the exact continuous-support problem inherits that hardness by representing a finite profile with masses equal to its ballot frequencies. The PTAS mirror therefore makes no claim that exact optimization becomes easy.
I think the authors and a referee would recognize this as their problem: it keeps the same ballot, committee, and worst-individual-dissatisfaction semantics. My weakest point is that the mass values do not affect the maximum beyond determining support. This is a natural continuous-population formulation, but it adds less mass-sensitive structure than a transfer or resource-allocation mirror would. Natural follow-up questions are whether the PTAS can be improved to an FPTAS, and whether the exact problem has useful parameterized algorithms in \(\tau\).
For Theorem 1 and the proposed *Continuous-Support Minimax Approval Voting PTAS*, the strongest objection is that the continuous population’s masses are invisible to the objective. For a committee \(W\),
\[
D_\mu(W)=\max_{A:\,\mu_A>0}|W\triangle A|.
\]
Changing the mass of any supported approval type leaves this value unchanged; only adding or removing a type from the support can change it. So every instance reduces to the same optimization problem on one copy of each supported ballot. The encoding length of the masses \(L\) plays no role.
That makes the mirror’s claimed high-multiplicity regime a weak fit for this particular result. The paper’s objective already discards repeated voters: its input can be reduced to the set of distinct approval ballots before running the algorithm. The continuous formulation therefore adds mass labels to a problem that has already quotiented them away. It raises no new question about how population proportions affect committee selection, and the paper’s PTAS applies to that support problem directly. This is an objection about whether population continuization contributes a distinct computational object, not about whether the algorithm’s answer changes.
The tempting repair is a mass-sensitive objective, such as the worst dissatisfaction among at least an \(\alpha\) fraction of society. That could be a worthwhile continuous problem, but it changes the minimax objective and is not a mirror of Theorem 1. Keeping the paper’s objective leaves masses irrelevant; making masses matter requires a different anchor.
I would still call this a weak negative case, not a decisive defeat. Approval types are complete descriptions for this problem, and large populations with many repeated ballots are plausible. The continuous-support formulation is sensible. My case is that its population aspect is inert for this theorem, and the paper has already reduced the relevant input to ballot support. If the reader treats any such support formulation as a worthwhile high-multiplicity mirror, this anchor survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.