skip to main content

This content will become publicly available on September 13, 2024

Title: Competitive Equilibria with a Constant Number of Chores

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
Award ID(s):
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Journal of Artificial Intelligence Research
Date Published:
Journal Name:
Journal of Artificial Intelligence Research
Page Range / eLocation ID:
1201 to 1219
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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
  2. 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
  3. We study the problem of fair and efficient allocation of a set of indivisible chores to agents with additive cost functions. We consider the popular fairness notion of envy-freeness up to one good (EF1) with the efficiency notion of Pareto-optimality (PO). While it is known that EF1+PO allocations exists and can be computed in pseudo-polynomial time in the case of goods, the same problem is open for chores. Our first result is a strongly polynomial-time algorithm for computing an EF1+PO allocation for bivalued instances, where agents have (at most) two disutility values for the chores. To the best of our knowledge, this is the first non-trivial class of chores to admit an EF1+PO allocation and an efficient algorithm for its computation. We also study the problem of computing an envy-free (EF) and PO allocation for the case of divisible chores. While the existence of EF+PO allocation is known via competitive equilibrium with equal incomes, its efficient computation is open. Our second result shows that for bivalued instances, an EF+PO allocation can be computed in strongly polynomial-time. 
    more » « less
  4. We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly polynomial Duan–Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges—that is, pairs of agents and goods that must correspond to the best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges or, if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time. 
    more » « less
  5. We study fair division of indivisible chores among n agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to one/any item (EF1/EFX) and the standard notion of economic efficiency is Pareto optimality (PO). There is a noticeable gap between the results known for both EF1 and EFX in the goods and chores settings. The case of chores turns out to be much more challenging. We reduce this gap by providing slightly relaxed versions of the known results on goods for the chores setting. Interestingly, our algorithms run in polynomial time, unlike their analogous versions in the goods setting.We introduce the concept of k surplus in the chores setting which means that up to k more chores are allocated to the agents and each of them is a copy of an original chore. We present a polynomial-time algorithm which gives EF1 and PO allocations with n-1 surplus.We relax the notion of EFX slightly and define tEFX which requires that the envy from agent i to agent j is removed upon the transfer of any chore from the i's bundle to j's bundle. We give a polynomial-time algorithm that in the chores case for 3 agents returns an allocation which is either proportional or tEFX. Note that proportionality is a very strong criterion in the case of indivisible items, and hence both notions we guarantee are desirable.

    more » « less