Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We study the fair allocation of mixture of indivisible goods and chores under lexicographic preferencesa subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envyfreeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with terrible chores, we show that determining the existence of an EFX allocation is NPcomplete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and Pareto optimal allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.more » « less

In fair division of indivisible goods, loutofd maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the l least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1outofn MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of loutoffloor((l+1/2)n) MMS allocations of goods for any integer l greater than or equal to 1, and present a polynomialtime algorithm that finds a 1outofceiling(3n/2) MMS allocation when l = 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any l > 1.more » « less

We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envyfreeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings).For matching indivisible items, we propose an adaptiveprioritybased algorithm, MATCHANDSHIFT, prove that it achieves (1/2)approximation of both class envyfreeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a waterfillingbased algorithm, EQUALFILLING, that achieves (11/e)approximation of class envyfreeness and class proportionality; we prove (11/e) to be tight for class proportionality and establish a 3/4 upper bound on class envyfreeness.more » « less

We study fair allocation of indivisible goods and chores among agents with lexicographic preferencesa subclass of additive valuations. In sharp contrast to the goodsonly setting, we show that an allocation satisfying envyfreeness up to any item (EFX) could fail to exist for a mixture of objective goods and chores. To our knowledge, this negative result provides the first counterexample for EFX over (any subdomain of) additive valuations. To complement this nonexistence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to maximin share (MMS), we show positive existence and computation for any mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as choresonly instances, and highlights the additional difficulty of these problems visàvis their goodsonly counterparts.more » « less

The classical house allocation problem involves assigning n houses (or items) to n agents according to their preferences. A key criteria in such problems is satisfying some fairness constraints such as envyfreeness. We consider a generalization of this problem wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of the envy value over all edges in a social graph. When agents have identical and evenlyspaced valuations, our problem reduces to the wellstudied problem of linear arrangements. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NPhardness results for disjoint unions of paths, cycles, stars, or cliques; we also obtain fixedparameter tractable (and, in some cases, polynomialtime) algorithms for paths, cycles, stars, cliques, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call separability which results in efficient parameterized algorithms for finding optimal allocations.more » « less

Strategic behavior in twosided matching markets has been traditionally studied in a onesided manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates twosided manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomialtime algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that twosided manipulations are more frequently available and offer better quality matches than their onesided counterparts.

In fair division of indivisible goods, ℓoutofd maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the ℓ least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1outofn MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of ℓoutof⌊(ℓ + 1/2)n⌋ MMS allocations of goods for any integer ℓ ≥ 1, and present a polynomialtime algorithm that finds a 1outof⌈3n/2⌉ MMS allocation when ℓ=1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any ℓ > 1.more » « less

We study the problem of fairly allocating a set of m indivisible chores (items with nonpositive value) to n agents. We consider the desirable fairness notion of 1outofd maximin share (MMS)the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundleand focus on ordinal approximation of MMS that aims at finding the largest dłeq n for which 1outofd MMS allocation exists. Our main contribution is a polynomialtime algorithm for 1outofł 2n/3 MMS allocation, and a proof of existence of 1outofłfloor 3n/4 MMS allocation of chores. Furthermore, we show how to use recentlydeveloped algorithms for binpacking to approximate the latter bound up to a logarithmic factor in polynomial time.more » « less

Stable matching models are widely used in market design, school admission, and donor organ exchange. The classic Deferred Acceptance (DA) algorithm guarantees a stable matching that is optimal for one side (say men) and pessimal for the other (say women). A sexequal stable matching aims at providing a fair solution to this problem. We demonstrate that under a class of correlated preferences, the DA algorithm either returns a sexequal solution or has a very low sexequality cost.more » « less