We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a given number of voters).  We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random is challenging and we propose a simple algorithm that does not offer guarantees on the distribution. Next, we consider the problem of testing if a given matrix can be implemented by an election with certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of testing if a given position matrix can be implemented by an election with a Condorcet winner.  We complement our theoretical findings with experiments.

Properties of Position Matrices and Their Elections

We study the formation of stable outcomes via simple dynamics in cardinal hedonic games, where the utilities of agents change over time depending on the history of the coalition formation process. Specifically, we analyze situations where members of a coalition decrease their utility for a leaving agent (resent) or increase their utility for a joining agent (appreciation). We show that, in contrast to classical dynamics, for resentful or appreciative agents, dynamics are guaranteed to converge under mild conditions for various stability concepts. Thereby, we establish that both resent and appreciation are strong stability driving forces.

Causes of Stability in Dynamic Coalition Formation

To aggregate rankings into a social ranking, one can use scoring systems such as Plurality, Veto, and Borda. We distinguish three types of methods: ranking by score, ranking by repeatedly choosing a winner that we delete and rank at the top, and ranking by repeatedly choosing a loser that we delete and rank at the bottom. The latter method captures the frequently studied voting rules Single Transferable Vote (aka Instant Runoff Voting), Coombs, and Baldwin. In an experimental analysis, we show that the three types of methods produce different rankings in practice. We also provide evidence that sequentially selecting winners is most suitable to detect the "true" ranking of candidates. For different rules in our classes, we then study the (parameterized) computational complexity of deciding in which positions a given candidate can appear in the chosen ranking. As part of our analysis, we also consider the Winner Determination problem for STV, Coombs, and Baldwin and determine their complexity when there are few voters or candidates. 

Rank Aggregation Using Scoring Rules


A classical problem in the fair allocation literature is finding an envy-free assignment of indivisible resources to agents with additive utility-based preferences over resources. Motivated by the possible non-existence but evident need of envy-free allocations in some applications, we study the following problem modeling one possible way out: Given an allocation of indivisible resources to agents, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

Multivariate Algorithmics for Eliminating Envy by Donating Goods


We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

A Refined Complexity Analysis of Fair Districting over Graphs


Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone's preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents' preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences


In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex.
The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

Equilibria in Schelling Games: Computational Hardness and Robustness

Following up on purely theoretical work, we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we perform extensive empirical studies hinting at numerous practically useful properties. Our theoretical extensions include the study of new problems (that is, incremental variants of Almost Stable Marriage and Hospital Residents), focusing on their (parameterized) computational complexity and the equivalence of various change types (thus simplifying algorithmic and complexity-theoretic studies for various natural change scenarios). Our experimental findings reveal, for instance, that allowing the new matching to be blocked by a few pairs significantly decreases the difference between the old and the new matching.

Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets

A recent report of Littmann published in the Communications of the ACM outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem Cycle-Free Reviewing that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit.

We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that Cycle-Free Reviewing is NP-hard in various restricted cases (i.e., when every author is qualified to review all papers and one wants to prevent that authors review each other's or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.

Combating Collusion Rings is Hard but Possible

The area of computational social choice (COMSOC) analyzes collective decision problems from an algorithmic perspective. So far, the main focus in this area lied on analyzing problems where a single preference relation for each agent is given and a single solution reflecting all agents' preferences needs to be found. However, this modeling is often not rich enough to capture the changing and ambivalent nature of real-world problems. We will argue that one possibility to incorporate such aspects is to allow for multiple preference profiles in the input and multiple solutions in the output. We systematically review different types of arising settings, point out how classical problems and solution concepts can be generalized, and identify several research challenges.

Broadening the Research Agenda for Computational Social Choice: Multiple Preference Profiles and Multiple Solutions (Blue Sky Ideas Track)

Posters & Demos II

poster

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

GTEP: Cooperative Game Theory, Social Choice / Voting

GTEP: Social Choice / Voting 1

Oral Session 2B1-1

technical paper

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).

A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS 2022

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Poster & Demo Session PD1C

Oral Session 1C1-1

Main_Track

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

S1: Computational Social Choice 2

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 

Niclas Boehmer

10

10

SHORT BIO

Presentations

Properties of Position Matrices and Their Elections

Causes of Stability in Dynamic Coalition Formation

Rank Aggregation Using Scoring Rules

Multivariate Algorithmics for Eliminating Envy by Donating Goods

A Refined Complexity Analysis of Fair Districting over Graphs

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences

Equilibria in Schelling Games: Computational Hardness and Robustness

Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets

Combating Collusion Rings is Hard but Possible

Broadening the Research Agenda for Computational Social Choice: Multiple Preference Profiles and Multiple Solutions (Blue Sky Ideas Track)

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES