BERLIN Workshop on COMPUTATIONAL SOCIAL CHOICE 

Date: Thursday, 27th July, 2023

Location: TU Berlin, MAR Building 

Address: Marchstraße 23, 10587 Berlin

Room: MAR 0.009 0.010 (take a left turn after entering the building)

Contact: Markus Brill (brill@tu-berlin.de)


Abstracts at the bottom of this page

Schedule

10:30 – 10:45 Arrival & Registration

10:45 – 11:00 Welcome & Introduction

11:00 – 12:30 Session 1  (Session Chair: Markus Brill)

12:30 – 14:00 Lunch break

14:00 – 15:30 Session 2  (Session Chair: Niclas Boehmer)

15:30 – 16:30 Coffee break

16:30 – 17:45 Session 3  (Session Chair: Piotr Faliszewski)

From 18:30 Dinner & drinks @ Schleusenkrug Lemke am Schloss

ABSTRACTS

Michelle Döring: Margin of Victory for Weighted Tournament Solutions     

 

Determining how close a winner of an election is to becoming aloser, or distinguishing between different possible winners of an election, are major problems in computational social choice. We tackle these problems for so-called weighted tournament solutions by generalizing the notion of margin of victory (MoV) for tournamentsolutions by Brill et al. [Artificial Intelligence, 2022] to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda’s rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we determine whether the MoV for winners and non-winners is tractable and give upper and lower bounds on the possible values of the MoV. Further, we axiomatically study and generalize properties from the unweighted tournament setting to weighted tournaments.

 


Jobst Heitzig: Social Choice for AI alignment     

 

I will pitch ideas for how methods from social choice might be used in making artificial intelligence systems behave in accordance with their users' potentially diverging preferences. In particular, I'll report on a recent toy experiment on Reinforcement Learning from Collective Human Feedback (RLCHF) conducted during the Amsterdam Computational Social Choice Summer School.

 


Jonas Israel: Partial Spatial Voting

 

We consider spatial voting where candidates are located in the Euclidean $d$-dimensional space and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of computing the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules such that the possible-winner problem is intractable for partial orders, but tractable in the one-dimension spatial setting (while intractable in higher fixed number of dimensions).

 


Stanisław Szufa: Identifying Hidden Subelections           

 

We study the problem of finding hidden substructures in ordinal elections. First, we focus on the computational complexity. Second, we analyze the synthetic and real-life data.

 


Andrzej Kaczmarczyk: Maps of Resource Allocation       

 

In this project in progress, we make the first steps towards understanding and analyzing structural properties of data related to resource allocation of indivisible good. To this end, we first define structural distances between instances of the resource allocation problems. Then, we provide new models of generating resource allocation tasks. Finally, we apply our distances to analyze the space of allocation tasks.

 


Tuva Vigen Bardal: Size Approval Voting Rules


 

Javier Cembrano: Impartial Selection with Additive Guarantees via Iterated Deletion        

 

Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\kappa})$ nominations, where $\kappa\in[0,1]$. For $\kappa=0$, \ie when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

 


Piotr Faliszewski: Guide to Experiments

 

In this talk I will outline an effort to go over numerical experiments in computational social choice that regard elections. I will discuss the initial findings and outline the scope of future research.



Jérôme Lang: Voting behavior in one-shot and iterative multiple referenda          


We consider a set of voters making a collective decision via simultaneous vote on two binary issues. Voters’ preferences are captured by payoffs assigned to combinations of outcomes for each issue and they can be nonseparable: a voter’s preference over an issue might be dependent on the other issue. When the collective decision in this context is reached by voting on both issues at the same time, multiple election paradoxes may arise, as studied extensively in the theoretical literature. In this paper we pursue an experimental approach and investigate the impact of iterative voting, in which groups deliberate by repeating the voting process until a final outcome is reached. Our results from experiments run in the lab show that voters tend to have an optimistic rather than a pessimistic behaviour when casting a vote on a non-separable issue and that iterated voting may in fact improve the social outcome. We provide the first comprehensive empirical analysis of individual and collective behavior in the multiple referendum setting.

 


Jannik Peters: Robust and verifiable proportionality axioms for multiwinner voting

 

When selecting a subset of candidates (a so-called committee) based on the preferences of voters, proportional representation is often a major desideratum. When going beyond simplistic models such as party-list or district-based elections, it is surprisingly challenging to capture proportionality formally. As a consequence, the literature has produced numerous competing criteria of when a selected committee qualifies as proportional. Two of the most prominent notions are Dummett's proportionality for solid coalitions (PSC) and Aziz et al.'s extended justified representation (EJR). Both guarantee proportional representation to groups of voters who have very similar preferences; such groups are referred to as solid coalitions by Dummett and as cohesive groups by Aziz et al. However, these notions lose their bite when groups are only almost solid or almost cohesive. In this paper, we propose proportionality axioms that are more robust: they guarantee representation also to groups that do not qualify as solid or cohesive. Further, our novel axioms can be easily verified: Given a committee, we can check in polynomial time whether it satisfies the axiom or not. This is in contrast to many established notions like EJR, for which the corresponding verification problem is known to be intractable.


In the setting with approval preferences, we propose a robust and verifiable variant of EJR and a simply greedy procedure to compute committees satisfying it. In the setting with ranked preferences, we propose a robust variant PSC, which can be efficiently verified even for general weak preferences. In the special case of strict preferences, our notion is the first known satisfiable proportionality axiom that is violated by the Single Transferable Vote (STV). We also discuss implications of our results for participatory budgeting, querying procedures, and to the notion of proportionality degree.

 


Robert Bredereck: Efficiently Computing Smallest Agreeable Sets          

 

We study the computational complexity of identifying a small agreeable subset of items. A subset of items is agreeable if every agent does not prefer its complement set. We study the setting where agents can give arbitrary utilities to the items, can only approve or disapprove items, or rank the items with Borda scores. We prove all variants NP-hard, and perform a parameterized analysis regarding the natural parameters number of agents, number of items, and the upper bound on the size of the agreeable subset in question.

 


Markus Utke: Fractional Delegations for Liquid Democracy         

 

Liquid democracy is a novel voting scheme aiming at combining the idealistic appeal of direct democracy with the practicality of representative democracy. We examine liquid democracy with ranked delegations, where every voter can either vote for themselves or specify a ranking of trusted voters that they want to delegate their vote to. Delegations are transitive, so if A delegates to B and B to C, then C is assigned the voting power of both A and B and might even delegate it further. Different delegation rules that choose the representative of each voter were proposed for ranked delegations, however none of them can satisfy a specific set of four natural properties. We generalize the approach to fractional delegation rules, that can delegate partial votes to multiple trusted voters. We identify two characterizations of a fractional delegation rule satisfying (generalized versions of) all four properties and present a polynomial time algorithm for its computation.

 


Dominik Peters: Robust Rent Division     

 

In fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates’ reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find a robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects a rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based on polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming.

 

Joint work with Ariel D. Procaccia and David Zhu.

https://dominik-peters.de/publications/robust-rent-division.pdf