The task in judgment aggregation is to find a collective judgment set based on the views of individual judges about a given set of propositional formulas. One way of guaranteeing consistent outcomes is the use of sequential rules. In each round, the decision on a single formula is made either because the outcome is entailed by the already obtained judgment set, or, if this is not the case, by some underlying rule, e.g. the majority rule. Such rules are especially useful for cases, where the agenda is not fixed in advance, and formulas are added one by one. This paper investigates the computational complexity of winner determination under a family of sequential rules, and the manipulative influence of the processing order on the final outcome.

Complexity of Sequential Rules in Judgment Aggregation

Tournaments are commonly used to identify winners, for example in sports. We study the computational complexity of problems related to scheduling the matches in a tournament and predicting the outcome with a special focus on round-robin tournaments, which is the most prominent tournament type used in sports. Besides the general financial and intrinsically motivated interest of various agents in tournament prediction, the recently very relevant winner determination for suddenly discontinued tournaments is a strong motivation. We show the immense theoretical complexity of predicting the winners in round-robin tournaments even under the assumption that only three matchdays remain to be played. On the other hand, we present an FPT algorithm and analyze its practical complexity using experiments on real-world and generated data, showing the applicability of the algorithm in praxis. To the best of our knowledge, this is the first exact and not purely brute-force oriented approach for predicting round-robin tournaments.

Complexity of Scheduling and Predicting Round-Robin Tournaments

When dealing with election data it is reasonable to assume that the votes are incomplete or noisy. The reasons are manifold and range from cost-intensive elicitation to manipulation. We study the important questions of evaluating elections with incomplete data and the robustness of elections with noisy data from a computational point of view. To capture different motivations, we consider three models for the distribution of preferences: the uniform distribution over the completions of incomplete preferences inspired by the possible winner problem, the dispersion around complete preferences, also called Mallows noise model, and a model in which the distribution over the votes of each voter is explicitly given. We consider both approval vector preferences and linear order preferences and show that the complexity of the problem can vary greatly depending on the voting rule, the distribution model, and the parameterization.


Complexity of Election Evaluation and Probabilistic Robustness

In participatory budgeting, citizens can take part in the decision on which projects a city should spend money. Formally, the input is a set of items, each having a certain cost, while agents can express their preferences. The task is to choose a set of items respecting a given bound. Recently Talmon and Faliszewski introduced a framework for budgeting based on approval votes. This paper revisits the introduced methods axiomatically from an irresolute point of view, especially showing that two of the proposed methods coincide. The study is complemented by approximation results.


Irresolute Approval-based Budgeting

In classical elections, voters only submit their ballot once, whereas, in iterative voting, the ballots may be changed iteratively. Following the work by Wilczynski [2019], we consider the case where a social network represents an underlying structure between the voters, meaning that each voter can see her neighbors’ ballots. In addition, there is a polling agency, which publicly announces the result for the initial vote. This paper investigates the manipulative power of the polling agency. Previously, Wilczynski [2019] studied constructive manipulation for the plurality rule. We introduce destructive manipulation and extend the study to the veto rule. Several restricted variants are considered with respect to their parameterized complexity. The theoretical results are complemented by experiments
using different heuristics.

Manipulation of Opinion Polls to Influence Iterative Elections

Hemaspaandra [22] celebrated the quite close relationship between computational social choice and computational complexity as a two-way street from which both areas benefited in the past, and expressed his hope that the areas become best friends forever. Later on, Rothe [38] celebrated the prominent Borda voting rule and surveyed recent advances on the complexity of problems related to the three most fundamental models of tampering with elections—namely, via manipulation, control, and bribery—and even related to using Borda beyond voting: in fair division and coalition formation in hedonic games. But now the party is over: no more celebration! Instead, we present a common criticism regarding computational social choice persistently making use of worst-case complexity. To overcome this shortcoming, we propose our blue sky idea of applying to problems from computational social choice the method of smoothed analysis due to Spielman and Teng [43, 44] and also
used by Bläser and Manthey [7], as some sort of a middle ground between the worst-case and the average-case analysis of algorithms.

Towards Reality: Smoothed Analysis in Computational Social Choice

S1: Computational Social Choice 2

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

S1: Computational Social Choice 1

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). 

Dorothea Baumeister

6

1

Presentations

Complexity of Sequential Rules in Judgment Aggregation

Complexity of Scheduling and Predicting Round-Robin Tournaments

Complexity of Election Evaluation and Probabilistic Robustness

Irresolute Approval-based Budgeting

Manipulation of Opinion Polls to Influence Iterative Elections

Towards Reality: Smoothed Analysis in Computational Social Choice

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES