We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of 4-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of 2-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) 2-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) 4-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.

We study the problem of fairly allocating a set of m goods among n agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint distribution. Prior works have shown that if this distribution is well-behaved, then an envy-free allocation exists with high probability when m=Ω(n log n). Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, it is known that this requirement improves to m=Ω(n log n / log log n), which is tight. However, these results rely on non-strategyproof mechanisms, such as maximum-welfare allocation or the round-robin algorithm, limiting their applicability in settings with strategic agents. In this work, we extend the theory to a broader, more realistic class of joint value distributions, allowing for correlations among agents, atomicity, and unequal probabilities of having the highest value for an item. We show that envy-free allocations continue to exist with a high probability when m=Ω(n log n). More importantly, we give a new randomized mechanism that is truthful in expectation, efficiently implementable in polynomial time, and outputs envy-free allocations with high probability, answering an open question from the literature. We further extend our mechanism to settings with asymptotic weighted fair division and multiple agent types and good types, proving new results in each case.

Data powers almost everything we experience on the web today---from the recommendations and ads we see to the AI systems and online marketplaces that shape our digital interactions. The increasing demand for high-quality data has given rise to platforms that facilitate the buying and selling of data. A key practical challenge in such markets is determining how to price data. Competitive equilibrium (CE), a foundational concept in classical market economics, determines prices for rivalrous goods by matching their supply and demand. In this work, we initiate the study of CE in data markets, explicitly incorporating the role of data in improving predictive performance in buyers' utility functions, and the non-rival nature of data by adapting the standard market-clearing condition to allow the simultaneous allocation of data records to multiple buyers. We analyze the existence, structure, and computation of CE in such data markets. We establish that CE always exists, and almost all instances admit a unique and rational equilibrium price vector. In general, however, there could be a non-convex set of prices, which rules out convex-programming approaches for finding a CE. Despite these challenges, we design an FPTAS for computing approximate equilibria using a Walrasian-style price adjustment algorithm. Our framework opens avenues for studying richer buyer utilities under correlated data sellers, and deeper structural and algorithmic aspects of data markets.

For any ɛ > 0, we give a simple, deterministic (4+ɛ)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an e(ω + 2 + ɛ)-approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 1/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both 1/2-EFX and an (8+ɛ)-approximation to the symmetric NSW problem under submodular valuations.

We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the egalitarian social cost in the fair division of chores. The two prevalent fairness notions in the fair division literature are envy-freeness and proportionality. Prior work has established that no envy-free mechanism can provide better than an Ω(log m / log log m)-approximation to the optimal makespan, where m is the number of machines, even when payments to the machines are allowed. In strong contrast to this impossibility, our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a 3/2-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. We conclude with important directions for future research concerning other fairness notions, including relaxations of envy-freeness. Notably, we show that the technique leading to the impossibility result for envy-freeness does not extend to its relaxations.

We study fair division of indivisible chores among n agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more than two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exist. We show the existence of · 1-out-of-9n/11 MMS allocations, which improves the state-of-the-art factor of 1-out-of-3n/4. · MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021). · 15/13-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of 13/11. We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a 15/13-MMS allocation for personalized bivalued instances.

We study fair division of indivisible goods under the maximin share (MMS) fairness criterion in settings where agents are grouped into a small number of types, with agents within each type having identical valuations. For the special case of a single type, an exact MMS allocation is always guaranteed to exist. However, for two or more distinct agent types, exact MMS allocations do not always exist, shifting the focus to establishing the existence of approximate-MMS allocations. A series of works over the last decade has resulted in the best-known approximation guarantee of 3/4 + 3/3836. In this paper, we improve the approximation guarantees for settings where agents are grouped into two or three types, a scenario that arises in many practical settings. Specifically, we present novel algorithms that guarantee a 4/5-MMS allocation for two agent types and a 16/21-MMS allocation for three agent types. Our approach leverages the MMS partition of the majority type and adapts it to provide improved fairness guarantees for all types.

Organizations increasingly seek to share and access datasets to improve their ML models and derive insights. Despite the immense demand for quality data, data exchange and collaboration have not reached their full potential. One of the key reasons is the lack of reciprocity, where some participants perceive their contribution to others to be of higher value than what they receive in return.

We explore the relationship between two popular concepts in the allocation of divisible items: competitive equilibrium (CE) and allocations that maximize Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these two concepts coincide: the classical Eisenberg- Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However, these two concepts diverge for non-homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, whereas computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities.

We consider fair division of a set of indivisible goods among n agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her (1-out-of-n) MMS value. An allocation is called MMS if all agents receive their MMS values. However, since MMS allocations do not always exist [Kurokawa et al., JACM'18], the focus shifted to investigating its ordinal and multiplicative approximations.

We study the fundamental problem of fairly allocating a set of indivisible goods among n agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her MMS value. An allocation is called MMS if all agents receive at least their MMS value. However, since MMS allocations need not exist when n > 2, a series of works showed the existence of approximate MMS allocations with the current best factor of . The recent work [3] showed the limitations of existing approaches and proved that they cannot improve this factor to 3/4 + Ω(1). In this paper, we bypass these barriers to show the existence of ()-MMS allocations by developing new reduction rules and analysis techniques.

We study the problem of distributing a set of indivisible goods among agents with additive valuations in a fair manner. The fairness notion under consideration is envy-freeness up to any good (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.

We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation and a non-constructive proof of the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudopolynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.

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.

We consider the problem of fairly allocating a set of indivisible goods among n agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The Garg-Taki algorithm gives the current best approximation factor of (3/4 + 1/12n). Most of these results are based on complicated analyses, especially those providing better than 2/3 factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of (3/4 + min(1/36, 3/(16n-4))). For small n, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques.

For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed till now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts—called epistemic EFX (EEFX) and minimum EFX value fairness (MXS)---inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts are excellent alternatives to EFX and MMS.

We study the problem of fairly and efficiently allocating indivisible chores among agents with additive disutility functions. We consider the widely used envy-based fairness properties of EF1 and EFX in conjunction with the efficiency property of fractional Pareto-optimality (fPO). Existence (and computation) of an allocation that is simultaneously EF1/EFX and fPO are challenging open problems, and we make progress on both of them. We show the existence of an allocation that is - EF1 + fPO, when there are three agents, - EF1 + fPO, when there are at most two disutility functions, - EFX + fPO, for three agents with bivalued disutility functions. These results are constructive, based on strongly polynomial-time algorithms. We also investigate non-existence and show that an allocation that is EFX+fPO need not exist, even for two agents.

The existence of EFX allocations is a fundamental open problem in discrete fair division. Since the general problem has been elusive, progress is made on two fronts: (i) proving existence when the number of agents is small, and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques.

For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω.

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.

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents’ valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent of m was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations before this work. In this article, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high-valued items are done separately by un-matching certain items and re-matching them by different processes in both algorithms. We show that these approaches achieve approximation factors of O ( n ) and O ( n log n ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item ( EF1 ). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an \(\frac{\mathrm{e}}{\mathrm{e}-1}\) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of \(\frac{\mathrm{e}}{\mathrm{e}-1}\) , hence resolving it completely.

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.

We study the chore division problem in the classic Arrow-Debreu exchange setting, where a set of agents want to divide their divisible chores (bads) to minimize their disutilities (costs). We assume that agents have linear disutility functions. Like the setting with goods, a division based on competitive equilibrium is regarded as one of the best mechanisms for bads. Equilibrium existence for goods has been extensively studied, resulting in a simple, polynomial-time verifiable, necessary and sufficient condition. However, dividing bads has not received a similar extensive study even though it is as relevant as dividing goods in day-to-day life. In this paper, we show that the problem of checking whether an equilibrium exists in chore division is NP-complete, which is in sharp contrast to the case of goods. Further, we derive a simple, polynomial-time verifiable, sufficient condition for existence. Our fixed-point formulation to show existence makes novel use of both Kakutani and Brouwer fixed-point theorems, the latter nested inside the former, to avoid the undefined demand issue specific to bads.

No abstract available.

We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of goods is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017). The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by ‘robust’ utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow–Debreu exchange market model.

We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.

We propose and address a new variation of the team orienteering problem (TOP) in which all members of the team are independent self-interested agents. The prize-collecting nature emanates from the fact that the prize available at a node of the traversal graph can be collected only by a single visiting agent. The problem is motivated by situations in which team members (agents) must accomplish tasks toward a common goal but are unable to communicate, such as a fleet of surveillance drones operating in a communication denied area or with remote pilots operating independently. We explore three policies for minimizing the amount of inefficiency these self-interested agents can bring into the situation. We analyze these policies in a game-theoretic framework and show upper bounds on the Price of Anarchy (PoA) ranging from$\approx 1.582$to unbounded depending on the policy, network type, and the number of players$k$. This is done by extending well-known PoA bounds for valid utility systems to a leader–follower setting. The PoA also depends on the behavior of the agents, which could not have goodwill toward other agents. In many cases, we are able to provide examples that establish the tightness of the bounds. Finally, solution methods are provided for each of these policies. Numerical results computed by these solution methods are then presented and compared with the optimal centrally coordinated solutions.Note to Practitioners—Unmanned aerial vehicles (UAVs) are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and when centralized optimal routes for each UAV are too complex to compute. For managers of UAV systems, our work provides a theoretical bound on how bad decentralized routing could be in the context of a prize-collecting game. Under a game-theoretic framework, we prove that the fleet will collect at least 50% of the prizes collected by the optimal centralized solution. Empirically, we show that the performance of the fleet is much better, usually providing at least 90% of the optimal centralized solution. Our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p in (-\infty, 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = -\infty while also retaining the remarkable fairness properties.

We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation, and a non-constructive proof of existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO). We present a pseudo-polynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive, and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. We show that for such instances an EF1+fPO allocation can be computed in polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in polynomial time. Next, we consider instances where the number of agents is constant, and show that an EF1+PO (also EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. Further, we show that the problem of computing an EF1+PO allocation polynomial-time reduces to a problem in the complexity class PLS. We also design a polynomial-time algorithm that computes Nash welfare maximizing allocations when there are constantly many agents with constant many different values for the goods.

We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to select k ≤ m goods in a fair and efficient manner. We first establish fundamental connections between the models of private goods, public goods, and public decision making by presenting polynomial-time reductions for the popular solution concepts of maximum Nash welfare (MNW) and leximin. These mechanisms are known to provide remarkable fairness and efficiency guarantees in private goods and public decision making settings. We show that they retain these desirable properties even in the public goods case. We prove that MNW allocations provide fairness guarantees of Proportionality up to one good (Prop1), 1/n approximation to Round Robin Share (RRS), and the efficiency guarantee of Pareto Optimality (PO). Further, we show that the problems of finding MNW or leximin-optimal allocations are NP-hard, even in the case of constantly many agents, or binary valuations. This is in sharp contrast to the private goods setting that admits polynomial-time algorithms under binary valuations. We also design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for the cases of (i) constantly many agents, and (ii) constantly many goods with additive valuations. We also present an O(n)-factor approximation algorithm for MNW which also satisfies RRS, Prop1, and 1/2-Prop.

We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division [5]. Towards resolving this problem, many impressive results show the existence of its relaxations. In particular, [1] shows the existence of 0.618-EFX allocations, and [4] shows that EFX allocation exists if we do not allocate at most n - 1 goods. The latter result was recently improved for three agents in [2], in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for an arbitrary number of agents is a systematic way to settle the big question.

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 that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [14] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open. Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna [24], and we also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-enumerative option known. 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 PPAD, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of [14] in the affirmative.

We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constant-factor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constant-factor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant.

We study the problem of distributing a set of indivisible items among agents with additive valuations in a fairmanner. The fairness notion under consideration is Envy-freeness up to anyitem (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al.[9] by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.

We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ε MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by un-matching certain items and re-matching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of , hence resolving it completely.

We consider the problem of fairly allocating a set of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic concept of efficiency, Pareto optimality. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. We address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market interpretation of a fractional max NSW allocation. We present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a market equilibrium into an integral allocation in a way that provides most of the fairness properties of an integral max NSW allocation.

We study the multiagent unmanned aerial vehicle (UAV) routing problem where a set of UAVs needs to collect information via surveillance of an area of operation. Each UAV is autonomous and does not rely on a reliable communication medium to coordinate with other UAVs. We formulate the problem as a game where UAVs are players and their strategies are the different routes they can take. Our model also incorporates the useful concept of information fusion. This results in a new variant of weighted congestion-type games. We show that the price of anarchy (PoA) of the game is at most 2, irrespective of the number of UAVs and their sensor capabilities. This also validates the empirical results of earlier works. Furthermore, we identify classes of games for the existence of a pure Nash equilibrium. To the best of our knowledge, these are the first such theoretical results in the related literature. Finally, we conduct experimental studies using randomly generated instances with several multiagent UAV routing policies. Our insights are that PoA increases with the congestion level when the same number of UAVs search a smaller area or more UAVs search the same area, and on an average, our proposed policies are less than 10% worse than the centralized optimal for the problem scenarios attempted. Note to Practitioners-UAVs are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and centralized optimal routes for each UAV in the fleet are too complex to compute. Autonomous solutions have several other advantages, let alone simplicity. For managers of UAV systems, our work provides the first theoretical characterization of how bad could decentralized routing be. Under various scenarios of information fusion, specifically weak and strong, and the attribution of information collected to each UAV of a team, we prove that the fleet will collect at least 50% of the best-centralized solution. Empirically, we show that, in fact, the performance of the fleet is much better and generally not worse than 10% of the best-centralized solution. Hopefully, our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.

We consider the problem of fairly allocating a set of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the 'unreasonable' fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic concept of efficiency, Pareto optimality. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. We address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market interpretation of a fractional max NSW allocation. We present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a market equilibrium into an integral allocation that provides most of the fairness properties of an integral max NSW allocation.

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, i.e., pairs of agents and goods that must correspond to 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.

We design a simple ascending-price algorithm to compute a (1 + ε)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ε and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.

We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of e^{1/{e}} ~~ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + epsilon.

We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria. In particular, our model does not satisfy the condition of non-satiation, which is used critically to show the existence of equilibria in traditional market models and we observe that our set of equilibrium prices could be a connected, nonconvex set. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models as well as new models, such as CEEI.

We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every ε > 0, our algorithm obtains a (2.404 + ε)-approximation in time polynomial in the input size and 1/ε. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [17]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

Our first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief utility functions. This settles an open question of Vazirani and Yannakakis (2011).

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of ''revealed preference'' analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it isNP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.

We design a simple ascending-price algorithm to compute a (1+\varepsilon)-approximate equilibrium in Arrow-Debreu exchange markets with weak gross substitute (WGS) property, which runs in time polynomial in market parameters and log 1/varepsilon. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which is easy to implement and avoids heavy machinery such as the ellipsoid method. In addition, our algorithm can be applied in an unknown market setting without exact knowledge about the number of agents, their individual utilities and endowments. Instead, our algorithm only relies on queries to a global demand oracle by posting prices and receiving aggregate demand for goods as feedback. When demands are real-valued functions of prices, the oracles can only return values of bounded precision based on real utility functions. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest.

We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with n agents and integral utilities bounded by U, the algorithm runs in O(n7 log3(nU)) time. This improves upon the previously best algorithm of Ye by a factor of . The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of . The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

The classic Arrow-Debreu market model captures both production and consumption, two equally important blocks of an economy, however most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this paper we show two new results on markets with production. Our first result gives a polynomial time algorithm for Arrow-Debreu markets under piecewise linear concave (PLC) utilities and polyhedral production sets provided the number of goods is constant. This is the first polynomial time result for the most general case of Arrow-Debreu markets.

Using Lemke's scheme, we give a complementary pivot algorithm for computing an equilibrium for Arrow--Debreu markets under separable, piecewise-linear concave (SPLC) utilities. Despite the polynomial parity argument on directed graphs (PPAD) completeness of this case, experiments indicate that our algorithm is practical---on randomly generated instances, the number of iterations it needs is linear in the total number of segments (i.e., pieces) in all the utility functions specified in the input. Our paper settles a number of open problems: (1) Eaves (1976) gave an LCP formulation and a Lemke-type algorithm for the linear Arrow--Debreu model. We generalize both to the SPLC case, hence settling the relevant part of his open problem. (2) Our path following algorithm for SPLC markets, together with a result of Todd (1976), gives a direct proof of membership of such markets in PPAD and settles a question of Vazirani and Yannakakis (2011). (3) We settle a question of Devanur and Kannan (2008) of obtaining a “systematic way of finding equilibrium instead of the brute-force way” for the separable case and we obtain a strongly polynomial algorithm if the number of goods or agents is constant. (4) We give a combinatorial way of interpreting Eaves' algorithm for the linear case, hence answering Eaves' question (1976), “That the algorithm can be interpreted as a `global market adjustment mechanism' might be interesting to explore.”

Even though production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. For markets with separable, piecewise-linear concave (SPLC) utilities and SPLC production, we obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria, and we further give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 [14]. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm is practical. Also, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.

After more than a decade of work in TCS on the computability of market equilibria, complementary pivot algorithms have emerged as the best hope of obtaining practical algorithms. So far they have been used for markets under separable, piecewise-linear concave (SPLC) utility functions [23] and SPLC production sets [25]. Can his approach extend to non-separable utility functions and production sets? A major impediment is rationality, i.e., if all parameters are set to rational numbers, there should be a rational equilibrium.

In this paper we consider the problem of computing market equilibria in the Fisher setting for utility models such as spending constraint and perfect, price-discrimination. These models were inspired from modern e-commerce settings and attempt to bridge the gap between the computationally hard but realistic separable, piecewise-linear and concave utility model and, the tractable but less relevant linear utility case. While there are polynomial time algorithms known for these problems, the question of whether there exist polynomial time Simplex-like algorithms has remained elusive, even for linear markets. Such algorithms are desirable due to their conceptual simplicity, ease of implementation and practicality. This paper takes a significant step towards this goal by presenting the first Simplex-like algorithms for these markets assuming a positive resolution of an algebraic problem of Cucker, Koiran and Smale. Unconditionally, our algorithms are FPTASs; they compute prices and allocations such that each buyer derives at least a -fraction of the utility at a true market equilibrium, and their running times are polynomial in the input length and 1/ε. We start with convex programs which capture market equilibria in each setting and, in a systematic way, convert them into linear complementarity problem (LCP) formulations. Then, departing from previous approaches which try to pivot on a single polyhedron associated to the LCP obtained, we carefully construct a polynomial-length sequence of polyhedra, one containing the other, such that starting from an optimal solution to one allows us to obtain an optimal solution to the next in the sequence in a polynomial number of complementary pivot steps. Our framework to convert a convex program into an LCP and then come up with a Simplex-like algorithm that moves on a sequence of connected polyhedra may be of independent interest.

Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case. As a corollary, we obtain the first elementary proof of existence of equilibrium for this case, i.e., without using fixed point theorems. In 1975, Eaves [10] had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave utilities. Our result settles the relevant subcase of his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.

Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed by Kannan and Theobald (SODA'07). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. Our approach also provides new proofs of important classical results such as the existence and oddness of Nash equilibria, and the index theorem for bimatrix games. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on [0,1]k for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.