An official website of the United States government
We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads (chores) that everyone dislikes as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. argues why allocating a mixed manna is genuinely more complicated than a good or a bad manna and why competitive equilibrium is the best mechanism. It also provides the existence of equilibrium and establishes its distinctive properties (e.g., nonconvex and disconnected set of equilibria even under linear utilities) but leaves the problem of computing an equilibrium open. Our main results are a linear complementarity problem formulation that captures all competitive equilibria of a mixed manna under SPLC utilities (a strict generalization of linear) and a complementary pivot algorithm based on Lemke’s scheme for finding one. Experimental results on randomly generated instances suggest that our algorithm is fast in practice. Given the [Formula: see text]-hardness of the problem, designing such an algorithm is the only non–brute force (nonenumerative) option known; for example, the classic Lemke–Howson algorithm for computing a Nash equilibrium in a two-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in [Formula: see text], a rational-valued solution, and an odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative. Furthermore, we show that, if the number of either agents or items is a constant, then the number of pivots in our algorithm is strongly polynomial when the mixed manna contains all bads.
more »
« less
Computing Competitive Equilibria with Mixed Manna
Fair division is the problem of allocating a set of items among a set of agents in a fair and efficient way. It arises naturally in a wide range of real-life settings. Competitive equilibrium (CE) is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties (e.g., envy-freeness, proportionality, core stability, Pareto optimality), it is also one of the most preferred mechanisms for fair division even though there is no money involved. The vast majority of work in fair division focuses on the case of disposable goods, which all agents like or can throw away at no cost. In this paper, we consider the case of mixed manna under linear utilities where some items are positive goods liked by all agents, some are bads (chores) that no one likes, and remaining some agents like and others dislike. The recent work of Bogomolnaia et al. [13] initiated the study of CE in mixed manna. They establish that a CE always exists and maintains all the nice properties found in the case of all goods. However, computing a CE of mixed manna is genuinely harder than in the case of all goods due to the nonconvex and disconnected nature of the CE set. Our main result is a polynomial-time algorithm for computing a CE of mixed manna when the number of agents or items is constant.
more »
« less
- Award ID(s):
- 1942321
- PAR ID:
- 10156571
- Date Published:
- Journal Name:
- AAMAS Conference proceedings
- ISSN:
- 2523-5699
- Page Range / eLocation ID:
- 420-428
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities and chores, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities and mixed manna. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.more » « less
-
Vorobeychik, Y; Das, S; Nowe, A (Ed.)We study the problem of fair allocation of indivisible items when agents have ternary additive valuations --- each agent values each item at some fixed integer values a, b, or c that are common to all agents. The notions of fairness we consider are max Nash welfare (MNW), when a, b, and c are non-negative, and max egalitarian welfare (MEW). We show that for any distinct non-negative a, b, and c, maximizing Nash welfare is APX-hard --- i.e., the problem does not admit a PTAS unless P = NP. We also show that for any distinct a, b, and c, maximizing egalitarian welfare is APX-hard except for a few cases when b = 0 that admit efficient algorithms. These results make significant progress towards completely characterizing the complexity of computing exact MNW allocations and MEW allocations. En route, we resolve open questions left by prior work regarding the complexity of computing MNW allocations under bivalued valuations, and MEW allocations under ternary mixed manna.more » « less
-
We study fair allocation of indivisible goods and chores among agents with lexicographic preferences---a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying envy-freeness 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 non-existence 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 chores-only instances, and highlights the additional difficulty of these problems vis-à-vis their goods-only counterparts.more » « less
-
We study fair resource allocation with strategic agents. It is well-known that, across multiple fundamental problems in this domain, truthfulness and fairness are incompatible. For example, when allocating indivisible goods, no truthful and deterministic mechanism can guarantee envy-freeness up to one item (EF1), even for two agents with additive valuations. Or, in cake-cutting, no truthful and deterministic mechanism always outputs a proportional allocation, even for two agents with piecewise constant valuations. Our work stems from the observation that, in the context of fair division, truthfulness is used as a synonym for Dominant Strategy Incentive Compatibility (DSIC), requiring that an agent prefers reporting the truth, no matter what other agents report.In this paper, we instead focus on Bayesian Incentive Compatible (BIC) mechanisms, requiring that agents are better off reporting the truth in expectation over other agents' reports. We prove that, when agents know a bit less about each other, a lot more is possible: using BIC mechanisms we can achieve fairness notions that are unattainable by DSIC mechanisms in both the fundamental problems of allocation of indivisible goods and cake-cutting. We prove that this is the case even for an arbitrary number of agents, as long as the agents' priors about each others' types satisfy a neutrality condition. Notably, for the case of indivisible goods, we significantly strengthen the state-of-the-art negative result for efficient DSIC mechanisms, while also highlighting the limitations of BIC mechanisms, by showing that a very general class of welfare objectives is incompatible with Bayesian Incentive Compatibility. Combined, these results give a near-complete picture of the power and limitations of BIC and DSIC mechanisms for the problem of allocating indivisible goods.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
