Search for: All records

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. 

A Simpler Approach to the EFX Problem Envy-freeness up to any item (EFX) has emerged as a compelling fairness notion in discrete fair division. However, its existence remains one of the biggest open problems in the field. In a breakthrough, Chaudhury et al. (2020) establish the existence of EFX allocations for three agents with additive valuations through intricate case analysis. The paper “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number” by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta offers a simpler approach for improving the EFX guarantee. They demonstrate the existence of EFX allocations for three agents when at least one has additive valuations (whereas the other two have general monotone valuations). Additionally, they nearly resolve a conjecture regarding the rainbow cycle number, leading to an (almost) tight bound for the existence of approximate EFX allocations with few unallocated items achievable through this approach. 

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 an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that EFX allocation exists if we do not allocate at most (n-1) goods. Reducing the number of unallocated goods has emerged as a systematic way to tackle the main question. For example, follow-up works on three- and four-agents cases, respectively, allocated two more unallocated goods through an involved procedure. In this paper, we study the general case and achieve sublinear numbers of unallocated goods. Through a new approach, we show that for every [Formula: see text], there always exists a [Formula: see text]-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We define the notion of rainbow cycle number [Formula: see text] in directed graphs. For all [Formula: see text] is the largest k such that there exists a k-partite graph [Formula: see text], in which each part has at most d vertices (i.e., [Formula: see text] for all [Formula: see text]); for any two parts V_iand V_j, each vertex in V_ihas an incoming edge from some vertex in V_jand vice versa; and there exists no cycle in G that contains at most one vertex from each part. We show that any upper bound on [Formula: see text] directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on [Formula: see text], yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. Funding: J. Garg was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1942321]. R. Mehta was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1750436]. 

We investigate the existence of fair and efficient allocations of indivisible chores to asymmetric agents who have unequal entitlements or weights. We consider the fairness notion of weighted envy-freeness up to one chore (wEF1) and the efficiency notion of Pareto-optimality (PO). The existence of EF1 and PO allocations of chores to symmetric agents is a major open problem in discrete fair division, and positive results are known only for certain structured instances. In this paper, we study this problem for a more general setting of asymmetric agents and show that an allocation that is wEF1 and PO exists and can be computed in polynomial time for instances with:- Three types of agents where agents with the same type have identical preferences but can have different weights. - Two types of choresFor symmetric agents, our results establish that EF1 and PO allocations exist for three types of agents and also generalize known results for three agents, two types of agents, and two types of chores. Our algorithms use a weighted picking sequence algorithm as a subroutine; we expect this idea and our analysis to be of independent interest. 

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.