Second Vienna-Graz Workshop on (Computational) Social Choice
The workshop will take place on February 8 and 9 at TU Wien.
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 “Vienna-Graz 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.
Thursday, February 8, 2024
11:30 - 12:15
Julia Neidhardt (TU Wien):Recommender Systems and Social Choice
This 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 fairness-aware 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 cross-country 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
14:30 - 15:15
Rudolf Vetschera (Uni Wien):Two-person 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 envy-freeness, Pareto optimality, and maximization of either the total welfare of all agents, the welfare of the worst-off agent, or the Nash product of agents' welfares. In the two-person 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: envy-freeness (EF), equitability (EQ), and Pareto-optimality (PO). In this paper, we consider whether a similar EF-EQ-PO 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, EF-PO 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 EF-EQ allocation exists and show that a procedure we call AWm yields an EF-EQ allocation. Unfortunately, the AWm allocation may not be PO within the set of all EF-EQ allocations, but we suggest how to adjust it to find an EF-EQ allocation that is Pareto-superior.
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 real-life divorce and suggest its application to other fair-division situations with indivisible items and a divisible asset like money.
16:00 - 16:30
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 so-called 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 non-received 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 NP-hardness 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 well-known challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and efficiency (such as Pareto-optimality). 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 Pareto-optimal sequence of allocations always exists. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal 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 envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness. Finally, if the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal 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 well-being 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 boolean-valued models, we use Suszko's reduction to establish Arrow's impossibility theorem.
10:30 - 11:00
11:00 - 11:45
Christian Hatschka (TU Wien):Algorithms for Multi-Winner 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 Chamberlin-Courant (abbrv. CC) systems. Our study focuses on (nearly) single-peaked resp. single-crossing 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.
Matthias Greger (TU München):Dynamics for Aggregating Cardinal Preferences
(joint work with Florian Brandl, Felix Brandt, Dominik Peters, Christian Stricker, Erel Segal-Halevi, Warut Suksompong)
We consider the problem of aggregating cardinal preferences over distributions over a finite set of alternatives from a game-theoretic 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
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 improving-move dynamics in the respective budgeting games, and include the well-known Method of Equal Shares. Finally, existence of strong equilibria in a restricted version of our budgeting games implies non-emptiness 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 approval-based 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.