Plant-and-Steal: Truthful Fair Allocations via Predictions

Authors: ilan reuven cohen
alon  eden
arsen  vasilyan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:07:37

Abstract: We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approximations exist for the problem for any number of agents. When adding incentives to the mix, a jarring result by Amanatidis, Birmpas, Christodoulou, and  Markakis [EC 2017] shows that the best possible approximation for two agents and $m$ items is $\lfloor \frac{m}{2} \rfloor$. We adopt a learning-augmented framework to investigate what is possible when some prediction on the input is given. For two agents, we give a truthful mechanism that takes agents' ordering over items as prediction. When the prediction is accurate, we give a $2$-approximation to the MMS  (consistency), and when the prediction is off, we still get an $\lceil \frac{m}{2} \rceil$-approximation to the MMS (robustness). We further show that the mechanism's performance degrades gracefully in the number of ``mistakes" in the prediction; i.e., we interpolate (up to constant factors) between the two extremes: when there are no mistakes, and when there is a maximum number of mistakes. We also show an impossibility result on the obtainable consistency for mechanisms with finite robustness. For the general case of $n\ge 2$ agents, we give a 2-approximation mechanism for accurate predictions, with relaxed fallback guarantees. Finally, we give experimental results which illustrate when different components of  our framework, made to insure consistency and robustness, come into play.

Main paper: 
 introduction: 
 Allocating items among self interested agents in a "fair" way is an age-old problem, with many applications such as splitting inheritance and allocating courses to students. As a starting point, consider the case of two agents. When the items are divisible, the famous cut-and-choose procedure achieves fairness in two senses. Firstly, no agent wants to switch their allocation with the other; i.e., there is no envy among the agents. Secondly, each agent gets a bundle of items which they value at least as much as their value for all the items divided by 2; that is, each one gets their "fair share". When moving to the case of indivisible goods, which is relevant to scenarios such as splitting inheritance and allocating courses, things get trickier. For instance, if there's a single item, the agent that does not receive that item does not get an envy-free allocation, nor do they get their "fair share" according to the previous definitions. Therefore, it is clear that some fairness needs to be sacrificed in this case.The study of fair allocations with indivisible goods has been a fruitful research direction, with many meaningful notions of fairness studied (see survey by Amanatidis et al. [10] ). In this paper, we focus on the notion of the Maximin Share, or MMS, introduced by Budish [18] . For two agents, this notion captures the value an agent will ensure if we implement the cut-and-choose procedure. That is, assume Alice splits the items into two bundles, and then Bob takes one of them (adversarially), and Alice gets the second one. The MMS captures exactly how much value Alice can guarantee for herself. Generalizing the notion for n agents is pretty straightforward -the MMS is the minimum value Alice can guarantee for herself when she partitions the items into n bundles, assuming n -1 bundles are taken adversarially.We study the case where agents have additive valuations over goods. 1 For the case of two agents, the allocation produced by the cut-and-choose procedure guarantees each of the agents their MMS value. For more than two agents, the existence of such an allocation is not longer guaranteed. Kurokawa et al. [30] show an instance of three agents, where in every allocation, at least one of the agents does not get their MMS value. Since allocating all the agents their MMS value is not always feasible, various papers studied the existence of approximately optimal allocation. An allocation is an α-approximate MMS allocation for α > 1 if every agents gets at least an 1/α fraction of their MMS value. Feige et al. [22] introduce an instance where one cannot find an α-approximate allocation for α < 40 39 . On the other hand, [30] show there always exists 3 2 -approximation. The 3 2 factor was gradually improved [16, 24, 23, 8, 4, 3, 5] , where the state-of-the-art algorithm achieves an approximation of 959/720 < 4/3 [3] . Adding incentives to the mix further complicates matters. Amanatidis et al. [7] study the case of two additive agents, and m items, where the algorithm (or mechanism) does not know the values of the agents. Thus, the algorithm's designer is faced with the task of devising an allocation rule such that (i) agents will maximize their allocated value by bidding truthfully, and (ii) the resulting allocation is an α-approximate MMS allocation for an α close to 1 as possible. [7] show that no incentive-compatible algorithm can approximate the MMS to a factor better than ⌊ m 2 ⌋, and this is matched by the following trivial mechanism -the first agent picks their favorite item, and the second agent gets the rest.For 2 < n < m,2 a trivial truthful algorithm that lets the first n -1 agents pick a single item in some order and gives the last agent the rest achieves an ⌊ m-n+2 2 ⌋-approximation, and no better mechanism is known. It is conjectured that one cannot drop the dependence in m for n > 2. We are left with a stark disparity. On the one hand, assuming agents' values are public information, approximate solutions are known to exist. On the other hand, when considering private values, it seems that only trivial approximations are possible. The goal of this paper is to bridge these two regimes using predictions.We study the problem of truthful allocations that approximate the MMS, taking a learning-augmented point of view. In the learning-augmented framework, the algorithm designer aims to tackle some intrinsic hardness of the problem at hand, which might arise due to computational constraints, space constraints, input arriving piecemeal online, or incentive constraints, among others. To help the designer overcome these constraints, the algorithm is given some side information which is a function of the input, or a prediction, in order to improve the algorithm's performance. The hope is that if the prediction is accurate, then the performance is greatly improved over the performance without the prediction (termed consistency). On the other end, if the prediction is inaccurate then the performance of the algorithm is comparable to the performance of the best algorithm that is not given access to predictions (termed robustness). The learning-augmented framework has proven useful in bypassing impossibilities that arise due to incentive issues [14, 1, 25, 15, 40, 33, 13] .When designing a learning-augmented mechanism, one should think of realistic predictions. For instance, predicting the entire valuation profile of all agents seems to be a strong assumption. A more plausible assumption is to have some ordinal ranking over the items of the agents. Indeed, it seems unlikely that the algorithm can accurately predict Alice's value for a car, but it is plausible that the algorithm can guess that Alice values the car more than she values the table. Ideally, the algorithm's performance should remain robust if the predicted ordering is almost perfect, with only a few pairs of items whose real ordering is swapped in the prediction. Another desired property is to make the prediction as space-efficient as possible, as previous results [20, 31, 32] show that succinct predictions are crucial for learning parameters from few samples and for incorporating a PAC-learnable component in the learning-augmented framework.In this paper we devise learning-augmented truthful mechanisms for the problem of approximate-MMS allocations, while taking into considerations the concerns mentioned above.Our Results. We start by studying the two agent case. We aim at getting: (a) Constant consistency: when the predictions are accurate, we want to get a constant approximation to the MMS. (b) Nearoptimal robustness: when the predictions are off, we want to get as close as possible to the optimal ⌊ m 2 ⌋-approximation we can obtain by truthful mechanisms [7] .Plant-and-Steal Framework. In Section 3 we present a framework for devising learningaugmented mechanisms for approximating the MMS with two agents. As using only predictions does not guarantee any robustness, we use reports to ensure each agent gets at least one valuable item. This is done while maintaining a near-optimal allocation according to predictions. Our framework, which we term Plant-and-Steal, is modular. Along with the set of goods and the agents' reports, it also receives a prediction and an allocation procedure. Different combinations of predictions and allocation procedures yields different consistency-robustness tradeoffs. It is worth noting that, although privacy is not the primary focus of this paper, the Plant-and-Steal framework uses agents' reports in a minimal way, as they are only required to select (i.e. "steal back") a single item from a predefined set of options, where this set is determined by the predictions, and not the actual reports.Ordering Predictions. In Section 4, we study learning-augmented mechanisms when the predictions given are preference orders over items of the agents, rather than the values. We instantiate the Plant-and-Steal framework with a Round-Robin-based allocation procedure. We observe that in the case of two agents, Round-Robin obtains 2-approximation to the MMS. The 2-consistency of using Plant-and-Steal with Round-Robin as the allocation procedure almost immediately follows. The ⌈ m 2 ⌉ robustness follows two facts: (a) Round-Robin produces allocations that are balanced in the number of items allocated to each agent; and (b) The Plant-and-Steal framework ensures each agent gets one of their 2 favorite items according to reports. In Appendix E, we show how to get an improved 3 2 consistency, while maintaining O(m) robustness when using a modified Round-Robin allocation procedure.In Sec 5, we then study the performance of the Plant-and-Steal framework when using the Round-Robin procedure, when the prediction given is not fully accurate, but accurate to some degree. To quantify the prediction's accuracy, we adopt the Kendall tau distance measure. The Kendall tau distance counts the number of pairs of elements swapped in the predicted preference order and the order induced by the true valuations. We show that combining the Plant-and-Steal framework with a Round-Robin allocation procedure obtains O( √ d)-approximation to the MMS when the Kendall tau distance is d. Since d goes from 0 to m 2 = Θ(m 2 ), we recover the constant consistency when there are no errors, and the O(m) robustness when the number of errors is maximal.In Appendix G, we study the two-agent case where the mechanism is given access to predictions which are not necessarily the preference order of the agents. We first show that for any prediction given to the learning-augmented mechanism, no mechanism can simultaneously be α-consistent while maintaining finite robustness for α < 6/5. For the proof, we leverage the characterization of two-agent truthful mechanisms by [7] .We then study small-space predictions. The Round-Robin-based mechanisms described above require an Ω(m)-bit prediction (to describe an arbitrary allocation of items). We first notice that we can implement a bag-filling type allocation procedure using O(log m)-bit predictions. This already achieves a constant consistency along with O(m) robustness. We then devise a more refined allocation procedure, which requires O(log m/ϵ)-bit predictions, and achieves 2 + ϵ consistency along with ⌈ m 2 ⌉ robustness.General number of agents n. In Appendix H, we devise a learning-augmented truthful mechanism for n ≥ 2 additive agents. We obtain a 2-consistent mechanism, while relaxing the robustness guarantees of the mechanism. We take a similar approach to the work of [18, 27, 28, 2, 5] , who compete against a relaxed benchmark of the MMS value for n > n agents, and try to minimize n. We obtain an max{m -n -1, 1}-approximation to the MMS for n = ⌈ 3n 2 ⌉ agents when the predictions are off. Our mechanism uses the modified Round-Robin procedure from [8] to determine the initial allocation using the predictions. It then applies a recursive plant-and-steal procedure to determine the final allocation.Experiments. Finally, In Section 6, we demonstrate how several components in our design come into play when experimenting with synthetic data. We run different variants of mechanism on two player instances, and show that when predictions are accurate, then only using predictions is nearly optimal, if predictions are noisy, then the stealing component ensures robustness, and our Plant-and-Steal framework achieves best-of-both-worlds guarantees.We summarize the bounds we obtain in Table 1 .Ordering predictions,n = 2 2 ⌈ m /2⌉ Section 4 3/2 ⌊ 2m /3⌋ Section 4 ≥ 5/4 Any [6] Arbitrary predictions, n = 2 Any ≥ ⌊ m /2⌋ [7]≥ 6/5 Bounded Section G.1 3 log m + 1 space 4 m -1 Section G.2 O(log(m)/ϵ) space 2 + ϵ ⌈ m /2⌉ Section G.3 n > 2 2 m -⌈ 3n /2⌉ -1 for n = ⌈ 3n /2⌉ 
preliminaries: 
 In the setting we study, there is a set N of n agents and a set M of m indivisible items. Each agent has a private additive valuation over the items, unknown to the mechanism designer, where the value of agent i for item j is v ij (also denoted as v i (j)). For a bundle S ⊆ M of items, v i (S) = j∈S v ij .The fairness notion we focus on is the following. Definition 2.1 (Maximin Share). The Maximin Share (MMS) of agent i with valuation v i and n agents isµ n i = max S1 • ... • Sn=M min j∈[n] v i (S j );that is, if i were to partition the items into n bundles, and then n -1 of those bundles are taken adversarially, what is the value i can guarantee for themselves. When clear from the context, we omit n and use µ i to denote the MMS of i with n agents.We are interested in mechanisms that produce approximately optimal allocations, as defined next.Definition 2.2 ((γ, k)-approximate MMS Allocation). An allocation X = (X 1 , . . . , X n ) is (γ, k)- approximate MMS allocation for γ > 1 and a natural number k if for every agent i, v i (X i ) ≥ µ k i /γ. When k = n,we say the allocation is a γ-approximate MMS allocation.We study mechanism that get some prediction on the input. Definition 2.3 (Learning-Augmented Mechanism). A learning-augmented mechanism takes agents' reports r = (r 1 , . . . , r n ) and predictions p in some prediction space P, and outputs a partition of the itemsX(r, p) = (X 1 (r, p), X 2 (r, p), . . . , X n (r, p)), X 1 (r, p) • X 2 (r, p) • . . . • X n (r, p) = M,where agent i gets X i (r, p).For learning-augmented mechanisms, truthfulness should hold for any possible prediction p. Definition 2.4. A learning-augmented mechanism is truthful if for every agent i and every possible report of other agents r -i and every possible prediction p,v i (X i (v i , r -i , p)) ≥ v i (X i (r i , r -i , p))for every r i .We next define the consistency and robustness measures according to which we measure the performance of our mechanisms. Definition 2.5 (α-consistency). Consider a prediction function f P which takes a valuation profile and outputs a prediction in prediction space P. A learning-augmented mechanism is α-consistent for α > 1 and prediction function f P if for every valuation profile v and every prediction p = f P (v), X(v, p) is an α-approximate MMS allocation. Definition 2.6 ((β, k)-robust). A learning-augmented mechanism is (β, k)-robust for β > 1 and natural number k if for every valuation profile v and every prediction p, X(v, p) is an (β, k)approximate MMS allocation. If k = n, we say the mechanism is β-robust.For ease of presentation, for valuation v i , report r i and prediction p i , we use v ℓ i , r ℓ i , p ℓ i to denote both the ℓ th highest good according to the valuation/report/prediction and its value. Note that, we may use v ℓ i for ℓ > m, in this case, v ℓ i = 0. For ℓ = 1, i.e., the highest good we use v * i , r * i , p * i .Ordering Predictions and Kendall tau Distance. Most of our mechanisms use predictions which take the form of an ordering over agents' items. That is, f P (v) outputs a vector of orderings p = (p 1 , . . . , p n ), where p ℓ i is the ℓ th highest valued item of i in M according to p. Accordingly, for agent i, let v ℓ i be the ℓ th highest valued item according to v. For two items j ̸ = j ′ , We use j ≻ pi j ′ to denote that j is higher ranked than j ′ according to p.When studying imprecise predictions, we want to quantify the degree to which the prediction is inaccurate. For this, we use the following measure. For an agent i, we define our noise level with respect to the Kendall tau distance (also known as bubble-sort distance) between v and p. Definition 2.7 (Kendall tau distance). The Kendall tau distance counts the number of pairwise disagreements between two orders. For i's valuation v i and predicted preference order p i , we defineK d (v i , p i ) = |{j ≻ pi j ′ : v i (j) < v i (j ′ )}.That is, the number of pairs of items where the prediction got their relative ordering wrong. We also denoteK d (v, p) = max{K d (v 1 , p 1 ), K d (v 2 , p 2 )}.We note that the Kendall tau distance between v i and p i , K d (v i , p i ), can go from 0 to m 2 .3 Plant-and-Steal FrameworkIn this section, we present the framework which is used to devise learning-augmented mechanisms for two agents. The ideas presented here also inspire the more complex learning-augmented mechanism for n > 2 agents. Missing proofs of this section appear in Appendix C. Our framework, which we term Plant-and-Steal is given the set of goods, an allocation procedure A, the prediction p and reports v. The framework operates as follows:1. It first applies A on the predictions p to divide the set of goods into two bundles A 1 , A 2 .The procedure A should be an allocation procedure with good MMS guarantees. We use different allocation procedures depending on the type of prediction given and on the consistency-robustness tradeoffs we are aiming for. 2. Planting phase: For each agent i, it picks i's favorite item in set A i according to prediction, and "plants" this item in the bundle A j of the other agent j ̸ = i. Let T 1 , T 2 denote the sets that result in this planting phase.ℓ ̸ = j r : (a) Let S ℓ = L 1 ∪ {j ′ ∈ S : j ′ ≤ j ℓ } and S r = L 2 ∪ {j ′ ∈ S : j ′ > j r }. (b) If v 1 (S ℓ ) < v 1 (S r ) : • j ℓ := j ℓ + 1. (c) Else:• j r := j r -1.3. Set j := j ℓ = j r .We consider two cases:Case 1: j = 0 (or symmetrically, j = m). Without loss of generality, suppose that j = m. We first show that if v 1 (S 1 ) < v 1 (S 2 ) then min{v 1 (S 1 ), v 1 (S 2 )} = µ 1 . Notice that since S 1 gets all the small items, it must be the case that v 1 (L 1 ) < v 1 (L 2 ). Suppose there's a different partitionT 1 • T 2 such that min{v 1 (T 1 ), v 1 (T 2 )} > min{v 1 (S 1 ), v 1 (S 2 )}. Without loss of generality, let v 1 (T 1 ∩ L) ≤ v 1 (T 2 ∩ L) (otherwise,. By the definition of L 1 , L 2 , it must be the case that v 1 (L 1 ) ≥ v 1 (T 1 ∩ L). Thus, Since T 1 \ (T 1 ∩ L) ⊆ S, it must be thatv 1 (S 1 ) = v 1 (L 1 ) + v 1 (S) ≥ v 1 (T 1 ∩ L) + v 1 (T 1 \ (T 1 ∩ L)) = v 1 (T 1 ) ≥ min{v 1 (T 1 ), v 1 (T 2 )}, a contradiction.On the other hand, ifv 1 (S 1 ) ≥ v 1 (S 2 ) = v 1 (L 2 ), by condition 2b of the above procedure, it must be the case that when j ℓ was equal m -1,v 1 (S ℓ ) < v 1 (S r ) = v 1 (L 2 ) = v 1 (S 2 ). Thus, v 1 (S 1 ) = v 1 (S ℓ ) + v 1 (m) < v 1 (S 2 ) + ϵµ 1 /4.We get thatEQUATIONwhere the second inequality follows since2µ 1 ≤ v 1 (S 1 ) + v 1 (S 2 ).Case 2: 0 < j < m. In this case, since both j ℓ and j r were moved, there were some values of j ℓ and j r such that v 1 (S ℓ ) ≤ v 1 (S r ) and some values such that v 1 (S ℓ ) > v 1 (S r ). Assume initially that v 1 (S ℓ ) ≤ v 1 (S r ). Since at each step of the procedure, the the lower-valued bundle can increase by at most ϵµ 1 /4, when the first item is added to S ℓ such that v 1 (S ℓ ) > v 1 (S r ), it must be the case that v 1 (S ℓ ) ≤ v ( S r ) + ϵµ 1 /4. It is easy to see that the invariant where |v 1 (S ℓ ) -v 1 (S r )| ≤ ϵµ 1 /4 is kept throughout the run of the procedure. Therefore, this also holds for the final S 1 and S 2 . Thus, we can use the same reasoning of Eq. ( 7) to conclude that min{v 1 (S 1 ),v 1 (S 2 )} ≥ (1 -ϵ/8)µ 1 .Thus, the sets S 1 and S 2 have a form S 1 = L 1 ∪ (S ∩ [1, j]) and S 2 = L 2 ∪ (S ∩ [j + 1, m])′ in [k 1 ] such that |[α, β] ∪ [α ′ , β ′ ]| = k 2 and i∈[α,β]∪[α ′ ,β ′ ] f (i) k 2 ≤ i∈[k1] f (i) k 1Proof. We prove the lemma using the probabilistic method. Let j be a uniformly random integer in [k 1 ], and choose α, β, α ′ and β ′ such that[α, β] ∪ [α ′ , β ′ ] = {j, j + 1 mod k 1 , • • • , j + k 2 -1 mod k 1 }.We see that indeed a set chosen as above can be represented as a union of two intervals. Now, since j is chosen uniformly at random form [k 1 ], we see that for every element i in [k 1 ] we havePr j∼[k1] [i ∈ {j, j + 1 mod k 1 , • • • , j + k 2 -1 mod k 1 }] = k 2 k 1 .Thus via linearity of expectation we have:E j∼[k1]   1 k 2 i∈{j,j+1 mod k1,••• ,j+k2-1 mod k1}} f (i)}   = 1 k 1 i∈[k1] f (i).Thus, since f (i) is non-negative for all values of i, we see that for some specific choice of j it has to be the case that1 k 2 i∈{j,j+1 mod k1,••• ,j+k2-1 mod k1}} f (i)} ≤ 1 k 1 i∈[k1] f (i),which finishes the proof. Now, we apply the lemma above. If m < 4⌈ t ϵ ⌉ + 2 we can satisfy Proposition G.2 by:1. First choosing a partition M = S 1 • S 2 such that min(v 1 (S 1 ), v 1 (S 2 )) ≥ µ 1 and |R 1 | ≥ |R 2 |.2. Define L 2 := S 2 , put the smallest ⌊m/2⌋ -|S 2 elements of S 1 into S, and define L 1 to contain the rest of elements in S 1 . 
stealing phase:: 
 To obtain the final allocation, each agent i now "steals" back their favorite item from set T j of agent j ̸ = i according to reports. Notice this is the first and only place where we use agents' reports.This procedure is trivially truthful because the only step where we use agents' reports is the one where they pick exactly one item to steal back from T j , and this T j only depends on predictions, and not reports (Lemma 3.1). To obtain robustness, we notice that each agent gets one of their two favorite items according to their true valuations (Lemma 3.2). This implies a robustness of m -1.We show that for balanced allocations, we get improved robustness guarantees (Lemma 3.4).For S ⊆ M , and agent i, let v * i (S) (p * i (S),r * i (S)) be the max valued item in S according to v i (p i , r i ). for g ∈ M and S ⊆ M , denote S + g := S ∪ {g} and S -g = S \ {g}. The Plant-and-Steal framework is presented in Mechanism 1. ← p * 1 (A1) ĵ2 ← p * 2 (A2) T1 ← A1 + ĵ2 -ĵ1 T2 ← A2 + ĵ1 -ĵ2 /* Steal according to report */ j1 ← r * 1 (T2) j2 ← r * 2 (T1) X1 ← T1 + j1 -j2 X2 ← T2 + j2 -j1We show that for any allocation function A and predictions p given to the framework, the resulting mechanism is truthful. Lemma 3.1 (Truthfulness Lemma). For any allocation procedure A, Plant-and-Steal mechanism using A is truthful.Since the framework is truthful, from now on, we assume that r = v. Next, we show that the Plant-and-Steal mechanism ensures that for each agent, an item is allocated with a value that is at least as good as their second-best option according to their value. Lemma 3.2. Consider the allocation (X 1 , X 2 ) returned by Plant-and-Steal with some allocation procedure A. For any agent i, thenv 1 i ∈ X i or v 2 i ∈ X i .We next claim that if i gets one of their two favorite items and any k -1 additional items, i's value is an m -k-approximation to µ i . Lemma 3.3. For any agent i, let S ⊆ M be a subset of the items of size|S| = k and v 1 i ∈ S or v 2 i ∈ S then v i (S) ≥ µ i /(m -k).We immediately get the following. Lemma 3.4 (Robustness Lemma). Let A be an allocation rule guaranteeing min{|A 1 |, |A 2 |} ≥ k, then when Plant-and-Steal uses A, the resulting mechanism is (m -k)-robust.Proof. By Lemma 3.2, we are guaranteed that each agent gets one of their two favorite items according to their report. Combining with the condition on A and Lemma 3.3, the proof is finished.1 = α 3 = 1, β 1 = β 3 = m, α 2 = β 2 = α 4 = β 4 = m + 1.Overall, this allocates S ′ to be the bottom ⌊m/2⌋ elements of S 1 . We see that this suffices to guarantee the properties that S ′ needs to satisfy in Proposition G.1.Therefore, henceforth we can assume that m > 4⌈t ϵ ⌉ + 2. Since |S 1 | ≥ m/2 and |L 1 | ≤ 8 ϵ + 2, and S 1 = L 1 ∪ (S ∩ [α 1 , β 1 ]) this implies that |S ∩ [α 1 , β 1 ])| > 3 t ϵ > m/2 Thus, we can ensure that |S ′ | = ⌊m/2⌋ -|S 2 | using a subset S ′ ⊂ S ∩ [α 1 , β 1 ]). If |S 2 | = 1 we only need choose S ′ to satisfy |S ′ | = ⌊m/2⌋ -|S 2 | and v 1 (S ′ ) ≤ v 1 (S 1 \ { ĵ, ĵ′ })/2.First of all, since every element in L 1 is larger than any element in S ∩ [α 1 , β 1 ]), we see that this is also true in averageEQUATIONThen, applying Lemma G.3 to the set S ∩ [α 1 , β 1 ]) we see that there exist disjoint subsetsEQUATIONCombing Equations 8 and 9, we see that takingS ′ = S ∩ ([α 3 , β 3 ] [α 4 , β 4 ]) satisfies v 1 (S ′ ) ≤ v 1 (S 1)/2 and the other requirements of Proposition G.1.Now, suppose |S 2 | > 1.Since by Proposition G.2, the set S does not contain the two largest elements ĵ and ĵ′ of S 1 , as well as the fact that every element in L 1 is at least as large as any element in S ∩ [α 1 , β 1 ]), we see that every every element inS 1 \ { ĵ, ĵ′ } is either in S ∩ [α 1 , β 1 ]) or greater than every element in S ∩ [α 1 , β 1 ]). this implies that:EQUATIONThen, we can again apply applying Lemma G.3 to the set S ∩ [α 1 , β 1 ]) we see that there exist disjoint subsetsEQUATIONCombing Equations 10 and 11, we see that takingS ′ = S ∩ ([α 3 , β 3 ] [α 4 , β 4 ]) satisfies v 1 (S ′ ) ≤ v 1 (S 1 \{ ĵ, ĵ′ })/2 as required in Proposition G.1. Note that this also implies that v 1 (S ′ ) ≤ v 1 (S 1 })/2 since ĵ, ĵ′ have the top two largest values of v 1 in S 1 .Overall, this finishes the proof of Proposition G.1.G.5 Proof of (2 + ϵ)-consistency.It remains to show that the algorithm is 2 + ϵ-consistent. We will be referencing the variables ĵ1 , ĵ2 , j1 , j2 , T 1 and T 2 within the Plant-And-Steal framework (Algorithm 1).We first reason about agent 2. First, notice that since agent 2 has a higher value for Si2 ,v 2 ( Si2 ) ≥ µ 2 .Since the mechanism had a chance to pick item ĵ2 from T 1 as j2 , it must be the case that v 2 ( j2 ) ≥ v 2 ( ĵ2 ) (and possibly j2 = ĵ2 ). If j1 = ĵ1 , then T 2 \ j1 = Si2 \ ĵ2 , andµ 2 ≤ v 2 ( Si2 ) = v 2 ( Si2 \ ĵ2 ) + v 2 ( ĵ2 ) ≤ v 2 (T 2 \ j1 ) + v 2 ( j2 ) = v 2 (X 2 ).Otherwise, j1 ∈ Si2 , andEQUATION)Since ĵ2 is the item with the highest value for agent 2 in Si2 , v 2 ( j2 ) ≥ v 2 ( ĵ2 ) ≥ v 2 (k 1 ). Combining with Eq. ( 12), we get thatv 2 (T 2 \ j1 ∪ { j2 }) ≥ v 2 ( Si2 \ ĵ2 ). Moreover, v 2 (T 2 \ j1 ∪ { j2 }) ≥ v 2 ( j2 ) ≥ v 2 ( ĵ2 ). Thus, v 2 (X 2 ) = v 2 (T 2 \ j1 ∪ { j2 }) ≥ v 2 ( Si2 )/2 = µ 2 /2, as desired. It is left to show that v 1 (X 1 ) ≥ µ 1 /(2 + ϵ). If i 1 = 2, then v 1 ( Si1 ) = v 1 ( S2 ) ≥ v 1 (S 2 ) ≥ (1 -ϵ/4)µ 1 .In this case, the same exact arguments used for agent 2 can be harnessed to show that v 1 (X 1 ) ≥ (1 -ϵ/4)µ 1 /2 ≥ µ 1 /(2 + ϵ). Thus, it is left to consider the case where i 1 = 1.Consider the (S 1 , S 2 ) partition that is set in the first step of Cut-and-Balance-and-Choose. Since v 1 (S ′ ) ≤ v 1 (S 1 )/2, we havev 1 ( S1 ) ≥ v 1 (S 1 )/2 ≥ (1 -ϵ/4)µ 1 /2 ≥ µ 1 2 + ϵ .If j2 = ĵ2 , we have thatv 1 (X 1 ) = v 1 ( S1 ∪ { j1 } \ { ĵ1 }) ≥ v 1 ( S1 ) ≥ µ 1 2 + ϵ ,where the first inequality follows since v 1 ( j1 ) ≥ v 1 ( ĵ1 ).Note also that if|S 2 | = 1 i.e., S 2 = {a}, if ĵ2 ̸ = a then v 1 (X 1 ) ≥ v 1 (S 2 ) since a ∈ T 2 , similarly if j2 ̸ = a then v 1 (X 1 ) ≥ v 1 (S 2 ), finally we have ĵ2 = k 2 = a and v 1 (X 1 ) ≥ µ 1 /(2 + ϵ) an in the first case.Therefore, we assume j2 ̸ = ĵ2 and |S 2 | > 1, and let ĵ′1 ∈ arg max j∈ S1\{ ĵ1} v 1 (j) v 1 (X 1 ) = v 1 (T 1 ∪ { j1 } \ { j2 }) = v 1 (T 1 ) + v 1 ( j1 ) -v 1 (k 2 ) ≥ v 1 ( S1 ∪ { ĵ2 } \ { ĵ1 }) + v 1 ( ĵ1 ) -v 1 ( j2 ) ≥ v 1 ( S1 \ { ĵ1 }) + v 1 ( ĵ1 ) -v 1 ( j2 ) = v 1 (S 1 \ S ′ \ { ĵ1 }) + v 1 ( ĵ1 ) -v 1 ( j2 ) ≥ v 1 (S 1 \ S ′ \ { ĵ1 }) + v 1 ( ĵ1 ) -v 1 ( ĵ′ 1 ) = v 1 (S 1 \ S ′ \ { ĵ1 , ĵ′ 1 }) + v 1 ( ĵ1 ), where the first inequality is since, v 1 j1 = max j∈T2 v 1j ≥ v 1 ĵ1 . The second inequality is since v 1 ( ĵ2 ) ≥ 0, the third inequality is by ĵ′ 1 definition since j2 ∈ S1 \ ĵ1 by our assumption that k 2 ̸ = ĵ2 . Finally, we have have|S 1 \ S ′ \ { ĵ1 , ĵ′ 1 }| ≥ |S ′ | since |S 1 | -2 -|S ′ | = |S 1 | -2 -(m/2 -|S 2 |) = |S 1 | -2 -(m/2 -(m -|S 1 |)) = m/2 -2 ≥ |S ′ |,where the last inequality is since |S 2 | > 1. Since we handles the case |S 2 | = 1 earlier, we can here assume|S 2 | > 1 in which case the set S ′ is required to satisfy v 1 (S ′ ) ≤ v 1 (S 1 \ { ĵ, ĵ′ })/2. Therefore, we have v 1 (S 1 \ S ′ \ { ĵ1 , ĵ′ 1 } ≥ v 1 (S ′ ). (1 -ϵ/4)µ 1 ≤ v 1 (S 1 ) = v 1 (S 1 \ S ′ \ { ĵ1 , ĵ′ 1 }) + v 1 ( ĵ1 ) + v 1 ( ĵ′ 1 ) + v 1 (S ′ ) ≤ v 1 (S 1 \ S ′ \ { ĵ1 , ĵ′ 1 }) + 2 • v 1 ( ĵ1 ) + v 1 (S ′ ) ≤ 2 • v 1 (S 1 \ S ′ \ { ĵ1 , ĵ′ 1 }) + 2 • v 1 ( ĵ1 ) ≤ 2 • v 1 (X 1 ), which implies that v 1 (X 1 ) ≥ µ12+ϵ , finishing the proof.In this section we provide a learning-augmented mechanism for n > 2 agents, Learning-Augmented-MMS-for-n-Agents. The mechanism we devise ensures that if the predictions are accurate, then each agent gets an allocation with value at least µ n i /2 (2 consistency). On the other hand, we show that for any prediction, every agent gets at least µ n i /α for n = ⌈3n/2⌉ and α = max{m -n -1, 1} (robustness). Theorem H.1. The Learning-Augmented-MMS-for-n-Agents Mechanism (Mechanism 6) is truthful, 2-consistent and (µ n i /α)-robust for n = ⌈3n/2⌉ and α = max{m -n -1, 1}.The final phase in the mechanism is a recursive plant and steal algorithm. The input to this algorithm is an ordered set of agents N , along with their predictions, reports, and a tentative allocation for each agent. At each recursive invocation, the algorithm splits the set of agents into two (almost) equal-size ordered sets N 0 and N 1 . Then the mechanism "plants" for the i th agent in each set N b their highest (according to predictions) valued item in their tentative allocation in the tentative set of the i th agent in N ¬b . Then we perform one round of Round-Robin, where the items available to the agents of set N b are those tentatively allocated to the agents of N ¬b (after the planting phase), and the allocations are determined according to agents reports. See Figure 3 for an illustration of a single round of plant and steal. The algorithm then recurses on each of the sets N 0 and N 1 , until all sets are of size 1. At this point, the single agent in the set is further allocated its remaining tentatively allocated items, and the process terminates. Let i 0 , i 1 denote the i th agent in N0, N1 respectively.j * 0 = p * i 0 (Ai 0 ) j * 1 = p * i 1 (Ai 1 ) A i 0 = A i 0 + j * 1 -j * 0 A i 1 = A i 1 + j * 0 -j * 1 /* Plant in's favorite item in a tentative set */ if par = 1 then i 0 = in,i 1 = i2 j * 0 = p * i 0 (A i 0 ) A i 1 = A i 1 + j * 0 , A i 0 = A i 0 -j * 0 /* Steal from the opposite set according to reports */ foreach b ∈ {0, 1} do X=Allocate-Best(N b , AN ¬b , r) foreach i ∈ N do Xi ← Xi ∪ Xi /* Reverse the order after the first level of recursion */ if first-level-flag then N0 ← (i |N |-1+par , . . . , i3, i1) N1 ← (i |N |-par , . . . i4, i2) /* Recursively invoke Split-Plant-Steal-Recurse on each set */ foreach b ∈ {0, 1} do Split-Plant-Steal-Recurse(N b , AN b , XN b ,first-level-flag = False)Given the above implementation details, it remains to prove Theorem H.1 regarding truthfulness, consistency and robustness of the mechanism. The proof is given in Appendix H.3.In this section we prove Theorem H.1, which we now recall. Theorem H.1. The Learning-Augmented-MMS-for-n-Agents Mechanism (Mechanism 6) is truthful, 2-consistent and (µ n i /α)-robust for n = ⌈3n/2⌉ and α = max{m -n -1, 1}.First, we give a simple observation regarding Algorithm 7.which in particular contains j. Hence, the first item in A 1 is allocated into X 1 . We now assume the claim holds for k = 1 and ℓ -1 and prove it for ℓ. Assume without loss of generality that ℓ is odd so that i ℓ ∈ N 0 .In step ℓ of the planting phase, the mechanism plants ℓ 0 's (the proof for ℓ 1 is identical) first (according to value p ℓ 0 ) item in A ℓ 0 . Then, during the tentative allocation phase, agent ℓ 0 is the ℓ th to choose among the items in A N1 minus the items that were allocated to the ℓ -1 agents that were before her in the tentative Round-Robin. By the induction hypothesis, every agent preceding her chose the item the mechanism planted for them previously in that round. Therefore, the item j that the mechanism planted for agent ℓ 0 is still available. Moreover, let M ℓ-1 denote the set of items after ℓ -1 rounds of the tentative Round-Robin in Algorithm 9. Further let A ℓ-1 N1 denote the set of items after ℓ -1 rounds of the Allocate-Best algorithm invoked in the stealing phase with the set N 0 , i.e., A ℓ-1 N1 = A N1 \ j∈N0,j<ℓ {X j }. Since the order in which the agents plant and steal in each round of the recursion is equivalent to the order in which the corresponding tentative allocation round was performed, it holds that A ℓ-1 N1 ⊂ M ℓ-1 . Since j = p * ℓ 0 (M ℓ-1 ), and p ℓ 0 = r ℓ 0 , it holds that r * ℓ 0 (A ℓ-1 N1 ) equals j. Therefore ℓ 0 will choose j to X ℓ 0 as claimed. Proving the claim for a general k is almost identical. At the planting phase of the k th round, the mechanism plants for every agent ℓ 0 ∈ N k 0 their k th item of A i in A N k 1 and vice versa. A similar argument to the one above, shows that this item will remain available until its their turn to choose an item for allocation, as by the recursion hypothesis, all agents preceding i in the Round-Robin will select the items the mechanism planted for them. Hence, the k th item in A ℓ 0 will be allocated to X ℓ 0 . Finally, once the set agent i belongs to becomes a singleton, by our halting condition, X i ← X i ∪ A i , so together with the previous argument, we get that for every ℓ, X i = A i as needed.We continue to prove that the mechanism is robust. Since when m < n, µ n i = 0 for every agent i, and each agent trivially gets their MMS value, we assume from now on that m ≥ n and show the mechanism achieves (m -n -1)-robustness for µ n i . We first prove in Lemma H.3 that for each agent i, v i (X i ) ≥ v ⌈3n/2⌉ i , and then prove in Lemma H.5 that the value of this item is not too small compared to µ ⌈3n/2⌉ i . Lemma H.3. For every agent i, v i (X i ) ≥ v ⌈3n/2⌉ i . Proof. We first prove the claim for agents that were allocated a value during the invocation of Algorithm 7. By the definition of the algorithm and its truthfulness when agent i is allocated an item, at most n -1 items were previously allocated to other agents. Hence, she can always choose her n th highest valued item. Therefore, we havev i (X i ) ≥ v n i ≥ v ⌈3n/2⌉ i , as claimed.We continue to prove the claim for the set of agents with no large predicted values. Consider the ℓ th agent in N , i ℓ , and consider the following coloring process. Initially, color all items in M black. We will then color all items i ℓ was able to choose from green, and items allocated before she had the chance to choose from gray (note that these colors are unrelated to the ones in the figure). Note that an item turns green when it belongs to the tentative allocation of opposite set to i ℓ 's and has not been taken by agents preceding her in the allocation order. We claim that by the time no black items remain, at most ⌈3n/2⌉ -1 have turned gray, implying that at some point during the recursion, i ℓ could have chosen their ⌈ 3n 2 ⌉ th highest valued item (according to r i ℓ ). We let N k denote the set of agents to which i ℓ belongs to at depth k of the recursion, starting withN 1 = N . At each recursive call, N k is partitioned into N k 0 , N k 1 .We further let b k ∈ {0, 1} denote the index of the set to which i ℓ belongs to: i ℓ ∈ N k b k . We will separately bound the number of items turned gray due to agents in N k b k and N k ¬b k . In the first iteration, for k = 1, let A 1N 1 b 0 , A 1 N 1 ¬b 0denote the tentative sets allocated to the agents of N 1 0 and N 1 1 after the planting phase (i.e., at the beginning of the stealing phase). The number of items that turn gray due to agents in N 1 b 1 is G 1 b 1 = ⌈ℓ/2⌉ -1, since i ℓ has access to all items in A 1 N ¬b 1 excluding the ⌈ℓ/2⌉ -1 items that were allocated to the agents in her set preceding her in the ordering. (The rest of the items in A 1 N ¬b 1 turn green.)Turning to G 1 ¬b 1 , each agent in the opposite set to hers, N 1 ¬b 1 , is allocated a single item (from A 1N 1 b 1) before continuing to the next round of the recursion. Therefore, G 1 ¬b 1 = |N 1 ¬b 1 | (and no item turns green).The recursion then continues with N 2 = N 1 b 1 and in reversed order (due to the order being reversed). Therefore, at the beginning of the second iteration, i ℓ is in location |N 1 b 1 | -⌈ℓ/2⌉ in N 2 . After the partition phase, i ℓ is in set N 2 b 2 and in location ⌈|N 1 b 1 |-⌈ ℓ 2 ⌉ 2 ⌉. Hence, G 1 b 1 = ⌈ |N 1 b 1 |-⌈ ℓ 2 ⌉ 2⌉ -1 due to agents in her set preceding here in the ordering. Also, G 1 ¬b 1 = |N 1 ¬b 1 | due to allocations to agents in the opposite set to hers.From now on, the order is preserved, so for every k ≥ 3,G k b k = |N k b k | and G k ¬b k = ⌈ |N 1 b 1 |-⌈ℓ/2⌉ 2 k-1 ⌉ -1.We continue by bounding . Hence, we have the following recursion formula. For even ℓ, T (ℓ) = ℓ/2 + T (ℓ/2), and for odd ℓ, either (a) T (ℓ) = ⌈ℓ/2⌉ + T (⌊ℓ/2⌋) or (b) T (ℓ) = ⌊ℓ/2⌋ + T (⌈ℓ/2⌉). In Claim H.4 below, we prove that for such a function, if it also holds that T (1) = 0 and T (2) = 1, then T (ℓ) ≤ ℓ -1. Therefore, we get that⌈log n⌉ k=1 G k ¬b k = ⌈log n⌉ k=1 |N k ¬b k |. Observe that if N k is even then N k b k = N k ¬b k = N k /2,⌈log n⌉ k=1 G k ¬b k ≤ n -1.We continue to bound⌈log n⌉ k=2 G k ¬b k = ⌈log n⌉ k=2 ⌈ |N 1 b 1 |-⌈ℓ/2⌉ 2 k-1 ⌉ -1. The sum ⌈log X⌉ k=1 ⌈ X 2 k ⌉ can be bounded by ⌈log X⌉ k=1 X 2 k + L,where L is the number of indices k for which the fraction X/2 k is rounded up. Observe that for every X, L can be bounded above by ⌈log X⌉ as L exactly equals the number of 1 bits in the binary representation of X. Hence, the overall number of items that turn gray can be bounded as follows:G ⌈log n⌉ = ⌈log n⌉ k=1 G k ¬b k + G k b k ≤ n -1 + ⌈ℓ/2⌉ -1 + ⌈log n⌉ k=2 ⌈n/2⌉ -⌈ℓ/2⌉ 2 k-1 -1 ≤ n -1 + ⌈ℓ/2⌉ -1 + ⌈n/2⌉ -⌈ℓ/2⌉ + ⌈log n⌉ -⌈log n⌉ + 1 ≤ ⌈3n/2⌉ -1.Therefore, the number of items that turn gray by the end of the recursion is at most ⌈3n/2⌉ -1, and so i ℓ get their ⌈3n/2⌉ highest valued item v ⌈3n/2⌉ i ℓ .We now prove the claim regarding the cost of the recursion that was used in the previous lemma. Proof. We prove the claim by induction on n. By T (1) = 0 and T (2) = 1 so the induction basis holds. We now assume correctness for all values smaller than n and prove for n.If n is even then Finally, we prove that the highest valued item allocated to each agent i is not too small compared to their MMS. Lemma H.5. Consider an MMS for agent i, and let j * be the highest valued item of i in her allocation.T (n) = n/2 + T (n/2) ≤ n/2 + n/2 -1 = n -1,Then v i (j * ) ≥ µ ⌈3n/2⌉ i /α for α = m -⌈3n/2⌉ -1.Proof. Consider an MMS allocation of M for k = ⌈3n/2⌉, and let A i be the set such that v i (A i ) = µ k i . By the assumption on j * , its value is higher then the highest valued item inA i , v i (j * ) ≥ v 1 i (A i ). Therefore, v i (A i ) ≤ |A i | • v i (j * ), implying v i (j * ) ≥ v i (A i )/|A i | = µ k i /|A i |. Since |A i | ≤ m -k -1 (as at least k -1 items must be allocated to the k -1 additional agents, it holds that v i (j * ) ≥ µ 3n/2 i /(m -⌈3n/2⌉ -1).Proof of Theorem H.1. The theorem follows by Lemmas H.1, H.2, H.3, and H.5.Justification: This is mainly a theoretical paper, and all the assumptions are clearly stated.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: The paper contains a detailed preliminary section where the model is fully described. The theorems and complete, and the ones not appearing in the body appear in the appendix.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
ordering predictions: 
 In this section, we consider the case of two agents, where the predictions (and in fact, also the reports) given to the mechanism are preference orders of agents over items. Our mechanisms makes use of the Plant-and-Steal framework instantiated by Round-Robin based allocation procedures. We first present the round-robin allocation procedures we'll use, and give their approximation guarantees when the input is accurate. Next, we prove the robustness and consistency guarantees. Finally, we quantify the accuracy of the predictions using the Kendall tau distance, and obtain fine-grained approximation results, where the approximation smoothly degrades in the accuracy.Amanatidis et al. [6] studied mechanisms where the preference orders of the agents over items are public (while valuations are private). They showed that no truthful mechanism can achieve a better approximation than 5/4 in this setting. This implies that when the predictions are preference orders, no learning-augmented mechanism can obtain consistency better than 5/4, no matter if the robustness is bounded or not. Proposition 4.1 (Corollary of Amanatidis et al. [6] ). For any ϵ > 0, no mechanism that is given preference orders as predictions can obtain consistency 5/4 -ϵ.Round-Robin Allocation Procedures. The two allocation procedures we use to instantiate the Plant-and-Steal framework take as input preference orders of agents over items:• Balanced-Round-Robin: the agents take turns, and at each turn, an agent takes their highest ranked remaining item. This results in a balanced allocation. • 1-2-Round-Robin: the agents take turns, where we compensate the second agent, who might not get their favorite item, to take two items each turn.In this section, we only prove consistency-robustness guarantees when Balanced-Round-Robin is used as the allocation procedure. In Appendix E we show different tradeoffs when 1-2-Round-Robin is used.ALGORITHM 2: Balanced-Round-Robin Input :Preference orders of agents over items v = (v1, v2).Output :An allocation A1 • A2 = M . Ai ← ∅ for every agent i ∈ {1, 2} for r = 1, . . . , ⌈|M |/2⌉ do A1 ← A1 + v * 1 (M \ A1 \ A2) A2 ← A2 + v * 2 (M \ A1 \ A2)Consider the allocation procedure depicted in Algorithm 2. In order to implement the two allocation procedures, we only needs to receive preference orders over items. Let A i = (a 1 i , . . . , a |Ai| i) be agent i's allocation by the algorithm, where a k i is the k'th choice of agent i. We observe the following. Observation 4.1. The output (A 1 , A 2 ) of the Balanced-Round-Robin procedure, satisfies:1. |A 1 | = ⌈ m 2 ⌉, |A 2 | = ⌊ m 2 ⌋. 2. For each agent i and round k, a k i ∈ {v ℓ i } ℓ∈[2k]; that is, in round k an agent gets one of their top 2k items. Amanatidis et al. [8] show that first allocating large items to agents, and then using a Round-Robin to allocate the remaining items to the remaining agents, gives a 2-approximation to the MMS. We observe that for two agents, Round-Robin as is, without the initial step, achieves this approximation guarantee. The proof of the following Lemma is deferred to Appendix D. Lemma 4.1. Let (A 1 , A 2 ) be the allocation of Balanced-Round-Robin. For every agent i,v i (A i ) ≥ µ i /2.We next use the allocation procedure to instantiate the Plant-and-Steal framework.Round-Robin-Based Mechanism. The mechanism we analyze, B-RR-Plant-and-Steal, results from instantiating Plant-and-Steal with Balanced-Round-Robin as A.We first show that if the predictions correspond to the preference orders of the real valuations, then B-RR-Plant-and-Steal outputs the same allocation as Balanced-Round-Robin. Lemma 4.2. When predictions correspond to actual values, B-RR-Plant-and-Steal outputs the same allocation as Balanced-Round-Robin.We are now ready to prove the performance guarantees of our mechanisms. Proof. By Lemma 3.1, the mechanism is truthful. By Observation 4.1, each agent receives at least ⌊m/2⌋ items; combining with Lemma 3.4, we get that the mechanism is ⌈ m 2 ⌉-robust. Finally, if predictions correspond to valuations, by Lemma 4.1 and Lemma 4.2, the allocation is a 2-approximation to the MMS. Thus, the mechanism is 2-consistent.We note that by Amanatidis et al. [7] , our robustness guarantee matches the optimal obtainable approximation by any truthful mechanism (up to the rounding).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Using the code provided, it is possible to reproduce the main experimental results.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
noisy predictions: 
 We now analyze Mechanism B-RR-Plant-and-Steal's performance under varying levels of noise. Consider the case where the Kendall tau distance between v and p is at most d. Our main theorem in this section shows that combining the Plant-and-Steal framework with a Round-Robin allocation procedure obtains O( √ d)-approximation to the MMS when the Kendall tau distance is d. Missing proofs of this section appear in Appendix F.To prove the approximation ratio, we relate the value that agent i obtains from the allocation, v i (X i ), to their maximin share, µ i , by considering the worst possible set of items that agent i might receive under the Round-Robin procedure when acting on their true preferences. Specifically, we define this worst-case set as R i = {v 2j i } j∈{1,...,⌊m/2⌋} . In Eq. ( 2) of Lemma 4.1, we prove that v i (R i ) ≥ µ i /2. Therefore, obtaining an allocation that is a factor of c times v i (R i ) ensures a factor of c/2 of the MMS value.We further simplify the analysis by applying the zero-one principle 3 . The zero-one principle basically let's us reduce the analysis to instances where the values are either 0's or 1's. For threshold τ ≥ 0, let h τ (q) = 1 if q ≥ τ and 0 otherwise, and let v τ i (S) = j∈S h τ (v i (j)). By the zero-one principle, for two sets S, T ⊆ M , in order to show that v i (S) approximates v i (T ), it is enough to show that v τ i (S) approximates v τ i (T ) for every threshold τ ≥ 0. Lemma 5.1. For c > 1 and for any two sets S, T ⊆ M , if for every threshold τ ≥ 0,v τ i (S) ≥ v τ i (T )/c, then v i (S) ≥ v i (T )/c.Thus, we will show that when the Kendall tau distance is d, for every threshold τ ≥ 0,v τ i (X i ) ≥ v τ i (R i )/c for some c = O( √ d).Recall that A i is the set of items assigned to i after running the Round-Robin procedure on the predictions p. We first show that for Kendall tau distance d, the additive approximationv τ i (A i ) gives to v τ i (R i ) is √ d. Lemma 5.2.If the Kendall tau distance between p and v is at most d, then for any threshold τ ≥ 0, we have thatv τ i (A i ) ≥ v τ i (R i ) - √ d.We note that although v τ i (A i ) gives an additive approximation to v τ i (R i ), it can still be the case that the Kendall tau distance is constant, yet v i (A i ) does not give any multiplicative approximation to µ i . 4 Therefore, we must use the fact that agent i gets to "steal" an item according to their true valuation in the Plant-and-Steal procedure in order to get our approximation guarantee. By combining these results, we prove the following theorem concerning the approximation ratio of B-RR-Plant-and-Steal's performance under varying levels of noise, d. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental results: 
 In this section 6 , we give experiments which illustrate the role of different components of our framework for two players under various noise levels of the predictions. The predictions we use for our experiments are the predicted values of the items. The noise we introduce permutes the vectors of values to match the instance's Kendall tau distance, and uses the permuted vector as prediction. We show that our framework is almost optimal for small amounts of noise while still showing resilience for higher noise levels. Moreover, we study the performance of variants which only use specific components of our framework.When using predictions, our initial allocation procedure is a cut-and-choose procedure, implemented as follows:• We use the first player's prediction to implement a bag-filling algorithm which sorts the items by values, and then partitions the items into two sets using a greedy procedure that assigns each item to the set with current lowest value. • We use the second player's prediction to allocate the agent the set with the higher predicted value of the two.This allocation ensures that the second agent obtains their MMS value according to the prediction. In the data we generates, we observe that in a sampled valuation, the two sets chosen by the bag-filling algorithm gives the two sets the same value, up to 0.5%, which ensures that the lowest valued set obtains a 1.026-approximation to the MMS.We inspect the following mechanisms:1. Random: a mechanism that ignores reports and predictions and randomly partitions the items into two sets of size m/2. 2. Random-Steal: a mechanism that ignores predictions, randomly partitions the items into two sets of size m/2, and then implements the stealing phase where each player takes their favorite item from the other player's set according to reports. 3. Partition: a mechanism that ignores reports, and partitions the items according to predictions, using the cut-and-choose procedure described above. 4. Partition-Steal: a mechanism that partitions the items according to predictions, using the cut-and-choose procedure described above, and then implements the stealing phase where each player takes their favorite item from the other player's set according to reports. 5. Partition-Plant-Steal: a mechanism that implements the Plant-and-Steal framework.partitions the items according to predictions, using the cut-and-choose procedure described above, "plants" each player's favorite item according to predictions, and then "steals" each player's favorite item from the other player's set according to reports.Experiments. We consider two-player scenarios with m = 100 items. For each distance measure, we generate 1000 valuation profiles. For each pair of valuation profiles and corresponding Kendall tau distance, we generate 100 predictions based on the distance. We then assess the performance of the mechanisms described earlier on these instances. We examine two distinct cases regarding the relationship between the players' preference orders: the Correlated case, where both players have identical preference orders, although their valuation magnitudes differ, and the Uncorrelated case, where the preference orders of the players are generated independently and chosen uniformly at random. Further details on the procedures used to generate the valuations and predictions are provided in Appendix A.Benchmark. We plot the percentage of these instances where both players get at least (1 -ϵ) of their MMS value for ϵ = 0.1, 0.05, 0.02.Results. The results are shown in Figure 1 . We first examine the performance of the two mechanisms that do not use predictions, Random and Random-Steal. Scenarios with correlated values perform significantly worse, as there is a non-negligible probability of an unbalanced partition of the relatively few high and medium valued items in a random partition. For ϵ values of 0.02, 0.05, 0.1, the Random strategy success rate is 11%, 25%, and 43%, respectively, under correlated preferences, compared to 33%, 43%, and 60% under uncorrelated preferences. Moreover, adding the stealing component significantly improves the success rate only in the uncorrelated case, as Random-Steal achieves success rates of 66%, 75%, and 87%. In the correlated case, as each player has a highly valuable item stolen, their obtained value is not expected to increase.In the mechanisms that use predictions, Partition, Partition-Steal and Partition-Plant-Steal, the performance degrades as a function of noise, as expected. When comparing the performance of Partition, which only relies on the prediction component of our framework, and Random-Steal, which only relies on the stealing component of our framework, we notice that in the uncorrelated case, for small amount of noise guarantee a higher success rate, while as the noise increases, the stealing component becomes more instrumental to the performance. This is in tact with the theoretical results, where using the prediction is crucial to achieve the consistency guarantees, which take place when the prediction is accurate, while stealing is important to achieve robustness guarantees in case the prediction is inaccurate. As described above, in the case where the valuations are correlated, stealing is not expected to help. Interestingly, on fully noisy input, even Random outperforms Partition as Partition might partition the items into unequally-sized sets, which performs worse than the equally-sized sets Random outputs.Our experiments show that Partition-Plant-Steal performs as well as the Partition strategy for small amounts of noise and outperforms it on uncorrelated instances for large amounts of noise. Moreover, for any amount of noise, it outperforms Random-Steal and converges to it for a fully noisy input. This illustrates the "best of both worlds" tradeoff obtained by our framework.Finally, when comparing the Partition-Plant-Steal strategy to the Partition-Steal strategy, we observe that Partition-Plant-Steal outperforms Partition-Steal in the correlated case with a small amount of noise (worst-case scenario) for ϵ = 0.02, as planting guarantees your favorite items would not be taken. In other scenarios, Partition-Steal outperforms Partition-Plant-Steal because "planting" removes a valuable item from the player's set that might be taken otherwise, especially in the uncorrelated case.Generating valuations. To generate interesting valuations for the players, we use a multi-step function to generate item values, since if the values are close together, any balanced partition obtains good MMS guarantees, without considering reports and predictions. Specifically, we consider a four-step (High/Med/Low/Extra-Low) random valuation function, where an item has a High valuation with probability 8/m, a Medium valuation with probability 1/4, a Low valuation with probability 1/2 and an Extra-Low valuation with the remaining probability. A High valuation is drawn from U [1000, 2000], a Medium valuation is drawn from U [400, 800], a Low valuations is drawn from U [100, 200] and an Extra-Low valuation is sampled from U [1, 2] . Figure 2 shows the value distribution generated by this process for two players. We generate values for m = 100 items.We generate valuations satisfying one of the two types of relations between players' preferences:• Correlated: the two preference orders are identical (but not the values).• Uncorrelated: Both preference orders are chosen independently and uniformly at random. Generating predictions. To generate predictions, we take valuations and permute elements randomly to create noise. We generate predictions under varying noise levels according to the Kendall tau distance between the valuations and the predictions. We very the Kendall tau distance between 1 to 2560, where 2560 corresponds to the expected noise level of a random permutation of 100 items. To randomly choose a permutation of a certain noise level, we start with the ordered permutation and then choose two indices j < k u.a.r. and swap items r and r + 1 for r ∈ {j, . . . , k -1} if it increases the Kendall Tau distance by one. We repeat this process until the distance of the resulting permutation equals the desired value.The notion of the maximin share allocation was introduced by Budish [18] as an ordinal notion, and extended to the notion we adopt by Bouveret and Lemaître [17] . Using machine learning advice in algorithm design was used in theory [21, 38] and practice [29] . The learning-augmented framework of studying consistency-robustness tradeoffs was introduced by Lykouris and Vassilvitskii [34] . [35, 39] studied the performance of algorithms using imprecise predictions. Fair division with incentives. The two closest papers to ours are Amanatidis et al. [6, 7] . In [6] , they initiate the study of truthful mechanisms for approximating the MMS value for agents with additive valuations. They show that no truthful mechanism can get an approximation better than 1/2 for the MMS in the case of 2 agents and 4 items. They give the best known approximation guarantee for n agents and m items of ⌊ m-n+2 2 ⌋. Finally they consider the public ranking model, where the ranking over items is public information. Using this, they are able to obtain a n+1 2 -approximation algorithm. One can view this as an algorithm that is given a prediction over the input, but does not provide robustness guarantees. [7] Fully characterize truthful mechanism for 2 agents with additive valuations. They use this characterization to provide a strong lower bound of ⌊ m 2 ⌋ for any truthful mechanism.[12] design truthful mechanisms for dichotomous submodular valuations that maximize welfare, along with desirable fairness properties such as EFX and NSW. For additive binary valuations, they also maximize the MMS in a truthful manner. [26] bypass the impossibilities imposed by [7, 37] for truthful fair allocations with indivisible and divisible goods by considering Bayesian Incentive Compatible mechanisms with symmetric priors. They are able to obtain EF-1 allocations for indivisible goods and proportional allocations for indivisible goods.Finally, [9] study the Nash equilibrium for simple mechanisms for agents with additive valuations. They show that for every number of agents, the Pure Nash equilibrium of the Round-Robin procedure produces an EF-1 allocation. For two agents, they show that the Pure Nash equilibrium of Plaut and Roughgarden [36] cut-and-choose procedure produces an EFX and MMS allocation.1-out-of-k. As stated above, the MMS value of an agent is defined by the highest value an agent can guarantee for themselves when partitioning the items into n different bundles, where n is the number of agents, and then getting the lowest valued bundle. Thus, an agent get a value larger than the worst one-out-of-n bundles that define the MMS.Noticing that finding an allocation that satisfies the MMS value of each agent is a demanding task (which was shown to be infeasible in some cases by Kurokawa et al. [30] ), Budish [18] relaxed the notion and defined the 1-out-of-n + 1 MMS to be the worst bundle out of the bundles that define the MMS when partitioning the items using an additional bundle. [18] showed it is possible to achieve this benchmark when adding a small number of access goods. There has been an effort to find the smallest k for which an allocation that guarantees a 1-out-of-k MMS for each agent exists. [2] were able to show the existence for k = 2n -2, [27, 28] achieved k = ⌈ 3n 2 ⌉, and recently, [5] showed the smallest up-to-date k = ⌈ 4n 3 ⌉. In our n-agent mechanism, our robustness guarantee approximates this relaxed benchmark for k = ⌈ 3n 2 ⌉.Learning-Augmented Mechanisms. Agrawal et al. [1] and Xu and Lu [40] first explored the learning-augmented framework in a mechanism design setting, where [1] studied the facility location problem while [40] applied the framework to several settings such as revenue-maximization, path auctions, scheduling and two-facility games. [14] give nearly optimal consistency-robustness tradeoffs to the strategyproof scheduling with unrelated machines. [25] use predictions to design mechanisms with improved Price of Anarchy bounds. [33, 19] study revenue maximization auctions with predictions, and [13] devise bicriteria mechanisms.C Deferred proofs from Section 3Proof of Lemma 3.1. We show that agent 1 is better off reporting their true valuation, a symmetric argument holds for agent 2. First, notice that sets T 1 and T 2 are determined using predictions, ignoring the reports. Next, notice that the item j2 is chosen only using agent 2's report. Therefore, the only way agent 1 can affect their allocation is by choosing which item in T 2 is allocated to them. agent 1 gets their favorite item in T 2 according to their report. Therefore, it is clear that the agent maximize their utility by reporting their true value.Proof of Lemma 3.2. Consider some agent i. We claim for every partition of the items into two non-empty sets, T 1 , T 2 , i is always guaranteed to have one of their two favorite items according to their true valuation v i in X i . This is because either (1) i has one of their two favorite items in T ℓ , ℓ ̸ = i, and i gets their favorite item from T ℓ ; or (2) i's two favorite items are in T i , and in this case, i gets all items from T i but one, so i is guaranteed one of them.Proof of Lemma 3.3. Let g ∈ S ∩ {v 1 i , v 2 i }, by the definition of S such g exists. Let S ′ = S \ {g}, by the definition of S, we have |S ′ | = k -1 and v i (S) ≥ v 2 i + v i (S ′ ). Consider a partition (S 1 , S 2 ) ∈ arg max (T1,T2) : T1 • T2=M min j∈{1,2} v i (T j ).By definition, µ i = min j∈{1,2} v i (S j ). We have,µ i v i (S) ≤ µ i v 2 i + v i (S ′ ) = min j∈{1,2} v i (S j ) v 2 i + v i (S ′ ) ≤ min j∈{1,2} v i (S j ) -v i (S ′ ) v 2 i ≤ min j∈{1,2} v i (S j \ S ′ ) v 2 i ≤ min j∈{1,2} {|S j \ S ′ | • max{v i (ℓ) : ℓ ∈ S j \ S ′ }} v 2 i . ≤ (m -k) • min j∈{1,2} max{v i (ℓ) : ℓ ∈ S j } v 2 i ≤ m -k.where the before last inequality is since if S j ⊆ S ′ for some j, then v 2 i + v i (S ′ ) ≥ µ i ; therefore S 1 \ S ′ and S 2 \ S ′ are two disjoint non empty subsets and|S 1 \ S ′ | + |S 2 \ S ′ | = m -k + 1,hence the maximum number of elements in one of these subsets is m -k.Proof of Lemma 4.1. By Observation 4.1, we haveEQUATIONSince i's favorite item must be absent from some set of the sets defining the MMS value,EQUATIONBy Equations ( 1),(2), we have:v i (A i ) ≥ ⌊m/2⌋ k=1 v 2k i ≥ µ i /2.Proof of Lemma 4.2. Let j 1 be the first item assigned in Balanced-Round-Robin to agent 1. By definition, j 1 is agent 1's favorite item in M according to p 1 . Clearly, in Plant-and-Steal, j 1 is also agent 1's favorite item in A 1 ⊆ M according to p 1 . Hence, ĵ1 = j 1 . By the definition of Plant-and-Steal, j 1 ∈ T 2 . Since we assume the prediction corresponds to agent 1's actual value, j 1 is also agent 1's favorite item in T 2 ⊆ M , which implies j1 = j 1 .Similarly Let j 2 be the first item assigned in Balanced-Round-Robin to agent 2. By definition, j 2 is agent 2's favorite item in M \ {j 1 } according to p 2 . SinceEQUATIONis also agent 2's favorite item in A 2 according to p 2 . Hence, ĵ2 = j 2 . Since we established that ĵ1 = j 1 , we have that T 1 ⊆ M \ {j 1 } and j 2 ∈ T 1 . Since we assume the prediction corresponds to agent 1's actual value, j 2 is also agent 1's favorite item in T 1 , implying j2 = j 2 . We get that X 1 = A 1 and X 2 = A 2 as required.E 1-2-RR-Plant-and-Steal Mechanism: A 3/2-consistent, ⌊ 2m /3⌋-robust MechanismIn this section, we show that using a modified round-robin allocation procedure to instantiate the Plant-and-Steal framework give an improved 3/2 consistency guarantee, while maintaining O(m) robustness. Consider the Balanced-Round-Robinallocation procedure depicted in Algorithm 2.One can show that the agent that picks first actually gets a value at least as large as their MMS, while for the second agent this analysis is indeed tight. 7 In order to compensate agent 2, 1-2-Round-Robin lets this agent pick two items each round. See Algorithm 3 for details.ALGORITHM 3: 1-2-Round-Robin Input :Preference orders of agents over items v = (v1, v2).Output :An allocation A1 • A2 = M . Ai ← ∅, for every agent i ∈ N for r = 1, . . . , ⌈|M |/3⌉: do A1 ← A1 + v * 1 (M \ A1 \ A2) A2 ← A2 + v * 2 (M \ A1 \ A2) A2 ← A2 + v * 2 (M \ A1 \ A2)Let a k i be agent i's kth choice in 1-2-Round-Robin, we observe the following. Observation E.1. The output (A 1 , A 2 ) of the 1-2-Round-Robin procedure, satisfies:1. |A 1 | = ⌈ m 3 ⌉ and |A 2 | = ⌊ 2m 3 ⌋. 2. a k 1 ∈ {v ℓ 1 } ℓ∈[3k-2] , a 2k-1 2 ∈ {v ℓ 2 } ℓ∈[3k-1] and a 2k 2 ∈ {v ℓ 2 } ℓ∈[3k] .Amanatidis et al. [6] show that 1-2-Round-Robin guarantees each agent 2/3 of their MMS. We provide the proof for completeness. Lemma E.1 (Amanatidis et al. [6] ). Let (A 1 , A 2 ) be the allocation of 1-2-Round-Robin. For every agent i, v i (A i ) ≥ 2µi /3.Proof. We first prove the approximation for player 1 (the first player to be allocated). First, observe that v 1 (M ) ≥ 2µ 1 . Let I 1 = {v 3k-2 1 : k = 1, . . . , ⌈m/3⌉} be the worst possible allocation agent 1 might get in the 1-2-Round-Robin allocation. Notice that v 1 (I1 ) ≥ v 1 (M )/3 ≥ 2µ 1 /3. By Observation E.1, v 1 (a k 1 ) ≥ v 3k-2 1 . Therefore, v 1 (A 1 ) ≥ v 1 (I 1 ) ≥ 2µ 1 /3. Now consider player 2. As stated in the proof of Lemma 4.1, v 2 (M \ v 1 2 ) ≥ µ 2 . Let I a 2 = {v 3k-1 2 : k ∈ N >0 ∧ 3k -1 ≤ m} and I b 2 = {v 3k 2 : k ∈ N >0 ∧ 3k ≤ m}. First, notice that v 2 (I a 2 ∪ I b 2 ) ≥ 2v 2 (M \ v 1 2 )/3 ≥ 2µ 2 /3. Moreover, by Observation E.1, we have, v 2 (a 2k-1 2 ) ≥ v 3k-1 2 , and v 2 (a 2k 2 ) ≥ v 3k 2 . Therefore, v 2 (A 2 ) ≥ v 2 (I a 2 ∪ I b 2 ) ≥ 2µ 2 /3.The mechanism we consider in this section, 1-2-RR-Plant-and-Steal, results from instantiating Plant-and-Steal with 1-2-Round-Robin as A.The next lemma states that if the predictions correspond to the preference orders of the real valuations, then 1-2-RR-Plant-and-Steal outputs the same allocation as 1-2-Round-Robin. The proof is omitted as it is identical to the proof of 4.2. Lemma E.2. When predictions correspond to actual values, 1-2-RR-Plant-and-Stealoutputs the same allocation as 1-2-Round-Robin.We next show that in 1-2-RR-Plant-and-Steal we are able to achieve a better consistency, while slightly weakening the robustness guarantee. Theorem E.1. Mechanism 1-2-RR-Plant-and-Steal is truthful, 3/2-consistent and ⌊ 2m 3 ⌋-robust.Proof. By Lemma 3.1, the mechanism is truthful. By Observation E.1, each agent receives at least ⌈m/3⌉ items; combining with Lemma 3.4, we get that the mechanism is ⌊ 2m 3 ⌋-robust. Finally, if predictions correspond to valuations, by Lemma E.1 and Lemma E.2, the allocation is 3/2approximation to the MMS. Thus, the mechanism is 2/3-consistent.Proof of Lemma 5.1. Let S = {s 1 , . . . , s k } (|S| = k) and T = {t 1 , . . . , t ℓ } (|T | = ℓ). We have the following.v i (S) = k j=1 v i (s j ) = k j=1 ∞ 0 h τ (v i (s j ))dτ = ∞ 0 k j=1 h τ (v i (s j ))dτ = ∞ 0 v τ i (S)dτ ≥ ∞ 0 v τ i (T )/c dτ = 1 c ∞ 0 ℓ j=1 h τ (t j )dτ = 1 c ℓ j=1 ∞ 0 h τ (t j )dτ = 1 c ℓ j=1 v i (t j ) = v i (T )/c,where we use the identity ∞ 0 h τ (q)dτ = q.Proof of Lemma 5.2. Let ⌊ m 2 ⌋ ≤ m i ≤ ⌈ m 2 ⌉ be the number of items agent i gets by Mechanism B-RR-Plant-and-Steal. Let A i = {a 1 i , a 2 i , . . . , a mi i } be the items assigned to agent i in the Round-Robin according to the predicted orderings p, where a ℓ i is the item allocated to i in the ℓ th round of Round-Robin. First, by Observation 4.1, we have:EQUATIONFor a fixed τ ≥ 0, let L τ = v τ i (R i ) be the number of values larger than threshold τ in R i . We show that if the Kendall tau distance is at most d, then it must be the case thatEQUATIONNote that h τ (v k i ) = 1 for k ≤ 2 • L τ since R i gets every second item by the sorted values of agent i. This implies that ifh τ (v 1 (a ℓ i )) = 0 then a ℓ i = v k i for k > 2 • L τ . Moreover, if ℓ ≤ L τ then a ℓ i = p k i for k ≤ 2 • L τ by Eq. (3). Thus, if Lτ k=1 h τ (v 1 (a k i )) < L τ - √ dthere are strictly more than ⌈ √ d⌉ items whose rank according to the true valuation is at most 2 • L τ , and their rank according to the prediction is at least 2 • L τ + 1. We show that this implies that the Kendall tau distance is larger than d, yielding a contradiction. Formally, letG 1 = {v k 1 } k∈{1,...,2•Lτ } \ {p k 1 } k∈{1,...,2•Lτ } be the set of items whose rank is at most 2 • L τ according to the real values but not according to the predictions, and letG 2 = {v k 1 } k∈{2•Lτ +1,...,m} \ {p k 1 } k∈{2•Lτ +1,...,m} be the set of items whose rank is strictly larger than 2 • L τ according to the real values but not according to the predictions. By the above,|G 1 | = |G 2 | > ⌈ √d⌉, and for each pairj ∈ G 1 , j ′ ∈ G 2 ,1. j rank according to v i is at most 2 • L τ and j ′ rank according to v i is at least 2 • L τ + 1;2. j ′ rank according to p i is at most 2 • L τ and j rank according to p i is at least2 • L τ + 1.That is, j and j ′ are ordered oppositely in the ordering according to p i and v i . Since there are |G 1 | • |G 2 | > d such pairs, we get that the Kendall tau distance is strictly greater than d, a contradiction.Proof of Theorem 5.1. Recall that, in Eq. ( 2) of Lemma 4.1, we establish that:EQUATIONIn addition, we apply the zero-one principle to show that Lemma 5.1 holds for the sets X i and R i with c = √ d + 3. The proof follows by combining these two results.Notice that |A i \ X i | ≤ 2, because in the "stealing" phase, agent i might not take the "planted" item from A i back, and the other agent might take one item from A i . 8 Moreover, by Lemma 3.2, either v 1 i or v 2 i are in X i . Therefore, for every threshold τ ≥ 0,EQUATIONwhere the inequality follows Lemma 5.2.EQUATIONi ) = 0, and Lemma 5.1 holds with c = 0. Therefore, the interesting case is when h τ (v 2 i ) = 1. Consider the ratiov τ i (Ri) v τ i (Xi) which we want to bound. Since v τ i (X i ) ≥ h τ (v 2 i ) = 1, v τ i (R i ) ∈ [1, √ d + 3] implies that v τ i (R i ) v τ i (X i ) ≤ v τ i (R i ) ≤ √ d + 3.On the other hand, by Eq. ( 6), settingv τ i (R i ) = √ d + 3 + δ for δ > 0 implies that v τ i (X i ) ≥ v τ i (R i ) - √ d -2 ≥ 1 + δ, which yields v τ i (R i ) v τ i (X i ) ≤ √ d + 3 + δ 1 + δ ≤ √ d + 3.We get that Lemma 5.1 holds for X i and R i with c = √ d + 3. Thus,v i (X i ) ≥ v i (R i )/( √ d + 3) ≥ µ i /(2 √ d + 6), where the last inequality follows Eq. ( 5).In this Section, we consider the case where predictions are not necessarily preference orders over items. In Section G.1, we show that for any prediction the mechanism might get, consistency is bounded away from 1. Sections G.2, G.3, we study succinct predictions, i.e. predictions about general structure of the preferences of two agents. Section G.2 presents a 4-consistent and ⌈m/2⌉-robust mechanism, whose consistency relies on the correctness of only a log m-bit prediction about the preferences of the two agents. In Section G.3, we show that a 2 + ϵ-consistent and ⌈m/2⌉-robust mechanism exists, whose consistency relies on correctly predicting only O(log m/ϵ) bit about the preferences of the two agents.In [7] they define the following family of mechanisms. Definition G.1 (Singleton Picking-Exchange Mechanisms [7] ). A mechanism X is a singleton picking-exchange mechanism if for each i ∈ {1, 2}, there is exactly one of two sets: either N i ⊆ M , or E i = {ℓ i } for a single item ℓ i ∈ M . If N i is non-empty, then the mechanism lets player j ̸ = i pick item ℓ ∈ N i that maximizes v j (ℓ), and i gets N i \ {ℓ}. If both E 1 , E 2 are non-empty, then the agents exchange the two itemsℓ 1 ∈ E 1 and ℓ 2 ∈ E 2 if v 1 (ℓ 2 ) > v 1 (ℓ 1 ) and v 2 (ℓ 1 ) > v 1 (ℓ 2 ). Notice that if m > 2, either E 1 or E 2 isempty and there will be no exchange.[7] showed the following. Lemma G.1. In order for a mechanism to be truthful and have a bounded approximation, it has to be a singleton picking-exchange mechanismWe make use of this characterization in our impossibility. Theorem G.1. For any ϵ > 0, there is no truthful a mechanism with consistency 6/5 -ϵ and bounded robustness.Proof. Consider the case where p 1 = p 2 = (1/2, 1/2, 1/3, 1/3, 1/3). Notice that for the predictions, µ 1 = µ 2 = 1. We show that for any singleton-picking-exchange mechanism, no agent obtains both large items (of value 1/2). Consider agent 1 (the argument is symmetric for agent 2). If N 1 is non-empty, then if both large items are in N 1 , surely 1 will only get one of them. If both large items are in N 2 , then agent 2 will surely pick one of them, and agent 1 will only get one of them. If one large item is in N 1 and the other is in N 2 , each agent i will pick the large item in N i . If agent 2 has a large item in E 2 , then since N 1 is non-empty, E 1 is empty and agent 2 will keep the large item. Now consider the case where E 1 is non-empty. In this case, E 1 contains one item, and N 1 is empty. Since E 2 can contain at most one item, and there are more than 2 items, in this case, E 2 = ∅, and |N 2 | = 4. Therefore, N 2 contains at least one large item. Since agent 2 will always pick the large item, agent one only gets one large item. We conclude that for any singleton picking-exchange mechanism, the large items are split among the agents. Since there are 3 small items, there must be an agent that gets at most one small item, and this agent has an overall value of at most 1/2 + 1/3 = 5/6, while the MMS is 1. Thus the claim follows.Let us formally define a mechanism that uses a space-s prediction Definition G.2. A learning-augmented mechanism is a space-s mechanism if the prediction space P can be represented by the elements of {0, 1} s .We first give a simple mechanism that only requires 3 log m + 1 bits of information about the valuations v 1 and v 2 . It will only need to know an index j 0 in [m] together with a bit b to produce an approximately-optimal allocation, and an additional 2 log n bits to implement the planting phase. The mechanism will utilize the Plant-and-Steal framework in conjunction with the well-known bag-filling allocation procedure:We see that, in order to predict the behaviour of the mechanism above, one only needs to predict accurately the index j 0 on which the mechanism terminates, as well as a bit b ∈ {1, 2} that encodes A1 • A2 = M j ← 1 for j = 1, . . . , m: do if v 1 ([j]) v 1 ([m]) ≥ 1 2 then Output (A1, A2) ← ([j], [m] \ [j]) and terminate if v 2 ([j]) v 2 ([m]) ≥ 1 2 then Output (A1, A2) ← ([m] \ [j], [j]) and terminate whether the algorithm terminates due to the condition v1([j]) v1([m]) ≥ 1 2 being satisfied or due to the condition v2([j]) v2([m]) ≥ 1 2 being satisfied. This can be encoded using log m + 1 bits. We also see that the The Plant-and-Steal framework when used with the Bag-Filling allocation procedure gives a truthful 4-consistent and a m -1-robust9 allocation mechanism. The truthfulness and robustness follow immediately from Lemmas 3.1 and 3.4 respectively. The 4-consistency holds for the following reason. It is a well-known fact (see i.e. [10] ) that the partition (A 1 , A 2 ) given by the bag-filling algorithm satisfies v 1 (A 1 ) ≥ µ 1 /2 and v 2 (A 2 ) ≥ µ 2 /2. By inspecting the Plant-and-Steal framework (Algorithm 1), we see that both agent 1 and agent 2 will either (i) retain their most preferred item in A 1 and A 2 respectively or (ii) Lose this item, but obtain an item that they prefer even more. Overall, this implies that in the worst case the difference v 1 (A 1 ) -v 1 (X 1 ) will equal to the value of the second-most favorite item of Agent 1 in A 1 . This implies that v 1 (X 1 )≥ 1 2 v 1 (A 1 ) ≥ µ1 4 . Analogously, we see that v 1 (X 2 ) ≥ 1 2 v 1 (A 2 ) ≥ µ2 4 .G.3 2 + ϵ-Consistent, ⌈ m 2 ⌉-Robust Mechanism Using a O(log m/ϵ)-Space Prediction We now show that a better consistency of 2 + ϵ can be achieved at the cost predicting O(log m/ϵ) bits of information about the valuations v 1 and v 2 . We will also obtain a better robustness of ⌈ m 2 ⌉. To do this, we will use the Plant-and-Steal framework in conjunction with the Cut-and-Balance allocation procedure. We first explain how the mechanisms above can be implemented by only v1(Sj) ≥ (1 -ϵ)max T 1 • T 2 =M min j∈{1,2} v1(Tj) = (1 -ϵ)µ1 Let S ′ ⊂ S1 be a set of ⌊m/2⌋ -|S2| items satisfying • v1(S ′ ) ≤ v1(S1)/2• if |S2| > 1 additionally satisfying v1(S ′ ) ≤ v1(S1 \ { ĵ, ĵ′ })/2, for some ĵ ∈ arg maxj∈S 1 v1(j) and ĵ′ ∈ arg max ℓ∈S 1 \ ĵ v1( ĵ) obtaining O(log m/ϵ) bits of information about the valuations v 1 and v 2 . This follows from the following proposition, the proof of which is given in Appendix G.4.EQUATIONProposition G.1. Suppose M = [m]. There is a partition M = L 1 • L 2 • S and indices α 1 , β 1 , α 2 and β 2 with |L 1 | + |L 2 | ≤ O 1 ϵ , such that the partition M = S 1 • S 2 de- fined as S 1 = L 1 (S [α 1 , β 1 ]) and S 2 = L 2 (S [α 2 , β 2 ]) satisfies |S 1 | ≥ |S 2 | and min(v 1 (S 1 ), v 1 (S 2 )) ≥ (1 -ϵ/4)µ 1 .Additionally, there exist integers α 3 , β 3 , α 4 and β 4 such that the setS ′ = S ([α 3 , β 3 ] [α 4 , β 4 ]) satisfies |S ′ | = ⌊m/2⌋ -|S 2 |, S ′ ⊂ S 1 , v 1 (S ′ ) ≤ v 1 (S 1 )/2 and if |S 2 | > 1 then S ′ also satisfies v 1 (S ′ ) ≤ v 1 (S 1 \ { ĵ, ĵ′ })/2, where ĵ ∈ arg max j∈S1 v 1 (j) and ĵ′ ∈ arg max j∈S1\ ĵ v 1 (j).The main ideas for proving Proposition G.1 are: (i) using the sets L 1 and L 2 to handle elements x whose value v(x) is large, and separate the remaining items into the set S (ii) Showing that the remaining items can be separated into well-behaved subsets of the form S [α i , β i ].The proposition above implies that the sets S 1 , S 2 and S ′ can be represented exactly via sets L 1 and L 2 , together with the indices {α 1 , • • • , α 4 , β 1 , • • • β 4 }. We will also need to know the index i 2 ∈ {1, 2}. Since the sets L 1 and L 2 have a size of O(1/ϵ), all this information amounts to O(log m/ϵ) bits as claimed.The following proposition implies the truthfulness, the robustness and the consistency of the mechanism that combines the Cut-and-Balance allocation procedure with the Plant-and-Steal framework. Theorem G.2. The Plant-and-Steal framework, when used with Cut-and-Balance allocation procedure, gives a truthful, 2 + ϵ-consistent and a ⌈m/2⌉-robust allocation mechanism.Proof. Truthfulness follows from Lemma 3.1. Since the sets A 1 and A 2 both have size at most ⌈m/2⌉, the robustness follows via Lemma 3.4.The proof of (2 + ϵ)-consistency is deferred to Appendix G.5. The main challenge for showing the bound on consistency is the fact that both the Cut-and-Balance allocation procedure and the Plant-and-Steal framework can reduce the consistency by a factor of 2. Naively, one would expect the overall consistency to be close to 4, given that each stage can lose a factor of 2 in consistency. However, our insight is that for the instances, on which the Cut-and-Balance allocation procedure loses a factor of 2 in consistency, the Plant-and-Steal framework will have consistency close to 1, and vice versa. This allows us to prove a tighter bound of 2 + ϵ on the consistency of our overall algorithm.We first show the following, which implies the first half of Proposition G.1.M = L 1 • L 2 • S and and indices α 1 , α 2 , β 1 , β 2 in [m] such that M = [α 1 , β 1 ] • [α 2 , β 2 ], for the sets S 1 = L 1 ∪ (S ∩ [α 1 , β 1 ]) and S 2 = L 2 ∪ (S ∩ [α 2 , β 2 ]) we have • min{v 1 (S 1 ), v 1 (S 2 )} ≥ (1 -ϵ/8)µ 1 • |L 1 | + |L 2 | ≤ ⌈ 8 ϵ ⌉ + 2 • |S 1 | ≥ |S 2 |.• For every x in L 1 and y in S 1 we have v 1 (x) > v 1 (y). Analogously, for every x in L 2 and y in S 2 we have v 1 (x) > v 1 (y)• There are ĵ, ĵ′ ∈ L 1 satisfying ĵ ∈ arg max ℓ∈S1 v 1 (ℓ) and ĵ′ ∈ arg max ℓ∈S1\ ĵ v 1 (ℓ),We do this by inspecting two types of items, large items, with value greater than ϵµ 1 /4, and small items items with value at most ϵµ 1 /4. We first show that there are O(1/ϵ) large items, therefore, separating these items into two bundles require at most O(1/ϵ) intervals. Moreover, we can find a separation of the larges items into two sets, L 1 , L 2 , and a single index j ∈ [m] such that all small items to the left of j (including) together with L 1 form S 1 , and all items to the right of j (excluding) together with L 2 form S 2 , such that S 1 , S 2 satisfy the approximation requirement. It is easy to see that this increases the number of intervals by at most 1.We start by showing there are not too many large items. Lemma G.2. There are at most ⌈ 8 ϵ ⌉ items with value strictly greater than ϵµ 1 for agent 1.Proof. Let items with value greater than ϵµ 1 /4 be the large items. Suppose there are at least ⌈ (S 1 ), v 1 (S 2 )} > ϵµ 1 /4 • 4 ϵ = µ 1 , a contradiction.We are now ready to prove Proposition G.2.Proof of Proposition G.2. Consider the set of large items, L = {j ∈ [m] : v 1 (j) > ϵµ 1 /4}, and let S = M \ L be the set of small items.We give a constructive proof which finds both sets L 1 , L 2 and an index j satisfying the condition stated in the lemma. Let(L 1 , L 2 ) ∈ arg max (T1,T2) : T1 • T2=L min j∈{1,2} v 1 (S j ).We use the following procedure to find j.1. Let j ℓ = 0 and j r = m.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We describe how the data is generated and provide the code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: The paper experiments with Bernoulli variables (indicating either success or failure) with non-negligible p values, which are known to be very highly concentrated.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The experiments were done on a standard PC (Intel i9, 32GB memory), and it took approximately 30 minutes. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The paper studies a mechanism design problem with the objective of outputting a fair allocation, which is a highly desirable goal. We study a generalization of the widely studied proportionality objective for discrete settings. We note that this objective is well motivated in settings like course-allocation [18] , but might be inappropriate in other settings.The techniques in this paper should be used with appropriate care. Moreover, over paper suggests that using past data might increase fairness, but every usage of data should be taken with extra precautions, as these might introduce implicit biases, as shown in the past. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Introducing a learning-augmented framework is shown to obtain stronger theoretical fairness guarantees than other mechanisms studied in the literature. Elements in the design might improve the performance of fair allocation mechanisms in settings such as course allocation, which is of course a positive societal impact. On the other hand, using past data can also result in introducing biases to the allocation, thus, using data should be done with awareness to such potential biases. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.Justification: Experimental details are described and documented code is provided. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Agent i with an additive valuation has a value vij = vi(j) for every item, and their value for bundle S is vi(S) = j∈S vij.For n > m, the MMS of each agent is trivially 0. The problem becomes more interesting for m ≫ n.Applied in[11], for instance, in the context of packet routing.Indeed, consider the case where there are four goods which both agents value at (1, 1, 0, 0). If agent i's prediction orders the last two items higher then the first two items, we will get that vi(Ai) = 0, while µi = 1.A similar analysis for Mechanism 1-2-RR-Plant-and-Steal will show a similar dependence on √ d (up to constant factors).The experiments, reproducible via Matlab (2022b) at https://tinyurl.com/PlantStealExperiments, were performed on a standard PC (Intel i9, 32GB RAM) in about 30 minutes.Consider the case where the agents' valuations are (m-1, 1, . . . , 1). According to Round-Robing allocation, the first item will be assigned to agent 1, and agent 2 will have m/2 items of value 1, while µ2 = m -1.In fact, this holds for any noise in the valuations of the other agent.Note that min(|A1|, |A2|) ≤ m -1 which implies that the algorithm is (m -1)-robust. 
 
 Appendix:  


Decision: Reviewers liked the novelty of the learning-augmented framework and the technical results (for two agents). Some reviewers are not completely satisfied with the robustness guarantee for general number of agents and the weak MMS bound under the learning-augmented framework (which sacrifices some privacy to obtain the prediction), while some other reviewers found the two agent case to be reasonably well-motivated especially given the large literature in MMS. Overall, the novelty outweighs the technical limitations. We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!

Reviews: review: paper_summary: paper_summary: This paper designs truthful algorithms for the fair allocation of indivisible goods in the learning-augmented framework. The algorithm is said to receive predictions about all agents' utilities for all goods (agents have additive utilities) or their ranking over the goods. The fairness notion studied is MMS (the maximin share). The main focus of the paper is on truthful mechanisms.

Most of the paper is focused on two agents. The idea of the proposed plant-and-steal framework is to use the predictions to initiate an allocation $A_1, A_2$; take the favorite good for agent 1 from $A_1$ and plant it in $A_2$ and vice versa; and, now with the utilities that agents report, let the agents steal their favorite item from the other bundle. This achieves a 2-approximate MMS (2-MMS in short) when predictions are completely correct (consistency), and $\lceil m/2 \rceil$-MMS when predictions are incorrect which matches what is achieved by the best truthful mechanism in the standard setting without predictions (robustness). 

Next, the paper focuses on when predictions are agents' rankings for goods instead of the actual cardinal utilities. Using the round-robin mechanism in the plant-and-steal framework achieves the same guarantees (2-MMS for consistency) and $\lfloor m/2\rfloor$-MMS for robustness). When the predicted rankings have a Kendall tau distance of at most d, this mechanism achieves $2 \sqrt{d} + 6$-MMS which interpolates between constant and $m/2$ in the worst-case.

The paper ends with synthetic experiments with two agents. 
In the appendix, the paper discusses mechanisms with $O(\log m /\epsilon)$ communication (previous ones had $\Omega(m)$) that achieve $2 + \epsilon$ robustness. The paper also generalizes the results to $n$ agents, achieving $2$-consistency and weaker robustness guarantees.

There are some other results in the appendix as well exploring pointwise tradeoffs in the Pareto frontier.
strength_weakness: strength_weakness: - The predictions are either the entire valuation matrix or all the rankings, which contain a lot of information.
- Most of the paper is focused on two agents. Even for two agents, I don’t think we learn the complete picture from the paper. I couldn’t find a lower bound for the Kendall tau parameterized result.
- While I like the algorithm's simplicity, I find it a relatively marginal improvement over the truthful mechanism of Amanatidis et al [7]. The technical novelty of the paper isn’t such that we say it’s a strength of the paper, in my opinion. The proofs and algorithms heavily use the priorly known results about truthful mechanisms and their MMS approximations Amanatidis et al [6, 7].
- The main body of the paper isn’t very well organized for a NeurIPS paper. The technical section starts on page 6. The experiment results (figures) are all in the appendix. Please reorganize, and instead of having two pages for “our results” allocate it to the technical section that speaks more formally about them.
- I couldn’t find the definition of “success rate” in the experiments. The y-label in Figure 2 is set to $\epsilon$ which should have been the subcaption of the subfigures. All in all, I couldn’t understand the results of the experiments and verify the takeaways.
- In the experiments, it’s unclear why a Mallows model was not used to generate rankings, which is a more justified statistical model to sample rankings. See e.g. https://proceedings.mlr.press/v97/tang19a.html for the Mallows model parameterized by the Kendall tau distance. I’m also not convinced much by the utility sampling procedure. Is having high-medium-low valuations necessary? How would the results change if it was just unit-sum valuations uniformly sampled from the Dirichlet(1,...,1) (random unit-sum vectors) or Gaussian perturbations of some ground truth valuation vector? 


Minor points:
- The MMS guarantee of $m - 3n/2 - 1$ should have some conditions between $n$ and $m$ perhaps $m \ge 2n$ or similar. It’d be great to be more precise in the theorem/lemma statements.
- In appendix A, there is a “$8/m$” probability mentioned, a $1/2$ and a $1/4$, which I don’t see why would sum to $1$.
- line 58, “With probability $2$”, should it be $½$?
- line 50, “959 / 720 > 4/3$”, the reverse inequality is true
- Please consider renaming Theorem F.1 to Theorem 4.2 as one cannot just search for the proof of Theorem 4.2 easily, e.g. using the package “thm-restate”. 
- You could save precious space by presenting algorithm 2 and mechanism 1 next to each other.
- line 122, one can “ran” -> run
- line 125, more “then” -> than
- table 1, $\hat{n}$ is undefined, please revise that part
- line 158, an $(1+\epsilon/2)$  -> change an to a. (I think a one is correct not an one.)
- lines 183 and 184, related “works” -> work
- line 291, thenB-RR-Plant-and-Steal -> add space between “then” and “B-RR-…”
questions: questions: - In the experiments, what is the definition of success rate? Have you considered other utility sampling methods and if so, how did the results differ?
- Are there any matching lower bounds for the $\sqrt{d}$ Kendall-tau result?
- Have you thought about identical utilities? Can we achieve better guarantees assuming that agents have identical utilities?
limitations: limitations: This is a theory paper and I don't see immediate serious concerns. I would recommend the authors to discuss how much inefficiency their method can have in terms of social welfare for instance. Discussing the remaining gaps in the analysis is also helpful for the reader or follow up work.
paper_summary: paper_summary: This submission studies the problem of approximating truthful mechanisms for the Maximin-Share allocation of individual goods whenever agents have incentives. Specifically, the authors design a learning-augmented algorithm for allocating goods to agents, given a prediction over the agents' ordinal preferences over goods. Like other work on learning-augmented algorithms, the goal is to take advantage of the prediction to get a better approximation when it is accurate, while still being robust to inaccurate predictions. 

The authors give results for both the two-agent case and the n-agent case. Their results are based on a novel framework for designing allocation algorithms which they term "plant-then-steal". At a high level, the framework operates by first applying some allocation procedure (to be instantiated by the algorithm designer) which treats the predictions over agent preferences as correct in order to split the goods into sets of bundles (one per agent). In the second step, the framework uses the predictions to "plant" each player's favorite item in someone else's bundle. In the third step, the framework "steals back" each agent's favorite item according to their reported preferences. 

For two players, the authors instantiate the plant-then-steal framework in order to get a 2-approximation whenever the predictions are correct (i.e. whenever they are "consistent"), and a worst-case "robustness" guarantee of m/2 when the predictions are arbitrarily wrong. (Here m is the number of items.) The authors also show that the performance of their instantiation degrades gracefully as a function of how inaccurate their predictions are, as measured by the Kendall tau distance between the predicted agent preferences and their actual preferences. 

The authors also study the setting in which the algorithm designer is given access to predictions which don't necessarily take the form of agent preference orders. They show a lower bound on the trade-off between consistency/robustness, then provide mechanisms for allocating items in this setting using their plant-then-steal framework. 

Beyond two players, the authors provide a 2-approximation whenever predictions are consistent, and obtain robustness guarantees of (m - n/2 - 1). Finally, the authors empirically evaluate several allocation schemes on two-player instances, and find that algorithms based off of their plant-then-steal framework perform well.
strength_weakness: strength_weakness: I have no major complaints. One relatively minor criticism is that the paper may be hard to read for someone who is not already familiar with the Maximin-Share allocation problem. For example, exactly what an agent report is is never clearly explained.
questions: questions: n/a
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_summary: The authors study the problem of fairly allocating a set of $m$ indivisible goods among a set of $n$ strategic agents with additive valuations in a fair manner. The goal is to obtain a truthful mechanism which guarantees a good approximation of maximin share (MMS) of each agent. It has already been shown that no truthful mechanism can guarantee better than $\lfloor \frac{2}{m} \rfloor$-MMS, while a $\frac{720}{959}>\frac{3}{4}$ MMS allocations can be guaranteed when the agents' valuations are public. This paper bridges this gap by having a learning augmented lens and using predictions on agents' valuations. 

In particular, the authors introduce a framework called "plant-and-steal" which works as follows. For two agents, given a prediction $p$ and an algorithm $A$, it runs $A$ on $p$ (i.e., assuming the valuations are as given in $p$). Then from the bundle of agent $i$, a most valuable good based on the prediction $p$ is taken from $i$'s bundle and given (planted) in the other agents bundle. This is done at the same time for both agents. Then, both agents steal a most valuable good based on their reported values from the other agents bundle. It is easy to see that this mechanism is truthful. The authors prove that if the prediction $p$ predicts the ordering of the goods for the agents and the algorithm $A$ is the round-robin algorithm, then plant-and-steal is $1/2$-consistent and $\lceil \frac{2}{m} \rceil$-robust. Furthermore, they prove that the guarantee "gracefully" degrades in the number of mistakes in the prediction. They use Kendall tau distance as a measure of preciseness of the prediction.

For more number of agent, they prove a similar approach gives $1/2$-consistency and $((m - \lceil 3n/2 \rceil - 1)^{-1}, \lceil 3n/2 \rceil )$-robustness. It means that no matter how bad the predictions, at least $(m - \lceil 3n/2 \rceil - 1)^{-1}$ fraction of the MMS values of each agent is guaranteed assuming that the number of agents is $\lceil 3n/2 \rceil$.

Finally, they also have experiments showing how well their framework works in practice.
strength_weakness: strength_weakness: The contribution of the paper is limited in my opinion since the main result only concerns two agents. For more number of agents, while the consistency guarantee is not bad, the robustness guarantee is very weak. 

I have a more fundamental concern regarding the presented algorithm. The existing algorithms for approximate MMS (in the classic fair division setting without predictions) guarantee $\alpha$-MMS allocations and currently the best known $\alpha$ is marginally above $3/4$. These algorithms are not truthful mechanisms, however, they guarantee every single agent that if she is truthful, she will end up having $\alpha$ fraction of her MMS value. In particular for two agents, $\alpha=1$. Now, what is the use of having truthful mechanism which guarantee only $2/m$ fraction of MMS values of the agents? In particular, the proposed mechanism, incentivise the agents to be truthful, and in the best case guarantees $1/2$-MMS and if its own prediction is off, even much worse. What I am trying to convey is that, while there exists algorithms that guarantee $3/4$ and better approximation of MMS, what is the incentive for strategic agents to participate in a truthful mechanism, give away all their data (since their dominant strategy is to be truthful) and in return get way less than they could possibly get.
questions: questions: Could you please address the raised concern in the last section? 

Comments and Suggestions:

L 22: For the case of two agents ... : the sentence does not read well. Maybe replace "which" with "what"

L 40: ... over goods.For ... $\rightarrow$ .. over goods. For ...

L 58: with probability $2$ $\rightarrow$ with probability $1/2$

L 57 until the end of the paragraph: I did not understand why you mentioned randomized allocations at all and if so, why so briefly. In my opinion you should either discuss it properly and cite the related work or not at all. Having only one sentence on it was a bit confusing.

L 92: $\lceil \frac{m}{2} \rceil$ $\rightarrow$ $\lfloor \frac{m}{2} \rfloor$

L 122: ran $\rightarrow$ run

L 125: then $\rightarrow$ than

L 163: use \boldmath in the paragraph title

L 209, 213: $\ell$th $\rightarrow$ $\ell$-th

L 254: present present $\rightarrow$ present

L 264: espace before "for"

L 271: show prove prove $\rightarrow$ prove

L 291: space after "then"

L 320: allocated $\rightarrow$ allocate
limitations: limitations: No. The main contribution of the paper is theoretical. However, still from theoretical point of view, there are limits that could have been discussed. For instance while the robustness guarantee (for two) agents is almost optimal, the consistency guarantee is far from optimal.
paper_summary: paper_summary: This paper considers the problem of fairly and truthfully allocating indivisible items where mechanisms are equipped with predictions. When the prediction is perfectly accurate, the mechanism's performance should be significantly improved (consistency); conversely, for a prediction with any accuracy, the mechanism's performance should still be guaranteed (robustness). The paper aims to design truthful mechanisms with predictions that optimize the approximation to maximin share (MMS).

The paper achieves a variety of consistency-robustness trade-offs under different settings. For $2$ agents and ordering predictions, which predict agents' ranking preferences over items, the paper gives a truthful mechanism that is $2$-consistent and $\lceil m/2 \rceil$-robust, where the robustness guarantee matches the best approximation ratio achievable by truthful mechanisms without predictions. Another truthful mechanism is provided with $3/2$-consistency and $\lfloor 2m/3 \rfloor$-robustness.

For $2$ agents and arbitrary predictions, the paper gives a lower bound for consistency when the robustness is bounded. Moreover, the paper studies the trade-offs achievable by more space-efficient predictions. Finally, for any number of agents, the paper presents a truthful mechanism with $2$-consistency and a slightly relaxed robustness guarantee.
strength_weakness: strength_weakness: (1) The motivation for studying space-efficient predictions is not convincing enough.

(2) Most of the results only hold for two agents.

(3) The lower bound is not very promising as even in the non-strategic setting, the best approximation ratio for MMS is larger than $4/3$.

(4) Minor:
- Line 28: "probability 2"
- Line 60: Should briefly explain what it means by "ex-post" guarantees.
- Line 121: $\mu_i$ is not defined before.
- Line 212: "over agents items"
- Line 228: "according predictions"
- Line 254: "present present"
- Line 271: "show prove prove"
- Line 291: "thenB"
- Line 320: "to allocated"
questions: questions: Can you further explain why studying space-efficient predictions is important and interesting?
limitations: limitations: Some of the results are not sufficiently motivated or not promising.

Comments: comment: Thank you for the detailed response. My apologies for the very late reply. I have read all the reviews and your responses. Also, I recently checked the appendix more thoroughly and looked at some of the proofs. I do appreciate the effort put into finding different trade-offs between robustness and consistency and the attempted generalizations to $n$ agents. The main body, the two technical sections 3 and 4, do not convey the depth explored. I still believe the main body should be revised significantly as a NeurIPS paper (see below). 

I share the concern of reviewer iNp4. The strong inapproximability of MMS shown for truthful mechanisms from prior work, do limit the significance of this study. Robustness guarantees of $m/2$-MMS or sometimes $m$-MMS are quite weak. 

I hold a different view than reviewer dEcz on the main result for two agents. I still think most of the "heavy-lifting" for results of two agents, e.g., characterizing truthful mechanisms including working with ordinal preferences, and the positive and negative results on MMS approximability, is done by prior work. Also, we do not get that close to a full picture for two agents in terms of the trade-offs between robustness and consistency --- as many papers do in the learning augmented framework. That said, I like the simple and nicely presented steal-and-plant mechanism.

I am increasing my score, mainly for the results in the appendix.

On re-organizing:
One idea is to move the experiments to the appendix --- all the plots which are in the appendix unfortunately, which shouldn't be the case. Instead of the long our results section, the technical sections can better describe the results in details. Perhaps include one of the more technically novel proofs (or a sketch of it) would better be included.
I thank the authors for their response. Let me describe my concern in more detail. I understand the motivation behind having truthful mechanisms in general. However, I believe the known results on MMS (unfortunately) lessen the significance of this study. It is already known that $\alpha$-MMS allocations exist for some $\alpha>3/4$. Let's assume this algorithm does not have access to all the data but the agents report their valuations. This algorithm guarantees each agent $i$, $\alpha MMS_{v'_i}$ assuming that agent $i$ reports $v'_i$. This is completely independent of what other agents are reporting. Hence, for this algorithm to output an $\alpha$-MMS allocation, it does not need all the agents to report truthfully. If someone can gain more by misreporting, it does not make other agents to end up with less than $\alpha$ fraction of their MMS value as long as they report truthfully (which makes it different from the prisoner's dilemma). On the other end, it has also been shown that no truthful mechanism can guarantee better than $2/m$-MMS which is very interesting. On one hand, from theoretical point of view, I get the appeal of trying to bridge this gap, but given the explanation I gave above, I think the known $\alpha$-MMS algorithms are strictly better to use in any implementation. So beyond theoretical curiosity, I do not find other motivations for the given mechanism.

Nevertheless, I must mention that I really like the fact you mentioned in your response that indeed your mechanism only asks for the highest valued item. I think this should be more highlighted in the paper. I find this the most important factor that makes your mechanism comparable with the $\alpha$-MMS allocation which asks the agents to report all the values. I think more discussions need to be added to the paper to make the result in better perspective with what is already known. I should also add to the strengths of the paper that having only the ordering of the goods as prediction is a very reasonable assumption. I increased my score.
Thanks for addressing my concern, and please add the explanations to the paper. I will maintain my score.
Thanks for your reply. After reading the other reviews and responses, I have decided to maintain my score. 

Moreover, I do not view the fact that most results in this submission are for the two-agent case as a substantial weakness, as the two-agent version of this problem is sufficiently well-motivated. While more substantial results for the n-agent case would of course be interesting, I think that it would be unfair to the authors to have them be on the hook to completely solve the n-player settj g, as (I believe) the two-agent results already clear the bar for NeurIPS.