COMSOC Video Seminar

International Seminar Series on Social Choice

Next seminar: Friday, 2021-06-25, 09:00 New York, 15:00 Paris. 90min including break. Everyone welcome.

Speakers: Rida Laraki and Bill Zwicker

To join, please sign up to the mailing list, where we will send a link including password to the seminar a day before. We will also post a link here shortly before the seminar, together with a password hint.

video recordings and seminar archive at the bottom of the page. Riddle archive.

2021-06-25: Rida Laraki and Bill Zwicker

Session Chair: Edith Elkind (Oxford)

---

Rida Laraki (Paris/Liverpool)

Stable Matching Games

Gale and Shapley introduced a matching problem between two sets of agents where each agent on one side has an exogenous preference over the agents of the other side. They defined a matching as stable if no unmatched pair can both improve their utility by forming a new pair. They proved, algorithmically, the existence of a stable matching. Shapley and Shubik, as well as many others, extended the model by allowing monetary transfers. We offer a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic game they have to play in a usual non-cooperative sense (without commitment) or in a semi-cooperative way (with commitment, as the outcome of a bilateral binding contract in which each player is responsible of his/her part of the contract). Depending on whether the players can commit or not, we define in each case a solution concept which combines Gale-Shapley pairwise external stability with a (generalized) Nash equilibrium internal stability. In each case, we give the necessary and sufficient conditions for the set of stable allocations to be non-empty, we study its geometry (full/semi-lattice), and provide an algorithm which converges to its maximal element. Finally, we prove that our second modelwith commitmentencompasses and refines most of the literature (matching with monetary transfers as well as matching with contracts).

Joint work with Felipe Garrido-Lucero.

---

Bill Zwicker (Union College)

John Nash meets Jorge Hirsch: Scale Invariant Citation Indices

A number of citation indices have been proposed for measuring and ranking the research publication records of scholars. Some of the best-known indices, such as those proposed by Hirsch and Woeginger, are designed to reward most highly those records that strike some balance between productivity (number of papers published) and impact (frequency with which those papers are cited). A large number of rarely cited publications will not score well, nor will a very small number of heavily cited papers. We propose several new citation indices, each resting on the notion of scale invariance, as introduced by John Nash in his solution of the two-person bargaining problem. Our main focus is on one of thesea scale invariant version of the Hirsch index. We argue that it has advantages over the original; it produces fairer rankings within subdisciplines, is more decisive (discriminates more finely, yielding fewer ties) and more dynamic (growing over time via more frequent, smaller increments). Simulations with Poisson noise suggest that scale invariance reduces the number of "accidental" reversals, wherein random irregularities cause researcher A to receive a lower index value than B, although A's productivity and impact are both slightly higher than B's. Moreover, we provide an axiomatic characterization of the scale invariant Hirsch index, via axioms that bear a close relationship, in discrete analogue, to those used by Nash. This argues for the mathematical naturality of the new index.

Joint work with Josep Freixas and Roger Hoerl.

2021-07-16: Vincent Merlin and Nick Mattei

Vincent Merlin (Caen)

TBA

---

Nick Mattei (Tulane)

Modeling Voters in Multi-Winner Approval Voting

In many real world situations, collective decisions are made using voting and, in scenarios such as committee or board elections, employing voting rules that return multiple winners. In multi-winner approval voting (AV), an agent submits a ballot consisting of approvals for as many candidates as they wish, and winners are chosen by tallying up the votes and choosing the top-k candidates receiving the most approvals. In many scenarios, an agent may manipulate the ballot they submit in order to achieve a better outcome by voting in a way that does not reflect their true preferences. In complex and uncertain situations, agents may use heuristics instead of incurring the additional effort required to compute the manipulation which most favors them. In this paper, we examine voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty using behavioral data obtained from Mechanical Turk. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. There are a number of predictive models of agent behavior in the social choice and psychology literature that are based on cognitively plausible heuristic strategies. We show that the existing approaches do not adequately model our real-world data. We propose a novel model that takes into account the size of the winning set and human cognitive constraints; and demonstrate that this model is more effective at capturing real-world behaviors in multi-winner approval voting scenarios.

Joint work with Jaelle Scheuerman, Jason Harman, and K. Brent Venable.

Most sessions will take place on Fridays at 9:00 New York / 15:00 Paris time. Exceptions to this rule will be announced on this page.

The next rump session is planned for Friday 2 July 2021. Please sign up here if you would like top speak!

Confirmed future speaker: Conal Duddy (Cork)

Be sure to sign up for email reminders.

Fig. 1: Some of the 142 attendees of our second seminar.

Join us for a regular series of seminars held via video meetings, open to anyone, and targeted to the interests of attendees of the COMSOC workshop series. Topics include, for example:

  • Voting and collective decision making

  • Preference elicitation and representation; restricted preference domains

  • Opinion diffusion and aggregation on social networks

  • Judgement aggregation

  • Fair division and allocation

  • Matching and coalition formation

Researchers from all disciplines are welcome to present and attend.

Steering Committee

  • Chair: Ulle Endriss (Amsterdam)

  • Edith Elkind (Oxford)

  • Vincent Merlin (Caen)

  • William S. Zwicker (Union College)

  • Technical Secretary: Dominik Peters (Harvard)

How-Tos

  • 20min talks, 10min Q&A

  • 10min break between talks, with an opportunity to meet others in random breakout rooms

  • Participants remain in a waiting room until shortly before the seminar, to allow speakers to practice screen sharing.

  • Turn on your video if possible, but mute your microphone.

  • To ask a question type your question in the chat, and prefix it with "QUESTION".

  • Please note that we will record the seminars. Stay muted if you do not want to be recorded.

Archive of Past Seminar Sessions

2021-05-28: Nicolas Maudet and Eric Pacuit [Video]

Session Chair: Ulle Endriss (Amsterdam)

---

Nicolas Maudet (Paris)

Swap Dynamics in Single-Peaked Housing Markets (Slides)

In this talk we will discuss recent results regarding swap dynamics in single-peaked housing markets. In this restricted domain, Top Trading Cycle (TTC) is no longer the only procedure satisfying Pareto-optimality, individual rationality and strategy-proofness. In particular, the Crawler procedure recently introduced by Bade enjoys the same properties. These two centralized procedures might however involve long trading cycles. In swap dynamics, agents perform instead pairwise mutually improving deals until a stable allocation is reached. We will discuss the properties of such dynamics, and show in particular how the outcomes reached compare to those returned by these centralized procedures.

Joint work with Aurélie Beynier, Simon Rey, and Parham Shams.

---

Eric Pacuit (Maryland)

Expansion Consistency in Voting (Slides)

Sen introduced the gamma condition, also known as expansion consistency, as part of a characterization of choice functions representable by a binary relation. Following Bordes, we consider expansion as an axiom on voting methods—as well as a natural weakening of expansion hinted at by Bordes, which we call binary expansion. Surveying standard voting methods, there is an apparent connection between the degree of resoluteness of a voting method and whether it satisfies (binary) expansion. We explain this observation with a new impossibility theorem: There is no voting method satisfying anonymity, neutrality, binary expansion, and an axiom we call quasi-resoluteness, which requires a single winner in any profile without tied margins. Finally, we explore the frequency with which some voting methods violate binary expansion using computer simulations.

This is joint work with Wes Holliday.

2021-05-14: Julia Stoyanovich and Simina Brânzei [Video]

Session Chair: Vincent Merlin (Caen)

---

Julia Stoyanovich (New York)

Algorithmic Techniques for Necessary and Possible Winners

We investigate the practical aspects of computing the necessary and possible winners in elections over incomplete voter preferences. In the case of the necessary winners, we show how to implement and accelerate the polynomial-time algorithm of Xia and Conitzer. In the case of the possible winners, where the problem is NP-hard, we give a natural reduction to Integer Linear Programming (ILP) for all positional scoring rules and implement it in a leading commercial optimization solver. Further, we devise optimization techniques to minimize the number of ILP executions and, oftentimes, avoid them altogether. We conduct a thorough experimental study that includes the construction of a rich benchmark of election data based on real and synthetic data. Our findings suggest that, the worst-case intractability of the possible winners notwithstanding, the algorithmic techniques presented here scale well and can be used to compute the possible winners in realistic scenarios.

Joint work with Vishal Chakraborty, Theo Delemazyre, Benny Kimelfeld, Phokion Kolaitis, and Kunal Relia.

---

Simina Brânzei (Purdue)

Searching, Sorting, and Cake Cutting in Rounds

We study sorting and searching in rounds motivated by a cake cutting problem. The search problem we consider is: we are given an array x=(x1,…,xn) and an element z promised to be in the array. We have access to an oracle that answers comparison queries and the goal is to find the location of z with success probability at least p∈[0,1] in at most k rounds of interaction with the oracle. The problem is called ordered or unordered search, depending on whether the array x is sorted or unsorted,respectively. We analyze the expected query complexity of randomized and deterministic algorithms, finding a surprising query complexity gap in the performance of randomized algorithms on a worst case input and deterministic algorithms on a random input. We also discuss the connections of these search problems to sorting in the rank query model and proportional cake cutting with contiguous pieces.

2021-04-23: Phokion Kolaitis and Judy Goldsmith [Video]

Please note that for this session we will start one hour later than usual: 10am New York / 4pm Paris.

---

Session Chair: Edith Elkind (Oxford)

---

Phokion Kolaitis (UC Santa Cruz & IBM)

Semantics and Complexity of Queries on Election Databases (Slides)

Election databases are the main elements of a new framework that aims to create bridges between the computational social choice and the data management communities. An election database contains incomplete information about the preferences of voters (in the form of partial orders), alongside with standard database relations that provide contextual information. The availability of the relational context allows for the formulation of sophisticated queries about voting rules, candidates, winners, issues, and positions on issues. We introduce the necessary answer semantics and the possible answer semantics to queries on election databases and explore the computational complexity of query evaluation under these semantics.

Joint work with Benny Kimelfeld, Julia Stoyanovich, and Muhammad Tibi.

---

Judy Goldsmith (Kentucky)

Opinion Diffusion with Heterogeneous Agents in a Dynamic Network (Slides)

I will present recent work with Patrick Shepherd and Mia Weaver on modeling opinion diffusion in networks with homophilic, heterophilic, and adversarial agents. We assume that the network can apply triadic closure, but agents can unfriend each other in order to increase their utility. This work serves to highlight Shepherd's social network software package, which can also support simulations in any social-network-based social choice processes. I will briefly mention our ongoing work on modeling individuals' willingness to confront biased remarks, and on learning agent strategies for epidemic responses.

The latter is joint work with Isaac Batts, Abigail Folberg, Emory Hufbauer, Jennifer Hunt, Hana Khamfroush, Patrick Shepherd, Mia Weaver, and Angela Zhang.

2021-04-09: Rump Session [Video]

This will be a session with 5-minute talks by 8 different speakers. A great way of finding out what people are working on.

Speakers: Georgios Papasotiropoulos (Athens), Ayumi Igarashi (Tokyo), Boris Tsvelikhovskiy (Pittsburgh), Nimrod Talmon (Ben-Gurion), Paul Harrenstein (Oxford), Kunal Relia (New York), Chinmay Sonar (UC Santa Barbara), Foroogh Salekpay (Rovira i Virgili)

Session Chair: Ulle Endriss (Amsterdam)

2021-03-25: Felix Brandt and Klaus Nehring [Video]

Session Chair: Bill Zwicker (Union College)

---

Felix Brandt (Munich)

A Natural Adaptive Process for Collective Decision-Making (Slides)

Consider an urn filled with balls, each labelled with one of several possible collective decisions. Now, draw two balls from the urn, let a random voter pick her more preferred as the collective decision, relabel the losing ball with the collective decision, put both balls back into the urn, and repeat. In order to prevent the permanent disappearance of some types of balls, a randomly drawn ball is labelled with a random collective decision once in a while. We prove that the empirical distribution of collective decisions converges towards the outcome of a celebrated probabilistic voting rule proposed by Peter C. Fishburn (Rev. Econ. Stud., 51(4), 1984). The proposed procedure has analogues in nature recently studied in biology, physics, and chemistry. It is more flexible than traditional voting rules because it does not require a central authority, elicits very little information, and allows agents to arrive, leave, and change their preferences over time.

Joint work with Florian Brandl.

---

Klaus Nehring (UC Davis)

The Median Rule in Judgment Aggregation: Extension to Weighted Judgment Contexts (Slides)

A judgement aggregation rule takes the views of a collection of voters over a set of interconnected issues and yields a logically consistent collective view. The median rule is a judgement aggregation rule that selects the logically consistent view which minimizes the average distance to the views of the voters (where the "distance" between two views is the number of issues on which they disagree). In the special case of preference aggregation, this is called the Kemeny rule. We show that, under appropriate regularity conditions, the median rule is the unique judgement aggregation rule which satisfies three axioms: Ensemble Supermajority Efficiency, Reinforcement, and Continuity. Our analysis covers aggregation problems in which the consistency restrictions on input and output judgements may differ. We also allow for issues to be weighted, and provide numerous examples in which issue weights arise naturally. The generalization to the weighted case requires non-trivial combinatorial conditions on the structure of the input and output spaces.

Joint work with Marcus Pivato.

2021-03-11: Rohit Vaish and John Dickerson [Video]

For this session we asked Jérôme Lang (Paris) to invite speakers and chair the session.

---

Rohit Vaish (Mumbai)

Stable Fractional Matchings (Slides)

In this talk, I will discuss a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). In this cardinal setting, stable fractional matchings can have much higher social welfare than their integral counterparts. This motivates the natural question of understanding the computational complexity of finding an optimal (i.e., welfare-maximizing) stable fractional matching. I will present simple approximation algorithms for this problem with weak welfare guarantees and show that, somewhat surprisingly, achieving better approximations is computationally hard. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. I will also discuss some structural observations as well as directions for future research.

Joint work with Ioannis Caragiannis, Aris Filos-Ratsikas, and Panagiotis Kanellopoulos.

https://arxiv.org/abs/1902.06698

---

John Dickerson (Maryland)

Scalable Equilibrium Computation in Multi-agent Influence Games on Networks

In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding. In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? In this talk, we will discuss our recent polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. Specifically, we showed that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time. We will also discuss a preliminary test of our model in the two-agent case on random graphs, where equilibria can be computed using mirror descent.

Joint work with Fotini Christia, Michael Curry, Constantinos Daskalakis, Erik Demaine, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, and Aidan Milliff. Preliminary version appeared at AAAI-2021.

2021-02-25: Ashley Piggins and Aris Filos-Ratsikas [Video]

Session Chair: Vincent Merlin (Caen)

---

Ashley Piggins (Galway)

Pure Strategy Nash Equilibrium in the Spatial Model with Valence: Existence and Characterization (Slides)

Pure strategy Nash equilibria (PSNE) almost never exist in spatial majority voting games when the number of positional dimensions is at least two. This is a persisting foundational issue with the spatial model. However, positive results are possible when we add a valence parameter to the model. For example, it is known that an equilibrium exists in a majority voting game if and only if the radius of the yolk, a classic concept in the spatial theory, is less than the square root of the valence parameter. We prove a general theorem that enables us to characterize the set of all PSNE for every spatial voting game with valence. We complement this by establishing an equilibrium existence theorem based on a new concept, the b-yolk.

Joint with Mathieu Martin, Zéphirin Nganmeni, and Élise F. Tchouante.

---

Aris Filos-Ratsikas (Liverpool)

Distortion-Information Tradeoffs in Social Choice and Matching via Queries

Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion, which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i.e., the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. We take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and, in many cases, outperform the best-known randomized ordinal mechanisms. We consider both the setting of general social choice and one-sided matching, and provide bounds on the possible tradeoffs between the distortion and the amount of information elicited.

Joint work with Georgios Amanatidis, Georgios Birmpas, and Alexandros Voudouris.

2021-02-11: Franz Dietrich and Sean Horan [Video]

Session Chair: Bill Zwicker (Union College)

---

Franz Dietrich (Paris)

Dynamically Rational Judgment Aggregation (Slides)

A key goal in judgment aggregation theory has always been to make collective judgments rational. So far, rationality has been understood in purely static terms: as coherence of judgments at a given time, where 'coherence' could for instance mean consistency, or completeness, or deductive closure, or combinations thereof. By contrast, this paper studies whether and how collective judgments can be dynamically rational, so that they respond well to new information, i.e., change rationally when information is learnt by everyone. Formally, we call a judgment aggregation rule dynamically rational with respect to a given revision operator if, whenever all individuals revise their judgments in light of some information (a proposition), then the new aggregate judgments are the old ones revised in light of this information. In short, aggregation and revision commute. We establish a general impossibility theorem: as long as the propositions on the agenda are sufficiently interconnected, no judgment aggregation rule with standard properties is dynamically rational with respect to any revision operator satisfying mild conditions (familiar from belief revision theory). The theorem is a counterpart for dynamic rationality of known impossibility theorems for static rationality. Turning to possibilities, the paper then makes a first attempt to restore dynamic rationality, by showing that certain rules ('hierarchy rules') generate dynamic rationality with respect to special ('hierarchical') revision operators. Like the familiar 'priority rules', such rules are guided by priorities between the propositions.

Joint work with Christian List.

http://franzdietrich.net/Papers/DietrichList-DynamicallyRationalJA.pdf

---

Sean Horan (Montréal)

Two-Stage Majoritarian Choice (Slides)

We propose a class of decisive collective choice rules that rely on an exogenous linear ordering to partition the majority relation into two acyclic relations. The first relation is used to make a shortlist of the feasible alternatives before the second is used to make a final choice. Rules in this class are characterized by four properties: two classical rationality requirements (Sen's expansion consistency and Manzini and Mariotti's weak WARP); and adaptations of two natural collective choice conditions (Arrow's independence of irrelevant alternatives and Saari and Barney's no preference reversal bias). These rules also satisfy a number of other desirable properties, including a version of May's positive responsiveness.

Joint work with Yves Sprumont.

2021-01-28: Umberto Grandi and Nimrod Talmon [Video]

Session Chair: Edith Elkind (Oxford)

---

Umberto Grandi (Toulouse)

Multiagent Ranked Delegations in Voting (Slides)

We propose a generalisation of liquid democracy in which a voter can either vote directly on the issues at stake, delegate her vote to another voter, or express complex delegations to a set of trusted voters. By requiring a ranking of desirable delegations and a backup vote from each voter, we are able to put forward and compare algorithms to solve delegation cycles and obtain a final collective decision.

Joint work with Rachael Colley and Arianna Novaro.

---

Nimrod Talmon (Ben-Gurion)

Participatory Budgeting with Project Interactions (Slides)

Participatory budgeting systems allow city residents to jointly decide on projects they wish to fund using public money, by letting residents vote on such projects. While participatory budgeting is gaining popularity, existing aggregation methods do not take into account the natural possibility of project interactions, such as substitution and complementarity effects. Here we take a step towards fixing this issue by augmenting the standard model of participatory budgeting with a partition over the projects where we model the type and extent of project interactions within each part using certain functions. We study the computational complexity of finding bundles that maximize voter utility, as defined with respect to such functions. Motivated by the desire to incorporate project interactions in real-world participatory budgeting systems, we identify certain cases that admit efficient aggregation in the presence of such project interactions.

Joint work with Pallavi Jain and Krzysztof Sornat.

2021-01-14: Kate Larson and Ernesto Savaglio [Video]

Session Chair: Ulle Endriss (Amsterdam)

---

Kate Larson (Waterloo)

Testing Axioms against Human Reward Divisions in Cooperative Games

Axiomatic approaches are an appealing method for designing fair allocation algorithms, as they provide a formal structure for reasoning about and rationalizing individual decisions. However, to make these algorithms useful in practice, their axioms must appropriately capture social norms. We explore this tension between fairness axioms and socially acceptable decisions in the context of cooperative game theory for the fair division of rewards. We use two crowdsourced experiments to study people’s impartial reward divisions in cooperative games, focusing on games that systematically vary the values of the single-player coalitions. Our results show that people select rewards that are remarkably consistent, but place much more emphasis on the single-player coalitions than the Shapley value does. Further, their reward divisions violate both the null player and additivity axioms but support weaker axioms. We argue for a more general methodology of testing axioms against experimental data, retaining some of the conceptual simplicity of the axiomatic approach while still using people’s opinions to drive the design of algorithms.

Joint work with Greg d'Eon.

---

Ernesto Savaglio (Pescara)

On Rational Choice from Lists of Sets (Slides)

We analyse the rationality of a Decision Maker (DM) who chooses from lists of sets of alternatives. A new class of choice functions, representing DM's choice behaviour, and a novel rationality axiom named No-Regret (NR) are introduced. We show that the NR property, which suggests ignoring alternatives disregarded in a previous choice procedure, is related to the famous rationality axioms Outcast, Heritage and Path-independence. Such relationships depend on implementations of choice functions on lists of sets by means of the standard choice function on alternatives. We point out that No-Regret is a rationality criterion that encompasses these compelling properties of the classical choice model and extends them to the more general framework of choice from lists of sets of alternatives.

Joint work with Gleb Koshevoy.

2020-12-17: Oskar Skibski and Elliot Anshelevich [Video]

For this session we asked Piotr Faliszewski (Kraków) to invite speakers and chair the session.

---

Oskar Skibski (Warsaw)

Axiomatic Characterization of PageRank (Slides)

We study the problem of identifying the most important nodes in a network. We propose to use an axiomatic approach to build a theoretical foundation for choosing a centrality measure in a specific setting. We propose six simple properties and prove that PageRank is the only centrality measure that satisfies all of them. Our axiomatization is the first axiomatic characterization of PageRank in its general form in the literature.

Joint work with Tomasz Was.

---

Elliot Anshelevich (RPI)

Bounding Distortion under Metric Preferences using Awareness of Voter Passion (Slides)

Distortion measures the inefficiency of using only ordinal information when attempting to select an optimal outcome, instead of the unknown numerical information. For example, in social choice applications, agents may have numerical costs for each of the possible alternatives, but the mechanism must decide on a good alternative based only on the ordinal preferences of the agents which are induced by the underlying costs. In this talk, I will address bounding distortion under metric preferences, i.e., under the assumption that the agent costs form a metric space and thus obey the triangle inequality. I will specifically focus on how a small amount of additional information about agent preferences can greatly reduce distortion, and the resulting information-distortion tradeoffs.

Joint work with Ben Abramowitz and Wennan Zhu.

2020-12-03: Markus Brill and Robert Bredereck [Video]

Session Chair: Edith Elkind (Oxford)

---

Markus Brill (Berlin)

The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections (Slides)

We propose the maximin support method, a novel extension of the D'Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D'Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and alternative D'Hondt extensions due to Phragmén.

Joint work with Luis Sánchez-Fernández, Norberto Fernández García, and Jesús A. Fisteus.

---

Robert Bredereck (Berlin)

Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks (Slides)

We consider the setting of asynchronous opinion diffusion with majority threshold: given a social network with each agent assigned to one opinion, an agent will update its opinion if the majority of its neighbors agree on a different opinion. The stabilized final outcome highly depends on the sequence in which agents update their opinion. We are interested in optimistic sequencessequences that maximize the spread of a chosen opinion. We complement known results for two opinions where optimistic sequences can be computed in time and length linear in the number of agents. We analyze upper and lower bounds on the length of optimistic sequences, showing quadratic bounds in the general and linear bounds in the acyclic case. Moreover, we show that in networks with more than two opinions determining a spread-maximizing sequence becomes intractable; surprisingly, already with three opinions the intractability results hold in highly restricted cases, e.g., when each agent has at most three neighbors, when looking for a short sequence, or when we aim for approximate solutions.

2020-11-12: Hervé Moulin and Matías Núñez [Video]

Please note that this session will start one hour later than usual, namely at 10:00 New York / 16:00 Paris time.

Session Chair: Vincent Merlin (Caen)

---

Hervé Moulin (Glasgow)

Universal Guarantees in Bargaining (Slides)

In the n-person bargaining model, the familiar Mid-point Domination property guarantees my worst utility if I have a 1/n-th chance of dictating the outcome. Another natural Guarantee gives to each participant the right to veto her fair share of outcomes. Yet another sets the disagreement utility at the arithmetic average of all outcomes. Maintaining equal treatment of agents and outcomes, and vNM utilities, the set of such Guarantees is of infinite dimension even with two agents and three outcomes. The natural subset of rank-additive Guarantees is of finite dimension, and in two-agent problems it boils down to the convex combinations of the veto Guarantees above. But more complicated options are feasible among three or more agents.

Joint work with Anna Bogomolnaia.

---

Matías Núñez (Paris)

Voter Coordination in Large Elections: A Case for Approval Voting (Slides)

We study the potential for voter coordination in large elections. Drawing on equilibrium analysis and numerical simulations, we compare the three most basic rules for 3-candidate elections, under which voters may vote for exactly one candidate (Plurality Voting), for exactly two candidates (Anti-Plurality) or for one or two candidates (Approval Voting). As well-known since Duverger (1951), Plurality Voting allows for voter coordination, but the election is indeterminate: at least two candidates are plausible winners. By contrast, coordination always fails under Anti-Plurality Voting. We further show that Approval voting always permits coordination when a Condorcet winner exists, and also ensures that, in most cases, only this normatively appealing candidate can be elected. At the heart of our numerical results lies a novel algorithm computing voter best replies in a large election.

Joint work with François Durand and Antonin Macé.

2020-10-29: Anna Bogomolnaia and Jean-François Laslier [Video] [2nd talk missing, sorry!]

Session Chair: Vincent Merlin (Caen)

---

Anna Bogomolnaia (Glasgow)

Guarantees in Fair Division (Slides)

We consider a fair division problem, with n agents and a set Ω to divide. An individual "guarantee" is a utility level which an agent is regarded as entitled to. It only depends on her preferences and exogenous rights, and on physical constraints of the division problem: the set Ω and the number n of participants (but it should not depend on preferences or other characteristics of other agents). For example, if Ω is a finite set of divisible goods and preferences are non-negative convex, a compelling symmetric and feasible guarantee is individual's utility of (1/n)Ω. If Ω is arbitrary but preferences are additive non-negative, it would be (1/n)-th of the individual's utility of the whole Ω. We consider a general case, when utilities are continuous, but neither convex nor monotonic, or even positive. In a "cake-cutting" problem, we can always guarantee each agent her minmax utility: that of her best share in the worst possible partition. It is lower than her maxmin utility (that of her worst share in the best possible partition), that cannot always be guaranteed to all agents (even for n=2). Moreover, a little-known generalization of the Divide and Choose algorithm to any number n of agents implements this guarantee with a simple sequence of cuts and queries. These findings rely on the equi-partition lemma, which shows that, for any n and any continuous utility u on a bounded measurable Ω in Euclidean space, one can always find a partition of Ω in n elements with identical utility. This is a highly non-trivial mathematical result, proven in a companion paper by R. Karasev and S. Avvakumov.

Joint work with Hervé Moulin.

---

Jean-François Laslier (Paris)

Evolutionary Foundations of the Universalisation Ethics, with Political Applications (Slides)

In this talk I will describe the "Homo moralis" model of partial Kantian morality, its evolutionary roots (genetics and culture) and its philosophical interpretation (the universalisation principle). I will present behavioural and political implications for three classical problems in the theory of voting: the divided majority problem, the costly participation dilemma, and the strategic revelation of information.

Joint work with Ingela Alger.

2020-10-15: Jörg Rothe and Lirong Xia [Video]

Session Chair: Bill Zwicker (Union College)

---

Speakers: Jörg Rothe (Düsseldorf)

What's New in Altruistic Hedonic Games? (Slides)

Hedonic games are coalition formation games where players have preferences over the coalitions they may join. Considering not only the players’ own (friend-oriented) preferences but also their friends’ preferences in such games, Nguyen et al. (AAMAS'16) introduced and studied three degrees of altruistic hedonic games based on selfish-first, equal-treatment, and altruistic-treatment preferences, which depend on the order in which players look at their own or their friends’ preferences. In this talk, a related approach due to Wiechers and Rothe (STAIRS'20) will be presented: By replacing the average by the minimum in their definitions, we introduce the corresponding minimum-based variants of the same three degrees of altruism. As innocent as this definitional change appears, it is as fundamental as switching from utilitarian to egalitarian social welfare. We study this novel concept of altruism in hedonic games in terms of the common notions of stability in such games, and the related decision problems in terms of their computational complexity. We also briefly mention an extension, due to Kerkmann and Rothe (IJCAI'20), of the model of altruism in hedonic games to coalition formation games in general.

---

Lirong Xia (RPI)

The Smoothed Possibility of Social Choice (Slides)

We develop a framework to leverage the smoothed complexity analysis by Spielman and Teng (2004) to circumvent paradoxes and impossibility theorems in social choice, motivated by the low-stakes, large-scale, and frequently-used modern applications of social choice powered by AI and ML. For Condorcet's paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the folklore impossibility theorem on the non-existence of voting rules that simultaneously satisfy anonymity and neutrality, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice—even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice. The main technical tool we developed is a dichotomous characterization of the smoothed likelihood for a Poisson multinomial variable to satisfy a system of linear inequalities, which might be of independent interest and can be used to study various other events in social choice, such as the likelihood of tied elections, likelihood of (weak) Condorcet winner(s) and Condorcet cycles, etc.

https://arxiv.org/abs/2006.06875

https://www.cs.rpi.edu/~xial/Files/Smoothed_Ties.pdf

2020-10-08: Dominik Peters and Juan D. Moreno-Ternero [Video]

Session Chair: Bill Zwicker (Union College)

---

Dominik Peters (Harvard)

Proportional Participatory Budgeting with Cardinal Utilities (Slides)

We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that guarantee proportional representation to groups of voters with common interests. To the best of our knowledge, all known rules for participatory budgeting do not satisfy either of the two axioms; in addition we show that the most prominent proportional rules for committee elections (such as Proportional Approval Voting) cannot be adapted to arbitrary costs nor to additive valuations so that they would satisfy our axioms of proportionality. We construct a simple and attractive voting rule that satisfies one of our axioms (for arbitrary costs and arbitrary additive valuations), and that can be evaluated in polynomial time. We prove that our other stronger axiom is also satisfiable, though by a computationally more expensive and less natural voting rule.

Joint work with Grzegorz Pierczyński and Piotr Skowron.

https://arxiv.org/abs/2008.13276

---

Juan D. Moreno-Ternero (Seville)

Sharing the Revenues from Broadcasting Sports Leagues (Slides)

We study the problem of sharing the revenues raised from the collective sale of broadcasting rights for sports leagues. We take the axiomatic approach and derive focal rules, arising from polar estimations of teams' loyal viewers, as well as compromises among them. We bring some of the testable implications from our axiomatic analysis to the real case of European football leagues.

Joint work with Gustavo Bergantiños.

https://mpra.ub.uni-muenchen.de/101139/

2020-10-01: Toby Walsh and Lihi Dery [Video]

Session Chair: Edith Elkind (Oxford)

---

Toby Walsh (Sydney)

Strategy-Proof Mechanisms for Facility Location (Slides)

Facility location is a fundamental problem in social choice with a number of practical application. In this talk, I study the impact on extending mechanisms for locating facilities on the line to mechanisms for locating facilities in Euclidean or Manhattan space. I consider three fundamental axiomatic properties: anonymity, which is a simple fairness property; Pareto optimality, which is one of the most fundamental efficiency properties; and strategy-proofness, which ensures agents have no incentive to mis-report their location. I also consider how well strategy-proof mechanisms can approximate the optimal welfare.

---

Lihi Dery (Ariel)

Beyond Majority: Label Ranking Ensembles based on Voting Rules (Slides)

Label ranking is a machine learning problem that is concerned with predicting the order of a set of labels for an object. Examples include: (a) predicting a ranked list of preferences for a given person, (b) providing an ordered list of the most suitable advertisements for a given Facebook profile, and even (c) predicting the most drug-resistant mutations in a genome. Ensemble models are a common machine learning technique that collects the results of multiple simple models and combines them into a single aggregated output, thus enhancing performance. We propose to apply voting rules as the aggregation technique for label ranking ensembles. Furthermore, we propose a novel aggregation method for label ranking ensembles that learns the best voting rule to be used in each setting. An evaluation of the proposed method shows that it obtains prediction performance that is significantly higher than that of the aggregation techniques currently used by state-of-the-art label ranking ensembles.

Joint work with Havi Werbin and Erez Shmueli.

https://doi.org/10.1016/j.eswa.2019.06.022

2020-09-24: Rump Session [Video]

This will be a session with 5-minute talks by 8 different speakers. A great way of finding out what people are working on.

Speakers: Alan Tsang (Carleton), Anaëlle Wilczynski (Paris-Saclay), Evi Micha (Toronto), Ali Ozkes (Vienna), Farhad Mohsin (RPI), Ulrike Schmidt-Kraepelin (Berlin), Yun Lu (Edinburgh), Jacques Bara (Warwick)

Session Chair: Ulle Endriss (Amsterdam)

2020-09-17: Francis Su and Matthew O. Jackson [Video]

For this, the California Session, we will start three hours later than usual, at 9:00 San Francisco, 12:00 New York, 18:00 Paris time.

Session Chair: Bill Zwicker (Union College)

---

Francis Su (Harvey Mudd)

Multilabeled Versions of Sperner's and Fan's Lemmas and Applications (Slides)

We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.

Joint work with Frédéric Meunier.

https://doi.org/10.1137/18M1192548

---

Matthew O. Jackson (Stanford)

Learning through the Grapevine: The Impact of Noise and the Breadth and Depth of Social Networks (Slides)

We examine how well people learn when information is noisily relayed from person to person; and we study how communication platforms can improve learning without censoring or fact-checking messages. We analyze learning as a function of social network depth (how many times information is relayed) and breadth (the number of relay chains accessed). Noise builds up as depth increases, so learning requires greater breadth. In the presence of mutations (deliberate or random) and transmission failures of messages, we characterize sharp thresholds for breadths above which receivers learn fully and below which they learn nothing. When there is uncertainty about mutation rates, optimizing learning requires either capping depth, or if that is not possible, limiting breadth by capping the number of people to whom someone can forward a message. Limiting breadth cuts the number of messages received but also decreases the fraction originating further from the receiver, and so can increase the signal to noise ratio. Finally, we extend our model to study learning from message survival: e.g., people are more likely to pass messages with one conclusion than another. We find that as depth grows, all learning comes from either the total number of messages received or from the content of received messages, but the learner does not need to pay attention to both.

Joint work with Suraj Malladi and David McAdams.

https://ssrn.com/abstract=3269543

2020-09-10: Hans Peters and Marcus Pivato [Video]

Session Chair: Ulle Endriss (Amsterdam)

---

Hans Peters (Maastricht)

Unanimous and Strategy-proof Probabilistic Rules for Single-peaked Preference Profiles on Graphs (Slides)

Finitely many agents have preferences on a finite set of alternatives, single-peaked with respect to a connected graph with these alternatives as vertices. A probabilistic rule assigns to each preference profile a probability distribution over the alternatives. First, all unanimous and strategy-proof probabilistic rules are characterized when the graph is a tree. These rules are uniquely determined by their outcomes at those preference profiles where all peaks are on leafs of the tree, and thus extend the known case of a line graph. Second, it is shown that every unanimous and strategy-proof probabilistic rule is random-dictatorial if and only if the graph has no leafs. Finally, the two results are combined to obtain a general characterization for every connected graph by using its block tree representation.

Joint work with Souvik Roy and Soumyarup Sadhukan.

---

Marcus Pivato (Cergy)

Bayesian Social Aggregation with Accumulating Evidence (Slides)

How should we aggregate the ex ante preferences of Bayesian agents with heterogeneous beliefs? Suppose the state of the world is described by a random process that unfolds over time. Different agents have different beliefs about the probabilistic laws governing this process. As new information is revealed over time by the process, agents update their beliefs and preferences via Bayes rule. Consider a Pareto principle that applies only to preferences which remain stable in the long run under these updates. I show that this "eventual Pareto" principle implies that the social planner must be a utilitarian. But it does not impose any relationship between the beliefs of the individuals and those of the planner.

Working Paper

2020-09-04: Dorothea Baumeister and Siddarth Barman [Video]

Please note that this session will be held on a Friday, given that there will be three sessions on computational social choice at ECAI on the Thursday of this week.

Session Chair: Ulle Endriss (Amsterdam)

---

Dorothea Baumeister (Düsseldorf)

Manipulation of Opinion Polls to Influence Iterative Elections (Slides)

In classical elections, voters only submit their ballot once, whereas in iterative voting, the ballots may be changed iteratively. In this talk I 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. I will present results on the manipulative power of the polling agency for the destructive case.

Joint work with Ann-Kathrin Selker and Anaëlle Wilczynski.

---

Siddharth Barman (Bangalore)

Fair Cake Division Under Monotone Likelihood Ratios (Slides)

The cake-cutting problem provides a model for addressing fair allocation of a divisible resource (metaphorically, the cake) among agents with distinct preferences. Classic results of Stromquist (1980) and Su (1999) show that envy-free (fair) cake divisions are guaranteed to exist under mild conditions. These strong existential results essentially follow from fixed-point theorems and stand without an algorithmic counterpart; Stromquist (2008) has shown that an envy-free cake division with contiguous pieces cannot be computed in bounded time.

In this talk I will present a result which complements these existential (and non-constructive) guarantees by way of developing efficient cake-cutting algorithms for a broad class of valuations. In particular, our algorithmic result holds when the agents' valuations are induced by linear translations of any log-concave function, such as Gaussian, exponential, linear, or binomial.

Joint work with Nidhi Rathi.

https://arxiv.org/abs/2006.00481

2020-08-20: Arkadii Slinko and Haris Aziz [Video]

This session was held four hours earlier than usual: 11:00 Paris, 17:00 Singapore, 19:00 Sydney, 21:00 Auckland.

Session Chair: Edith Elkind (Oxford)

---

Arkadii Slinko (Auckland)

Manipulation in Secret Sharing (Slides)

Secret sharing is a cryptographic implementation of a power-sharing agreement in society. At the centre of it is 'the secret', which is a string of 0 and 1 by knowing which a certain activity can be launched: accessing a bitcoin wallet; launching a nuclear warhead; signing a message on behalf of a large organisation, e.g., Adobe. The power structure is given by the set of authorised coalitions−coalitions who are authorised to launch the activity. We consider the digital forensics aspects of secret sharing. Sometimes an investigation is needed to establish: Who made this suspicious transaction with bitcoins? Who signed this offensive letter? Who opened a certain vault?

We investigate the problem of framing, which occurs when a coalition is able to calculate the share of a participant who does not belong to it. In the extreme case one authorised coalition can calculate shares of another authorised coalition and use the secret in some way blaming another authorised coalition for their action. We show that in any efficient and secure secret-sharing scheme framing is unavoidable.

Joint work with Yvo Desmedt and Songbao Mo.

---

Haris Aziz (Sydney)

The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints (Slides)

We consider the problem of probabilistic allocation of objects under ordinal preferences. Our main contribution is an allocation mechanism, called the vigilant eating rule (VER), that applies to nearly arbitrary distributional constraints. It is constrained ordinally-efficient, can be computed efficiently for a large class of constraints, and treats agents equally if they have the same preferences and are subject to the same constraints. When the set of feasible allocations is convex, we also present a characterization of our rule based on ordinal egalitarianism. Our general results concerning VER do not just apply to allocation problems but to any collective choice problem in which agents have ordinal preferences over discrete outcomes. As a case study, we assume objects have priorities for agents and apply VER to sets of probabilistic allocations that are constrained by stability. VER coincides with the (extended) probabilistic serial rule when priorities are flat and the agent-proposing deterministic deferred acceptance algorithm when preferences and priorities are strict. While VER always returns a stable and constrained efficient allocation, it fails to be strategyproof, unconstrained efficient, and envy-free. We show, however, that each of these three properties is incompatible with stability and constrained efficiency.

Joint work with Florian Brandl.

2020-07-23: Reshef Meir and Gil Kalai [Video]

This July many of us were hoping to travel to Israel for the 8th International Workshop on Computational Social Choice. This is a special session, with two speakers from Israel, organised to mark this occasion. Please note that this session will take place on a Thursday, as will most sessions in the foreseeable future.

Session Chair: Bill Zwicker (Union College)

---

Reshef Meir (Technion)

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment (Slides)

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. The primary contribution is an analysis of the incentives of reviewers during the bidding phases, when reviewers have private costs and some information about the demand for each paper, and want to obtain the best possible k papers for a predetermined k. We show that by assigning budgets to reviewers and a 'price' for every paper that is (roughly) inversely proportional to its demand, the best response of a reviewer is to bid sincerely, i.e., on her most favorite papers, and match the budget even when it is not enforced. Finally, we show via extensive simulations on bidding data from real conferences, that our suggested bidding scheme would substantially improve the assignment, under several common assignment algorithms.

Joint work with Natan Kaminsky, Jérôme Lang, Julien Lesca, and Nicholas Mattei.

---

Gil Kalai (Jerusalem)

New Quantitative and Qualitative Aspects of Social Choice Theory

Arrow's theorem is a far-reaching extension of Condorcet's paradox for the majority rule to general voting rules. We will ask to what extent other properties of the majority rule have such wide extensions, and what are some properties of the majority rule that distinguish it from other voting rules.

2020-07-10: Bettina Klaus and Omer Lev [Video]

Session Chair: Dominik Peters (CMU)

---

Bettina Klaus (Lausanne)

The Core for Housing Markets with Limited Externalities (Slides)

We propose a variant of the housing market model à la Shapley and Scarf (1974) that incorporates a limited form of externality in consumption; that is, agents care both about their own consumption (selfish preferences) and about the agent who receives their endowment (altruistic preferences). First, we consider different domains of preference relations by taking selfish and altruistic aspects of preferences into account (separable preferences, additive separable preferences, and selfish and/or altruistic lexicographic preferences) and several results regarding the core for such housing markets are collected. Second, if preferences are either selfish lexicographic or altruistic lexicographic, we characterize the corresponding top trading cycles rule by individual rationality, Pareto optimality, and strategy-proofness. Since on the lexicographic preference domains the core can be multi-valued, our characterization sheds light on the fact that the properties that also characterized the strict core rule for Shapley-Scarf housing markets (Ma, 1994) characterize the top trading cycles rule and not the strict core rule (or correspondence).

Joint work with Claudia Meo.

---

Omer Lev (Ben-Gurion)

We Need a Little More Space: A Few More Spatial Problems (Slides)

Spatial models in voting have received a lot of attention in recent years, both in the physical sense (e.g., gerrymandering) as well as the conceptual sense (e.g., distortion). We will show two separate threads of spatial problems, which have received less attention recently. One deals with the well-known Hotelling-Downs model, adapted to the more common (in COMSOC literature) winner-take-all setting. We characterize Nash equilibria for multiple voting rules, and try to measure the "amount" of equilibria, by measuring the probability of randomly reaching a NE. The second deals with the problem of placing voting locations, in which we show many settings of the problem are difficult even to approximate (but a few are not!). Both problems present a rich set of questions which require further exploration.

Joint work with Zack Fitzsimmons, Alexander Karpov, and Svetlana Obraztsova.

2020-07-03: Jérôme Lang and Ulle Endriss [Video]

Session Chair: Edith Elkind (Oxford)

---

Jérôme Lang (Paris)

Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions: Survey Talk (Slides)

Solution concepts in collective decision making are usually defined assuming complete knowledge of individuals' preferences and of the mechanism used for aggregating them. This is often impractical or unrealistic. Under incomplete knowledge, a solution advocated by many consists in quantifying over all completions of the incomplete preference profile (or all instantiations of the incompletely specified mechanism). Voting rules can be 'modalized' this way (leading to the notions of possible and necessary winners), and also efficiency and fairness notions in fair division, stability concepts in coalition formation, and more. The talk will give a very brief survey of works along this line, focusing on examples.

---

Ulle Endriss (Amsterdam)

Axiomatic Justification of Election Outcomes (Slides)

In social choice theory, we routinely attempt to justify the use of a given voting rule on axiomatic grounds. In this talk, I instead want to ask the question of what it might mean to directly justify an election outcome on axiomatic grounds. A possible answer, I will argue, is that a justification has two parts: a set of normative principles (meaning, axioms) and a step-by-step explanation of how those principles force us to choose the outcome in question for a given profile of preferences. I will also discuss recent work on the use of tools from the field of automated reasoning to compute such justifications.

Joint work with Arthur Boixel.

http://www.ifaamas.org/Proceedings/aamas2020/pdfs/p168.pdf

2020-06-26: Leeat Yariv and Tetsuya Hoshino [Video]

This June many of us were hoping to travel to Mexico for the 15th Meeting of the Society for Social Choice and Welfare. To mark this occasion we are organising two special sessions with speakers from Mexico as well as some of the original keynote speakers. This is the second of these sessions. Please note that we will start one hour later than usual: 09:00 Mexico, 10:00 New York, 16:00 Paris.

Session Chair: Andrei Gomberg (ITAM)

---

Leeat Yariv (Princeton)

Who Cares More: Allocation with Diverse Preference Intensities

Goods and services—public housing, medical appointments, schools—are often allocated to individuals who rank them similarly but differ in their preference intensities. We characterize optimal allocation rules in such settings, considering both the case in which individual preferences are known and ones in which they need to be elicited. Several insights emerge. First-best allocations may involve allocating to some agents lotteries between very high-ranked and very low-ranked goods. When preference intensities are private information, second-best allocations always involve such lotteries and, crucially, may coincide with first-best allocations. Second-best allocations may also entail disposal of services. We also discuss market-based alternative approach and show how it differs.

Joint work with Pietro Ortoleva and Evgenii Safonov.

---

Tetsuya Hoshino (ITAM)

Time-Consistent Rational Inattention is Entropic (Slides)

We study a dynamic rational inattention problem in which, each period, an agent acquires costly information about an evolving state and chooses an action. A dynamic rational inattention problem is time-consistent if its value function satisfies the dynamic programming principle. The main result is that if every dynamic rational inattention problem is time-consistent then the cost function is entropic—that is, linear in the reduction in entropy of beliefs. This result corresponds to the converse to Steiner, Stewart, and Matějka (2017), who showed that every dynamic rational inattention problem with entropy costs is time-consistent.

2020-06-19: Romans Pancs and Jordi Massó [Video]

This June many of us were hoping to travel to Mexico for the 15th Meeting of the Society for Social Choice and Welfare. To mark this occasion we organised two special sessions with speakers from Mexico as well as some of the original keynote speakers. This is the first of these sessions. We started one hour later than usual: 09:00 Mexico, 10:00 New York, 16:00 Paris.

Session Chair: Vincent Merlin (Caen)

---

Roman Pancs (ITAM)

Electoral Maldistricting

We introduce the framework to examine, both theoretically and empirically, (geographic) electoral maldistricting. Maldistricting is defined as electoral districting in pursuit of a policy or incumbency objective at the expense of social welfare. Thanks to a revelation principle-like property of our environment, analysis is performed on the set of implementable (via some districting) legislatures. Implementable legislatures are characterized multiply, including in terms of their informativeness about voter ideology. Maldistricting is quantified by an observed legislature’s distance from welfare-maximizing legislatures relative to the maldistricted ones. If voter turnout can vary across geographic locations, electoral districting becomes more delicate.

Joint work with Andrei Gomberg and Tridib Sharma.

---

Jordi Massó (Barcelona)

All Sequential Allotment Rules are Obviously Strategy-proof (Slides)

For the division problem with single-peaked preferences (Sprumont, 1991) we show that all sequential allotment rules, identified by Barberà, Jackson and Neme (1997) as the class of strategy-proof, efficient and replacement-monotonic rules, are also obviously strategy-proof. Although obvious strategy-proofness is in general more restrictive than strategy-proofness, this is not the case in this setting.

Joint work with Pablo Arribillaga and Alejandro Neme.

2020-06-05: Nisarg Shah and Péter Biró [Video]

Session Chair: Vincent Merlin (Caen)

---

Nisarg Shah (Toronto)

Resolving the Optimal Metric Distortion Conjecture (Slides)

In the metric distortion framework of voting, voters and candidates lie in a metric space, and each voter ranks the candidates by their distance from her. The voting rule takes only the preference rankings as input, and picks a candidate that approximately minimizes the total distance from the voters. The distortion of a rule is its worst-case approximation ratio. A major conjecture in this framework is that the optimal deterministic voting rule has distortion 3. We resolve this conjecture positively by constructing a new voting rule that has distortion 3. We do so by proving a novel lemma about matching rankings of candidates to candidates, which may be of independent interest. We also provide parametric distortion bounds and improved bounds for randomized rules.

---

Péter Biró (Budapest)

Fairness in Kidney Exchange Programmes (Slides)

Most of the large European countries are operating national kidney exchange programmes (KEPs) with various policies and performances. The primal objective is always to maximise the number of transplants, but increased attention is being paid to the quality of transplants as well, especially when compatible or ABO-incompatible pairs are incentivised to join these programmes instead of conducting a direct transplant. We argue that the concept of stability can play an important role in future applications due to individual fairness and incentive considerations. Furthermore, fairness concepts can also become crucial at country level when multiple countries are joining their pools. In this talk we will review the recent developments on the aspects of individual and collective fairness for KEPs from both theoretical and practical point of views, starting with a story from the 2008 COMSOC conference.

2020-05-29: Gabrielle Demange and Yair Zick [Video]

Session Chair: Bill Zwicker (Union College)

---

Gabrielle Demange (Paris)

Resolution Rules in a System of Financially Linked Firms (Slides)

The reimbursement abilities of firms holding liabilities on each other are intertwined, potentially generating coordination failures and defaults through uncontrolled contagion. In stress episodes, these linkages thus call for an orderly resolution, as implemented by a regulatory authority assigning the amount each firm within the system reimburses to each other one. The paper studies such resolution by considering `rules', assuming their primary goal is to avoid default on external debts, say, banks' defaults on deposits. The main objective is to investigate what proportionality means for a rule, taking into account various legal and informational constraints.

---

Yair Zick (Singapore)

A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts [updated]

The past few years have seen several works on learning economic solutions from data; these include optimal auction design, function optimization, stable payoffs in cooperative games and more. In this work, we provide a unified learning-theoretic methodology for modeling such problems, and establish tools for determining whether a given economic solution concept can be learned from data. Our learning theoretic framework generalizes a notion of function space dimension -- the graph dimension -- adapting it to the solution concept learning domain. We identify sufficient conditions for the PAC learnability of solution concepts, and show that results in existing works can be immediately derived using our methodology. Finally, we apply our methods in other economic domains, yielding a novel notion of PAC competitive equilibrium and PAC Condorcet winners.

Joint work with Tushant Jha.

2020-05-22: Rump Session [Video]

Session Chair: Ulle Endriss (Amsterdam)

Speakers: Nick Arnosti (Columbia), Haris Aziz (Sydney), Paul Gölz (CMU), Ronald de Haan (Amsterdam), Hadi Hosseini (Rochester), Neeldhara Misra (Gandhinagar), Joe Singleton (Cardiff), Piotr Skowron (Warsaw), Zoi Terzopoulou (Amsterdam), Stanislav Zhydkov (Warwick)

2020-05-15: Makoto Yokoo and Xiaohui Bei [Video]

Session Chair: Haris Aziz (Sydney)

This session was held at a different time, eight hours earlier than usual: 01:00 New York, 07:00 Paris, 10:30 India, 13:00 China/Singapore, 14:00 Japan, 15:00 Sydney, 17:00 Auckland on Friday; and 22:00 California on Thursday.

---

Makoto Yokoo (Kyushu University)

Game-Theoretic Analysis for Two-Sided Matching with Resource Allocation (Slides)

In this work, we consider a student-project-resource matching-allocation problem, where students have preferences over projects and the projects have preferences over students. Although students are many-to-one matched to projects, indivisible resources are many-to-one allocated to projects whose capacities are endogenously determined by the resources allocated to them. Traditionally, this problem is decomposed into two separate problems: (1) resources are allocated to projects based on expectations (resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (matching problem). Although both problems are well-understood, if the expectations used in the first are incorrect, we obtain a suboptimal outcome. Thus, this problem must be solved as a whole without dividing it in two parts. We show that no strategyproof mechanism satisfies fairness (i.e., no student has justified envy) and weak efficiency requirements on students' welfare. Given this impossibility result, we develop a new strategyproof mechanism that strikes a good balance between fairness and efficiency and assess it by experiments.

---

Xiaohui Bei (Nanyang Technological University)

Fair Division of Mixed Divisible and Indivisible Goods

In this talk, we will discuss the challenges of defining fairness and designing fair division algorithms when the resources to be allocated contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. We propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We show that an EFM allocation always exists for any number of agents and discuss how to find an ε-EFM allocation in polynomial time in the Robertson-Webb model.

Joint work with Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu.

2020-05-08: Ágnes Cseh and Remzi Sanver [Video 1] [Video 2]

Session Chair: Edith Elkind (Oxford)

---

Ágnes Cseh (Potsdam)

Popular Roommate Assignments (Slides)

Popularity is an optimality notion that connects the Condorcet criterion known from voting with stability known from matchings under preferences. The popular roommates problem is defined on a non-bipartite graph, where each vertex submits a strictly ordered preference list of its neighbors. A matching M is popular if there is no matching N such that vertices that prefer N to M outnumber those that prefer M to N. The complexity of finding a popular matching had been open for a long time before its solution last year. In this talk, we review recent progress on complexity, approximation, and algorithms for this problem.

https://arxiv.org/abs/1807.01112

---

Remzi Sanver (Paris)

A Solution to the Two-person Implementation Problem

We propose strike mechanisms as a solution to the classical problem of Hurwicz and Schmeidler (1978) and Maskin (1999) according to which, in two-person societies, no Pareto efficient rule is Nash-implementable. A strike mechanism specifies the number of alternatives that each player vetoes. Each player simultaneously casts these vetoes and the mechanism selects randomly one alternative among the unvetoed ones. For strict preferences over alternatives and under a very weak condition for extending preferences over lotteries, these mechanisms are deterministic-in-equilibrium. They Nash-implement a class of Pareto efficient social choice rules called Pareto-and-veto rules. Moreover, under mild richness conditions on the domain of preferences over lotteries, any Pareto efficient Nash-implementable rule is a Pareto-and-veto rule and hence is implementable through a strike mechanism.

Joint work with Jean-François Laslier and Matías Núñez.

2020-05-01: Piotr Faliszewski and Clemens Puppe [Video]

Session Chair: Ulle Endriss (Amsterdam). 142 participants.

---

Piotr Faliszewski (Kraków)

Drawing a Map of Elections in the Space of Statistical Cultures

We consider the problem of forming a testbed of elections to be used for various election-related experiments (such as testing algorithms or estimating the frequency of a given phenomenon). We seek elections that come from well-known statistical distributions and are as diverse as possible. To this end, we define a (pseudo)metric over elections, generate a large set of election instances, and measure distances between them, to assess how diverse they are. We argue that our metric is a reasonable choice, and we show how the resulting set of elections can be used to evaluate election-related algorithms.

Joint work with Stanislaw Szufa, Piotr Skowron, Nimrod Talmon, and Arkadii Slinko.

---

Clemens Puppe (Karlsruhe)

Strategy-Proofness implies Minimal Participation if Voting is Costly (Slides)

We study a model in which agents with single-peaked preferences can participate in a costly voting procedure to determine the value of a one-dimensional variable. We show that, for all positive participation cost and all profiles of individual preferences, there exists a generically unique equilibrium with one single participant whenever the voting mechanism is strategy-proof, anonymous, and responsive in the sense that the outcome reacts to a unanimous move of the votes of all agents in the same direction. Since this single participant is never the median voter, we obtain as a corollary that no deterministic mechanism can implement the median if all participants vote according to their unique dominant strategy; even worse, the peak of the single participant in equilibrium is maximally far away from the median voter. By contrast, there are simple probabilistic strategy-proof mechanisms that yield the median as outcome. Inspired by this observation, we investigate if the median can be ‘approximately implemented’ by a natural deterministic counterpart, and come to a negative conclusion.

Joint work with Michael Müller.

Working Paper


2020-04-24: Vincent Conitzer and Edith Elkind [Video]

Session Chair: Dominik Peters (CMU). 260 participants.

---

Vincent Conitzer (Duke)

Computational Social Choice for Moral Artificial Intelligence (Slides)

Many algorithms in AI require an objective function to be specified. When such an algorithm is to be deployed in the real world, it is often not obvious what the objective function should be. For example, there are often nontrivial ethical tradeoffs. Generally, stakeholders will disagree on how these should be made. Moreover, even for themselves, they will generally not be able to write down a complete objective function; perhaps at most, they can be asked to make a few judgments on some concrete examples. How do we aggregate these individual judgments into an objective function for the algorithm to use?

Joint work with Lok Chan, Yuan Deng, John Dickerson, Kenzie Doyle, Rachel Freedman, Max Kramer, Duncan McElfresh, Jana Schaich Borg, Walter Sinnott-Armstrong, and Hanrui Zhang.

---

Edith Elkind (Oxford)

Keeping Your Friends Close: Land Allocation with Friends (Slides PDF/PPTX)

We examine the problem of assigning plots of land to prospective buyers who prefer living next to their friends. They care not only about the plot they receive, but also about their neighbors. This externality results in a highly non-trivial problem structure, as both friendship and land value play a role in determining agent behavior. We examine mechanisms that guarantee truthful reporting of both land values and friendships. We propose variants of random serial dictatorship (RSD) that can offer both truthfulness and welfare guarantees. Interestingly, our social welfare guarantees are parameterized by the value of friendship: if these values are low, enforcing truthful behavior results in poor welfare guarantees and imposes significant constraints on agents' choices; if they are high, we achieve good approximation to the optimal social welfare.

Joint work with Neel Patel, Alan Tsang, and Yair Zick.

https://arxiv.org/abs/2003.03558

Interested in giving a talk? Fill out the quick form and we will be in touch. Thanks!