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.
[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.