Erel Segal-Halevi

We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof, and fair. Most previous work assumes that agents evaluate budgets according to the [ ] distance to their ideal budget. We investigate and compare different models from the larger class of star-shaped utility functions—a multidimensional generalization of single-peaked preferences. For the case of two alternatives, we extend existing results by proving that under very general assumptions, the uniform phantom mechanism is the only strategyproof mechanism that satisfies proportionality—a minimal notion of fairness introduced in prior work. Moving to the case of more than two alternatives, we establish sweeping impossibilities for [ ] and [ ] disutilities: no mechanism satisfies efficiency, strategyproofness, and proportionality. We then propose a new kind of star-shaped utility based on evaluating budgets by the ratios of shares between a given budget and an ideal budget. For these utilities, efficiency, strategyproofness, and fairness become compatible. In particular, we prove that the mechanism that maximizes the Nash product of individual utilities is characterized by group-strategyproofness and a core-based fairness condition. History: This manuscript was accepted for the Special Issue on Mathematics of Market Design. Funding: This work was supported by the Israel Science Foundation [Grants 712/20 and 1092/24], Singapore Ministry of Education [Grant MOE-T2EP20221-0001], Deutsche Forschungsgemeinschaft [Grants BR 2312/11-2 and BR 2312/12-1], and an NUS start-up grant.

When an old apartment building is demolished and rebuilt, how can we fairly redistribute the new apartments to minimize envy among residents? We reduce this question to a combinatorial optimization problem called the *Min Max Average Cycle Weight* problem. In that problem we seek to assign objects to agents in a way that minimizes the maximum average weight of directed cycles in an associated envy graph. While this problem reduces to maximum-weight matching when starting from a clean slate (achieving polynomial-time solvability), we show that this is not the case when we account for preexisting conditions, such as residents' satisfaction with their original apartments. Whether the problem is polynomial-time solvable in the general case remains an intriguing open problem.

We study fair division of indivisible chores among n agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more than two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exist. We show the existence of · 1-out-of-9n/11 MMS allocations, which improves the state-of-the-art factor of 1-out-of-3n/4. · MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021). · 15/13-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of 13/11. We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a 15/13-MMS allocation for personalized bivalued instances.

Two prominent objectives in social choice are utilitarian - maximizing the sum of agents' utilities, and leximin - maximizing the smallest agent's utility, then the second-smallest, etc. Utilitarianism is typically computationally easier to attain but is generally viewed as less fair. This paper presents a general reduction scheme that, given a utilitarian solver, produces a distribution over states (deterministic outcomes) that is leximin in expectation. Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces a lottery that is approximately-leximin (in expectation) - with the same approximation factor. We apply our scheme to several social choice problems: stochastic allocations of indivisible goods, giveaway lotteries, and fair lotteries for participatory budgeting.

We consider the classical cake cutting problem where we wish to fairly divide a heterogeneous resource among interested agents. Work on this subject typically assumes that the cake is represented by an interval. We introduce a generalized setting where the cake is represented by an arbitrary undirected graph, which allows us to model the division of road networks. Unlike in the interval setting, common fairness criteria such as proportionality cannot always be satisfied in graphical cake cutting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with additive valuations, and exhibit a tight guarantee for each graph in the case of two agents. We also study several variants and extensions, including when more than one connected piece per agent is allowed as well as when the item to be divided is undesirable.

We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize the existence of a connected strongly-proportional allocation—one in which every agent receives a contiguous piece worth strictly more than their proportional share. The characterization is supplemented with an algorithm that determines its existence using O(n·2n) queries. We devise a simpler characterization for agents with strictly positive valuations and with equal entitlements, and present an algorithm to determine the existence of such an allocation using O(n2) queries. We provide matching lower bounds in the number of queries for both algorithms. When a connected strongly-proportional allocation exists, we show that it can also be computed using a similar number of queries. The full version is available at https://arxiv.org/abs/2312.15326.