This paper studies fair division of divisible and indivisible items among agents whose cardinal preferences are not necessarily monotone. We establish the existence of fair divisions and develop approximation algorithms to compute them. We address two complementary valuation classes, subadditive and nonnegative, which go beyond monotone functions. Considering both the division of cake (divisible resources) and allocation of indivisible items, we obtain fairness guarantees in terms of (approximate) envy-freeness (EF) and equability (EQ). In the context of envy-freeness, we prove that an EF division of a cake always exists under cake valuations that are subadditive and globally nonnegative (i.e., the value of the entire cake for every agent is nonnegative, but parts of the cake can be burnt). This result notably complements the nonexistence of EF allocations for burnt cakes known for more general valuations. For envy-freeness in the indivisible-items setting, we establish the existence of EFE3 allocations for subadditive and globally nonnegative valuations; again, such valuations can be non-monotone and can impart negative value to specific item subsets. In addition, we obtain universal existence of EFE3 allocations under nonnegative valuations. We study equitability under nonnegative valuations. Here, we prove that EQE3 allocations always exist when the agents’ valuations are nonnegative (and possibly non-monotone). Also, in the indivisible-items setting, we develop an approximation algorithm that, for given nonnegative valuations, finds allocations that are equitable within additive margins. Our results have combinatorial implications, which highlight the reach of the developed guarantees beyond fair division and even algorithmic game theory.

We consider the fundamental problem of allocating T indivisible items that arrive over time to n agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to the online multicolor discrepancy problem: vectors v1,...,vT ∈ ℝd with ||vi||2 ≤ 1 arrive online and must be, immediately and irrevocably, assigned to one of n colors to minimize [EQUATION] at each step, where Sℓ is the set of vectors having color ℓ. The special case of n = 2 is called online vector balancing. It is known that envy minimization reduces to multicolor discrepancy minimization. For an adaptive adversary, both problems have the same optimal bound: [EQUATION]; it is not known, however, whether this matches for weaker adversaries. Against an oblivious adversary, Alweiss et al. [2021] give a bound of O (log T), with high probability, for online multicolor discrepancy. Recently, Kulkarni et al. [2024] improve this to a tight [EQUATION] bound for online vector balancing. However, it has remained an open problem whether a [EQUATION] bound is possible for multicolor discrepancy. Furthermore, these results imply the state-of-the-art upper bounds for online envy minimization (for an oblivious adversary) for n and two agents, respectively; it is open whether better bounds are possible. We resolve all the aforementioned open problems. We establish that online envy minimization is, in fact, equivalent to online multicolor discrepancy for oblivious adversary: we give an [EQUATION] bound, for multicolor discrepancy, and a lower bound of [EQUATION] for envy minimization, resolving both problems. For weaker adversaries we prove that the two problems are no longer equivalent. Against an i.i.d. adversary, for online vector balancing, we give a [EQUATION] lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. Full version: https://arxiv.org/abs/2502.14624.

We study the problem of fairly allocating m indivisible items among n agents. Envy-free allocations, in which each agent prefers her bundle to the bundle of every other agent, need not exist in the worst case. However when agents have additive preferences and the value By of agent i for item j is drawn independently from a distribution Di, envy-free allocations exist with high probability when m ∈ Ω(n log n/log log n).

Allocating items in a fair and economically efficient manner is a central problem in fair division. We study this problem for agents with additive preferences, when items are all goods or all chores, divisible or indivisible. The celebrated notion of Nash welfare is known to produce fair and efficient allocations for both divisible and indivisible goods; there is no known analogue for dividing chores. The Nash welfare objective belongs to a large, parameterized family of objectives called the p-mean welfare functions, which includes other notable members, like social welfare and egalitarian welfare. However, among the members of this family, only the Nash welfare produces fair allocations for goods. Incidentally, Nash welfare is also the only member that satisfies the axiom of scale invariance, which is crucially associated with its fairness properties.

Food waste and food insecurity are two closely related pressing global issues. Food rescue organizations worldwide run programs aimed at addressing the two problems. In this paper, we partner with a non-profit organization in the state of Indiana that leads Food Drop, a program that is designed to redirect rejected truckloads of food away from landfills and into food banks. The truckload to food bank matching decisions are currently made by an employee of our partner organization. In addition to this being a very time-consuming task, as perhaps expected from human-based matching decisions, the allocations are often skewed: a small percentage of the possible recipients receives the majority of donations. Our goal in this partnership is to completely automate Food Drop. In doing so, we need a matching algorithm for making real-time decisions that strikes a balance between ensuring fairness for the food banks that receive the food and optimizing efficiency for the truck drivers. In this paper, we describe the theoretical guarantees and experiments that dictated our choice of algorithm in the platform we built and deployed for our partner organization. We develop a new model for dynamic fair division with two-sided preferences. There is an undirected, weighted graph, whose nodes represent counties, a subset of which have food banks that can receive donations, edge weights represent distance, and node weights represent the food-insecure population. Drivers appear over time, one in each step, and need to be matched, immediately and irrevocably, to a food bank. Drivers have a random origin node, a random final destination node, and a donation of random value. Our goal is to balance driver efficiency (drivers should not have to drive a lot) with fairness (every food bank should receive value proportionately to the food-insecure individuals it serves). We give matching upper and lower bounds that completely characterize this trade-off. Our work also makes contributions to the literature on load balancing and balls-into-bins games, that might be of independent interest. Specifically, we study the allocation of m weighted balls into n weighted bins, where each ball has two non-uniformly sampled random bin choices, and prove upper bounds, that hold with high probability, on the maximum load of any bin.

Underserved communities face critical health challenges due to lack of access to timely and reliable information. Nongovernmental organizations are leveraging the widespread use of cellphones to combat these healthcare challenges and spread preventative awareness. The health workers at these organizations reach out individually to beneficiaries; however such programs still suffer from declining engagement. We have deployed SAHELI, a system to efficiently utilize the limited availability of health workers for improving maternal and child health in India. SAHELI uses the Restless Multiarmed Bandit (RMAB) framework to identify beneficiaries for outreach. It is the first deployed application for RMABs in public health, and is already in continuous use by our partner NGO, ARMMAN. We have already reached ~100K beneficiaries with SAHELI, and are on track to serve 1 million beneficiaries by the end of 2023. This scale and impact has been achieved through multiple innovations in the RMAB model and its development, in preparation of real world data, and in deployment practices; and through careful consideration of responsible AI practices. Specifically, in this paper, we describe our approach to learn from past data to improve the performance of SAHELI’s RMAB model, the real-world challenges faced during deployment and adoption of SAHELI, and the end-to-end pipeline.

We consider the problem of a revenue-maximizing seller with a large number of items $m$ for sale to $n$ strategic bidders, whose valuations are drawn independently from high-dimensional, unknown prior distributions. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute, and, even when they can be found, are often rife with various counter-intuitive properties. In this paper, following a model introduced recently by Cai and Daskalakis [CD22], we consider the case that bidders' prior distributions can be well-approximated by a topic model. We design an active learning component, responsible for interacting with the bidders and outputting low-dimensional approximations of their types, and a mechanism design component, responsible for robustifying mechanisms for the low-dimensional model to work for the approximate types of the former component. On the active learning front, we cast our problem in the framework of Randomized Linear Algebra (RLA) for regression problems, allowing us to import several breakthrough results from that line of research, and adapt them to our setting. On the mechanism design front, we remove many restrictive assumptions of prior work on the type of access needed to the underlying distributions and the associated mechanisms. To the best of our knowledge, our work is the first to formulate connections between mechanism design, and RLA for active learning of regression problems, opening the door for further applications of randomized linear algebra primitives to mechanism design.

We study the problem of allocating indivisible goods among strategic agents. We focus on settings wherein monetary transfers are not available and each agent's private valuation is a submodular function with binary marginals, i.e., the agents' valuations are matroid-rank functions. In this setup, we establish a notable dichotomy between two of the most well-studied fairness notions in discrete fair division; specifically, between envy-freeness up to one good (EF1) and maximin shares (MMS). First, we show that a known Pareto-efficient mechanism is group strategy-proof for finding EF1 allocations, under matroid-rank valuations. The group strategy-proofness guarantee strengthens an existing result that establishes truthfulness (individually for each agent) in the same context. Our result also generalizes prior work from binary additive valuations to the matroid-rank case. Next, we establish that an analogous positive result cannot be achieved for MMS, even when considering truthfulness on an individual level. Specifically, we prove that, for matroid-rank valuations, there does not exist a truthful mechanism that is index oblivious, Pareto efficient, and maximin fair. For establishing our results, we develop a characterization of truthful mechanisms for matroid-rank functions. This characterization in fact holds for a broader class of valuations (specifically, holds for binary XOS functions) and might be of independent interest.

We consider the fundamental problem of allocating a set of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the absence of monetary transfers, Pareto efficient and truthful rules are dictatorial, while there is no deterministic truthful mechanism that allocates all items and achieves envy-freeness up to one item (EF1), even for the case of two agents. In this paper, we investigate the interplay of fairness and efficiency under a relaxation of truthfulness called non-obvious manipulability (NOM), recently proposed by~\citep{troyan2020obvious}. We show that this relaxation allows us to bypass the aforementioned negative results in a very strong sense. Specifically, we prove that there are deterministic and EF1 algorithms that are not obviously manipulable, and the algorithm that maximizes utilitarian social welfare (the sum of agents' utilities), which is Pareto efficient but not dictatorial, is not obviously manipulable for $n \geq 3$ agents (but obviously manipulable for $n=2$ agents). At the same time, maximizing the egalitarian social welfare (the minimum of agents' utilities) or the Nash social welfare (the product of agents' utilities) is obviously manipulable for any number of agents and items. Our main result is an approximation preserving black-box reduction from the problem of designing EF1 and NOM mechanisms to the problem of designing EF1 algorithms. En route, we prove an interesting structural result about EF1 allocations, as well as new ``best-of-both-worlds'' results (for the problem without incentives), that might be of independent interest.