2024 Past Seminars

Host: Marcus Pivato

Abstract. Charity is typically carried out by individual donors, who donate money to charities they support, or by centralized organizations such as governments or municipalities, which collect individual contributions and distribute them among a set of charities. Individual charity respects the will of the donors, but may be inefficient due to a lack of coordination; centralized charity is potentially more efficient, but may ignore the will of individual donors. We present a mechanism that combines the advantages of both methods for donors with Leontief preferences (i.e., each donor seeks to maximize an individually weighted minimum of all contributions across the charities). The mechanism distributes the contribution of each donor efficiently such that no subset of donors has an incentive to redistribute their donations. Moreover, it is group-strategyproof, satisfies desirable monotonicity properties, maximizes Nash welfare, can be computed efficiently via convex programming, and can be attained by natural best-response spending dynamics.

(Joint work with Matthias Greger, Erel Segal-Halevi, and Warut Suksompong.)

Host: Jobst Heitzig 

Abstract. Whether independent agents can share a resource fairly, and how to do it, is an important and easily understood social choice problem. Among the criteria that have been proposed for a good allocation are maximum total utility, identified with utilitarianism, and maximum Nash utility, the basis of Nash bargaining. The Rawlsian idea of maximizing the minimum utility of any agent is also applicable. Yet another criterion is envy-freeness: one agent envies another if it prefers the other’s assignment to its own; in an envy-free allocation, no agent envies any other.

This presentation assumes a finite set of indivisible items, over which each of two players has known preferences. Preference is measured on a cardinal scale and is additive in that each player’s utility for any bundle of items is the sum of its utilities for the specific items in the bundle.

It is known that an envy-free allocation exists if and only if some maximin allocation gives each player at least half of the total utility in its own measure. Moreover, when this condition fails – so that no envy-free allocation exists – there is always an allocation with the related property called EFx. The focus here is on the existence of envy-freeness and its relation to efficiency-related properties such as maximum utility sum and maximum Nash product. After a formal study of what is possible, a comprehensive simulation is conducted to measure the frequencies of the various possibilities.

The objective of this study is to identify properties of allocation problems that can potentially simplify the task of fair allocation, demonstrate their existence and relationships, and assess how difficult they are to use in simulations.

(Joint work with Rudolf Vetschera, Steven Brams, Christian Klamler, and Fan Wei.)

Host: Marcus Pivato

Abstract. This paper develops and defends a new approach to belief aggregation, involving confidence in beliefs. It is characterised by a variant of the Pareto condition that enjoins respecting consensuses borne of compromise. Confidence aggregation recoups standard probability aggregation rules, such as linear pooling, as special cases, whilst avoiding the spurious unanimity issues that have plagued such rules. Moreover, it generates a new family of probability aggregation rules that can faithfully accommodate within-person expertise diversity, hence resolving a longstanding challenge. Confidence aggregation also outperforms linear aggregation: the group beliefs it provides are closer to the truth, in expectation. Finally, confidence aggregation is dynamically rational: it commutes with update.

Host: Marcus Pivato

Abstract. When selecting a subset of candidates (a so-called committee) based on the preferences of voters, proportional representation is often a major desideratum. When going beyond simplistic models such as party-list or district-based elections, it is surprisingly challenging to capture proportionality formally. As a consequence, the literature has produced numerous competing criteria of when a selected committee qualifies as proportional. Two of the most prominent notions are Dummett's proportionality for solid coalitions (PSC) and Aziz et al.'s extended justified representation (EJR). Both definitions guarantee proportional representation to groups of voters who have very similar preferences; such groups are referred to as solid coalitions by Dummett and as cohesive groups by Aziz et al. However, these notions lose their bite when groups are only almost solid or almost cohesive. In this paper, we propose proportionality axioms that are more robust than their existing counterparts, in the sense that they guarantee representation also to groups that do not qualify as solid or cohesive. Importantly, we show that these stronger proportionality requirements are always satisfiable. Another important advantage of our novel axioms is that their satisfaction can be easily verified: Given a committee, we can check in polynomial time whether it satisfies the axiom or not. This is in contrast to many established notions like EJR, for which the corresponding verification problem is known to be intractable.

In the setting with approval preferences, we propose a robust and verifiable variant of EJR and a simple greedy procedure to compute committees satisfying it. We show that our axiom is considerably more discriminating in randomly generated instances compared to EJR and other existing axioms. In the setting with ranked preferences, we propose a robust variant of Dummett's PSC. In contrast to earlier strengthenings of PSC, our axiom can be efficiently verified even for general weak preferences. In the special case of strict preferences, our notion is the first known satisfiable proportionality axiom that is violated by the Single Tranferable Vote (STV). In order to prove that our axiom can always be satisfied, we extend the notion of priceability to the ranked preferences setting. We also discuss implications of our results for participatory budgeting, querying procedures, and to the notion of proportionality degree.

Joint work with Jannik Peters (TU Berlin).

Host: Danilo Coelho

Abstract. (Pierre Bardier) In the theory of economic design and voting, incompatibilities between axioms have given rise to a myriad of notions of the degree to which a given axiom is satisfied. However, these are, generally, model-and-axiom-specific. In contrast, this paper explores the potential of defining such a notion as the probability with which an axiom, as well as a set of axioms, is satisfied, without restricting the analysis to particular types of properties or problems. 

The formal framework we provide is consistent with the use of simulation models, which aim at assessing the empirical performance of rules but focus, in general, on a single axiom, of a particular type.

We then propose and axiomatize a criterion to evaluate and compare the performance of rules given a set of axioms, based on two key components: the probabilities of satisfaction and the normative desirability of axioms, and, crucially, that of their combinations. Finally, we propose and axiomatize a criterion to measure axioms' compatibility between each other for a given rule, building on an analogy with cooperative game theory.

Abstract. (Rajarshi Ghosh) We propose a new voting mechanism in which voters simultaneously report their von Neumann-Morgenstern (vNM) utility functions across multiple decision problems, each of which has a finite number of alternatives. Each voter must report a real-valued “valuation” for each alternative of each decision. Each voter’s valuation vector is rescaled to have unit magnitude (where this magnitude is measured using a specially constructed quadratic form). We show that it is a dominant strategy for each voter to reveal her true vNM utility function. With very high probability, the mechanism selects the alternative that maximizes a weighted utilitarian social welfare function. The mechanism does not use money, and does not assume quasilinear utilities.

(Joint work with Marcus Pivato)

Host: Danilo Coelho

Abstract. The incompatibility between stability and strategyproofness in stable matching markets has given rise to a variety of “one-sided” manipulation studies where misreporting agents are also the intended beneficiaries. In this talk, I will introduce a novel “two-sided” manipulation framework wherein the misreporting agent(s) and the beneficiary may be on different sides of the market. In particular, I will describe two-sided manipulation strategies in the following variations: (i) accomplice manipulation, with a misreporting agent (say, an accomplice man) and a single beneficiary (say, a woman); (ii) one-for-all manipulation, with the misreporting agent (man) and multiple beneficiaries (all women); and (iii) two-for-one manipulation, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman). I will discuss several structural results on optimal manipulation strategies, their consequences in designing manipulation algorithms, and the conditions under which the stability of the resulting matchings is preserved.

Host: TBA

Abstract. In this talk I will describe some recent progress in computational fair division of indivisible items, when agents have submodular valuations. We will start with the setting where agents with matroid rank valuations -- every good provides a marginal value of 0 or 1 when added to a bundle and valuations are submodular. We will describe the Yankee Swap algorithm, a simple framework that can efficiently compute allocations that maximize any justice criterion (or fairness objective) satisfying some mild assumptions. Yankee Swap is guaranteed to maximize utilitarian social welfare, ensure strategyproofness and use at most a quadratic number of valuation queries. We will discuss how the framework can be generalized to settings where agents have bivalued submodular utilities, as well as settings with mixed manna. Finally, we will describe some recent hardness of approximation results when agents have more than two possible marginal gains.

Relevant papers:

• Fitzsimmons, Viswanathan and Zick "On the Hardness of Fair Allocation Under Ternary Valuations", 2024, in preparation.

• Viswanathan and Zick "A General Framework for Fair Allocation under Matroid Rank Valuations", EC 2023

• Cousins, Viswanathan and Zick "Dividing Good and Great Items Among Agents with Bivalued Submodular Valuations", WINE 2023

• Cousins, Viswanathan and Zick "The good, the bad and the submodular: Fairly allocating mixed manna under order-neutral submodular preferences", WINE 2023