Social choice functions (SCFs) map the preferences of a group of agents over some set of alternatives to a non-empty subset of alternatives. The Gibbard-Satterthwaite theorem has shown that only extremely unattractive single-valued SCFs are strategyproof when there are more than two alternatives. For set-valued SCFs, or so-called social choice correspondences, the situation is less clear. There are miscellaneous--mostly negative--results using a variety of strategyproofness notions and additional requirements. The simple and intuitive notion of Kelly-strategyproofness has turned out to be particularly compelling because it is weak enough to still allow for positive results. For example, the Pareto rule is strategyproof even when preferences are weak, and a number of attractive SCFs (such as the top cycle, the uncovered set, and the essential set) are strategyproof for strict preferences. In this paper, we show that, for weak preferences, only indecisive SCFs can satisfy strategyproofness. In particular, (i) every strategyproof rank-based SCF violates Pareto-optimality, (ii) every strategyproof support-based SCF (which generalize Fishburn's C2 SCFs) that satisfies Pareto-optimality returns at least one most preferred alternative of every voter, and (iii) every strategyproof non-imposing SCF returns a Condorcet loser in at least one profile.

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

An important aspect of multi-agent systems concerns the formation of coalitions that are stable or optimal in some well-defined way. The notion of popularity has recently received a lot of attention in this context. A partition is popular if there is no other partition in which more agents are better off than worse off. 
In 2019, a long-standing open problem concerning popularity was solved by proving that computing popular partitions in roommate games is NP-hard, even when preferences are strict. We show that this result breaks down when allowing for randomization: mixed popular partitions can be found efficiently via linear programming and a separation oracle. Mixed popular partitions are particularly attractive because they are guaranteed to exist in any coalition formation game.
Our result implies that one can efficiently verify whether a given partition in a roommate game is popular and that strongly popular partitions can be found in polynomial time (resolving an open problem). By contrast, we prove that both problems become computationally intractable when moving from coalitions of size 2 to coalitions of size 3, even when preferences are strict and globally ranked.


Finding and Recognizing Popular Coalition Structures

Coalition formation games aim at predicting the cooperative behavior of agents when forming alliances. Agents entertain preferences over coalition structures, and the goal is to find a coalition structure that is good for both individual agents and the society as an entity. We measure the quality of partitions in terms of Pareto optimality, individual rationality, and various notions of popularity. We give both efficient algorithms and hardness results for computing partitions that satisfy these properties for additively separable hedonic games and give an outlook to results on other classes of coalition formation games, including roommate games and flatmate games.

Desirable Partitions in Coalition Formation Games



**Session chair:** Dorothea Baumeister

S1: Computational Social Choice 3

technical paper

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

AAMAS 2021

Social Choice and Cooperative Game Theory

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS 2020

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

Martin Bullinger

3

6

SHORT BIO

Presentations

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

Finding and Recognizing Popular Coalition Structures

Desirable Partitions in Coalition Formation Games

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES