2021 Past Seminars

Host: Hervé Moulin

Abstract: We consider a participatory budgeting problem in which each voter submits a proposal for how to divide a single divisible resource (such as money or time) among several possible alternatives (such as public projects or activities) and these proposals must be aggregated into a single aggregate division. Under \ell_1 preferences---for which voter's disutility is given by the \ell_1 distance between the aggregate division and the division he or she most prefers---the social welfare-maximizing mechanism, which minimizes the average \ell_1 distance between the outcome and each voter's proposal, is incentive compatible (Goel et al. 2016). However, it fails to satisfy the natural fairness notion of proportionality, placing too much weight on majority preferences. Leveraging a connection between market prices and the generalized median rules of Moulin (1980), we introduce the independent markets mechanism, which is both incentive compatible and proportional. We unify the social welfare-maximizing mechanism and the independent markets mechanism by defining a broad class of moving phantom mechanisms that includes both. We show that every moving phantom mechanism is incentive compatible. Finally, we characterize the social welfare-maximizing mechanism as the unique Pareto-optimal mechanism in this class, suggesting an inherent tradeoff between Pareto optimality and proportionality. 

This is joint work with David M. Pennock, Dominik Peters, and Jennifer Wortman Vaughan.

Host: Remzi Sanver

Abstract: We study whether Approval mechanisms --i.e. voting systems that allow subjects to vote for as many alternatives as they want-- can help a committee reach consensus. By focusing on the single-peaked domain, we prove that if an Approval mechanism satisfies a set of desirable properties, then it leads to a predictable and unanimous decision (i.e. the equilibrium outcome is unique and it is approved by everyone). Moreover, we establish that the set of Approval mechanisms that satisfy these properties is quite rich: essentially, for every Nash-implementable choice rule, there exists an Approval mechanism that unanimously implements it. 

This is joint work with Matias Nunez.

Host:  Youngsub Chun 

Abstract: The nonasymptotic Condorcet jury theorem states that, under certain conditions,  group decision-making by simple majority voting can decide more efficiently than single-person decision-making, in terms of having a higher probability of choosing the better alternative. Wit (1998) showed that the nonasymptotic Condorcet jury theorem holds under strategic voting in the basic model in which each member receives a binary signal. We examine the robustness of the nonasymptotic Condorcet jury theorem shown by Wit (1998) with respect to the assumptions of information structure. We show two results. The first result is that the nonasymptotic Condorcet jury theorem holds robustly in a general signal model with finite signals for binary states when the strongest signals for each state are realized with probability larger than 1/2. The second result is that the nonasymptotic Condorcet jury theorem may not hold when the strongest signal that indicates a particular state is realized with probability less than 1/2. We provide a sufficient condition for this anti-Condorcet jury theorem with respect to the prior probability and the likelihoods of signals.

Host: Arkadii Slinko

Abstract: We provide an exhaustive classification of all preference domains that allow the design of unanimous social choice functions (henceforth, rules) that are non-dictatorial and strategy-proof. This taxonomy is based on a richness assumption and employs a simple property of two-voter rules called invariance. The preference domains that form the classification are semi-single-peaked domains (introduced by Chatterji et al. (2013)) and semi-hybrid domains (introduced here) which are two appropriate weakenings of the single-peaked domains, and which, more importantly, are shown to allow strategy-proof rules to depend on non-peak information of voters’ preferences. As a refinement of the classification, single-peaked domains and hybrid domains emerge as the only preference domains that force strategy-proof rules to be determined completely by the peaks of voters’ preferences. We also provide characterization results for strategy-proof rules on these domains.

Host: Simona Fabrizi

Abstract: While collective decision-making does not always lead to decisive outcomes in practice, models of collective choice almost invariably rule out the possibility of indecisiveness. Taking a step to address this disconnect, I extend three prominent collective choice procedures (the top cycle, uncovered set, and Banks set) to a general setting where social comparisons may be incomplete. I provide axiomatic foundations for the three procedures in this setting—to show that indecisiveness does not undermine their fundamental appeal. 

Host: Danilo Coelho

Abstract. Objects of different quality are to be assigned to agents. Agents can be assigned at most one object and there are not enough high-quality objects for every agent. The social planner is unable to use transfers to give incentives for agents to convey their private information; instead, she is able to imperfectly verify their reports. We characterize the set of mechanisms that maximize welfare and then apply our results to the case of colleges' admissions. We find that optimal mechanisms are, in general, ex-post inefficient and do strictly better than the standard mechanisms that are studied in the matching literature.

This is joint with Francisco Silva, Pontificia Universidad Catolica de Chile. 

Host: Jobst Heitzig

Abstract: In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects.  An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. In this paper we show that in the case of strict preferences the unique strong core allocation (or competitive allocation) “respects improvement”:  if an agent’s object becomes more attractive for some other agents, then the agent’s allotment in the unique strong core allocation weakly improves.  We obtain a general result in case of ties in the preferences and provide new integer programming formulations for computing (strong) core and competitive allocations.  Finally,  we conduct computer simulations to compare the game-theoretical solutions with maximum size and maximum weight exchanges for markets that resemble the pools of kidney exchange programmes. 

Joint work with Flip Klijn, Xenia Klimentova and Ana Viana. Manuscript is available at https://arxiv.org/pdf/2102.00167.pdf

Host: Marcus Pivato

Abstract:  This talk focuses on the notion of power in proxy-voting systems where proxies are delegable, also known as liquid democracy. Building on the Banzhaf-Penrose power index for weighted voting games, I will present an index that can quantify the influence of both voters and delegators, and characterise it axiomatically. Then, using this index, I will study games where agents are engaging in a truth-tracking task but their utilities depend on competing interests: on the one hand they want to improve their decision-making accuracy (by delegating to more competent agents), and on the other hand they want to retain power. In such games power-seeking behavior, in equilibrium, has a balancing effect on the number of delegations that agents are able to accrue, thereby mitigating power imbalances in the system.

This is joint work with Yuzhe Zhang (University of Groningen).

Host: Marcus Pivato

Abstract: Public policies are supposed to be determined by maximization of the social lifetime utility. This paper focuses on the general process, aggregation rules and unanimity conditions, which makes these policies socially eligible by individuals through their own discount factors and instantaneous utilities. We show that perfect altruism via an adapted form of unanimity is the key condition helping to characterize a time consistent society concerned with intergenerational fairness in the presence of individuals who are heterogeneous in discount factors as well as in instantaneous utilities. In addition, different intensity levels of altruism are proved to provide different forms of aggregated social discounting and instantaneous utility, these forms giving birth to several lifetime utilities, from the standard exponential discounted function to the quasi-hyperbolic and the k-hyperbolic ones. Moreover, by showing that the degree of social present-bias can be regulated by the choice of the number of periods involving altruism through unanimity, new insights emerge and potentially overturn some of the most standard economic policy recommendations.

Joint work with Antoine Billot (LEMMA, Université Paris II Panthéon-Assas).

Host: Marcus Pivato

Abstract.  In this paper, we analyze social orderings when there may be a risk on i) the actual allocation people will receive; ii) their preferences; and iii) the size of the population. Such a risk exists for instance when considering policies that affect future people, for instance climate policy. We show that in this context, there is no social ordering that meets minimal requirements of fairness, social rationality, and respect for people's ex ante preferences. We explore three ways to avoid this impossibility. First, if we drop the ex ante Pareto requirement, we can obtain fair ex post criteria that take an (arbitrary) expected utility of an equally-distributed equivalent level of well-being. Second, if the universal social ordering is not an expected utility, we can obtain fair ex ante criteria that assess uncertain individual prospects with a certainty-equivalent measure of well-being. Third, if we accept that interpersonal comparisons rely on VNM utility functions even in absence of risk, we can construct expected utility social orderings that satisfy of some version of Pareto ex ante.

Joint work with Stéphane Zuber (CNRS and Paris School of Economics)

Host: Arkadii Slinko

Abstract:  We study a setting in which a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes, in particular in systems for democratic deliberation support, such as, for instance, LiquidFeedback or Polis.

Based on joint work with Davide Grossi, Nimrod Talmon, Udi Shapiro, Abheek Ghosh and Paul Goldberg.

Host: Remzi Sanver

Abstract.  A hyper-preference maps every linear order (preference) over a finite set M of alternatives to a linear order over all orders of elements of M. An Arrowian aggregation rule that cannot be manipulated with respect to at least one hyper-preference is called minimally strategy-proof. We provide a characterization of minimal strategyproofness. Based on this characterization, we show that some classes of rules (Condorcet-Kemeny rules and Slater rules) that are betweenness strategy-proof as introduced in Bossert and Sprumont (2014) or Kemeny strategy-proof according to Athanasoglou (2016) become manipulable, whereas others (status-quo rules) retain minimal strategy-proofness. Moreover, we show that an aggregation rule is strategyproof for all hyper-preferences in a rich domain if and only if it is either constant or dictatorial, where richness requires that each ordering of a pair of preferences can be obtained from some hyper-preference.

Joint work with Onur Doğan.

Host: Jobst Heitzig

Abstract. We study the problem of allocating indivisible goods among agents with additive valuations. Prior work achieves exact fairness in expectation when randomization is allowed or approximate fairness when a deterministic allocation must be chosen. We set out to achieve both simultaneously, by constructing randomized allocations that are exactly fair ex ante and approximately fair ex post. Our main result is that a randomized allocation that is both envy-free ex ante and envy-free up to one good ex post always exists and can be computed efficiently. We also consider efficiency guarantees, provide other possibility and impossibility results, and extend our results to the allocation of indivisible chores.

Joint work with Rupert Freeman and Rohit Vaish.

Link to paper: https://www.cs.toronto.edu/~nisarg/papers/best_of_both.pdf

Host:  Simona Fabrizi

Abstract.   Social media provides platforms for influence seekers to shape public opinion through attention hacking: the act of exploiting platforms' content sorting algorithms to highlight certain information items to users, e.g., by using bots. While innocuous bots make up a significant proportion of online activities, nefarious attention hacking bots are highly worrisome. By up- or downvoting posts, they seek to elevate or suppress specific topics in the public perception, flood platforms with misinformation, and overwhelm with narratives counter to a genuine public interest. The detection of such computational propaganda is difficult as these bots mask their identity, mimicking human behavior to an increased extent. Inflated online votes by nefarious attention hacking bots counteract wisdom-of-crowds effects induced by genuine users which otherwise inform about the epistemic quality of a given post. This nullifies the reliability of online voting judgments on posts' quality. To restore wisdom-of-crowds effects, it is desirable to remove such bots from the voting jury. To this end, we design two jury selection procedures that discard agents classified as nefarious. Both cluster binary vote data---one using a Gaussian Mixture Model, one using the k-means algorithm---and label agents by logistic regression. We evaluate these jury selection procedures with an agent-based model, and show that the Gaussian procedure detects more nefarious bots, but both procedures select juries with vastly increased correctness of vote by majority.

Host:  Arkadii Slinko

Abstract.  We revisit the problem of existence of stable systems of contracts with arbitrary sets of contracts. We show that stable sets of contracts exists if choices of agents satisfy path-independence. We call such choice functions Plott functions. Our proof is based on application of Zorn lemma to a special poset of semi-stable pairs. Moreover, we construct a dynamic process on the poset (generalizing algorithm of Gale and Shapley) the steady states of which are stable sets. We also discuss Lehmann hyper-orders and establish a bijection between the set of Lehmann hyper-orders and the set of Plott functions. 

This is a joint paper with Vladimir Danilov.

Host: Piotr Faliszewski

Abstract.  We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and -- in addition to a global budget limit, there are several groupings of the projects, each group with its own budget limit. We study the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. We show that the problem is generally intractable and describe efficient exact algorithms for several special cases, including instances with only few groups and instances where the group structure is close to be hierarchical, as well as efficient approximation algorithms. Our results could allow, e.g., municipalities to hold richer PB processes that are thematically and geographically inclusive.

Joint work with: Pallavi Jain, Nimrod Talmon and Meirav Zehavi.

Host:  Simona Fabrizi 

Abstract.  The formal study of coalition formation in multiagent systems is typically realized using so-called hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has received considerably less attention. In this talk, we study the convergence of simple dynamics based on single-agent deviations in hedonic games. We consider various strategies for proving convergence of the dynamics based on potential functions. In particular, we showcase methods for dealing with non-monotonic potential functions. On the other hand, it is a challenging task to pinpoint the boundary of tractability of stable states. We show how to construct complicated counterexamples with the aid of linear programs. These counterexamples can usually be used to prove computational intractabilities, and we outline a general approach to generate such proofs.

References:

F. Brandt, M. Bullinger, and A. Wilczynski. Reaching Individually Stable Coalition Structures in Hedonic Games. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5211–5218, 2021.

F. Brandt, M. Bullinger, and L. Tappe. Single-Agent Dynamics in Additively Separable Hedonic Games. 2021 (working paper).

Host:  Piotr Faliszewski

Abstract.  Liquid democracy is a novel paradigm for collective decision-making that gives agents the choice between casting a direct vote or delegating their vote to another agent. We consider a generalization of the standard liquid democracy setting by allowing agents to specify multiple potential delegates, together with a preference ranking among them. This generalization increases the number of possible delegation paths and enables higher participation rates because fewer votes are lost due to delegation cycles or abstaining agents. In order to implement this generalization of liquid democracy, we need to find a principled way of choosing between multiple delegation paths. We call such functions delegation rules, and analyze their space from axiomatic, empirical, and algorithmic viewpoints. 

References

• Liquid Democracy with Ranked Delegations (working paper, 2021), Markus Brill, Théo Delemazure, Anne-Marie George, Martin Lackner, Ulrike Schmidt-Kraepelin 

• Popular Branchings and Their Dual Certificates (Mathematical Programming, 2021) Telikepalli Kavitha, Tamás Kiraly, Jannik Matuschke, Ildikó Schlotter, Ulrike Schmidt-Kraepelin

Host:  Jobst Heitzig

Abstract.   We show that if a rule is strategy-proof, unanimous, anonymous and tops-only, then the preferences in its domain have to be local and weakly single-peaked, relative to a family of partial orders obtained from the rule by confronting different alternatives with distinct levels of support. We also show that if this domain is enlarged by adding a non local and weakly single-peaked preference, then the rule becomes manipulable. Finally, we illustrate why local and weak single-peakedness constitutes a weakening of already known and well-studied restricted domains of preferences.

This is a joint with Agustín Bonifacio and Pablo Neme (both at the Universidad Nacional de San Luis, Argentina).

Host:  Marcus Pivato

Abstract.  “Banning the Box” refers to a policy campaign aimed at prohibiting employers from soliciting applicant information that could be used to statistically discriminate against categories of applicants (in particular, those with criminal records). In this article, we examine how the concealing or revealing of informative features about an applicant's identity affects hiring, wages, and, most importantly, applicant incentives to invest in human capital.

We show that there are situations in which an employer and an applicant are in strict agreement about whether to ban the box.  There are also situations where concealing applicant information can help the applicant and hurt the employer and, more surprisingly, where concealing this information helps the employer but hurts the applicant.  Our results have policy implications spanning beyond employment decisions, including the use of credit checks by landlords and standardized tests in college admissions.  Our findings also speak to issues of algorithmic fairness, and how information about protected classes should most beneficially be utilized.

Joint work with John Patty.

Host:   Marcus Pivato

Abstract.  Defenders of the Electoral College routinely invoke a traditional argument to reject proposals for a national popular vote. Granted, they say, Florida in 2000 was a national nightmare, but the agony would be far greater if such a dispute extended over the entire nation. Proponents of a direct vote reply by conjecturing that the Electoral College increases the frequency of disputable elections. Indeed, the 2020 US presidential election was another instance of disputable election on the legal front. We investigate whether we should expect disputable outcomes to be more frequent under the present US indirect system as compared with a direct vote and, if so, by how much. We use two methods: an historical analysis of actual outcomes in presidential elections, and an a priori formal model borrowed from Social Choice Theory (IAC). Depending on the thresholds one posits for disputability, the historical analysis shows that disputable elections have been about two to six times more frequent under the Electoral College. In a model where all the states have the same population the IAC model produces an impressively compatible intermediate ratio of 4:1. We also explore the impact of differences in the population of the states on the likelihood of legal disputes via computer simulations.

Joint work with Jack Nagel and Théo Duchemin.