Report

Teaser, summary, work performed and final results

Periodic Reporting for period 3 - ACCORD (Algorithms for Complex Collective Decisions on Structured Domains)

Teaser

The project is concerned with design and analysis of mechanisms for aggregating collective preferences, where the output of the mechanism may have complex structure (e.g., a fixed-size set of winners; a winner and runners-up; a ranking of alternatives). While in general the...

Summary

The project is concerned with design and analysis of mechanisms for aggregating collective preferences, where the output of the mechanism may have complex structure (e.g., a fixed-size set of winners; a winner and runners-up; a ranking of alternatives). While in general the associated computational problems may be intractable, a particular focus of the project is on existing and new restricted preference domains for which tractability results are more likely; examples of such domains include preferences that are essentially single-dimensional, such as single-peaked and single-crossing preferences, and their extensions. The goal is to formulate desirable properties of preference aggregation mechanisms with complex outputs, to design mechanisms that have many of these properties, and identify preference domains for which these mechanisms are computationally tractable. This project is important for society, as preference aggregation is a fundamental building block of democratic decision-making, and having better preference aggregation mechanisms will enable the society to make democratic decisions in a wider range of scenarios. The overarching goal of this line of research is to provide computationally efficient and theoretically justified tools for collective decision making, together with a good understanding of the limits of their applicability.

Work performed

Significant progress has been made on identifying new restricted domains that make collective decision-making problems computationally tractable, and on axiomatic analysis of multiwinner voting rules, both for rules defined on ranked ballots and for rules defined on approval ballots.

Martin Lackner (RA on the project) and Dominik Peters (a PhD student of the PI, who has recently joined the project as an RA on a part-time basis) introduced the domain of preferences single-peaked on a circle, and obtained a number of algorithmic results for it, including an efficient algorithm for recognizing such preferences as well as algorithms for some voting rules that are NP-hard for the general domain. Another restricted preference domain that has been studied is that of preferences single-peaked on trees. The PI together with Dominik Peters has identified several subdomains of this domain that can be efficiently recognized and admit polynomial-time algorithms for winner determination under the Chamberlin--Courant voting rule. Finally, Dominik Peters has established that another potentially useful restricted domain, that of d-dimensional Euclidean preferences, is hard to recognize for any constant d>1. In a recent journal paper, Martin Lackner (an RA on the project) has provided a number of algorithms and intractability results for the problem of recognizing preferences that are almost single-peaked, for various notions of distance to the single-peaked domain.

A number of papers identified new settings where one can obtain positive algorithmic or existence results by focusing on restricted preference domains. In her ADT\'15 paper the PI (together with an external collaborator) proposed a family of rules that extend the Chamberlin--Courant rule and showed that rules in this family are efficiently computable when preferences are single-peaked or single-crossing. Further, restricting the preferences to belong to the single-peaked or single-crossing domain has been shown to be useful for computing Nash equilibria of Plurality voting, and we can describe the outcome of a natural opinion diffusion process for preferences that are single-peaked and single-crossing.

The PI also gave an invited talk in Early Career Spotlight track at IJCAI\'16, where she summarized existing work on restricted preference domains and future research directions.

The PI has published two papers in Social Choice and Welfare (the leading social choice journal) that deal with axiomatic properties of committee selection rules. One of these papers lays the axiomatic foundations for committee selection rules that are based on scoring functions, in the context of ranked ballots. In particular, this paper defined the family of committee scoring rules, which provides an analogue to the important family fo scoring rules in the context of single-winner elections; this family has been subsequently analyzed by Piotr Skowron (an RA on the project) and co-authors in a series of papers. The second SCW paper focuses on committee selection rules that are based on approval ballots, and formulates the axiom of justified representation for such rules, as well as its extension called extended justified representation. Both axioms turned out to be useful tools for classifying approval-based voting rules and present interesting algorithmic challenges; in particular, the latter axiom can be used to characterize a prominent voting rule (PAV) in the class of weighted approval-based rules. In a follow-up paper, the PI together with two project RAs and external collaborators defined an intermediate property, called proportional justified representation and investiagted which voting rules have this property; in another paper, two project RAs identified a voting rule that is computationally tractable and offers proportional justified representation. In yet another paper, two project RAs explored the connection between apportionment rules and approval-based committee selection; their work provi

Final results

Defining an exploring preferences single-peaked on a circle and identifying tractable subdomains of the domain of preferences single-peaked on a tree constitutes significant progress beyond the state of the art, as it considerably extends the class of preferences on which important practical preference aggregation problems can be efficiently solved. When implemented in a tool (which will be produced at a later stage of the project), algorithms for such domains can be used by end users, who may come from a variety of backgrounds, for the preference aggregation tasks they face in real life, thereby enabling better decision-making in the society. The axioms for multiwinner rules that have been identified in the course of our research are equally important, as they offer criteria for choosing decision-making rules.