Second ViennaGraz Workshop on (Computational) Social Choice
The workshop will take place on February 8 and 9 at TU Wien.
February 8^{th} – 9^{th} 2024
 All day event.
 TU Wien, Faculty of Informatics, FAV Hörsaal 1

1040 Vienna, Favoritenstraße 911
Ground Floor, Room HH EG 02
On This Page
About the Event
Computational social choice is a rapidly growing field of research at the intersection of computer sciences, economics, and political science that studies how we can make collective decisions in a better and fairer way, from the distribution of household chores to national elections. The Series “ViennaGraz Workshop on (Computational) Social Choice” aims to bring together researchers from Vienna, Graz and beyond that work on (Computational) Social Choice and related fields. After a first successful edition in Graz, we are proud to host this year’s edition at TU Wien.
Program
Thursday, February 8, 2024
11:30  12:15
Julia Neidhardt (TU Wien):
Recommender Systems and Social ChoiceThis talk explores the connection between recommender systems and social choice theory. We start with an introduction to recommender systems, covering various recommendation techniques. The discussion then shifts to group recommender systems, emphasizing the application of social choice theory in this context. Finally, we examine current research trends that integrate recommender systems with social choice theory, particularly focusing on fairnessaware recommendations.
12:15  13:00
Carolina Plescia (Uni Wien):
Do people want a ‘fairer’ electoral system? An experimental study in four countries(joint work with André Blais and John Högström)
When judging how ‘fair’ voting rules are, a fundamental criterion used by both scholars and politicians is their ability or inability to produce proportional results – that is, the extent parties’ seat distribution after the elections accurately reflects their vote shares. How about citizens? Do citizens care about how proportional the outcome is? Or do they judge the outcome solely on the basis of how well (or poorly) their party performed? Taking advantage of a uniquely designed survey experiment, this article investigates the causal effect of proportionality on voter support for voting rules in four countries: Austria, England, Ireland and Sweden. The results show that proportionality drives support for the voting rules not above, but beyond party performance. There is little crosscountry variation, which suggests that proportionality is appreciated in different contexts with little status quo bias. These findings have important implications for our understanding of the causal mechanisms linking electoral rules to voter support.
13:00  14.30
Lunch Break
14:30  15:15
Rudolf Vetschera (Uni Wien):
Twoperson fair division with additive valuations(joint work with D. Marc Kilgour)
In the literature, many desirable properties for allocations of indivisible goods have been proposed, including envyfreeness, Pareto optimality, and maximization of either the total welfare of all agents, the welfare of the worstoff agent, or the Nash product of agents' welfares. In the twoperson context, we study relationships among these properties using both analytical models and simulation in a setting where individual preferences are given by additive cardinal utilities. We provide several new theorems linking these criteria and use simulation to study how their values are related to problem characteristics, assuming that utilities are assigned randomly. We draw some conclusions concerning the relation of problem characteristics to the availability of allocations with particular properties.
15:15  16:00
Christian Klamler (Uni Graz):
Adjusted Winner with Indivisible Items and Money(joint work with D. Marc Kilgour and Steven J. Brams)
Adjusted Winner (AW) is an algorithm for dividing divisible items between two players that satisfies three properties of fairness: envyfreeness (EF), equitability (EQ), and Paretooptimality (PO). In this paper, we consider whether a similar EFEQPO allocation exists when all items are indivisible except one item m (for money).
We show that it is possible for there to be no EF allocation. Alternatively, EFPO allocations may exist, but none of them may be EQ. But we also find a condition (Condition C) that is sufficient to guarantee that an EFEQ allocation exists and show that a procedure we call AWm yields an EFEQ allocation. Unfortunately, the AWm allocation may not be PO within the set of all EFEQ allocations, but we suggest how to adjust it to find an EFEQ allocation that is Paretosuperior.
Computer simulations indicate, if all possible valuations of the indivisible items and m are equiprobable, that Condition C is satisfied 67% of the time, increasing to 96% when the players’ valuations of m are at least equal to the average valuation of an item. Although information on the preferences of a player can make AWm manipulable, a player is assured of obtaining at least 50% of its valuation of all items if it is truthful and Condition C is satisfied. We apply AWm to the division of marital property in a reallife divorce and suggest its application to other fairdivision situations with indivisible items and a divisible asset like money.
16:00  16:30
Coffee Break
16:30  17:15
Andreas Darmann (Uni Graz):
Minimizing Agents’ Dissatisfaction under Preference Graphs(joint work with Nina Chiarelli, Clément Dallard, Stefan Lendl, Martin Milanič, Peter Muršič and Ulrich Pferschy)
We consider the problem of allocating indivisible items to agents, where each item can be assigned to at most one agent. Each agent has preferences over the single items, which are expressed by means of a dedicated directed acyclic graph, the socalled preference graph: the items desired by an agent are represented by the vertices of the graph, and an arc (a, b) means that the agent prefers item a over item b. In such a setting, we measure the dissatisfaction of an agent with an allocation in terms of the number of nonreceived items which are desired by the agent and for which no more preferred item is allocated to the agent.
In particular, the following two problem variants are tackled: seeking an allocation of the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents or (ii) the maximum dissatisfaction among the agents. For each of the variants we analyze the status of computational complexity involved. The obtained results include NPhardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. Besides the general case, we also consider the situation in which the agents have identical preferences (i.e., all agents have the same preference graph); this scenario allows for additional positive results.
17:15  18:00
Oliviero Nardi (TU Wien):
Repeated Fair Allocation of Indivisible Items(joint work with Ayumi Igarashi, Martin Lackner and Arianna Novaro)
The problem of fairly allocating a set of indivisible items is a wellknown challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envyfreeness and proportionality) and efficiency (such as Paretooptimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In the case of a fixed number of repetitions, we show that if this number is a multiple of the number of agents, a proportional and Paretooptimal sequence of allocations always exists. On the other hand, irrespective of the number of repetitions, an envyfree and Paretooptimal sequence of allocations may not exist. However, for the special case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envyfree and Paretooptimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envyfreeness. Finally, if the number of repetitions can be chosen freely, we show that envyfree and Paretooptimal allocations are achievable for any number of agents.
Friday, February 9, 2024
9:00  9:45
Philipp Peitler (Uni Wien):
Putting Context into Preference Aggregation(joint work with Karl Schlag)
The axioms underlying Arrow's impossibility theorem are very restrictive in terms of what can be used when aggregating preferences. Social preferences may not depend on the menu nor on preferences over alternatives outside the menu. But context matters. So we weaken these restrictions to allow for context to be included. The context as we define describes which alternatives in the menu and which preferences over alternatives outside the menu matter. We obtain unique representations. These are discussed in examples involving markets, bargaining and intertemporal wellbeing of an individual.
9.45  10.30
Daniel Eckert (Uni Graz):
A Problem with the Many: Suszko’s Thesis and Arrow’s Theorem(joint work with Karl Schlag)
Based on an early formulation of preference aggregation by Skala (1978) as booleanvalued models, we use Suszko's reduction to establish Arrow's impossibility theorem.
10:30  11:00
Coffee Break
11:00  11:45
Christian Hatschka (TU Wien):
Algorithms for MultiWinner Elections with Structured Preferences(joint work with Jiehua Chen and Sofia Simola)
We investigate winner determination for two popular proportional representation systems: the Monroe and ChamberlinCourant (abbrv. CC) systems. Our study focuses on (nearly) singlepeaked resp. singlecrossing preferences. We show that for single crossing approval preferences, winner determination of the Monroe rule is polynomial and show some results for nearly structured preferences as well.
11.45 12.30
Matthias Greger (TU München):
Dynamics for Aggregating Cardinal Preferences(joint work with Florian Brandl, Felix Brandt, Dominik Peters, Christian Stricker, Erel SegalHalevi, Warut Suksompong)
We consider the problem of aggregating cardinal preferences over distributions over a finite set of alternatives from a gametheoretic point of view. In detail, instead of having a central aggregation mechanism, each agent is equipped with a certain amount of "decision power". Restricting ourselves to two specific utility models, namely linear and Leontief utility functions, we show that Nash welfare (the product of agents' utilities) is maximized by the limits of two natural dynamic processes. Advantages and disadvantages of such a dynamical approach are also discussed. The talk is based on contents from Funding Public Projects: A Case for the Nash Product Rule and Balanced Donor Coordination.
12:30  14:00
Lunch Break
14:00  14:45
Adrian Haret (LMU München):
Game Theoretic Foundations for Multiwinner Voting(joint work with Sophie Klumper, Jan Maly and Guido Schäfer)
A key intuition underlying many fairness axioms in multiwinner voting is that an optimal outcome is attained when no subset of voters can improve their position by reallocating their endorsements. In the talk, we will see how to formalize this intuition using a new class of games we call budgeting games, where committees occur as a result of voters’ decisions about how to allocate a given budget. Key notions in multiwinner voting theory, such as priceability, the core and EJR (Extended Justified Representation) can be thought of as equilibria of budgeting games. Remarkably, our budgeting games do not just capture existing concepts, but also give rise to entirely new families of voting rules. Such rules are based on improvingmove dynamics in the respective budgeting games, and include the wellknown Method of Equal Shares. Finally, existence of strong equilibria in a restricted version of our budgeting games implies nonemptiness of the core for a special class of multiwinner elections.
14:45  15:30
Michael Bernreiter (TU Wien):
Combining Voting and Abstract Argumentation to Understand Online Discussions(joint work with Jan Maly, Oliviero Nardi and Stefan Woltran)
Online discussion platforms are a vital part of the public discourse in a deliberative democracy. However, how to interpret the outcomes of the discussions on these platforms is often unclear. In this paper, we propose a novel and explainable method for selecting a set of most representative, consistent points of view by combining methods from computational social choice and abstract argumentation. Specifically, we model online discussions as abstract argumentation frameworks combined with information regarding which arguments voters approve of. Based on ideas from approvalbased multiwinner voting, we introduce several voting rules for selecting a set of preferred extensions that represents voters’ points of view. We compare the proposed methods across several dimensions, theoretically and in numerical simulations, and give clear suggestions on which methods to use depending on the specific situation.