Accepted Papers

We consider a novel setting where a set of items are matched to the same set of agents repeatedly over multiple rounds. Each agent gets exactly one item per round, which brings interesting challenges to finding efficient and/or fair {\em repeated matchings}. A particular feature of our model is that the value of an agent for an item in some round depends on the number of rounds in which the item has been used by the agent in the past. We present a set of positive and negative results about the efficiency and fairness of repeated matchings. For example, when items are goods, a variation of the well-studied fairness notion of envy-freeness up to one good (EF1) can be satisfied under certain conditions. Furthermore, it is intractable to achieve fairness and (approximate) efficiency simultaneously, even though they are achievable separately. For mixed items, which can be goods for some agents and chores for others, we propose and study a new notion of fairness that we call {\em swap envy-freeness} (swapEF).

In approximate mechanism design, the “classic setting” for facility location problems considers strategy proof mechanisms that approximate well the optimal total or maximum distance of agents from the nearest facility. Performance is typically characterized by the maximum approximation ratio. This focuses on problems with high quality solutions where distances are small, and may overlook more challenging problems with low quality solutions where some of the distances are necessarily large. By considering instead egalitarian welfare, we uncover a richer space of well behaved mechanisms. With deterministic mechanisms, for example, we show that the MIDORNEAREST mechanism matches the optimal approximation ratio of the MEDIAN mechanism for the objective of maximum distance, but offers a better and optimal approximation ratio for the objective of the minimum utility. By comparison, the MEDIAN mechanism has an unbounded approximation ratio of the optimal minimum utility. For a single facility, our results are tight, giving upper and lower bounds on approximation ratios that match with both deterministic and randomized mechanisms. For multiple facilities, our results are asymptotically tight, giving upper and lower bounds that are within a constant factor. With randomized mechanisms, we construct the first mechanism that, on a wide range of non-extreme problems, is optimal with respect to optimizing both the maximum distance and the minimum utility. Our results uncover a much richer landscape of strategy proof mechanisms returning good approximate egalitarian solutions.

We study the classic problem of fairly allocating a divisible resource modeled as a line segment $[0,1]$ and referred to as a cake. An important question in the area of fair division is to find a tractable algorithm to compute envy-free cake division. In this work, we consider  an interesting variant of the problem where agents are embedded in a graph whose edges describe the relationships between agents, and each agent evaluates her  share relative to those of her neighbors. Given a graph, the goal is to find a locally envy-free allocation where every agent values her share of the cake  to be at least as much as that of any of her neighbors' share. 

 We develop a novel protocol that finds locally envy-free allocations among $n$ agents on any tree graph using at most $O(n^{2n})$ queries under the standard Robertson-Webb (RW) query model. Our protocol has a query complexity of only a single exponential for tree graphs,  significantly smaller than the six-towers-of-$n$ query complexity of the envy-free protocol given by \cite{aziz2016discrete}.  We further show that if the underlying tree graph has a depth of at most two, a locally envy-free allocation can be computed using $O(n^4 \log n)$ RW queries. We believe that the machinery developed in this work provides new insights for understanding the computational bottleneck for finding envy-free cake divisions.

We study the sequential decision-making problem of allocating a divisible resource to agents that reveal their stochastic demands on arrival over a finite horizon. Our goal is to design fair allocation algorithms that exhaust the available resource budget. 

This is challenging in sequential settings where information on future demands is not available at the time of decision-making. We formulate the problem as a discrete time Markov decision process (MDP). We propose a new algorithm, SAFFE, that makes fair allocations with respect to all  demands revealed over the horizon by accounting for expected future demands at each arrival time. Using the MDP formulation, we show that the allocation made by SAFFE optimizes an upper bound of the Nash Social Welfare fairness objective. We further introduce SAFFE-D, which improves SAFFE by more carefully balancing the trade-off between the current revealed demands and the future potential demands based on the uncertainty in agents' future demands. We bound its gap to optimality using concentration bounds on total future demands. On synthetic and real data, we compare SAFFE-D against a set of baseline approaches, and show that it leads to more fair and efficient allocations and achieves close-to-optimal performance. 

Fair distribution of indivisible tasks with non-positive valuations (aka chores) has given rise to a large body of work in recent years. A popular approximate fairness notion is envy-freeness up to one item EF1, which requires that any pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods always exists and can be computed via several well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach utilizing information asymmetry by introducing dubious chores -- items that inflict no cost on receiving agents, but are perceived costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envy-freeness---compared to relaxations such as EF1---which enables progress towards addressing open problems on the existence and computation of EF1 and PO. In particular, we show that finding allocations with optimal number of dubious chores is computationally hard even for highly restricted classes of valuations. Nonetheless, we prove the existence of envy-free and PO allocations for $n$ agents with only $2n-2$ dubious chores and strengthen it to $n-1$ dubious chores in four special classes of valuations. Our experimental analysis demonstrate that baseline algorithms only require a relatively small number of dubious chores to achieve envy-freeness in practice.

Fair division provides a rich computational and mathematical framework for the allocation of indivisible goods, which has given rise to numerous fairness concepts and their relaxations. In recent years, much attention has been given to theoretical and computational aspects of various fairness concepts. Nonetheless, the choice of which fairness concept is in practice perceived to be fairer by individuals is not well understood. We consider two conceptually different relaxations of envy-freeness and investigate how individuals perceive the induced allocations as fair. In particular, we examine a well-studied relaxation of envy-freeness up to one good (EF1) which is based on counterfactual thinking that any pairwise envy can be eliminated by the hypothetical removal of a single good from the envied agent's bundle. In contrast, a recently proposed epistemic notion, namely envy-freeness up to $k$ hidden goods (HEF-k), provides a relaxation by hiding information about a small subset of $k$ goods. Through various crowdsourcing experiments, we empirically demonstrate that allocations achieved by withholding information are perceived to be fairer compared to two variants of EF1.

Kidney exchange programs (KEPs) typically seek to match incompatible patient-donor pairs based on a utilitarian objective where the number or overall quality of transplants is maximized---implicitly penalizing certain classes of difficult-to-match (e.g., highly-sensitized) patients. Prioritizing the welfare of highly-sensitized (hard-to-match) patients has been studied in several previous works \cite{Roth05:Pairwise,mcelfresh2018balancing,farnadi2021individual} as a natural \textit{fairness} criterion. 

We formulate the KEP problem as $k$-set packing (inspired from the works of \cite{biro2009maximum,lin2019randomized}) with a probabilistic group fairness notion of proportionality fairness---namely, fair $k$-set packing (\f{}). In this work we propose algorithms that take arbitrary proportionality vectors (i.e., policy-informed demands of how to prioritize different groups) and return a probabilistically fair solution with provable guarantees. Our main contributions are randomized algorithms as well as hardness results for \f{} variants. Additionally, the tools we introduce serve to audit the price of fairness involved in prioritizing different groups in realistic KEPs and other $k$-set packing applications. We conclude with experiments on synthetic and realistic kidney exchange \textsc{FairSP} instances.

We initiate the study of fair distribution of delivery tasks among a set of agents wherein delivery jobs are placed along the vertices of a graph.

Our goal is to fairly distribute delivery costs (modeled as a submodular function) among a fixed set of agents while satisfying some desirable notions of economic efficiency. We adopt well-established fairness concepts—such as envy-freeness up to one item (EF1) and minimax share (MMS)—to our setting and show that fairness is often incompatible with the efficiency notion of social optimality. Yet, we characterize instances that admit fair and socially optimal solutions by exploiting graph structures. We further show that achieving fairness along with Pareto optimality is computationally intractable. Nonetheless, we design an XP algorithm (parameterized by the number of agents) for finding MMS and Pareto optimal solutions on every instance, and show that the same algorithm can be modified to find efficient solutions along with EF1, when such solutions exist. We complement our theoretical results by experimentally analyzing the price of fairness on randomly generated graph structures.

We consider the problem of fairly allocating courses to students where each student is only interested in a subset of the courses and each resource can only be assigned to a bounded number of agents. In addition, each course corresponds to an interval of time, and the objective is to assign non-overlapping courses to students so as to produce ``fair and high utility'' assignments. 

In this paper, we investigate various objective functions, fairness definitions, and preference types. Specifically, we consider \textit{total utility}, \textit{max-min} (Santa Claus objective), and various versions of \textit{envy-freeness}. The total utility objective function maximizes the sum of the utilities of all courses assigned to students. The max-min objective maximizes the minimum utility obtained by any student. Finally, envy-freeness ensures that no student envies another student's allocation. We establish that the course allocation under the time conflicts problem is NP-complete in general, but under specific settings, there exist exact/approximate polynomial time algorithms. For settings with binary valuations, we provide three polynomial time algorithms to obtain $1/2$-approximate total utility, envy-freeness up to one item, and a constant approximate max-min, respectively. Finally, the experimental results demonstrate that our algorithms yield high-quality results in real-world settings.

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 being 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.

We study the one-sided matching problem where there are m items and n agents who are partitioned into disjoint classes. Each class needs to receive a fair treatment in a desired matching. This model, recently proposed by Benabbou et al. (IJCAI-2019) and Hosseini et al. (AAAI-2023), captures a plethora of real-life examples, such as the allocation of public housing across different ethnic groups and the allocation of medical resources across different age groups. The main interest has been to achieve class envy-free matchings, demanding that each class receive the total utility greater or equal to the maximum value of a matching they would achieve from the items matched to another class. Unfortunately, it is impossible to achieve class envy-freeness for worst case utilities without allowing us to waste items. To analyze whether a class envy-free matching exists in practice, we consider a distributional model where the agents' utilities for the items are drawn from a probability distribution. Our main result is the asymptotic existence of class envy-free and non-wasteful matchings when the number of all agents goes to infinity. To this end, we design a round-robin style algorithm and prove that it produces a desirable matching with high probability.