We show that if the ground set of a matroid can be partitioned into \(k \ge 2\) bases, then for any given subset \(S\) of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with \(S\) may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabo (Electron. J. Comb. 2011) in the affirmative. We also investigate equitable splittings of two disjoint sets \(S_1\) and \(S_2\), and show that there is a partition into \(k\) bases such that the sizes of the intersections with \(S_1\) may differ by at most one and the sizes of the intersections with \(S_2\) may differ by at most two; this is the best one can hope for arbitrary matroids.

We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered to be one of the most fascinating fairness concepts in this line of work. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. [2023] introduced a promising relaxation of EFX, called epistemic EFX (EEFX). An allocation is EEFX, if for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes ``EFX-satisfied''. Caragiannis et al. [2023] prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive? We address this important open question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, besides EF1, EEFX is the only known relaxation of EFX to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that even for an arbitrary number of (more than one) agents with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so.

We study the problem of computing fair divisions of a set of indivisible goods among agents with additive valuations. For the past many decades, the literature has explored various notions of fairness, that can be primarily seen as either having envy-based or share-based lens. For the discrete setting of resource-allocation problems, envy-free up to any good (EFX) and maximin share (MMS) are widely considered as the flag-bearers of fairness notions in the above two categories, thereby capturing different aspects of fairness herein. Due to lack of existence results of these notions and the fact that a good approximation of EFX or MMS does not imply particularly strong guarantees of the other, it becomes important to understand the compatibility of EFX and MMS allocations with one another. In this work, we identify a novel way to simultaneously achieve MMS guarantees with EFX/EF1 notions of fairness, while beating the best known approximation factors by Chaudhury et al. and Amanatidis et al. Our main contribution is to constructively prove the existence of (i) a partial allocation that is both 2/3-MMS and EFX, and (ii) a complete allocation that is both 2/3-MMS and EF1. Our algorithms run in pseudo-polynomial time if the approximation factor for MMS is relaxed to 2/3 - e for any constant e>0 and in polynomial time if, in addition, the EFX (or EF1) guarantee is relaxed to (1-d)-EFX (or (1-d)-EF1) for any constant d>0. In particular, we improve from the best approximation factor known prior to our work by Chaudhury et al., which computes partial allocations that are 1/2-MMS and EFX in pseudo-polynomial time.

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 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 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.

We consider the problem of guaranteeing maximin-share ($\MMS$) when allocating a set of indivisible items to a set of agents with fractionally subadditive ($\XOS$) valuations. For $\XOS$ valuations, it has been previously shown that for some instances no allocation can guarantee a fraction better than $1/2$ of maximin-share to all the agents. Also, a deterministic allocation exists that guarantees $0.219225$ of the maximin-share of each agent. Our results involve both deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee for fractionally subadditive valuations to $3/13 = 0.230769$. We develop new ideas on allocating large items in our allocation algorithm which might be of independent interest. Furthermore, we investigate randomized algorithms and the Best-of-both-worlds fairness guarantees. We propose a randomized allocation that is $1/4$-$\MMS$ ex-ante and $1/8$-$\MMS$ ex-post for $\XOS$ valuations. Moreover, we prove an upper bound of $3/4$ on the ex-ante guarantee for this class of valuations.

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.

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either p or q, where p and q are integers and p2. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.

We study the problem of fairly allocating a set of indivisible goods to a set of n agents. Envy-freeness up to any good (EFX) criterion (which requires that no agent prefers the bundle of another agent after the removal of any single good) is known to be a remarkable analogue of envy-freeness when the resource is a set of indivisible goods. In this paper, we investigate EFX for restricted additive valuations, that is, every good has a non-negative value, and every agent is interested in only some of the goods. We introduce a natural relaxation of EFX called EFkX which requires that no agent envies another agent after the removal of any k goods. Our main contribution is an algorithm that finds a complete (i.e., no good is discarded) EF2X allocation for restricted additive valuations. In our algorithm we devise new concepts, namely configuration and envy-elimination that might be of independent interest. We also use our new tools to find an EFX allocation for restricted additive valuations that discards at most n/2 -1 goods.