Invited Talks

Speaker: Michael Wooldridge, University of Oxford

Title: TBD

Speaker: Ioannis Caragiannis, Aarhus University

Title: Impartial selection, additive approximation guarantees, and priors

Abstract: We study the problem of impartial selection, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular individual among a set of community members. The input can be modelled as a directed graph, where each node represents an individual, and a directed edge indicates nomination or approval of a community member to another. An impartial mechanism is robust to potential selfish behaviour of the individuals and provides appropriate incentives to voters to report their true preferences by ensuring that the chance of a node to become a winner does not depend on its outgoing edges. The goal is to design impartial mechanisms that select a node with an in-degree that is as close as possible to the highest in-degree. Recent progress has identified impartial selection rules with optimal approximation ratios. It was noted, though, that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of quality. We present randomized impartial selection mechanisms with additive approximation guarantees of o(n), where n is the number of nodes in the input graph. We furthermore demonstrate that prior information on voters’ preferences can be useful in the design of simple (deterministic) impartial selection mechanisms with good additive approximation guarantees. In this direction, we consider different models of prior information and analyze the performance of a natural selection mechanism that we call approval voting with default (AVD).

Accepted Papers

Authors Title
Leora Schmerler and Noam Hazon. Strategic voting in negotiating teams
Ben Armstrong and Kate Larson. On the Limited Applicability of Liquid Democracy
Nimrod Talmon and Rutvik Page. Proportionality in Committee Selection with Negative Feelings
Felix Brandt, Martin Bullinger and Anaëlle Wilczynski. Reaching Individually Stable Coalition Structures
Patrick Lederer. Strategyproof Randomized Social Choice for Restricted Sets of Utility Functions
Mithun Chakraborty, Ulrike Schmidt-Kraepelin and Warut Suksompong. Picking Sequences and Monotonicity in Weighted Fair Division
Chenhao Wang and Qiong Liu. Load Balancing Game in Loss Communication Networks
Zun Li and Michael Wellman. Evolution Strategies for Approximate Solution of Bayesian Games
Umang Bhaskar, Sricharan Ar and Rohit Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
Grzegorz Gawron and Piotr Faliszewski. Using Multiwinner Voting to Search for Movies
Dvir Gilor, Rica Gonen and Erel Segal-Halevi. Ascending-Price Mechanism for General Multi-Sided Markets
Rupert Freeman, Evi Micha and Nisarg Shah. Two-Sided Matching Meets Fair Division
Hadi Hosseini, Fatima Umar and Rohit Vaish. Accomplice Manipulation of the Deferred Acceptance Algorithm
Jaelle Scheuerman, Jason Harman, Nicholas Mattei and Kristen Brent Venable. Modeling Voters in Multi-Winner Approval Voting
Hadi Hosseini and Andrew Searns. Guaranteeing Maximin Shares: Some Agents Left Behind
Jonathan Scarlett, Nicholas Teh and Yair Zick. For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods
Omer Lev, Nicholas Mattei, Paolo Turrini and Stanislav Zhydkov. Peer Selection with Noisy Assessments
Kotone Ninagawa, Yasser Mohammad and Amy Greenwald. Baseline Strategies for the ANAC Automated Negotiation League
Hanrui Zhang, Yu Cheng and Vincent Conitzer. Automated Mechanism Design for Classification with Partial Verification
Steven Jecmen, Hanrui Zhang, Ryan Liu, Nihar Shah, Vincent Conitzer and Fei Fang. Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments
Scott Emmons, Caspar Oesterheld, Andrew Critch, Vincent Conitzer and Stuart Russell. Symmetry, Equilibria, and Robustness in Common-Payoff Games
Andrea Martin, Nicholas Mattei and Kristen Brent Venable. Behavioral Stable Marriage Problems
Caspar Oesterheld and Vincent Conitzer. Decision Scoring Rules
Gabriel Andrade, Rafael Frongillo, Sharadha Srinivasan and Elliot Gorokhovsky. Graphical Economics with Resale
Anilesh Kollagunta Krishnaswamy, Haoming Li, David Rein, Hanrui Zhang and Vincent Conitzer. Classification with Strategically Withheld Data
Jonathan Wagner and Reshef Meir. A VCG Adaptation for Participatory Budgeting
Mehmet Ismail. The strategy of conflict and cooperation