Erratum to "Proportionality and Strategyproofness in Multiwinner Elections" [1]
Dominik Peters, 2020-02-16
Boas Kluiving, Adriaan de Vries, and Pepijn Vrijbergen (University of
Amsterdam) have pointed out to me that the proof of Lemma 5.5 (the
induction step that shows that if there exists a good rule for m+1
alternatives, then there exists one for m alternatives) contains a gap:
it is not clear why the rule f_m does not elect candidate c_{m+1}.
I do not know how to fix this gap, and regret the error.
One solution is given in a version of this paper that appears in my
DPhil thesis [2] in chapter 7. There, I add an additional axiom called
weak efficiency. It requires that a candidate who is approved by no
voter may not be part of the winning committee, unless there are fewer
than k candidates in total that receive at least one approval.
For small parameter values, the SAT solver indicates that the main
theorem of the paper holds as stated (without weak efficiency), but
I can't prove suitable induction steps. I would be very interested
in a proof.
=====
Added 2023-10-02:
Another possible solution goes along the following lines:
(1) Change the model to allow rules to output committees of size at
most k instead of exactly k (this strengthens an impossibility).
(2) Weaken strategyproofness to only allow manipulations where
before the manipulation none of the approved alternatives
were winning and manipulations where after the manipulation
all approved alternatives are winning.
(3) Strengthen proportionality to JR.
Notice that Lemma 5.2 now follows from (3). One can check that the
proof of the base case works even with (1) and (2).
The induction step for n works even for (1) by using (2).
The induction step for m work because of (1).
The induction step for k works because of (3).
=====
[1] D. Peters. Proportionality and strategyproofness in multiwinner
elections. In Proceedings of the 17th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS), pages 1549–1557, 2018.
[2] D. Peters. Fair Division of the Commons. DPhil thesis,
University of Oxford, 2019.
https://dominik-peters.de/publications/thesis.pdf#page=97