First Vienna Workshop on
Computational Social Choice
Computational social choice is a rapidly growing field of research at the intersection of computer sciences and economics, specifically social choice theory. Its goal is the study of computational aspects of collective decision making. On the one hand, computational social choice aims to apply techniques from (theoretical) computer science, such as complexity analysis and algorithm design, to questions of social choice theory, like voting and stable matching. On the other hand, methods from social choice theory are applied to problems that appear in computer sciences, for example in network design or multiagent systems.
The goal of the First Vienna Workshop on Computational Social Choice is to bring together the growing community of researchers in Vienna interested in computational social choice and connect them with leading experts in the field. The workshop took place on September 25, 2020.
ORGANIZATION
Stefan Woltran
Martin Lackner
Jan Maly
PROGRAM AND SCHEDULE
Friday, September 25
First Session |
||
|---|---|---|
| 09:00 | Christian Klamler | Empirical Analysis of the 2015/2019 Styrian Parliamentary Elections |
| 09:35 | Martin Lackner | Perpetual Voting: Fairness in Long-Term Decision Making |
| 10:00 | Coffee Break | Second Session |
| 10:45 | Jérôme Lang | Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions. (Survey talk) |
| 11:20 | Jiehua Chen | How Hard Is It to Satisfy (Almost) All Roommates? |
| 11:45 | Thekla Hamm | Choosing Impactful Actions to Win an Election |
| 12:05 | Lunch |
ABSTRACTS
Empirical Analysis of the 2015/2019 Styrian Parliamentary Elections
Christian Klamler, Universität Graz
We use preference data from the 2015 and 2019 parliamentary elections in the Austrian federal state of Styria to analyze different voting rules. Via exit polls right after the official elections, ordinal and cardinal preference information from approximately 1000 voters in each election was collected. First, the hypothetical social outcomes under different voting rules are compared. Second, a categorization of different types of parties and the impact of different voting rules on such types is investigated. Finally, consistency and stability aspects are analyzed.
Perpetual Voting: Fairness in Long-Term Decision Making
Martin Lackner, TU Wien
In this talk I will introduce a new voting formalism to support long-term collective decision making: Perpetual voting rules. These are voting rules that take the history of previous decisions into account. Due to this additional information, perpetual voting rules may offer temporal fairness guarantees that cannot be achieved in singular decisions. In particular, such rules may enable minorities to have a fair (proportional) influence on the decision process and thus foster long-term participation of minorities. The proposed voting rules are explored via an axiomatic analysis and perpetual voting rules that are particularly recommendable in long-term collective decision making are identified.
Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions. (Survey talk)
Jérôme Lang, Université Paris-Dauphine
Most solution concepts in collective decision making are defined assuming complete knowledge of individuals' preferences and of the mechanism used for aggregating them. This is often unpractical or unrealistic. Under incomplete knowledge, a solution advocated by many consists in quanrtifying over all completions of the incomplete preference profile (or all instantiations of the incompletely specified mechanism). Voting rules can be 'modalized' this way (leading to the notions of possible and necessary winners), and also efficiency and fairness notions in fair division, stability concepts in coalition formation, and more. I give here a (brief) survey of works along this line.
How Hard Is It to Satisfy (Almost) All Roommates?
Jiehua Chen, TU Wien
The classic Stable Roommates problem (which is the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e., a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who she prefers to have as a partner, and two agents form a blocking pair if they prefer to be with each other rather than with their assigned partners.
Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egalitarian Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost γ, i.e., the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if she is matched; otherwise it is the length of its preference list. We also study finding almost stable matchings, formalized as the Minimum Blocking Pair Stable Roommates problem, which seeks to find a matching with a minimum number β of blocking pairs. Our main result is that Egalitarian Stable Roommates parameterized by γ is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by β is W[1]-hard, even if the length of each preference list is at most five.
Choosing Impactful Actions to Win an Election
Thekla Hamm, TU Wien
We study a fundamental question that lies at the center of every election campaign: which actions can one take in order to win an upcoming election? To capture this, we propose a natural and highly versatile model focusing on how individual actions can impact the preferences of voters over candidates. The problem of choosing a set of actions (with predetermined effects) that will allow the selected candidate to win the election in this model generalises problems in the related settings electoral control. As the problem is NP-complete in general, we initiate its study through the lens of parameterised complexity and obtain a complete complexity picture with respect to the most obvious parameterisations of the problem. We also showcase how the identified algorithmic lower bounds can be circumvented by developing a treewidth based algorithm for the problem which can solve instances comprising a large number of voters, candidates and actions.
VENUE
Hörsaal FAV01
TU Wien, Favoritenstraße 9-11
PARTICIPANTS
Michael Bernreiter, TU Wien
Jiehua Chen, TU Wien
Daniel Eckert, Univ. Graz
Robert Ganian, TU Wien
Thekla Hamm, TU Wien
Christian Klamler, Univ. Graz
Martin Lackner, TU Wien
Jérôme Lang, Université Paris Dauphine
Timo Lang, TU Wien
Jan Maly, TU Wien
Anna Rapberger, TU Wien
Johannes Wallner, TU Wien
Stefan Woltran, TU Wien
PHOTOS
SPONSORS
The workshop is supported by the VCLA.
