Incentives and Expressiveness in Multi-Winner Approval-Based Elections

Abstract: The focus of this talk is on elections with approval ballots. Approval voting is a popular format that has been used extensively for committee selection and other multi-issue elections. A voting rule in this setting takes as input ballots where each agent specifies her approved subset among m available alternatives, and outputs a binary decision for each alternative.

In the first part of the talk, we will consider questions related to the strategic behavior of the voters. It is known that strategyproof voting rules exist under approval ballots, such as the Minisum rule, where no voter can become better off by unilaterally misreporting her preferences. The picture however is different when it comes to coalitional manipulations where a coalition of voters attempt to alter their ballots so that the new outcome is strictly better for some members and at least as good for the remaining coalition. Voting rules that are robust against this strategic behaviour are called strongly group-strategyproof (GSP). Our main result is that strongly GSP approval-based voting rules which furthermore satisfy the minimum efficiency requirement of unanimity do not exist. Our proof builds a connection to single-winner voting with ranking-based ballots and exploits the infamous Gibbard-Satterthwaite theorem to reach the desired impossibility result.

In the second part of the talk, we consider more expressive models of approval voting, where the voters can also specify conditional preferences on the alternatives, via dependency graphs. We focus on a generalization of the classic Minisum rule, introduced by Barrot and Lang (2016), and referred to as Conditional Minisum. Under this model, the price we have to pay for the higher level of expressiveness is that we end up with a computationally hard rule. Motivated by this, we study special cases that admit efficient algorithms for CMS. Our main result in this direction is that we identify the condition of bounded treewidth (of an appropriate graph, emerging from the provided ballots) as the necessary and sufficient condition for exact polynomial algorithms.

Bio:  Vangelis Markakis has been a faculty member, currently an Associate Professor, in the department of Informatics of the Athens University of Economics and Business, since 2009. He received his M.Sc. (2004) and Ph.D. degree (2005) from the Georgia Institute of Technology, USA. Later on, he worked as a postdoctoral researcher at the University of Toronto (Canada, 2005-2006) and at CWI (Center for Mathematics and Computer Science, the Netherlands, 2007-2008). He has also held research appointments with Stanford University (visiting scholar, Spring 2014) and Input Output Global (research fellow, Fall 2022-present). His research interests lie in theoretical computer science and algorithmic game theory, with an emphasis on resource allocation problems, mechanism design, and more broadly on algorithms for combinatorial optimization. He has also participated as a management committee member in EU networks on related topics and in several basic research projects funded by the EU and by the Greek State.