Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Authors: Hannaneh Akrami
Kurt Mehlhorn
Masoud Seddighin
Golnoosh Shahkarami
Venue: NeurIPS 2023 poster (2023)
Keywords: Algorithmic game theory
Fairness
Randomized
Allocation
Maximin-share
Fractionally Subadditive

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

Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Hannaneh Akrami
Kurt Mehlhorn
Max Planck Institute for Informatics Graduiertenschule Informatik Universität des Saarlandes
Max Planck Institute for Informatics
Universität des Saarlandes
mehlhorn@mpi-ine mpg. de
hakrami @mpi mpg de
Masoud Seddighin
Golnoosh Shahkarami
Tehran Institute Advanced Studies http:tttiiiiinnnitttttete.eeeeee institute
Max Planck Institute for Informatics
Graduiertenschule Informatik Universität des Saarlandes
gshahkardmpi-ingg innf .mp de
Abstract
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, has been previously shown that for some in- stances no allocation can guarantee a fraction better than 1/2 of maximin-share to all the agents. Also, deterministic allocation exists that guarantees 0.219225 of the maximin-share of each agent. Our results involve both deterministic and ran- domized 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- botff-boh-wwwweet worlds fairness guarantees. We propose randomized allocation that is 1/4-MMS ex ex-ante and 1 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.
Introduction
Fair allocation has been central problem in economics for decades. This problem arises naturally in real-world applications such as advertising, negotiation, rent sharing, inheritance, etc Caragiannis al. (2019); Dehghani al. (2018); Dickerson al. (2014); Foley (1967); Nash (1950); Varian (1973). In discrete fair division, the basic scenario is that we want to distribute a set M of m indivisible items among n agents, such that the allocation is deemed fair by the agents. Each agent has a valuation function U; 2M + R that represents her happiness for receiving subset of items.
How do evaluate fairness? This question has been the subject of intense debates in various contexts, inc including philosophy, economics, distributive justice, and mathematics. Since the introduction of the cake-cutting! problem Steinhaus (1948), scientists have suggested several different notions evaluate fairness. The challenge that a fairness notion must be both reasonable terms of justice and implementable in practice. Conceived by Steinhaus, proportionality is one of the most natural
(Cake-cutting is the continuous version of the fair allocation problem where the resource is divisible cake.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and prominent notions. An allocation is proportional if the share allocated to every agent is worth at least 1/n of her value for the entire resource.
Unfortunately, despite many positive results on proportionality for cake-cutting, simple examples indicate that proportionality is not proper faimess criterion for the case of indivisible items. For example, when there is one item and two agents, one agent receives nothing, though her proportional share is non-zero assuming that the item has positive value for both of the agents. An alternative form of proportionality adopted to deal with indivisibilities is Maximin-share (MMS). For every agent i, the maximin-siie share of agent denoted by MMS, defined as follows:
MMS, (a JERRS)S
max min 2y (Il)),,
where 52 is the set of all partitions of M into n parts. It is known that even when all the valuations are additive, MMS allocations, in which each agent gets at least MMS,, need not exist Feige et al. (2022): Kurokawa et al. (2018): Procaccia and Wang (2014). Nevertheless, several studies in recent years show that it is possible to guarantee constant factor of maximin-share to all agents for various classes of valuation functions, including additive, submodular, and fractionally subadditive. See Table I for the offtc-of-theaarr guarantees on the maximin--harre For Submodular valuation class, a 10/27-MMS allocation can be computed in polynomial time. For all other classes of valuation functions mentioned in Table 1, the states-of ooties--f-thh-arr aht are existential results.
Table I: A summary of the results for MMS in different valuation classes.
Valuation Class
Approximation Guarantee
Upper bound
Additiiv
+ 30.30 Akrami and Garg (2024)
20 Feige et al. (2022)
Submodular
10 Uzlahu and Felge (2023)
Ghodsi et (2018)
Fractionally Subaddilive
0,219225 Seddighin and Seddighin (2022)
Ghodsi al. (2018)
Subadditive
Tog for Iog
Seddighin and Seddighin (2022)
Ghodsi et al. (2018)
Let us revisit the instance with one item and two agents. Suppose that the item has value 6 for both agents. By definition, the proportional share of each agent 6/2 3, and since one agent receives no item, satisfying proportionality or any approximation of it is impossible. On the other hand, we have MMS, MMS,- O. Thus, allocating the item to any agent satisfies maximin-share Indeed, we can circumvent the -unraatttteedd existence of fair allocation by reducing our expectation of fairness to maximin-shar item, and the other receives nothing. Therefore, having one agent with zero utility is inevitable for any deterministic allocation in this example. The question then arises: can we do better? One way to improve the allocation is to use randomization and obtain a better guarantee in expectation (ex-ante). For example, we can allocate the item to each agent with probability 1/2. This way, the expected utility of each agent is equal to 3. In economic terms, this allocation satisfics proportionality ex-ante. Note that one agent receives no item ex-post (that is, after fixing the outcome); however, it guarantees proportionality ex-ante to both agents.
However, regardless of how we allocate the item, one agent receives one
Considering random allocations and ex-ante fairness makes the problem much handier. For instance, assuming there are n items and n agents, allocating each item to each agent with probability 1/n satisfies proportionality ex-ante. However, this randomized allocation has no ex ex-post fairness guarantee: with a non-zero probability, the outcome allocates all the items to one agent, and the rest of the agents receive no item. It tempting to find allocations that simultaneously admit ex-ante and ex-post guarantees. The support of such an allocation is limited to outcomes with some desirable fairness guarantee. For example, consider the following random allocation: we choose a random permutation of these n items and allocate the 7 item in the permutation to agent i. This allocation satisfics proportionality ex-ante and maximin-shar ex post.
Recently, several studies have investigated randomized allocations with both ex-ante and ex ex-post guarantees. Some notable results with the focus on additive valuations are (i) an ex-ante envy- free and ex-post EF1 allocation algorithm Freeman et al. (2020), (ii) an ex-ante proportional and ex-post 1 1/2-MMS allocation algorithm Babaioff et al. (2022), and (iii) an ex-post 3/4-MMS and ex-ante 0. 0.785-MMS allocation algorithm Akrami et al. (2023b). Very recently, Feldman et al. (2023) studied www-oof--oooolllcooooo for subadditive valuations and gave an allocation algorithm with ex-ante guarantee of 1 -reennnsssss and cx- ex-post guarantee of 1 1/2-EFX and EFI.
2

---

In this paper, our goal is to explore fair deterministic and randomized allocations for fractionally subadditive valuation functions. A valuation function v;(-) is fractionally subadditive (XOS), if there exists a set of several additive valuation functions Ui,,, "4,,;,,,,;:--- M..,,....., M 2 - I2z0 such that for every set S we have (S) = max1 ux,x(S), Fractionally subadditive is a super-class of different set functions such as additive, gross substitute, and submodular. In addition, fractionally subadditive is subclass of subadditive set functions.
The fairness notion we consider is maximin-share. Indeed, we are looking for allocations that satisfy an approximation of maximin-shie -hhre both ex-ante and ex ex-post for fractionally subadditive valuations. Of course, we expect our ex-ante guarantee to be stronger than the ex ex-post one. Moreover, we improve the ex-post guarantee (deterministically) for this class of valuations. We refer to the next subsection for an overview on our results and techniques.
1.1 Our Results and Techniques
In this paper, we provide improved guarantees for maximin-share in the fractionally subadditive setting. We investigate both randomized and deterministic allocation algorithms.
Randomized Allocations For randomized allocations, we take one step toward extending the best- of worl-d idea for fairness concepts to valuations more general than additive. For the additive setting, Babaioff et al. (2022) proved the existence of randomized allocations that are proportional ex- ante and 1 /22 ex-post. However, as we show in Section 3, though guaranteeing proportionality ex-ante is easy for XOS valuations, this notion is not always proper choice as fairness criterion. In fact, for some instances, proportionality can be as small as O(1 /') of the MMS value, which is highly undesirable. Therefore, here we focus guaranteeing MMS both ex-ante and ex-post. In contrast to the additive setting, for XOS valuations guaranteeing MMS ex-ante is not easy. Recall that in the additive setting, fractional allocation that allocates fraction 1/n of each item to each agent is proportional and consequently MMS. However, for some XOS instances this allocation is O(1/n)-MMS (Observation 3.2). Indeed, we show that there instances for which guaranteeing MMS ex-ante is not possible. More precisely, we show that there are instances that no randomized allocation can guarantee factor better than 3/4 4 of maximin-share to all agents (Lemma 3.3). On the positive side, we propose an algorithm that finds a randomized allocation which is 1 1/4MMMS ex-ante and 1 //8MMMS ex-post (Theorem 1.1). The idea prove the ex-ante approximation guarantee of our allocation is inspired by Ghodsi et al. (2018). 3). In the beginning of the algorithm, as long as there exists remaining agent i who likes a remaining item by least 1/2 of her MMS value, we allocate by to i and remove them from M and A. By the end of this phase, we get an upper bound on the value of the remaining items for the remaining agents. Let (.) = min 2. u; (-)} for all agents i. In the second phase, we find a half-integral allocation that maximizes social welfare with respect to these new valuations ūt For every i, (-) is the same as (-).), except that for every bundle X with uy (X): 1/2 we have (X) = 1/2. Then, we convert this fractional allocation into randomized one. To prove the ex-post guarantee, the fact that the allocation is half-integral plays a key role.
Theorem 1.1. There exists a randomized allocation that is 1 1/4MMMS ex-ante and 1 1/8-MMS ex-post.
Deterministic Allocations Since the impossibility result on MMS by Procaccia and Wang (2014), there has been a considerable effort in the line of improving the approximate MMS factor for various classes of the valuation functions Akrami and Garg (2024); Akrami et al. (2023a); Barman and Krishnamurthy (2020); Garg and Taki (2021); Ghodsi et al. (2018); Kurokawa et al. (2018). However, all these results and their techniques apply to less general classes of valuation functions than XOS. In this work, we give deterministic algorithm which outputs an allocation with 3/ 13-MMS guarantee when valuation functions are XOS. This way, we improve the sate-off-hhe-at on approximate MMS for XOS valuations from 0.219225 Seddighin and Seddighin (2022) to 3/ = 0.230769. In order to do so, like in our randomized algorithm, we first allocate large items. However, in addition to allocating single large items, here we also allocate pairs and triples of items if they satisfy some agent up to 3/ 13 factor of their MMS value. This way we get stronger upper bound on the value of most of the remaining items. the last step, we output an allocation which maximizes the social welfare with respect to valuations iz(-)= min 13 (x())) for the remaining agents and items. Note that this last step is also in correspondence with the last step of the randomized algorithm. Here we cap the value of the bundles with 6/ 13 (instead of 1/2) and we output integral allocation with maximum
6
3

---

social welfare (instead of a half-integral allocation with maximum social welfare). Moreover, here we need to do a more careful analysis to show that the output is indeed a 3/ 3/13-MMS allocation. Theorem 1.2. Given an instance with XOS valuations, there exists 3/13- /M3 allocation.
Both of our results are constructive; however, their running times are not polynomially bounded. One step that cannot be done in polynomial time is computing the MMS values of the agents and another one is computing an allocation with maximum social welfare.
1.2 Further Related Work
Maximin-share fairness notion. Budish (2011) introduced the MMS notion. As we already mentioned, there are instances with additive valuations for which no MMS allocation exists Feige et al. (2022); Kurokawa al. (2018); Procaccia and Wang (2014). Therefore, several studies considered the approximation guarantees. For additive valuations, the first approximation guarantee, 2/3-MMS, is given by Kurokawa et al. (2018). The approximation factor improved over time by Ghodsi et al. (2018) to 3/4, and then to 3/4 + o(1) by Garg and Taki (2021) and Akrami et al. (2023a). The best-known result for this valuation classed is 3/4 4 3/3836 which was very recently proposed by Akrami and Garg (2024). Moreover, there are several works on MMS approximations for submodular valuations Barman and Krishnamurthy (2020); Ghodsi al. (2018), and subadditive valuations Ghodsi et al. (2018), Seddighin and Seddighin (2022). Also, Farhadi et al. (2019) proved the tight bound of 1 1/n-MMS for the setting where agents can have different entitlements.
Fractionally subadditive valuations. A 1/5-MMS approximation algorithm for fractionally sub- additive valuations proposed by Ghodsi al. (2018), ()) and improved later to 0.2173913-MM/ approx- imation by Seddighin and Seddighin (2022). Fractionally subadditive valuations for hereditary set systems have been studied by Li and Vetta (2018). Different other notions of fairness have been studied for this class of valuation. Feige (2009) studied maximizing social welfare. Also, Hoefer al. (2023) proved the existence of randomized allocations which are proportional ex-ante and proportional up to one item (PROP1) ex-post.
beot-of-hoth-worlds fairness. Aleksandrov et al. (2015) first explored this line of research in the context of the food bank problem for a special case of additive valuations. Freeman et al. (2020) proposed a randomized polynomial-time algorithm for additive valuations that is envy-free ex-ante and EFI ex-post. Afterward, Aziz (2020) modified this algorithm to also get the Probabilistic Serial fractional outcome Bogomolnaia and Moulin (2001) well as a weak notion of efficiency with a simpler proof. Babaioff et al. (2022) provided an allocation algorithm in which the expected value of each agent's 's bundle is at least a I/n-fraction of her value for the set of all items (ex-ante proportional) and ex-post proportional up to one item and 1/2-MMS allocations for the additive valuations. Feldman et al. (2023) gave an allocation algorithm for subadditive valuations with guarantees of 1 //2-envy-freenee conducted for additive valuations with binary marginals Aziz (2020); Halpern et al. (2020), and for matroid rank valuations Aziz et al. (2023); Babaioff et al. (2021).
ex-ante and 1/2-EFX and EFI ex ex-post. Moreover, studies have been
2 Preliminaries
A fair division instance is denoted by I (N, V) where N = [n]] is set of n agents, . is set of m indivisible items and V = (U)...., vn)) is a vector of valuation functions. Each agent has a valuation function 0; 2M + R22 that represents her value for every bundle of items. Thus, for every set S of items, (S) shows the value of S to agent i. We denote the 7th item by bj- An allocation of items is a partition of M into n parts (i.e., bundles) where the 7th bundle is the share allocated to agent i. For an allocation A, we denote the bundle of agent by A,. Here we assume that the valuations monotone, i.e., for every two sets S and T such that S T, we have v5(5) < u2 (T)). and normalized, i..., (0) = 0 for all í E A. Our discussion in this paper involves two classes of valuation functions: additive and fractionally subadditive valuation functions. A valuation function (+()) is additive, if for every set S of items, we have (S) = Σoies (e((b;)).
Definition 2.1 (XOS). A valuation function vz(-) is fractionally subadditive (XOS), if there exists set of several additive valuation functions u1,1, U1,2,-.., Ui,e 2 -> Rzo such that for every set we have 0 (S) = maxiskse (S).

---

Given an allocation A, we denote by Ma,e, an additive function of is that defines 2s (,(,,, i.c., (A,), u (A.). Another term we frequently use in this paper contribution; which is defined to evaluate the marginal value of one set to another.
Definition 2.2 (Contribution). For every sets S, T of items such that 5 T, we define the marginal contribution of S T with respect valuation function e, denoted by ( as C. v(T) v(T \ S), i.c., the contribution of S to I" is the decrease in the value when S is removed from T'.
With abuse of notation, for an allocation of items to agents with valuation vector V (VI, vn)
and every set S of items, we define the contribution of S to A with respect to V. denoted by C (S) as (S) Eisien Cee (A,n)) SS). However, since an XOS valuation function might include many additive functions, this equation not always practical. Therefore, we bound (A) as follows.
Observation 2.3. Given an allocation A of items to agents with valuation vector V, and every set S of items, we have C (S) S Eisisn Wi (A4, NS).
Our goal is to allocate the items to the agents in a fair manner. Here we discuss two share-based notions of fairesss, namely proportionality, and maximin-share For agent i, we define the proportional share of agent i, denoted by ne as n. = (.( /n. We also define the maximin-shan -hare of agent i, denoted by MMS; as
MMS; =
min (I1,), (I, II EB SS
max
where Ω is the set of all partitions of M into n bundles. Moreover, if for a partition II (I,, .l,...,, II,)) of M into bundles we have u; (I[, > MMS, for all E [n]. we say II is an "MMS partition" of agent i. For brevity, in the rest of the paper, we assume that the valuations are scaled so that for each agent we have MMS,
1. We also define approximate versions of these two notions as follows. For a constant a > O, we say an allocation is a-proportional, if it guarantees each agent a bundle with value at least am, Likewise, in an a-MMS allocation, the value of the share allocated to each agent i is at least a.
Randomized allocation. In this paper, we also consider randomized allocations. A randomized allocation is a distribution over a set of deterministic allocations. For randomized allocation R, we denote by D(R) the set of allocations in the support of R. Given randomized allocation R. the expected welfare of agent for R is defined as u; (R) EAED(R) is (A,) PA where PA is the probability of allocation A in R.
Fractional allocation. En route proving our results, we leverage another relaxed form of alloca- tion called fractional allocation. In fractional allocation, we ignore the indivisibility assumption and treat each item as a divisible one. Formally, fractional allocation FF is a set of nm variables fi,j indicating the fraction of item by allocated to agent i. Therefore, we expect allocation F to satisfy the following constraints:
Σ ISiSh
fig S
(we have one unit of each item)
Vi
0 fis
(each agent receives non-negative share of each item)
A fractional allocation is complete if Σ, fty = for all items by. i.e., all items are completely allocated. Given a fractional allocation J. we define the utility of agent for F in the same way as we calculate it for integral allocations: (F) = max; Eieism u4 (1,,({b;)) ((b,))ffa.. Complete fractional
allocations give rise to randomized allocations in the standard way, i.e., the probability PAA of an allocation A is defined as
PA II Sgj 1siSnb,EA,
Lemma 2.4. Let F. be a complete fractional allocation and let randomized allocation R be defined by (1). Then given an XOS valuation function v, (R( 2 v,(F) for all 1 <
We also need to redefine contribution for fractional allocations and fractional bundles. Suppose that F is a fractional allocation and a fractional set of items. Since items are fractionally allocated, the term contribution must be defined more precisely. For example, suppose that set S consists of
5

---

fraction 0.4 of item by. and in allocation F, 0.2 of by belongs to agent 11, 0.5 of by belongs to agent 22. and 0.3 of b, belongs to agent 13. Here we should exactly determine that this 0.4 fraction of item by in S corresponds to the share of which agent or agents. One reasonable strategy is to choose the share of each agent in way that after removal of S from F we have the smallest possible decrease in the social welfare. Based on this strategy. assuming that sj is the fraction of item by in S, we define the contribution of S to F, denoted by C (S) as the answer of the following optimization program:
minimize
Σ 15isn
ve(F) (F()
subject to
Σ
Sijj - S'.j = 83
VJ
Isisn
0 S fig Sig
Vij
Generally, it is hard to deal with the above optimization program. Here, use important property of C5 (.) to obtain our results.
Lemma 2.5. Let F be an arbitrary fractional allocation and assume that for every agent i, ()()) XOS. Then, for every partition of the items into fractional sets S1, S.......... St. we have Eiskgl OZ S Eisisn (.FF).
For randomized allocation, we define two types of faimess guarantees, namely ex-ante and ex-post as in Definitions 2.6 and 2.7.
Definition 2.6 (ex-ante). Given a randomized allocation R, we say R is a-MMS ex-ante, if for every agent i, we have U/ (R) 2 a. Similarly, R is a-proportional, if for every agent ()( am;;
Definition 2.7 (ex-post). An allocation R is a-MMS ex-post, if for every allocation A E D(R), have that allocation A is a-MMS. Also, we say R is a-proportional ex-post if every allocation in the support of R is a-proportional.
One tool that we refer to in this paper is the result of Babaioff et al. (2022) for converting a fractional allocation into a faithful randomized allocation.
Theorem 2.8 (Proved by Babaioff et al. (2022)). Assume that the valuations are additive and let F be a fractional allocation. Then there exists randomized allocation R such that the ex-ante utility of the agents for R is the same as the utility of the agents in F, and for every allocation A in the support of R. the following holds: Vi, (..) 2 v; (R)) max f.0 $(011 va (bb)))
In this paper, use more delicate amalysis of the method used in Theorem 2.8 to convert fractional allocations into randomized ones. This helps us improve our ex-post approximation guarantees.
3 Ex-ante Guarantees
In this section, goal is to explore the possibility of designing randomized allocation that is c-MMS ex-ante or a-proportional ex-ante. Note that, in contrast to the additive case, for XOS valuations there is meaningful correspondence between proportionality and maximin-share; proportional share can be larger or smaller than maximin-share Recall that for the additive case, we always have T, MMS, and therefore, maximin-share is implied by proportionality. For fractionally subadditive valuations, however, πi can be as small as MMS./n.
For the additive setting, a simple fractional allocation that allocates fraction 1/n of each item to each agent guarantees proportionality and consequently maximin- Using Theorem 2.8 one can convert this allocation to randomized allocation that is proportional ex-ante. In Observation 3.1 we show that proportionality can be guaranteed ex-ante for XOS valuations.
Observation 3.1. Every randomized allocation that allocates each item with probability 1/n to each agent is proportional ex-ante.
In contrast to the additive setting, finding an allocation that guarantees maximin-share is not trivial. Indeed, the simple fractional allocation that guarantees proportionality in Observation 3.1 can be as bad as ((1nn)-MMS

---

Observation 3.2. Given any instance I, let F(I) be the fractional allocation that allocates a fraction 1 1/n of each item to each agent. Then, there exists an instance such that the maximin-shee share guarantee of F(Z) is O(1/n).
Generally, there are two main challenges in the process of designing a randomized allocation that guarantees an approximation of maximin-share. In contrast to the additive setting, finding a fractional is not easy, As well as that, transforming
or randomized allocation that approximates maximin-shae a fractional allocation into a randomized one is not straightforward. Indeed, as we show in Lemma 3.3, neither fractional allocations nor randomized allocations can guarantee MMS. We prove an upper bound on the best approximation guarantee of each one of these allocation types.
Lemma 3.3. For XOS valuations, the best MMS guarantee for fractional allocations and the best ex-ante MMS guarantee for randomized allocation is upper bounded by 3 3/4.
Before we prove our lower bound on the maximin-share guarantee for randomized allocations, we note that another challenge about XOS valuations is that in sharp contrast to additive valuations, transforming a fractional allocation to a randomized one is not easy. Indeed, we can show that for a fractional allocation FF there might be randomized allocations R and R' with different utility guarantees for the agents, such that in both R and R' the probability that each item by is allocated to agent i is equal to ft.j. Example 3.4 gives more insight into this challenge.
Example 3.4. Consider the following instance: there are n² items. The valuation of agent i is an XOS set function consisting of n additive valuation functions as follows: partition the items into n bundles each with n items. For each additive function ui,k. the value of each item in the :dth bundle is 1/n and the value of the rest of the items is O. Define allocations R and R' as follows: (i): allocation R allocates each item to each agent with probability 1/n,, and (ii): allocation R' considers a random permutation of the bundles in the optimal MMS partition of the agents and allocates the 7th bundle in the permutation to agent i. In both of these allocations, each item is allocated to each agent with probability 1/n. However, the moximinn-harre guarantee of R Olog n/n)). On the other hand, allocation R' guarantees value to all agents.
Despite these hurdles, in Theorem 3.5 we show that there exists randomized allocation that guarantees 1 1/4MMMS to all the agents ex-ante. To prove Theorem 3.5, we first show that fractional allocation exists that is 1 /4-MMS. Next, we convert it to a randomized allocation. Theorem 3.5 along with Lemma 3.3 leave a gap of [1/4 /4, 3/4) /4 between the best upper bound and the best lower-bound for the maximin- maximin-shaareae guarantee of fractional allocations in the XOS setting.
Theorem 3.5. There exists a randomized allocation that is 1 1/4MMMS ex-ante.
4 Ex-ante and Ex-post Guarantees
Unfortunately, the randomized allocation obtained by Theorem 3.5 has no ex-post fairness guarantee. The issue is that we use Theorem 2.8 to convert the fractional allocation into a randomized one. However, Theorem 2.8 only guarantees that the ex-post value of each agent is at least the value of her fractional allocation minus the value of the heaviest item which is partially (and not fully) allocated to her in the fractional allocation. However, currently, we have no upper bound on the value of the allocated items, and therefore, the ex-post value of an agent might be close to O. To resolve this, we allocate valuable items beforehand to keep the value of the remaining items as small as possible. In Lemma 4.1 we explain simple and very practical fact that is frequently used in the previous studies. Ghodsi et al. (2018); Seddighin and Seddighin (2022); Barman and Krishna Murthy (2017); Amanatidis et al. (2019).
Lemma 4.1. Removing one item and one agent from the instance does not decrease the maximin-share value of the remaining agents for the remaining items.
Given that our goal is construct a randomized allocation which is 1 1/4-MMS ex ex-ante, by Lemma 4.1 we can assume without loss of generality that the value of each item to each agent is less than 1 1/4; otherwise, we can reduce the problem using Lemma 4. However, a combination of this assumption and Theorem 3.5 still gives no ex-post guarantee. To improve the ex-post guarantee, we revisit the proof of Theorem 2.8 and show that for our setting, a stronger guarantee can be achieved using the matching method for converting fractional allocation into a randomized one.
7

---

Lemma 4.2. Assume that the valuations are additive and let F be complete fractional allocation
with fij {0, 1/2, 11 for all and j. Then there is a randomized allocation R with D
(A), }²,, such that
For every agent we have = (F(
For every agent have
min 0: (4)) 2; 2 (R( max (ox(b))) Sú = 1/22
2
In Lemma 4.2, show that find fractional allocation with special structure that makes the transformation step more efficient. These ideas together help us achieve randomized allocation with 1/4-MMS guarantee ex-ante and 1/8-MMS guarantee ex-post. In order do so, use the following algorithm:
1. While there exists an item by with value at least 1/4 to an agent i, allocate by to agent and remove i and by respectively from N and M.
2. For the remaining agents [n] and items proceed as follows: for every agent define it as follows: for every subset of items, R5( = min(t, (S)). Let (Ø1. f2 and return half-integral allocation J that maximizes the social welfare with respect to 0, i...
= arg max LiEN' 0; (Fi) where II is the set of all half-integral allocations of the remaining items to the remaining agents.
3. Convert F into a randomized allocation using Lemma 4.2.
The goal Step is to find a fractional allocation that is 1/4-MMS. However, we want this allocation to have special structure that facilitates constructing the randomized allocation. Therefore, instead of directly choosing the allocation that maximizes social welfare, we consider o, as the valuation function of agent i and return half-integral allocation F. Lemma 4.3. is 1/ LM..
Now we are ready to prove Theorem 1.1.
Theorem 1.1. There exists a randomized allocation that is 1/4-MMS ex-ante and 1/8-MMS ex-post.
Proof. The ex-ante guarantee follows from Lemmas 4.3 and 1.
Let A and A² be the integral allocations obtained by Lemma 4.2. Consider any agent i, and uaa be such that (R) E, Je (bz). Then, by Lemma 4.2 for E (1,2) we have
u (4F) 2 ua (R,) max u4, (b,) ʃt,j 1/2]
and since by Lemma 4.1 we know the value of each item for each agent less than 1/4, we have
c,(4)) 2 (R,)) max, (b(b,)
1
1
1
2
4
8
8
Hence, the ex-post guarantee holds as well.
3/13-MMS Allocation
In this section, our goal is to improve the approximation guarantee of MMS for deterministic alloca- tions in the fractionally subadditive setting. We show that guarantceing a factor 3/13 0.230769 of maximin-skee share to all the agents is always possible. Before this work, the best approximation guarantee for mexximin-share in the XOS setting was 0.211225-MMA Seddighin and Seddighin (2022).
Our algorithm for improving the ex-post guarantee is based on our previous algorithms plus two additional steps and more in-depth analysis. In this algorithm, before finding the allocation that maximizes social welfare, we strengthen our upper bound on the value of items. For this, we add two more steps to our algorithm in which we satisfy some of the agents with two items and three items. In contrast to the first step (i.e., allocating single items to agents), these steps might decrease the maximin-shie value of the remaining agents for the remaining items. Let = 6/13. 13. The goal to find t/2-MMS allocation. Our allocation algorithm is as follows:

---

1. If there exists an item by with value at least t/2 to an agent i, allocate b, to agent i and remove i and by respectively from N and M.
2. If there exists pair of items bj, by with the total value of at least t/2 to some agent i, allocate {by, ] to agent and remove and (bz, b from N and M respectively.
3. If there exists a triple of items bj, bx, b. with the total value of at least 1/2 some agent i, allocate {by, bR, b to agent i and remove and {bz. by, ba) from N and M respectively.
4. For the remaining agents N and items M' proceed as follows: for every agent i, define T3 as follows: for every subset S of items, (,( min(t, (s)). Let ū (W1,...,, (n)) and return an allocation A that maximizes the social welfare with respect to E, i... arg AEE EiEN' (A(.)) where II is the set of all allocations of M' to.
In the rest of this section, we analyze the above algorithm. By Lemma 4.1, after Step 1, the MMS value of all the agents at least 1. Let n be the number of remaining agents after Step 1. We denote by ny and n2, the number of agents that are satisfied in Steps 2 and 3 respectively and let n' = n2 - R1 n2 = |A'| be the number of remaining agents after Step 3. In contrast to the first step, Step 2 and 3 might decrease the maximin-share value of the remaining agents for the remaining items. However, we prove that the remaining items satisfy special structural properties.
Observation 5.1. Since no item can satisfy any remaining agent after Step 1, for every agent and every item by. we have 2z ((b)))) < t/2.
Also, by the method that we allocate the items in Step 3. after this step Observation 5.2 holds. Observation 5.2. Since after Step 3, no triple of items can satisfy an agent, for every different items by. bR. by and every agent we have v. (1b,, bg, b,)) < t/2.
Note that since the valuations XOS, Observation 5.2 implies no upper bound better than t/2 on the value of a single item to an agent. For example, consider the following extreme scenario: for a small constant
0, the value of every subset of items agent i is equal t/2 c. It is easy to check that this valuation function is XOS. For this case, the value of every triple of items is also equal 1/2 e, but this implies no upper bound better than 1/2 on the value of a single item.
Lemma 5.3. Fix a remaining agent and consider the n bundles with value at least 1 in an MMS purtition of agent i after Step 1. Put these bundles into 4 different sets Bo, B1, B2, B23, where for 0 < 8 S 2, set Be contains bundles that lose exactly E items in Steps and 3, and B23 contains bundles that lose more than 4 items in these steps. After Step 3, the following inequality holds: n' < Bol + B1] + 3 B2l.
Finally, in Step 4, we find the integral allocation A that maximizes social welfare with respect to ō for the remaining agents. Let Z ESEN (Aa). Since for each remaining agent i, ū. (AA)) is upper-bounded by 4, we have Z S n't. If for every agent i, (A..) > 1/2 holds, then A is 1/2-MMS, and we are done. Therefore, for the rest of this section, assume that for an agent i", we have 22- (A:-) < t/2.
Let Bo, B1, and Bg be the sets defined for agent i in Lemma 5.3. In Lemma 5.4, we give lower bounds on the contribution of the bundles in Bo, B₁ and B2 to A respectively.
Lemma 5.4. After Step 3, for all bundles
2t. X E B1, there exists a partition of X into X and X2 such that CA((X)) + CA(X2) 2 3t.
X E Bu, there exists partition of X into X and X² such that
e E B2, (x) Lt.
Theorem 1.2. Given an instance with XOS valuations, there exists a 3/13-MMS allocation.
Proof. Let A be the output of our Algorithm. Towards a contradiction, assume for agent it, Wi- (Az-) < 3/13 = 1/2. For all agents i which are removed during the first three steps, we have (A.) t/2 13. Therefore, it N.. For all X E Bo, let X and X² be as defined in

---

Lemma 5.4. We have
t(n' - 2 > Σ (AA))
(for Coralic a & and Br. (A,-) < t/2)
2 Σ
+ E
+ E (X
X
XEB
X
(Lemma 2.5)
+ 1 21 2 tn'.
2 t Bu +
1|Bil
(Lemma 5.4 and Lemma 5.3)
3
6 Conclusion
In this paper, we developed randomized and deterministic allocations that guarantee approximations of maximin-share for fractionally subadditive valuations.
For deterministic allocations, achieve better approximation with the same technique, idea would be to allocate more items to agents the first phase. We believe is promising that this extension gives better approximation factor. However, extending the analysis is not trivial, and new ideas will be necessary to prove its correctness. A more fundamental obstacle lies in the fact that, regardless of the number items allocated in the first phase, the approximation factor converges to 1/4. Therefore, developing new techniques is imperative to improve the approximation factor beyond 1/4.
For randomized allocations, our goal was to guarantee a fraction of MMS ex-ante, and a smaller fraction of MMS ex-post. Several interesting questions remain open. The most straight-forward direction is to improve approximation guarantees for both ex-ante and ex ex-post cases. None of our results proved to be tight. Another notable point is that the running time of none of our algorithms is polynomially bounded. Are there efficient algorithms which achieve the same guarantees?
References
Akrami, H. and Garg, J. (2024). Breaking the 3/4 barrier for approximate maximin share. In Proceedings of the 2024 ACM-SIAM Symposium Discrete Algorithms, SODA, 2024.
Akrami, H., Garg, J., Sharma, E., and Taki, (2023a). Simplification and improvement of MMS approximation. CoRR, abs/2303.16788.
Akrami. H., Garg, J., and Taki, S. (2023b). Improving approximation guarantees for maximin share. CoRR, abs/2307.12916.
Aleksandrov, M., Aziz, H.. Gaspers, S., and Walsh, T. (2015). Online fair division: Analysing food bank problem. In IJCAI 2015, Buenos Aires, Argentina. July 25-31, 2015, pages 2540-2546. AAAI Press.
Amanatidis, G., Ntokos, A., and Markakis, E. (2019). Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination. arXiv preprint arXiv:1909.0765:
Aziz, H. (2020). A probabilistic approach to voting, allocation, matching, and coalition formation. CoRR, 101/2002.
Aziz, H., Ganguly, A., and Micha, E. (2023). Best of both worlds fairness under entitlements. AAMAS.
Babaioff, M., Ezra, T., and Feige, U. (2021). Fair and truthful mechanisms for dichotomous valuations.
In AAAI 2021, IAAI 2021, EAAI 2021, Virtual Event, February 2-9, 2021, pages 5119-5126. AAAI Press.
Babaioff, M., Ezra, T., and Feige, U. (2022). On best-of-bothh-worldd fair-share allocations. WINE 2022, Troy, NY. USA, December 12-15, 2022, Proceedings, pages 237-255, Springer.
10

---

Barman, S. and Krishna Murthy, S. K. (2017). Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 664-664. ACM.
Barman, S. and Krishnamurthy, S. K. (2020). Approximation algorithms for maximin fair division.
ACM Trans. Economics and Comput., 8(1):5:1-5:28.
Bogomolnaia, and Moulin, H. (2001). new solution to the random assignment problem. Econ. Theory, 100(2)295-328.
Budish, E. (2011), The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy. 119(6):0011-1103
Caragiannis, Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., and Wang. (2019). The un- reasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):12.
Dehghani, S., Farhadi, A., HajiAghayi, M., and Yami, H. (2018). Envy-free chore division for an arbitrary number of agents. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2564-2583. SIAM.
Dickerson, J. P., Goldman, J., Karp. J., Procaccia, A. D., and Sandholm, (2014). The computational rise and fall of fairness. In Twenty-Fighth AAAI Conference on Artificial Intelligence.
Farhadi, A., Ghodsi, M.. Hajiaghayi, M. T., Lahaie, S., Pennock, D. M., Seddighin, M., Seddighin, S., and Yami, H. (2019). Fair allocation of indivisible goods to asymmetric agents. J. Artif. Intell. Res., 64:1-20.
Feige, U. (2009). On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 122-41222-142.
Feige, U., Sapir, A., and Tauber, L. (2022). tight negative example for mms fair allocations. In Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, pages 355-372. Springer.
Feldman, M., Mauras, S., Narayan, V. V., and Ponitka, 'T. (2023). Breaking the envy cycle: Best-of- both-worlds guarantees for subadditive valuations. CoRR, abs/2304.03706.
Foley, D. K. (1967). Resource allocation and the public sector. YALE ECON ESSAYS, VOL 7, NO 1, PP 45-98, SPRING 1967. 7 FIG, REF
Freeman, R., Shah, N., and Vaish, R. (2020). Best of both worlds: Ex-ante and ex-post fairness in resource allocation. In Proceedings of the 21 ACM Conference Economics and Computation, pages 21-22.
Garg, J. and Taki, S. (2021). An improved approximation algorithm for maximin shares. Artif. Intell., 103:403347.
Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., and Yami, H. (2018). Fair allocation of indivisible goods: Improvements and generalizations. Proceedings of the 2018 ACM Conference on Economics and Computation, pages 539-556. ACM.
Halpern, D., Procaccia, A. D., Psomas, A., and Shah, N. (2020). Fair division with binary valuations: One rule to rule them all. WINE 2020, Beijing, China, December 7-11, 2020, Proceedings.
Hoefer, M., Schmalhofer, M., and Varricchio, G. (2023). Best of both worlds: Agents with entitle- ments. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 June 2023, pages 564-572. ACM.
Kurokawa, D., Procaccia, A. D., and Wang. J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM), 65(2):8.
Li, 7. and Vetta, A. (2018). The fair division of hereditary set systems. In WINE 2018, Oxford, UK December 15-17, 2018, Proceedings.

---

Nash Jr, J. F. (1950). The bargaining problem. Econometrica: Journal of the Econometric Society, pages 155-162.
Plaut, B. and Roughgarden, т. (2020). Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2): 1039-1068.
Procaccia, A. D. and Wang, J. (2014). Fair enough: Guaranteeing approximate maximin shares. EC '14 page 675-692, New York, NY, USA. Association for Computing Machinery.
Seddighin, M. and Seddighin, S. (2022). Improved maximin guarantees for subadditive and frac- tionally subadditive fair allocation problem. In AAAI 2022, IAAI 2022, EAAI 2022 Virtual Event, February 22 March 1, 2022. AAAI Press.
Steinhaus, H. (1948). The problem of fair division. Econometrica, 16(1).
Uziahu, G. B. and Feige, U. (2023). On fair allocation of indivisible goods to submodular agents.
Varian, H. R. (1973). Equity, envy, and efficiency.
12


Reviews:
[{"review_id": "vtjaMADk5G", "reviewer": "Reviewer_Y5Uh", "summary": "This paper studies the problem of fair division of indivisible goods for XOS valuations. The notion of fairness considered here is the well-studied maximin-share (MMS). While it is known that an MMS allocation may fail to exist, even for additive valuations, obtaining positive results for increasingly better approximations of MMS is an active area of research.\n\nThe paper proves the following two results for the setting of XOS valuations:\n- Existence of a 3/13-MMS allocation. This improves over the previously best known 0.219225-MMS\n- A \"best-of-both-worlds\" result: Existence of a distribution over allocations that is 1/4-MMS ex-ante, and 1/8-MMS ex-post.", "questions": "Questions:\n\n1. In the overview of prior work, it would be nice to mention which of these results from prior work also yield efficient algorithms and which are mainly existential. Could you please comment on this, e.g., regarding the results in table 1? Are they all inefficient algorithms?\n\n2. It would be nice to include a brief discussion on what the obstacles are to further improve the approximation guarantees. Are there fundamental obstacles that would require new techniques, or could the same ideas be pushed further?\n\n\nComments:\n\n- lines 15-20: It is a bit misleading to say that the \"basic scenario\" for fair division is the indivisible setting; this has only been the case in recent years. Traditionally the problem has been studied in the divisible setting \"for decades\".\n\n- table 1: is there a typo in \"log n n\"? perhaps \"n log n\" would be clearer\n\n- line 63: \"envy-free\" has not been introduced yet (even informally)\n\n- line 66: briefly and informally define what is meant by \"best-of-both-worlds\" in this context\n\n- line 68: \"for a more general class of fractionally subadditive valuation functions\": the previous sentence talks about subadditive valuations, so this sentence does not make sense\n\n- line 73: \"fractionally subadditive set functions are closely related to subaddditive set functions\" What do you mean? Isn't the first just a subset of the second?\n\n- line 165: what if u_{i,i'} is not unique?\n\n- line 180: the normalization assumption MMS_i = 1 is something that cannot be achieved efficiently. Is this the only reason why your algorithms are not efficient? I think it would be nice to comment on the non-efficiency of the algorithms more generally in the introduction.\n\n- line 195: Instead of \"determine\", perhaps \"define\" would be more appropriate here\n\n- lines 246-247: the wording of Observation 3.2 is a bit confusing. It doesn't make sense to first say that there is an allocation and then that there is an instance. It should be the other way.\n\n- Lemma 3.3: does your construction use any ideas from existing similar upper bounds?\n\n- Example 3.4: the first sentence does not make sense, since the proof of Observation 3.2 is not included in this version (but only in the full version)\n\n- lines 397-400: is it correct that all of your existential results yield inefficient algorithms? Then why only mention the efficient computation of 1/4-MMS as an open problem, and not the other ones?\n\n\n\n\nTypos:\n\n- line 83: world -> worlds\n- line 100: max -> min\n- line 101: finds -> find\n- line 118: max -> min\n- line 165: am -> an\n- lines 441-447: double citation", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- the problem and results should be of interest to the fair division community\n- technically solid", "weaknesses": "- a bit unclear how new the techniques are, and how they compare to the ones in prior work\n- the writing is a bit confusing at times", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback. We will enhance the writing accordingly for the final version. \n\nRegarding the first question, \n- for Additive valuation, the state-of-the-art gives a constructive algorithm which is not polynomial but yields a PTAS. \n- In Submodular valuation class, a 10/27-MMS allocation can be computed in polynomial time. \n- For Fractionally Subadditive valuation, there is a polynomial algorithm that achieves 1/8 approximation. But the result on the best - approximation factor 0.219225 is existential. \n- In Subadditive valuation, the result on the best approximation factor is existential.\n\nRegarding your second question, to achieve a better approximation with the same technique, one idea would be to allocate more items to agents in the first phase. We believe it promising that this extension gives a better approximation factor; however, the analysis could not be trivially extended and new ideas will be needed for the proof of correctness. The more fundamental obstacle is that using this approach, no matter how many items we allocate in the first phase, the approximation factor converges to 1/4. Thus, in order to improve the approximation factor beyond 1/4, new techniques are required."}, {"review_id": "mtgg3KPI2c", "reviewer": "Reviewer_DbzA", "summary": "This paper focuses on the problem of fair allocation of indivisible items to agents with fractionally subadditive valuations. The authors propose both deterministic and randomized allocation algorithms with improved approximation guarantees for the maximin-share objective. \n\nIn the deterministic setting, the authors provide an algorithm that achieves an approximation guarantee of 3/13 \\approx 0.230, which improves the best-known approximation in the literature. This algorithm also uses the idea of maximizing capped social welfare, but before this step, it carefully analyzed how to allocate large items.\n\nIn the randomized setting, the authors prove that there is a randomized allocation that is 1/4 MMS in expectation, and complement this result with an upper bound of 3/4. The authors also show how to decompose this randomized allocation to deterministic ones that are all 1/8 MMS, which means in the best-of-both-worlds setting, there is an allocation algorithm that achieves an approximation guarantee of 1/4 ex-ante and 1/8 ex-post.", "questions": "How large is the support of the randomized allocation in the best-of-both-worlds setting (in terms of # realizations)?\n\nThanks for the authors' answer in the rebuttal.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Improved approximation guarantees for XOS valuations: The paper proposes a deterministic allocation algorithm with improved approximation guarantees for the maximin-share objective.\n\n2. The best-of-both-worlds setting: The authors show the existence of a randomized allocation that is ¼ MMS in expectation and propose a new decomposition method to decompose the randomized allocation to 1/8 MMS deterministic allocations.", "weaknesses": "1.\tThe results are still not tight, but I do not view this as a drawback. \n\n2.\tIn the best-of-both-worlds setting, the ex-post guarantee 1/4 is worse than the best-known deterministic guarantee. A better ex-post guarantee is expected. Again, I think this is not a drawback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The size of the support is $2$. Due to the space limit, we could not discuss how we convert the fractional allocation into a randomized one. The idea is to construct two allocations such that for all items like $g$ which are fractionally allocated to two agents like $i$ and $j$, $g$ is allocated to $i$ in exactly one of the realizations and to $j$ in the other one."}, {"review_id": "d1UUa9cKAo", "reviewer": "Reviewer_TogA", "summary": "The paper studies fair allocation under fractionally subadditive (XOS) valuations, where a valuation function is XOS if it can be represented by a maximization among a set of additive valuation functions. Both deterministic allocation and randomized allocation settings are considered in the paper. For the deterministic allocation, they improve the previous bound to 3/13; while for the randomized allocation, they obtain an algorithm with 1/4-MMS ex-ante and 1/8-MMS ex-post, which means that for any agent, the expected value obtained from the allocation is at least 1/4-MMS and the worst-case value is at least 1/8-MMS. The negative side is also investigated. The authors show that any randomized allocation algorithm cannot have an ex-ante ratio better than 3/4.  ", "questions": "Considering the special case that the additive functions behind each agent's XOS valuations have a value of either 1 or 0 for each element, any interesting result here?", "limitations": "Yes, the authors state some limitations and future directions in the last section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper makes technical contributions. It improves the previous bound for the deterministic fair allocation under XOS valuations, and obtains the first results for the randomized allocation under the MMS criteria. These results may influence some future works on the fair division area.\n", "weaknesses": "It might be better to present detailed proof of at least one technical lemma in the paper, but I understand that the space is too limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "That is an interesting special case to consider. After receiving your review, we found a negative result that exact $MMS$ allocations cannot be guaranteed in this case. For the positive results, to the best of our knowledge, no better approximation factor is know for this particular setting."}, {"review_id": "IUfB42fH0k", "reviewer": "Reviewer_U5pm", "summary": "This paper considers several classical fair division problems. This paper considers both the deterministic and randomized allocations under the XOS valuations. The XOS valuation is a subclass of the subadditive functions and it generalizes the submodular function. The deterministic allocation is an assignment between a partition of the items and agents. Randomized allocation is a distribution defined over a batch of deterministic allocation. The expectation value of the randomized allocation is called ex-ante, while the ex-post ensures fairness after fixing some outcome. The fairness criteria studied in this paper are MMS and proportional share.\n\nThe main contribution of this work is the existence of a randomized allocation that is 1/4-MMS ex-ante and 1/8-MMS ex-post. They also show that any ex-ante MMS guarantee for randomized allocation is at most 3/4. This is the first known result for randomized allocation under the MMS criteria and the XOS function. Besides this, by extending the technique from the randomized allocation, they also prove that there exists a 3/13-MMS deterministic allocation under the XOS function. This improves the previous best-known result by 0.21.", "questions": "I don't have any specific questions.", "limitations": "This is a theoretical paper, there is no potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I appreciated that the submission is carefully written and structured, so reads well given the technicality of the material. Especially, the flow of the paper is well-designed. The presentation of the algorithmic idea is also clear.\n\n2. The studied problems are classical fair division problems and I also believe that the paper made a solid contribution to the fair division field.\n\n", "weaknesses": "I believe the paper is a quality submission and my evaluation is based on technical contribution. On the downside, I didn't see a clear connection between the studied problem and the machine-learning community. The studied problem is a pretty classical fair division problem and thus the paper seems more suitable for conferences like EC/WINE/AAAI/IJCAI.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:
We found all the comments fair and valid. Therefore, we would like to use this opportunity to thank all the reviewers for the time and effort they dedicated to our paper. We will apply all the comments in the final version.

Meta-review: I am recommending this paper for acceptance. Overall the reviewers were unanimously supportive on this paper, and that it makes a clear theoretical contribution worthy of being presented at NeurIPS (with scores of 3x7s and 1x6). The rebuttal helped clarify some smaller technical concerns.
Decision: Accept (poster)