2023 Past Seminars

Host: Marcus Pivato

Abstract. We propose a fair and efficient solution for assigning agents to posts subject to congestion, when agents care about both their post and its congestion. Examples include assigning jobs to busy servers, students to crowded schools, commuters to congested routes, workers to crowded office spaces or to team projects etc...

In our first model congestion is anonymous (it only depends on the number of agents in a given post). Ex Ante Fairness allows each one of the n agents to veto all but her n best outcomes by capping the amount of congestion they accept in each post. Ex Post Fairness, interpreted as a fractional (randomised or time sharing) version of Envy Freeness, characterises a unique efficient solution, implemented by a combination of ex ante fair deterministic assignments envy-free up to one unit of congestion.

These two results generalise to our second model where congestion has a possibly different weight for each agent. Ex Ante Fairness still allows agents to cap the congestion they tolerate in each post, and fractional Envy Freeness picks a single efficient and ex ante fair solution.

Joint work with Anna Bogomolnaia.

Host: Marcus Pivato

Abstract. We compare Ranked-Choice Voting (RCV) and Plurality Voting (PV) in elections with 3 candidates. Voters receive consequential benefits from the election of a candidate close to their preferred policy position and also benefit from expressing their preferences sincerely. We provide conditions under which RCV will ensure both the existence of a sincere voting equilibrium and the election of the Condorcet winner, while PV may fail in both respects.

(Joint work with Richard Holden.)

Host: Marcus Pivato

Abstract. Cryptocurrencies are quickly becoming an essential component of the digital realm.  Yet, present-day cryptocurrencies are intrinsically plutocratic (one coin – one vote).  As part of our effort to develop an alternative egalitarian computational foundation for the digital realm, we are exploring a notion of cryptocurrencies that is grassroots and egalitarian, termed sovereign cryptocurrencies.

Sovereign cryptocurrencies are a digital means for turning mutual trust into liquidity.  They are similar to mainstream cryptocurrencies in that they exist only in the digital realm; created and traded digitally according to an agreed-upon protocol; and their value critically depends on the integrity of execution of their protocol.  They are different from mainstream cryptocurrencies and similar to national fiat currencies in being units of debt issued by a sovereign entity that controls their scarcity. Sovereign cryptocurrencies can be issued digitally by anyone -- people, communities, corporations, banks, municipalities and governments -- and traded by anyone. With sovereign cryptocurrencies, independent local digital economies can emerge without initial capital or external credit, and gradually merge into one global digital economy.

In this talk we introduce the principles that underlie sovereign cryptocurrencies; elaborate economic scenarios derived from these principles; present the Sovereign Cryptocurrencies protocol and describe its implementation by grassroots dissemination; and explore the use of sovereign cryptocurrencies for the creation of sybil-resilient democratic digital communities.

Host: Marcus Pivato

Abstract. Perpetual voting is a new formalism to support long-term collective decision making. The corresponding perpetual voting rules take the history of previous decisions into account and ---due to this additional information ---can offer fairness guarantees that are unachievable in single-shot decisions. In particular, such rules enable minorities to have a fair (proportional) influence on the decision process and thus sustain participation. I will discuss strengths and caveats of perpetual voting and present results of our axiomatic analysis.

(Joint work with Jan Maly.) 

Host: Marcus Pivato

Abstract. Extensive measurement is the standard measurement-theoretic approach for constructing a ratio scale. It involves the comparison of objects that can be “concatenated" to form new ones—for example, by stacking rods together from end to end, or by placing weights together in pans of an equal-arm balance. It is, in my view, an open question whether or not extensive measurement can be applied to individual well-being. This paper supposes that it can and explores the implications of extensively measurable welfare for social choice theory. We do this in two frameworks: one with a fixed population and no interpersonal comparisons, another with variable populations and full interpersonal comparability. Within each framework, we prove a welfarism theorem and characterize the social welfare functions that satisfy the axioms of extensive measurement at both the individual and social levels. The main result is a simple axiomatization of classical (i.e., total) utilitarianism. We conclude by drawing some broader lessons for foundational issues in social choice and welfare theory, including the utilitarian relevance of Harsanyi's aggregation theorem, as well as the interpretation of and justification for informational invariance conditions on social welfare functionals. 

Host: Marcus Pivato

Abstract. In many settings, a collective decision has to be made over a set of alternatives that has a combinatorial structure: examples are multi-winner elections, participatory budgeting, collective scheduling, and collective network design. A further common point of these settings is that agents generally submit preferences over issues (e.g., projects to be funded), each having a cost, and the goal is to find a feasible solution maximising the agents' satisfaction under problem-specific constraints. We propose the use of judgment aggregation as a unifying framework to model these situations, which we refer to as collective combinatorial optimisation problems. Despite their shared underlying structure, collective combinatorial optimisation problems have so far been studied independently. Our formulation into judgment aggregation connects them, and we identify their shared structure via five case studies of well-known collective combinatorial optimisation problems, proving how popular rules independently defined for each problem actually coincide. We also chart the computational complexity gap that may arise when using a generic judgment aggregation framework instead of a specific problem-dependent model.

(Joint work with Linus Boes, Rachael Colley, Umberto Grandi and Jérôme Lang.)

Host: Marcus Pivato

Abstract. We introduce Pendular Voting, a two-stage voting procedure that works as follows.  In the first stage, an agenda-setter chooses a proposal to replace the status quo, and  a random sample of the citizenry votes on the proposal. Depending on the outcome,  a second proposal to replace the status quo is added: This option is either closer  to or more distant from the status quo than the original proposal, depending on the voting outcome of the first stage. Then, in a second stage, the entire electorate  expresses by majority voting pairwise preferences over the status quo, the initial proposal, and the third option. The middle alternative is the default outcome in case  of cyclical collective preferences. We provide a theoretical foundation for the concept  of a "counter-proposal" and suggest how the Swiss system of direct democracy could  be improved. We examine the scope for Pendular Voting when there is uncertainty  about the distribution of the citizens’ preferences. We show that Pendular Voting engineers outcomes that are closer to the median voter’s preferred position than standard procedures. This also holds in expectation when initial agenda-setters are selfish.

Host:  Marcus Pivato

Abstract. Our work deals with one-to-one matchings where each agent must be assigned to exactly one element and agents have strict ordinal preferences over the elements to be matched with. We explore fair matchings by relaxing envy-freeness to account for justified envy based on the rank in the agents’ preferences. A rank-envy-free matching prevents that an agent prefers the match of another agent whereas she has ranked it better. We show that, while we can always efficiently construct a rank-envy-free matching in house allocation, i.e., when matching agents with objects, it is way more demanding in marriage or roommate settings, i.e., when matching agents with other agents. We study parameterizations of rank-envy-freeness, as well as natural relaxations of this concept. We also investigate the connections between this family of rank-based fairness criteria and known optimality or stability concepts.

Joint work with Khaled Belahcène, Baptistin Coutance, Vincent Mousseau, and Prasanna Maddila

Host: Marcus Pivato

Abstract. One often has to aggregate over two or more components: risk and time, commodities and persons, etc. In classical models the order of aggregation then does not matter. This leads to our first result: the prettiest axiomatization of discounted expected utility you ever saw. Paradox 1: this is too simple to be true? 

Modern behavioral generalizations relax classical complete separability but maintain weak separability (= Pareto optimality etc.). Paradox 2: for two or more components this weakening is just impossible. 

                                            ???? 

Further, one now crucially has to choose the order of aggregation. Million-$ question: which first? Many ongoing, seemingly unrelated, debates in different fields amount to this same million-$ question: ex-ante vs. ex-post fairness, equity in Harsanyi’s veil of ignorance, monotonicity in Anscombe-Aumann’s framework, incentive compatibility of random incentives, hedging in ambiguity measurements, etc. We show that a century-old forgotten theorem from macro-economics, Nataf (1948), can resolve all aforementioned paradoxes and debates in their various fields. 

(Joint work with Chen Li and Kirsten Rohde)

Host:  Danilo Coelho 

Abstract. In many organizations, members need to be assigned to certain positions, whether these are legislators to committees, executives to roles, or workers to teams. In such settings, the design of the assignment procedure becomes an institutional choice that is influenced and agreed upon by the very members being assigned. Will these agents seek to reform the assignment procedures by voting in favor of some alternative allocation over their current allocation? I explore this question of institutional stability by bringing together matching theory and social choice. I introduce majority stability---i.e., institutional stability under majority rule---and juxtapose it with other voting rules an organization might use to resolve internal conflict. Institutional stability is undermined by correlation across agents' preferences over positions, as the resulting envy enables a decisive coalition to arise endogenously to change the institution. For extremely correlated preferences, I establish a Chaos Theorem wherein there exists a majority-approved agenda from any matching allocation to any other allocation. Nevertheless, I show that institutions are robust to intermediate correlation across preferences under majority rule, in sharp contrast to plurality rule (i.e., popular matching, studied in computer science). Given the prevalence of (super-)majority rules in practice, this suggests why we observe institutional stability.

Host:  Marcus Pivato

Abstract. We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where decisions needs to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair---not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters' preferences. We formulate axioms of proportionality in this general model. Our axioms do not require predefining groups of voters; to the contrary, we ensure that the opinion of every subset of voters whose preferences are cohesive-enough are taken into account to the extent that is proportional to the size of the subset. Our axioms generalise the strongest known satisfiable axioms for the more specific models. We explain how to adapt two prominent committee election rules, Proportional Approval Voting (PAV) and Phragmén Sequential Rule, as well as the concept of stable-priceability to our general model. The two rules satisfy our proportionality axioms if and only if the feasibility constraints are matroids.