Plant-and-Steal: Truthful Fair Allocations via Predictions
Authors: Ilan Reuven Cohen
Alon Eden
Talya Eden
Arsen Vasilyan
Venue: NeurIPS 2024 poster (2024)
Keywords: mechanism design
learning-augmented
fairness
algorithms with predictions.
Primary area: algorithmic_game_theory
TL;DR: We devise truthful mechanisms for approximating the Maximin-Share (MMS) allocation via a learning augmented framework.

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.

Plant-and-Steal: Truthful Fair Allocations via Predictions
Ilan Reuven Cohen
Alon Eden The Hebrew University al eden@mail.huja ac. i1
Bar-Ilan University
ilan-reuven, www.wee.cchenobiuu.cco wwwen@biu.ac.... ac.
Talya Eden
Arsen Vasilyan UC Berkeley arsenOberkeley.com
Bar-Ilan University
Abstract
We study truthful mechanisms for approximating the Maximin -Shre (MMS) value 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, jarring result by Amanatidis, Birmpas, Christodoulou, and Markakis [EC 2017 7] shows that the best possible approximation for two agents framework investigate
and m items is 1. We adopt what is possible when a prediction on the input is given. For two agents, we give truthful mechanism that takes agents' ordering over items prediction. When the prediction is accurate, our mechanism gives 2-approximation to the MMS (consistency), and when the prediction is off, mechanism still obtains an m approximation to the MMS (robustness). We further show that the mechanism' 's performance degrades gracefully the number of "mistakes" in the prediction: i.c., we interpolate between the two extremes: when there are no mistakes, and when there 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 2 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 ensure consistency and robustness, come into play.
2
Introduction
Allocating items among self interested agents in "fair" way is age-old problem, with many applications such as splitting inheritance and allocating courses to students. As 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; ie.. there is no envy among the agents. Secondly, each agent gets 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 relevant scenarios such as splitting inheritance and allocating courses, things get trickier. For instance, if there's 's single item, the agent that does not receive that item does not get an envy-free allocation, nor they get their "fair share" according to the previous definitions. Therefore, it is clear that some faimess 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 al. [10]). In this paper,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 bundles are taken adversarially.
We study the case where agents have additive valuations over goods.' For the case of two agents, the procedure guarantees each of the agents their MMS value.
allocation produced by the 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 a-approximate MMS allocation for a > if every agents gets least an 1/a fraction of their MMS value. Feige et al. [22] introduce an instance where one cannot find an a-approximate allocation for 39 On the other hand, [30] show there always exists 3 aapppoximation. The a/ 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 the mix further complicates matters.
40
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 '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 a-approximate MMS allocation for an close to I as possible. [7] show that no incentive-con crrentvv-compatbbee algorithm can approximate the MMS to a factor better than 12 J. 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 < < m, a trivial truthful algorithm that lets the first n 1 agents pick single item in some order and gives the last agent the rest achieves an m-=++2 J -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- aaatingguummeeeedd point of view. In the Seaming--uggment framework, the algorithm designer aims to tackle some intrinsic hardness of the problem 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 function of the input, or a prediction, in order to improve the algorithm's '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- augmeente framework has proven useful in bypassing impossibilities that arise due to incentive issues [14, 1, 25, 15, 40, 33, 13].
When designing beariing-augmette 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 's performance should remain robust if the predicted ordering is almost perfect, with only few pairs of items whose real ordering is swapped in the prediction. Another desired property is to make the prediction as space-efficiem as possible, as previous results [20, 31, 32] show that succinct predictions crucial for learning parameters from few samples and for incorporating PAC-learnable component in the augmented framework.
'Agent i with additive valuation has value By ex( for every item, and their value for bundle S is (S) Ejes Fig- Forr > m, the MMS of each agent is trivially 0. The problem becomes more interesting for >>

---

In this paper we devise learning -ugmmened 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) Near- optimal robustness: when the predictions are off, we want to get as close as possible the optimal [ -approximation we can obtain by truthful mechanisms [7].
Plant-and Framework. In Section we present a framework for devising learning- augmented 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 near-optimal allocation according predictions. Our framework, which we term sant-anddSteal. is modular. Along with the set of goods and the agents' reports, also receives a prediction and an allocation procedure. Different combinations of predictions tradcoff'. It is worth noting that,
and allocation procedures yields different consistency-robustie although privacy is not the primary focus of this paper, the Plant-and- and-Stal framework uses agents' reports in minimal way, as they are only required to select (i.e. "steal back") 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 lcarning-augmentn mechanisms when the predic- tions given are preference orders over items of the agents, rather than the values. We instantiate the Plant-and anttt-nnd-ttall framework with Round-Robin based allocation procedure. We observe that in the case of two agents, Hound-Robing obtains 2-approximation with Round- -oond-Roiin as the allocation procedure almost immediately follows. using robustness follows two facts: (a) cound-Robin produces allocations that are balanced the framework ensures each agent gets one of their favorite items according to reports. In Appendix E, we show how to get an improved - consistency, while maintaining (m) robustness when using modified found-Robin allocation procedure.
the MMS. The 2-consistency of
m The 2
number of items allocated to each agent; and (b) The
In Sec 5, we then study the performance of the Round-Robin Robin procedure, when the prediction given is not fully accurate, but accurate to some degree. To quantify the prediction's '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-Stenn framework with a Round- Robin allocation procedure obtains V/Va)aapppoximmaioon to the MMS when the Kendall tau distance is d. Since d goes from 0 to (m) = ((m)), ). we recover the constant consistency when there are no errors, and the (m)) robustness when the number of errors is maximal.
framework when using the
General Predictions. In Appendix G, we study the two-agent case where the mechanism given access to predictions which are not necessarily the preference order of the agents. We first show that for any prediction given to the be a-consistent while maintaining finite robustness for a 6/5. For the proof, we leverage the characterization of two-agent truthful mechanisms by [7].
mechanism, no mechanism can simultancously
We then study small-space predictions. The -ennd--Roinn----se 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 Ollog m)-bit predictions. This already achieves a constant consistency along with 0(m) robustness. We then devise a more refined allocation procedure, which requires O(log m/))-bit predictions, and achieves 2 + consistency along with m robustness.
General number of agents n. In Appendix H, we devise learning- augmented truthful mechanism for n 2 2 additive agents. We obtain 2-consistent mechanism. while relaxing the robustness guarantees of the mechanism. We take a similar approach to the work of [18, 27, 28, 2, 5J, who compete against relaxed benchmark of the MMS value for ñ > agents, and try to minimize n. We obtain an max (m- ń - 1, laaprroximation to the MMS for = 3n agents when the predictions off. Our mechanism uses the modified Bound-Robin procedure from [8] to determine the initial
2
3

---

allocation using the predictions. It then applies a recursive plant-and 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, predictions are noisy, then the stealing component ensures robustness, and our framework achieves best-of-both both-ohotwoodds guarantees.
We summarize the bounds we obtain in Table 1.
Setting
Consistency
Robustness
Reference
2
m/2
Section 4
Ordering predictions,
3/2
2m/a]
Section 4
5/4
Any
[6]
Arbitrary predictions,
Any
m//2]
[7]
2 6/5
Bounded
Section G.1
3 log m + space Ollg(m))/4 space
4
1
Section G.2
+
mm/2]
Section G.3
2
2
3n/2
for
Section H
ñ = [3m/2]
Table
Known bounds for truthful ceaningg-uggmentie MMS mechanisms.
Further Related Work. In addition to the the studies mentioned above, we give comprehensive review further related work in Appendix B.
Preliminaries
In the setting we study, there is set N of agents and set M of 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 Viy (also denoted as (i)). For bundle S C M of items, v,(S) EEes Vij.
The fairness notion we focus on is the following.
Definition 2.1 (Maximin Share). The Maximin Share (MMS) of agent with valuation on and agents is
1 S1 U..US. S.USS.MM55 jE(n)
max min (s())
that is, if adversarially, what is the value can guarantee for themselves. When clear from the context, we omit and use p4 to denote the MMS of with agents.
partition the items into bundles, and then - 1 of those bundles are taken
We are interested mechanisms that produce approximately optimal allocations, as defined next.
Definition 2.2 ((y, -ppproxxiee MMS Allocation). An allocation (XI.... ) (7, k)- approximate MMS allocation for >> and natural number k if for every agent i,
<x())) 2 ph/n
When & say the allocation is aappproxmmate MMS allocation.
We study mechanism that get some prediction on the input.
Definition 2.3 (Learnig-AAugmente Mechanism). A learning augmented mechanism takes agents'
reports = (ri....,ral and predictions in some prediction space P. and outputs a partition of the items
X(r, (X, p), X2(r, p).... (r.,,,), X (r. =M,
where agent gets X1(1, p).

---

For learning -ugmmented mechanisms, truthfulness should hold for any possible prediction p. Definition 2.4. A learning-augmenti mechanism is truthful for every agent i and every possible report of other agents -- and every possible prediction P.
rx 2 ((((((Gr-..))
for every TT.
We next define the consistency and robustness measures according to which we measure the perfor- mance of our mechanisms.
Definition 2.5 (a-consistency). Consider prediction function fr which takes a valuation profile and outputs a prediction in prediction space P. A learning-augment mechanism is a-consistent for a > and prediction function fP for every valuation profile v and every prediction = fv(),, (v. is a-approximate MMS allocation.
Definition 2.6 ((3, k))robust), A learning-augen augmented mechanism is (B, k)-robust for B > 1 and natural number if for every valuation profile and every prediction p. X(v.P) an k)) approximate MMS allocation. Ifk 11, say the mechanism is B-robust.
For ease of presentation, for valuation v; report r; and prediction ps, we use of, r/. pf to denote both the gh highest good according to the valuatiionrreportprreiiiioooo of for > m, in this case, i O. For e = 1, i.e., the highest good we use ef p?.
and its value. Note that, we may use
Ordering Predictions and Kendall tau Distance. Most of our mechanisms use predictions which take the form of an ordering over agents' items. That is, fv(v) outputs vector of orderings p ..p....,,p))). where pf is the hh highest valued item of i in M according p. Accordingly, for agent i, let of be the 9th highest valued item according to v. For two items * j'. We use j > 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 inacourate. 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
Definition 2.7 (Kendall tau distance). The Kendall tau distance counts the number of pairwise disagreements between two orders. For i's valuation v, and predicted preference order pi, we define
Ka P:) = Vi pp j v,(i) v;(i')}.
That is, the number of pairs of items where the prediction got their relative ordering wrong. We also denote Ka(v,p) mmxx(Ka(e) P1), (a(v,,P2))
We note that the Kendall tau distance between uy and pt, Ka(U:.p)) can go from to (7)
3 Plant-and-Sten Framework
In this section, we present the framework which is used to devise learning- auggmeted mechanisms for two agents. The ideas presented here also inspire the more complex learning- aaggenntd mechanism for n > 2 agents. Missing proofs of this section appear in Appendix C. Our framework, which we term Plant-ande Dlant-and-Steal reports v. The framework operates follows:
given the set of goods, an allocation procedure A, the prediction p and
1. It first applies A on the predictions p to divide the set of goods into two bundles A1, Ag 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-robustie
tradeoffs we are aiming for.
2. Planting phase: For each agent picks i's favorite item in set A, according to prediction, and "plants" this item in the bundle Ay of the other agent * i. Let Tı, T2 denote the sets that result in this planting phase.
3. Stealing phuse: To obtain the final allocation, each agent now "steals" back their favorite item from set T, agent j # i according to reports. Notice this is the first and only place where use agents' reports.
5

---

This procedure is trivially truthful because the only step where we use agents' reports is the one where they pick exactly one item steal back from j,, and this T, only depends on predictions. and not reports (Lemma 3. ). 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 We show that for balanced allocations, we get improved robustness guarantees (Lemma 3.4).
For S S M, and agent let 1f (S) (S),;; (S)) be the max valued item in S according to U; (Pa, T;). for g E M and S C M, denote + == U {g} and S - S {g}. The Plant-and-Stes framework is presented in Mechanism 1.
MECHANISM 1: Two agent Plant-and--ee Sttal Framework
Input Allocation Procedure A, set of items M, predictions and reports Output Allocations X₂ X2 M
/* Find an initial allocation by applying A on the predictions */
(AI.42 = A(M,N, N. p)
/* Plant favorite items according predictions */
+- t-ii
j2 pā(A2)
Ti + A1 + 12
T2 + A2 + f1 32
/* Steal according to report +/
r
+
- 32 - T2 21
We 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 -odnt-and-aa Ste-Steal mechanism using A is truthfull
Since the framework truthful, from now on, we assume that = V. Next, we show that the Plant-and- -Seal mechanism ensures that for each agent, item is allocated with value that is least as good as their second-best option according to their value.
Lemma 3.2. Consider the allocation (X1. returned by Plant- and-Steal with some allocation procedure A. For any agent i, then i E X; or vi E X,,
We next claim that if i gets one of their two favorite items and any k additional items, i's value an k-approximation to J4c
Lemma 3.3. For any agent i, let S C M be subset of the items of size |S| = k and ea E S or of then
vx(S) 2 15/(m k).
We immediately get the following.
Lemma 3.4 (Robustness Lemma). Lei A an allocation rule guaranteeing min (lnn(Arll14,) 2 then when Plant- and-Stedd uses A, the resulting mechanism is (m - k))-rousst.
Proof. By Lemma 3.2, we are guaranteed that each agent gets one of their two favorite items according their report. Combining with the condition on A and Lemma 3.3, the proof is finished.
4 Ordering Predictions
In this section, consider the case of two agents, where the predictions (and in fact, also the reports) given the mechanism are preference orders of agents over items. Our mechanisms makes use of the Plant-and-Ste 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 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 truthful mechanism can achieve better approximation than 5/4 in this setting. This implies that when the predictions are preference orders, no augneettdd 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 predictions can obtain consistency 5/4 5/4-6.
Round-Robin Allocation Procedures. The two allocation procedures use instantiate the Plant aand-Steal framework take as input preference orders of agents over items:
Balanced-Roul
the agents take turns, and each turn, agent takes their highest ranked remaining item. This results in a balanced allocation.
1 1-2-Round-Robhe the agents take turns, where compensate the second agent, who might not get their favorite item, to take two items each turn.
In this section, we only prove consistency-robustee guarantees when MoanceddRound-Rolle is used as the allocation procedure. In Appendix we show different tradeoffs when 1-2 22-oonnd-Roa -obnn used.
ALGORITHM 2:
Input :Preference orders agents over items v = (0i, V2).
Output : An allocation A₁ ( A2 = M.
A, + 0 for every agent E {1,2}
for I. [[M [/2 do
A1 A1 + +
A1
\ A2)
A2 - A2
A1 A2)
Consider the allocation procedure depicted in Algorithm In order to implement the two allocation procedures, we only needs to receive preference orders over items. Let A; = (a.... a | be agent i's allocation by the algorithm, where of is the k'th choice of agent i. We observe the following. Observation 4.1. The output (A1, A2) of the Balanced- Round- Rod in procedure, satisfies:
1. |A1 = [ |A21 = 1
2. For each agent i and round k. at E beejssi that is, in round ls 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 allocate the remaining items to the remaining agents, gives 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 deferred to Appendix D.
Lemma 4.1. Let A2) be the allocation of Balanced Round-Rob (A.).) 2 22/2.
For every agent i,
We next use the allocation procedure to instantiate the Plant-and-Ste framework.
Sriind-Robin-Baae Mechanism. The mechanism we analyze, B-RR--lant---------- and-Stall, results from instantiating Plant-and-Stan with Ballancad-Round-Robhe as A.
We first show that if the predictions correspond to the preference orders of the real valuations, then CPR-Plant-aaa -nnd- outputs the same allocation as Balanced
Lemma 4.2. When predictions correspond actual values, RR-Plaatt und-Steal outputs the same allocation as wlwaacdddooudd...
We are now ready prove the performance guarantees of our mechanisms.
7

---

Theorem 4.1. Mechanism B-RR- ---nt--tnt---- Ielaant-nd-Stenn and-Steal is truthful, 2-consistent and mm -robust.
Proof. By Lemma 3.1, I, the mechanism is truthful. By Observation 4.1, each agent receives at least Im/2] items; combining with Lemma 3.4, we get that the mechanism is [ |-robust. Finally, if pre- dictions 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).
Noisy Predictions
We now analyze Mechanism B- D-RR-PIss Plwaaaaand--teeeeee performance under varying levels of noise. Consider the case where the Kendall tau distance between and p most d. Our main theorem in this section shows that combining the Plant-and and-Steal framework with Kound-Robie allocation procedure obtains O( ((Vd)-au apprrxximaiinnn 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, ny( (X.). to their maximin share, Ma, by considering the worst possible set of items that agent might receive under the Round-Rowd Round-Robin procedure when acting on their true preferences. Specifically, we define this worst-case set as R2 {u," [m/2]- In Eq. (2) of Lemma 4.1, we prove that v; (R2)) 2 1s/2. /2. Therefore, obtaining an allocation that is a factor of e times v; (Rs) ensures a factor of e/2 of the MMS value.
We further simplify the analysis by applying the zero-one principle'. The zero-one principle basically let's us reduce the analysis to instances where the values are either O's or I's. For threshold 2 0, let hrr (q) = 1 if q 2 t and 0 otherwise, and let of (S) Ejes h, (v)().)
By the zero-one principle, for two sets S, S M, in order to show that (S) approximates vx(T), is enough to show that of (S) approximates vz (T) for every threshold r 2 0.
Lemma 5.1. For c > and for any two sets S,T C M,, if for every threshold 2 of (S) 2 of (T)/c, then (S) 2 (TT//cc
Thus, we will show that when the Kendall tau distance is d, for every threshold 2 0, of (X,) 2 of (Rt)/c for some O(vd). Recall that A, 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 approximation of (A,) gives to (R,) is Vd.
Lemma 5.2. If the Kendall tau distance between p and v is at most d, then for any threshold T 2 0, we have that ui (A,) 2 o. (R₂) Vd.
We note that although o/ (A,) gives an additive approximation to of R:), it can still be the case that the Kendall tau distance is constant, yet (A,) does not give any multiplicative approximation to p4. Therefore, we must use the fact that agent gets to "steal" an item according to their true valuation in the Plant-and-Ste combining these results, we prove the following theorem concerning the approximation ratio of B-RR-Plant and and-Steall performance under varying levels noise, d.
procedure in order to get our approximation guarantee. By
Theorem 5.1. Consider prediction and valuations v such that Ko(v, p) = d, then Mechanism B- B-RR- Plant --w--nnd-eeete gives (2vd d + 6 -approximation to the MMS.
'Applied in [11], instance, in the context packet routing.
'Indeed, consider the case where there are four goods which both agents value 1,,1,0,0) 0). prediction orders the last two items higher then the first items, will get that v, (A,)) = O. while μı; 1.
.) If agentt i's
A similar analysis for Mechanism 1-2-RR- RR- Pal-Plantt-a Saann-and-Steeee Steal will show a similar dependence on vd (up constant factors).

---

Experimental Results
In this section we give experiments which illustrate the role of different components of our frame- work 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 ss 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 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 sampled valuation, the two sets chosen by the bag-fillin filliinng algorithm gives the two sets the same value, up to 0.5%, which ensures that the lowest valued set obtains a 1. u226-apprximmttio 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. Sondom-Steale
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 's set according 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- Piaiiion--laat---en Plant-Steal:
mechanism that implements the Plant- Plant-and-a and-Steal framework. partitions the items according to predictions, using the cut-and- 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 '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 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.
We plot the percentage of these instances where both players get at least (1 c) of their MMS value for 0.1, 0.05, 0.02.
Benchmark.
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 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
Results.
'The experiments, reproducible via Matlab (2022b) at http://tnnnu...oom//aaaalllleeee were performed standard PC (Intel 19, 32GB RAM) in about 30 minutes.

---

0002
0.95
0.1
10.5
0.8
Concelatd
0.6
0.0
0.6
0.2
10.2
0.2
01
20
40
160
6.01
2,500
10
40
100
640
2,500
5 10
40
100
600
2,500
0.8
0.8
0.8
Uncorrelaed
0.6
0.4
0.4
0.2
0.2
0.2
10
40
160
640
2,560
40
1000
G40
2,580
5
10
300
G40
2,580
Kendall ton distance
Keudall tau distance
Kendall tau distance
Figure 1: Mechanisms: Random (yellow), Random-Steal (cyan), Partition (red), Partition-Steal (green), Partition-Plant Plant-Steal (blue). Data generation: correlated (first row) and uncorrelated (second row). Success rate: the percentage of instances where both players receive at least (1 <) --fracctoon of their MMS values for different values of e: 0.02 (first column), 0.05 (second column), and 0.1 (third column).
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-Stedt achieves success rates of 66%, 75%, and 87%. In the correlated case, as each player has a highly valuable item stolen, their obtained value not expected to increase.
In the mechanisms that use predictions, Partition, Partition-Steal and Purtition Plant-Staade the performance degrades as function of noise, expected. When comparing the performance of Partition, which only relies on the prediction component of our framework, and Random-Steed Steal,, which only relies on the stealing component of our framework, for small amount of noise guarantee higher success rate, while as the noise increases, the stcaling instrumental to the performance. This is in tact with the theoretical results,
notice that in the uncorrelated case,
component becomes where using the prediction is crucial to achieve the consistency guarantees, which take place when the prediction is accurate, while stealing important to achieve robustness guarantees in case the prediction is inaccurate. As described above, in the case where the valuations are correlated, stealing not expected to help. Interestingly, fully noisy input, 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- 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-Sir -Seal and converges to it for fully noisy input. This illustrates the "best of both worlds" tradeoff obtained by framework.
Finally, when comparing the Partition- Plant- that Partition-Plant-Slere outperforms Partition-Steal in the correlated case with a small amount of noise (worst-case scenario) for e 0.02, as planting guarantees your favorite items would not be taken. In other scenarios, Partition-Steal outperforms Sartition-Plant-Stee because "planting" removes a valuable item from the player's set that might be taken otherwise, especially in the uncorrelated case.
Plant-Steal Steal strategy the Partition- Bartition-Steal Steal strategy, we observe
10

---

Acknowledgments and Disclosure of Funding
Arsen Vasilyan was supported in part by NSF awards CCF-2006664, DMS-2022444 CCF-1565235 CCF-1955217, CCF-2310818, Big George Fellowship and Fintech @ CSAIL. The work of A. Vasilyan was partially done while visiting Bar-Ilan university as a part the MISTI-Israel program, supported by the Zuckerman Institute. Part of this work was conducted while Arsen Vasilyan was visiting the Simons Institute for the Theory of Computing.
The work of L.R. Cohen was supported in part by ISF grant 1737/21. The work of A. Eden was supported by the Israel Science Foundation (grant No. 533/23).
References
[1] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Eco- nomics and Computation, Boulder, CO, USA, July 11 15, 2022, pages 497-528. ACM, 2022. URL battps:///oi.. org.
doi: 10.1 01111444444488635388888
[2] Elad Aigner-Horev and Erel Segal-Halevi Envy-fiee matchings in bipartite graphs and their applications to fair division. Inf. Sci., 587:164-187, 2022. doi: IN..
URL https:///oi..... org/ 1016/ -ins 2022 11.059..
[3] Hannaneh Akrami and Jugal Garg. Breaking the 3/4 barrier for approximate maximin share. CoRR, abs/2307.073044 2023. doi: 10.48550/AXX1.22300007700 URL https://doi org/ 10. 48850//aXivv 200223007000 073304.
[4] Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and improvement of MMS approximation. In Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 2485-2493. ijeai.org, 2023. doi: 10.24963/ICAA122233776. URL htte:/jaaa...////1..... 2023/276.
https://ddi.org/// 24963/ h/t/////jja.../
[5] Hannaneh Akrami, Jugal Garg, and Setareh Taki. Improving approximation guarantees for maximin share. CoRR, Abs/2307.12916 2023. doi: 10:4850/ARXIV.230..1299 URL https://doi.orgge htrg/10.4855/0 48550/ arxiv. 2307 12916.
[6] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. On truthful mechanisms for maximin share allocations. In Subbarao Kambhampati. editor, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 31-37. IJCAI/AAAI Press, 2016. URL http::/www. .jjcai org/ Abstract/16/012
[7] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference Economics and Computation, EC 17, Cambridge, MA, USA, June 26-30, 2017, pages 545-562. ACM, 2017. doi: 10.1145/3033274.008511 URL https: //doi.oog/10.
30851477
[8] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, 13(4):52:1-52:1 2017. doi: 10. 145/3147773
URL https: //doi. org/10..o/o. 1115///1111////77777
[9] Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos. Stefano Leonardi, and Rebecca Reiffenhäuser. Allocating indivisible goods to strategic agents: Pure nash equilibria and fairess.. In Michal Feldman, Hu Fu, and Inbal falgam-Cohen editors, Web and Interner Economics 17th International Conference, WINE 2021, Poisdam, Germany, December 14-17, 2021, Proceedings, volume 13112 of Lecture Notes in Computer Science, pages 149-166. Springer, 2021. doi: 10.1007/978- 978- 38-3--300 94676-0_9.
URL https: http::::://ii..////...//////////

---

[10] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris FilosRaasikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell. 322: 2023. doi: 10. ///.///TTT..202.... 103366 URL, httpt://p///o...... www//o......... 1016// artint........ 2023. 103965.
[11] Yossi Azar and Yossi Richter. The zero-one principle for switching networks. In László Babai, editor, Proceedings of the 36th Anmual ACM Symposium Theory of Computing, Chicago, II, USA, June 13-16, 2004, pages 64-71. ACM, 2004. doi: 10. 1..1144/007752210007366 URL https://doi.onn org/oogg//// 10. 1145/10073355 1007369.
[12] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence. EAAI 2021, Virtual Event, February 2-9, 2021, pages 5119-5122 5126. AAAI Press, 2021. doi: N0.1609/AAAAVV351..11 16616.16677. URL https: / /doi. http:/ooo.oorr//o////o 10. 1 aaai. vv516..66..... 16647.
[13] Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Bicriteria multidimensional mechanism design with side information. CoRR, 144/2202..1234,, 2023. doi: 10.48550/ARXIV. 14234. URL httph: //doi. org/10 48550/ 2302. 14234.
[14] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT. Cambridge, Massachusetts, USA, volume 251 of L/PIcs, pages 11:1-11:22 11:2.. Schloss Dagstuhl- Leibniz-Zentrum Zentrum für Informatik, 2023. doi: 10.4230/ LIPICS.ITCS.2023.1 URL https: //ooi. org/10. 11..1..4430211 4230/LIPICS. ITCS. 2023. 11.
[15] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, and Cherlin Zhu. Online mechanism design with predictions. CoRR, abs/2310.02872 2023. doi: 1044550/ARXIV2231000555 URL
https://doi. org/10.
[16] Siddharth Barman and Sanath Kumar Krishnamurthy, Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 8(1):5: 2020. doi: 10.1 145/3381555.
URL :/dtss://doi.. org/ 10. 1145/3381525
[17] Sylvain Bouveret and Michel Lemaître. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Auton. Agents Multi Agent Syst., 30())255--200, 2016. doi: 10.1007/510458-015-99938
URL htttps:///oi. http://doo.org/////// wrw/o.g.//0o 107700000048--11-99998
[18] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political E 11966):0061-1103, 2011.
[19] Ioannis Caragiannis and Georgios Kalantzis. Randomized augnennnedgggmeneeddd auctions with revenue guarantees. CoRR, Abs/24401.13384 2024. doi: 10.48550/ARXI1.220..333 URL https: //tp::///oooooo/.../// hetg//...8555.... 20550//rXivv 2401 13384.
[20] Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Online Allocation. In 50th International Colloquium on Automata, Languages, and Program- ming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LiPles), pages 43:1-43:22 2023. ISBN 978-3-95971-278-5. doi: 1.42330..Pccs.CCAA.PP2333.3
[21] Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu, editors, Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6-10. 2009, pages 71-78. ACM, 2009. doi: 10. 11114///156667415566663 URL attps://don org/ 10. 1145/ 1566374 1566384.
[22] Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In Michal Feldman, Hu Fu, and Inbal Talgam-Cohen, editors, Web and Internet Economics 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, volume 13112 of Lecture Notes in Computer Science, pages 352-372. Springer, 2021. doi: 10. 3-0088---300-------- 20. URL https::t htops:///od. /doii org/ /0. 1007 00000077778-3-000 94676-0 20.
12

---

[23] Jugal Garg. Peter McGlaughlin, and Setareh Taki. Approximating maximin share allocations. In Jeremy T. Fineman and Michael Mitzenmacher, editors. 2nd Symposium on Simplicity in Algorithums, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIes, pages 20:1-20:11. Schloss Dagstuhl Leibniz-7Zetrrm für Informatik, 2019. doi: 10,4230/OASICS. SOSA.2019.20. URL https:t/pp/.m //t.://doiioooo org/10 /0/ 200.423000000 2230/OASIcs SOSA. 2019. 20.
[24] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 539-556 ACM, 2018. URL wwwphhttps://tooo org 10////11110 10111114/11111 3219166 3219238.
doi: 10.1145/2219166.221999
[25] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, pages 529-557. ACM, 2022. doi: 10.1 00.1445944908863333266 URL battps://dole //dooi.oog//// www.orgg//... 1141 30t///3499446....533333
[26] Vasilis Gkatzelis, Alexandros Psomas, Xizhi Tan, and Paritosh Verma. Getting more by knowing less: Bayesian incentive compatible mechanisms for fair division. CoRR, abs/2306 020440, 2023, doi: 1144850/ARXXI.23360000000 URL https: :/toii:///..///// org/10 //// 48550/arXiv 2306. 02040.
[27] Hadi Hosseini and Andrew Searns. Guaranteeing maximin shares: Some agents left behind. In Rua Zhou, editor, Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 238-244 ijcai.org. 2021. doi: 10.24 (0.24963/JJCAA12221333 URL https : //woi//oioo/////////dd org/ 10tgg//1...0. 24922/1294ee jiaai......... 2021/34.
[28] Hadi Hosseini, Andrew Searns, and Erel Segal- Halevi. Ordinal maximin share approximation for goods (extended abstract). In Proceedings the Thirty-Second International Joint Conference on Artificial Intelligence IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 6894-6899, ijeai.org, 2023. doi: 10.24963/JCAA12223377 URL https: //to://oooooooo //t///i..og//../////// 24963/1jcai. 2023/778.
[29] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein, editors, Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 489-504. ACM, 2018. doi: URL https: //w. /00g/ 11111....111111 /
N0.1145/183313331990
[30] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing ap- proximate maximin shares. J. ACM, 65(2)88:18::7, 2018. doi: 10.1145/314075. URL
https://doi. org/10. 1145/3140756.
[31] T Lavastida, B Moseley, R Ravi, and C Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. In European Symposium on Algorithms, 2021.
[32] Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6523 6532. PMLR, 2021. URL http: pttcce/dgp/..c.ingg.. html.
mlr. wttpppsssss/////ee
[33] Pinyan Lu, Zongqi Wan, and Jialin Zhang. Competitive auctions with imperfect predictions. CoRR, abs/2309.15414, 2023. doi: 10448550/ARXIV.2309.555 URL https://doi org/ 10. 48550//8XXiv... 2309..1514..
[34] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
J. ACM, 68:4):24:1-24:25, 2021. doi: 10.1145/3447579, URL htttps://dot org/ 0t///10.11111 1145/ 3447579.
[35] Michael Mitzenmacher. How useful is old information? IEEE Trans. Parallel Distributed Syst., 11(1):6-20, 2000. doi:
URL https://doi. wwg.oog///// 11t.:/..111197..84555555
13

---

[36] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM
J. Discret. Math., 34(2):1039-11) 1010--109....---111 2020, doi: 10.1137/19M1249975 URL https://doi. org/10. 1111111991111 19M124397X.
[37] Biaoshuai Tao.
On existence of truthful fair cake cutting mechanisms. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 15, 2022, pages 404-434 ACM, 2022. doi: URL https: htt.://ooooooo//./o///o 10. 01445/34904863358833
10.1 111144444486635338838
[38] Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz, editors, Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Mas- sachusetts, USA, June 7-11, 2010, pages 109-118. ACM, 2010. doi: 10.1 10.1145/180734421877760. URL. www.hhttp//.c.....m /tti.//oiiooo// http://ooo//oo/o/oo///o..ooooolt 10. 1111/11111111 1807342.0 1807360.
[39] Adam Wierman and Misja Nuyens. Scheduling despite inexact job-size information. Zhen Liu, Vishal Mísra, and Prashant J. Shenoy, editors, Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2008, pages 25-36. ACM, 2008. doi: (0.1145/137445.1375555 10. 09.1145/1375557 1375461.
URL https://ddo org/
[40] Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Luc De Raedt, editor, Proceedings of the Thirty- Chirty-FFrst International Joint Conference on Artificial Intelligence, IJCAI 2022, pages 571-577 ijeai. org, 2022. doi: 10.24963/ICAA.20228111 URL petps://dot org/10. 24963/ /asis/ijcaaa ijcaiiccaii.. hetjaaiii//////2 2022/02222222
A Experimental Supplement
generate interesting valuations for the players, we use 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 four-step Hhigh/MMe/LLo//Etrre//
Generating valuations.
random valuation function, where item has 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 U10000, 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 U11, 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 chosen independently and uniformly random.
Generating predictions. To generate predictions, we take valuations and permute elements ran- domly create noise. We generate predictions under varying noise levels according the Kendall tau distance between the valuations and the predictions. We very the Kendall tau distance between 1 2560, where 2560 corresponds the expected noise level of random permutation of 100 items. To randomly choose a permutation of certain noise level, we start with the ordered permutation and then choose two indices k u.a.r. and swap items and increases the Kendall Tau distance by one. We repeat this process until the distance of the resulting permutation equals the desired value.
for [i..., 1} if
B Related Work
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-
framework of
studying consistency-robustees. tradeoff's was introduced by Lykouris and Vassilvitskii [34]. [35, 39]
studied the performance of algorithms using imprecise predictions.
14

---

2,000
1,500
values
1,000
500
20
60
80
100
index
Figure 2: Plotting randomly sampled valuations for two players, where the values are sorted such that lower indexed items have higher values.
Fair division with incentives. The two closest papers 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 ranking over items is public information. Using this, they are able to obtain a 2 -t--approximatti algorithm. One view this provide robustness guarantees. [7] Fully characterize truthful mechanism for 2 agents with additive valuations. They use this characterization to provide strong lower bound of for any truthful mechanism.
20 "ーz Finally they consider the public ranking model, where the
algorithm that is given prediction over the input, but does not
[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 symmetrie 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-Rohh Robin procedure produces 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 guarantee for themselves when partitioning the items into different bundles, where 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 a demanding task (which was shown be infeasible in some cases by Kurokawa et al. [30]), Budish [18] relaxed the notion and defined the l-out-of-n + MMS to be the worst bundle out of the bundles that define the MMS when partitioning the items using additional bundle. [18] showed it is possible achieve this benchmark when adding a small number access goods. There has been an effort to find the smallest & for which an allocation that guarantees l-out-of-k MMS for each agent exists. [2] were able to show the existence for l: = 2n 2, [27, 28) achieved = [3n and recently, [5] showed the
smallest up-to-date k [ In our n-agent mechanism, our robustness guarantee approximates this relaxed benchmark for k 3n
15

---

Mechanisms. Agrawal et al. [1] and Xu and Lu [40] first explored the surming-augmented framework in mechanism design setting, where [1] studied the facility loca- tion problem while [40] applied the framework to several settings such as evenue-maximizatie path auctions, scheduling and two-facility games. [14] give nearly optimal consistency-robuseeess 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 3
Proof of Lemma 3.1. We show that agent is better off reporting their true valuation, a symmetric argument holds for agent 2. First, notice that sets Ti and Z2 are determined using predictions, ignoring the reports. Next, notice that the item j2 is chosen only using agent 2 i's report. Therefore, the only way agent I can affect their allocation by choosing which item in T2 allocated to them. agent gets their favorite item in T2 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, Ti, T2, is always guaranteed to have one of their two favorite items according to their true valuation in X,, This is because either (1) i has one of their two favorite items in Tr, + i, and gets their favorite item from Tr; or (2) i's two favorite items are in T,, and in this case, i gets all items from T; but one, is guaranteed one of them.
Proof of Lemma 3.3. Let g E 5 S [u: v. by the definition S such g exists. Let = {g}. by the definition of S, we have |S = k - and (5)) 2 of + vs(S") Consider partition
(S1,5)) E arg max T.) TUUT=M min (Ty)) SE(1,2)
By definition, μ4 minje (S,). We have,
H4
14 o? + (S()
(S)
(1,) (S))
min (S₁) (s()
minje(1.2) U; \ {5')
uf
minje (1S, \ SS max(u, Sj (8))
(m - k) min max(u
k.
where the before last inequality is since if Sj C S' for some j. then of + v;((') 2 ps; therefore
Si S and S2 \ 5" are two disjoint non empty subsets and |S| \ S' + 1S2 \ S'| = m 1, hence the maximum number of elements in one of these subsets is k.
D Deferred proofs from Section 4
Proof of Lemma 4.1. By Observation 4.1, we have us va(a)) 2 2k therefore
|4.
[m/2]
2: *((A)) =
(I)
1=1
16

---

Since i's favorite item must be absent from some set of the sets defining the MMS value,
Σ
km
Since the of are ordered, of 2 u hence
Σ
1m/2]
2
2
m/21 2k+1 Therefore,
-=
k=1
m
14/2
(2)
By Equations (1),(2, we have:
mm/2]
(AA)) 2
u 1:/2.
k=1
Proof of Lemma 4.2. Let ji be the first item assigned in aalaanndd-ooodd-Roo definition, J1 is agent I's favorite item in M according to P1- Clearly, in Plant and-Steal, Ji is also agent I's favorite item in A S M according to P1. Hence, j1 = j1- By the definition of E T2. Since we assume the prediction corresponds agent I's actual value, is also agent I's favorite item in T2 M, which implies
agent 1. By
Pl ant-and--Steaa
j1.
Similarly Let ja the first item assigned in Balanced- Roundd RRobin to agent 2. By definition, //2 is agent 2's favorite item in M (i1} according to P2- Since E A1. A2 M (i1). Therefore, d2 is also agent 2's favorite item in A2 according P2- Hence, f2 j2- Since established that j1. have that Tj S M \ {ji} and Tí. Since we assume the prediction corresponds to agent I's actual value, J2 is also agent I's favorite item in Ti, implying 32 j2. We get that X1 = A1 and X2 = A₂ as required.
E 1-2-RR-Plant- and-Steal Mechanism: 3/2-consistent,
Mechanism
In this section, we show that using a modified round-robin allocation procedure to instantiate the Pl Plant-andSSted framework give improved 3/2 consistency guarantee, while maintaining (mm) robustness. Consider the Balanced RounddRooiinnl One can show that the agent that picks first actually gets value least as large their MMS, while for the second agent this analysis is indeed tight." In order to compensate agent 2, 1 lets this agent pick two items each round. See Algorithm 3 for details.
procedure depicted Algorithm
ALGORITHM 3: 1-2- Round-Robin
Input :Preference orders agents over items v = (01, V2). Output An allocation Ai (J Ag M.
A, + 0, for every agent i E N
for I,.... [[ /3]] do
A A1 (M
A1
A2)
A2 + A2 + D (M
A1
A2)
Az - A2 +
(M
A1 A2)
Let at be agent i's kth choice in 1-2-Round-Robin we observe the following.
Observation E.1. The outpul (A1, of the 1--2-Round-Ree procedure, satisfies:
1. A [ and A
2m
3
2. at (offee[BK 2]. a²
for (e and a² E {ub]ee(an)
"Consider the case where the agents' valuations are (m-1, I,... 1). According to Round Robing allocation, the first item will be assigned agent and agent will have m/2 items of value 1, while μ22
17

---

Amanatidis et al. [6] show that Ro--RouundRobiin guarantees each agent 2/3 of their MMS. We provide the proof for completeness.
Lemma E.1 (Amanatidis al. [6]). Let (A1, A2) be the allocation of agent i, vA(A,) 2 2/4/3.
For every
Proof. We first prove the approximation for player (the first player to be allocated). First, observe that en (M) 2 2/11- Let 1 = [ A = 1, [,....[mm/.] be the worst possible allocation agent I might get in the 1-2-Round- Robdnn allocation. Notice that ei (11) 2 (M 2 2 /3. By
Observation E.I, 01 (a+) 2 u Therefore, 01 (A1) 01 (41 2 231/3.
Now consider player 2. As stated in the proof of Lemma 4.1, 2 \ 22) 2 P2. Let
1
f02n-1
& N A 3/ - 1 S m] and 122 { l E N A 3k m)).
First, notice that
02 (2 (2)) 2 202 v/)/3 3 2 2
Moreover, by Observation E.I, we have, v2(22 ((2--))) v²(A2) 2 (2 TB) 232/3.
1/2
3k- and 02 (a
02
Therefore,
The mechanism consider in this section, with 1 1-2-Round-Robies as A.
results from instantiating
The next lemma states that if the predictions correspond to the preference orders of the real valuations, then CO--RR-Plant-aam and-Steadl outputs the same allocation as 1-2 -2-Round-RRo -oonn. The proof is omitted it is identical to the proof of 4.2.
Lemma E.2. When predictions correspond to actual values, 1-2-RR-Plame www.----oonnt-nd-SStea-aa--e -aa--anttttt-ppit the same allocation as ---Rondd-Rool
We next show that in ww----ant--------eeeeeeee-ll and-Steal able achieve better consistency, while slightly weakening the robustness guarantee.
Theorem E.1. Mechanism 2- ---RRR-Paant LaaattanddSttee truthful, 3/2 3/2-consistent and
2mp -robust.
Proof. By Lemma 3. the mechanism truthful. By Observation E, each agent receives least [m/3] items; combining with Lemma 3.4, we get that the mechanism is 3
2m -robust.. Finally,
predictions correspond to valuations, by Lemma E. and Lemma E.2, the allocation 3/2- approximation to the MMS. Thus, the mechanism is 2/ 2/3-consistent.
F Deferred proofs from Section 5
Proof of Lemma 5.1. Let S = {s...... su} (1S) k) and T = (t.....,fy ..) (TT) = E). We have the following.
k [o((s))
Σ/ hr(o((s)))dt / Σ hr((s(s,)) 1 of (S)dr
(s(S)
5=1
5=1
[ (T) dr
1 о / (t, 1 Σ / hr(t,)d7 Σ exttt)
1
2
j=1
(T)/cc
where we use the identity J h (q)dr = q.
Proof of Lemma 5.2. Let | < < be the number of items agent i gets by Mechanism
B B-RR-PI- foa-Plat--o aant-and-aaa and-Steal. Let A, {a a ...... th be the items assigned to agent i in the
18

---

Round-Rood Sohnd-Robin according to the predicted orderings p. where of is the item allocated to in the 5 round of Round-Robin. First, by Observation 4.1, we have: of E {vt (vE.se(,.....0)
For a fixed v 2 0, let L, = ou (Rt) be the number of values larger than threshold r in R. We show that if the Kendall tau distance is at most d, then it must be the case that
(A,) 2 L, - vd.
(4)
Note that (uf) for S 2- L, since R₁ gets every second item by the sorted values of agent i. This implies that if hr (vi (af)) = 0 then of = v for k > 2 Ly, Moreover, if f < Lr then of = p for k S 2- Ly by Eq. (3). Thus, if >k= (v) < L, - vd there are strictly more than [vd]] items whose rank according to the true valuation is 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 contradiction. Formally, let
G1 = JoE \ (ep keft,......
be the set of items whose rank is at most 2 L, according the real values but not according to the predictions, and let
G2= = kef2k.....
\ {et kef2..22..
be the set of items whose rank is strietly larger than L, according to the real values but not according to the predictions. By the above, |G1| = [G2 > [vd], and for each pair j E G1,5' E G2,
1. j rank according to o; is at most 2 L, and j' rank according to U; is at least 2 L + 1;
2. j' rank according to p. is at most 2- Ly and j rank according to p. is at least 2 L, + 1.
That is, j and j' are ordered oppositely in the ordering according to p. and Since there are |G |G2| > such pairs, we get that the Kendall tau distance is strictly greater than d, a contradiction. C
Proof of Theorem 5.1. Recall that, in Eq. (2) of Lemma 4.1, we establish that:
vy (R.) 2 p4/2
(5)
In addition, apply the zero-one principle to show that Lemma 5.1 holds for the sets X, and R, with vd + 3. The proof follows by combining these two results.
Notice that [A, \x, S 2, because in the "stealing" phase, agent might not take the "planted" item from A; back, and the other agent might take one item from A,, Moreover, by Lemma 3.2, either ul or v² are in X,, Therefore, for every threshold r 2 O,
(X,) Z max (a (vf), o7 (A.) - 2}
> max (h- (1 o7 (R,) Vd-2),
(6)
where the inequality follows Lemma 5.2.
If (vf") O, then of (R:) < [R,]- hrr (v²) 0, and Lemma 5.1 holds with = 0. Therefore, the (R.)
which we want to bound. Since interesting case is when (x,) = Consider the ratio (X.)
of (X,) 2 (uf) = 1, vz (R.) E [1, Vd + 3] implies that v/ (Rt)) S ( S Vd+33
(X,)
On the other hand, by Eq. (6), setting of (R,) = Vd + 3 + 8 for > implies that of (X,) 2
of (R.) - Vd - 2 > 1 + 8, which yields
of (R.) (X,)
I Vd + 8
< Vd+ 1+8
We get that Lemma 5.1 holds for X; and R; with c= /d + 3. Thus,
(X,) 2 (R.)((V 3) 2 / (2Vd + 6),
where the last inequality follows Eq. (5).
In fact, this holds for any noise in the valuations of the other agent.
19

---

G Non-ordering Predictions
In this Section, we consider the case where predictions are not necessarily preference orders over items. In Section G.I, we show that for any prediction the mechanism might get, consistency is bounded away from Sections G.2, G.3, we study succinct predictions, i.c. predictions about general structure of the preferences of two agents. Section G.2 presents 4-consistent and [m/ -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 + e-consistent and [m/2] -rrbustt mechanism exists, whose consistency relies on correctly predicting only (log m/e) bit about the preferences of the two agents.
G.1 No Mechanism with 6/5 Consistency and Bounded Robustness
In [7] they define the following family of mechanisms.
Definition G.1 (Singleton Picking-Exchangg Exchange Mechanisms [7]). A mechanism is a singleton picking-exchange mechanism if for each E {1,2), there is exactly one of sets: either N; M, or F = {&e for single item E, E M. If N₂ is non-empty, then the mechanism lets player j & i pick item E N; that maximizes Uz (E), and gets N₂ \ {f). If both F1, F2 are non-empty, then the agents exchange the two items & E Ei and lg E Eg uf (42) > vi (f1) and v2 >> 2s (l2). Notice that if m either En or Eg is empty 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 -exchinngee mechanism
We make use of this characterization in our impossibility.
Theorem G.1. For any > O, there is no truthful a mechanism with consistency 6/5 and bounded robustness.
Notice that for the predictions, M1 122 = 1. We show that for any singleton-picking exchanng mechanism, no agent obtains both large items (of value 1/2). Consider agent (the argument is symmetric for agent 2). If N₁ is non-empty, then if both large items are in N1, surely 1 will only get of them. If both large items are N2, then agent will surely pick one of them, and agent 1 will only get one of them. If one large item is in N, and the other is in N2, each agent i will pick the large item N.. If agent has large item in E2, then since N2 is non-empty, E₁ is empty and agent 2 will keep the large item. Now consider the
Proof. Consider the case where P1 p2
where F₁ is non-empty. In this case, Fy contains Eg can contain at most one item, and there are more than 2 items, in this case, Eg = 0, and NN21 = 4. Therefore, N2 contains 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-exchhi exchangh mechanism, the large items are split among the agents. Since there are 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.
item, and N1 is empty. Since
G.2 4- 4-Consistent, (m 1)-Rousst Mechanism Using a log m + 1-Space Prediction
Let us formally define mechanism that uses space-s prediction
Definition G.2. A learning-aus augmented mechanism is a space-s mechanism if the prediction space PP can be represented by the elements of (0, 1)
We first give simple mechanism that only requires 3 log + bits of information about the valuations 01 and V2. It will only need to know an index jo in [m] together with a bit b to produce an axproximately-optinee The mechanism will utilize the Plant-and-Starn framework in conjunction with the well-known bag-filling allocation procedure:
allocation, and an additional 2 2og bits to implement the planting phase.
We see that, order to predict the behaviour the mechanism above, one only needs to predict accurately the index jo which the mechanism terminates, as well as bit b {1, 2) that encodes
20

---

MECHANISM 4: Bag-Filln Filling
Input Preference orders of agents over items (ei, U2) on set of items M [m1]]
Output: Allocation Ai U A2 M
j
for j = 1,.... m; de
if (I(Gi) [ 2 2 then Output A2) 6- ([i), [v]] \ [T) and terminate
if (a((1)) 2 then Output (Ai, A2) < ([m] \ [3) [)) and terminate
[m(
whether the algorithm terminates due to the condition
2
! being satisfied or due to the 2
condition
mx(()) (mm)
2 2 being satisfied. This can be encoded using log m + 1 bits.
We also see that the The Plant-and-Stee framework when used with the Fag-Filling allocation procedure gives truthful 4-consistent and 1-robust 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 (A1, Ag) given by the bag-filling algorithm satisfies 81 (A1) Z /1/2 and (2 2 U2 /2/2. By inspecting the Allan-and-Sten 2 will either (i) retain their most preferred item in A₁ and A2 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 vn (A1) - 0n (X1) will equal to the value of the second-most favorite item of Agent in A1. This implies that Di (X1)= 2 (A1) 2 la, Analogously, we see that 01 (X2) 2 un (A2) 12
framework (Algorithm 1), we see that both agent and agent
G.3 2 + c-Consistent, 1T -Robust Mechanism Using O(log m/ m/c)-spppp Space Prediction
We now show that a better consistency of + c can be achieved at the cost predicting Olog m/c) bits of information about the valuations 01 and U2. We will also obtain better robustness of [T] To do this, we will use the Plant-and- Steall framework in conjunction with the Cut-and aatt-and-Balanee Balance
allocation procedure. We first explain how the mechanisms above can be implemented by only
ALGORITHM 5: Cut- Bad-aae
Output Allocations A, U A2 = M
Consider partition S, U S2 = M satisfying S11 2 |Sa] and
min (E(1.2
01 (1,)
mamx T2=Mr min vT(T)) (1 - c)pı Se(1.)
Let c be a set [m/2] | items satisfying
(S S (S
if Sa] > 1 additionally satisfying vi() S v1 ().31))2, for some arg arg ma (7) jnd arg max (i)
Set S, + S₁ S and $2 + S'
Let 12 < arg maxie (St) and let in be the index of the other bundle
Set A + S., and A + Sig. and output the allocation A2)
obtaining Oloog m/c) bits of information about the valuations and 02. This follows from the following proposition, the proof of which is given in Appendix G.4.
Proposition G.1. Suppose M [m]. There is partition M L. LU U and indices
01, 02 and 32 with [h|| + |Tall < O (2). such that the purtition M = S U2 de-
fined as S = L, L(S B1]) and S₂ = L2U(Sn 821) satisfies S 2 S2 and min( (S2)) 2 (1 c/44)/n
Additionally, there exist integers az B3, 44 and B4 such that the set S' = SN([as 8a] Uia4 Bal) satisfies | mm 1S2]. S' C Si vi (S") < (21)/2 and if [S2] > then S' also satisfies (i()") < vi (S (.,')) where j E arg maxjes, vi( and E arg max 21 vi))).
NNte that min(|A,) I. (Aal) S which implies that the algorithm is (m robuut
21

---

The main ideas for proving Proposition G.1 are: (i) using the sets L1 and Lg to handle elements whose value v(z) is large, and separate the remaining items into the set S (ii) Showing that the remaining items can be separated into well-hehaved subsets of the form S SN 8.].
The proposition above implies that the sets S1; S2 and S' can be represented exactly via L1 and L2. together with the indices {ai. ... a4, B1, -.- 34). We will also need to know the index i2 [1, Since the sets L1 and L2 have size of O(1/e), all this information amounts to Olog m/e) bits as claimed.
The following proposition implies the truthfulness, the robustness and the consistency of the mecha- nism that combines the Bat-and-BBlle ance allocation procedure with the Plant- and-Steal frame- work.
The Plant - aeee-and-Saa Snnd-tteal framework, when used with Cut - and-aand-aa-aaa Bace ance allocation procedure, gives truthfful, 2 e-consistent and a [m/2]] [m///-robust -robust allocation mechanism.
Theorem G.2.
Proof. Truthfulness follows from Lemma 3.1. Since the sets A and A2 both have size at most [m/2], the robustness follows via Lemma 3.4.
The proof of (2 + c)cosissteyyyy deferred to Appendix G.5. The main challenge for showing allocation procedure and the
the bound on consistency is the fact that both the Cut-and Plant-and -Steal framework can reduce the consistency by factor of Naively, one would expect the overall consistency to be close to 4, given that each stage can lose factor of 2 in consistency. However, our insight is that for the instances, on which the Cut-and-BR Balance allocation procedure loses factor of 2 in consistency, the Plant-and-Set
framework will have consistency close to 1, and vice versa. This allows us to prove a tighter bound of 2 + e on the consistency of our overall algorithm.
G.4 Proof of Proposition G.1
We first show the following, which implies the first half of Proposition G.I.
Proposition G.2. There exists a partition M = L1 U L2 and and indices on, 02 81, in [m] the sets S Li (Sn[aa, and S2 L2 U (Sn[a2, 3x)
such that M- [an, B/o,, Bar.for
we have
(in 01 (1))) 2 (1 - c/8)/1
L1l + L2l S - +
|S1| 2 [
For every x in La and y in Si we have en (x)) > vily). Analogously, for every x in L2 and y in S2 we have Un (x) > vi(v)
There are 3,33 Li satisfying arg maxres, vn (c) and j arg pax (E).
We do this by inspecting two types of items, large items, with value greater than e/11 /4, and small items items with value at most /4. We first show that there are O(1/e) large items, therefore, separating these items into two bundles require at most ((1/e) intervals. Moreover, we can find separation of the larges items into two sets, L1, L2, and a single index j E [m] such that all small items to the left of j (including) together with L1 form S1, and all items to the right of j (excluding) together with La form S2, such that S1, S2 satisfy the approximation requirement. It is easy to see that this increases the number of intervals by at most
We start by showing there are not too many large items. Lemma G.2. There are most items with value strictly greater than epi for agent
Proof. Let items with value greater than c/114 /4 be the large items. Suppose there are at least [ + large items. If [ even, consider a partition (S1, Sz) such that each S; gets at least 1/2 large items and the rest are allocated arbitrarily. If [ is odd, consider the allocation which each S; gets (ī²) + 1)/2 large items and the rest are allocated arbitrarily. In either case, each S, gets at least S /2 > 4 large items. Thus, min(v:
vn (S2)) (S;),,
eu1/4 1 M4, contradiction.
22

---

We are now ready to prove Proposition G.2.
Proof of Proposition G.2. Consider the set of large items, L {j E [m] v1(1) e4//4), and let S MM \ L be the set of small items.
We give constructive proof which finds both sets L1, L2 and an index j satisfying the condition stated in the lemma. Let
min 2n (S)). (L1, L2) E arg (agmax : UT= je(1.2)
We use the following procedure to find j.
1. Let je = 0 and j. = m.
2. While je # jr:
(a) Let St = L j' sc) and S, = L2 Uff ES f
(b) If 01 (St) < 21 (1,))
je- 1.
(c) Else:
Jr = jr 1.
3. Set j == je jr:
We consider two cases:
Case 1: j O (or symmetrically. j m). Without loss of generality, suppose that j = m. We first show that if 0n (S1) < (S2) then (in)) 21 (S2)}
μıر Notice that since S1 gets all the small items, it must be the case that 01 (L,) < 01 (L2). Suppose there's a different partition Ti U22 such that min(er (Ti), ui (T2)
(Sn(fr(S),, (S))). Without loss of generality, let en (Tr n L) S vi (T2 n L) (otherwise, we can rename both bundles). By the definition of L1, L2, it must be the case that vn (In) 2 en (Ti n L). Thus, Since Ti \ (Ti L) S S, it must be that
ii (8i) 1i ()) 2 vn (TinL) (T) (TTnL)) vi (Ti) N min(vi (Ti), vi (T2)),
contradiction.
On the other hand, if (S1) 2 01 (S2) 0i (L2), by condition 2b of the above procedure, it must be the case that when je was equal m - 1,
(S²) < 1a (S,) = v1((2) = u, (S2).
Thus,
(Si) (1() + (m() (1 + E41/4.
We get that
01 (S2) 2 vi( ////4 2 2p1 (1()2) cui/4 = min(e1(11), un (S2) (Sa) 2 (1 - (118)
where the second inequality follows since 2/41 S v (Si) + (S2).
Case 2: 0 j < m. In this case, since both je and j. were moved, there were some values of je and j, such that (St) S vi (S,) and some values such that in (St) > 2n (S.). Assume initially that vi (S²) S 2i (S.). Since at each step of the procedure, the the lower-valued bundle can increase by at most eu1 /4, when the first item is added to St such that (St) > 01 (S.). it must be the case that in (S²) < S,S,) eu1 4. It is easy to see that the invariant where |v> (S²) Un (S,)) < Eju1 / is kept throughout the run of the procedure. Therefore, this also holds for the final S and Sz. Thus, we can use the same reasoning of Eq. (7) conclude that min (S1), 21 (S2)} 2 (1 c/8)
Thus, the sets S₁ and S. have a form S = L, (S j]) and S2 L2 L2u(Sn + 1, ml) and have the form required. If |S|| < |S2l we can swap our definitions for the sets Si and S2, thus ensuring that [S| > S2). Due to our definitions of T,, and To2 we have for every x in L, and y in S we have in (x) > (v). Analogously, for every in L2 and y in S2 we have 21 (x) > 22 (g).
23

---

We can ensure that There are 3.3 E L1 satisfying
j arg max (f) and E arg max 1i (e), EES1
BESiVj
by adding such values from Sn [ai, 3i] to Lı (we see that after this all other properties still hold).
Overall, that L1| + L2 S
2, required.
Now, we proceed to proving the second half of Proposition G.1. We will need the following lemma.
Lemma G.3. Let l and k2 be positive integers satisfying k1 > 12, and let f be function mapping [k1] non-negative real numbers. Then, there exist a pair of integers a, B, of and 3 [k1] such that [|o, 3] U [a', ,8] k2 and
Eiela on f(i)
Eie(ka) f(i)
k1
Proof. We prove the lemma using the probabilistic method. Let j be uniformly random integer in [k1], and choose a, 3, and 3' such that
(o, [3] U [o', 33 = (i.++ +1 mod ..,... . + k2 mod k
We see that indeed set chosen as above can be represented a union of intervals. Now, since is chosen uniformly at random form [ki]. we see that for every element in [ki] we have
h-2
Pr liE E (J,++1 +1 mod k1, ... . + 2:2 mod ki) |~
k1
Thus via linearity of expectation we have:
Σ
1
S0).
1
K1
mod Ai, + mod k)
AE(Aa]
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 that
1
Σ
f(i)}
1
Σ f(1, sE(R
(e(s++1 mod kar" 5+h2-1 mod R1))
which finishes the proof.
Now, we apply the lemma above. < 4[ + we can satisfy Proposition G.2 by:
1. First choosing partition M S₁ U such that min(v: (S1), U1 (S2)) 2 μl and R1 Rgl.
2. Define L2 = S2, put the smallest [m/2] - |S2 elements of S into S, and define Lı to contain the rest of elements in Si.
3. Define a₁ = 03 = 1, 3 = B3 m, 3₂ = a4 = B1 m + 1.
Overall, this allocates S' to the bottom [m/2] elements of S,. We see that this suffices to guarantee the properties that S' needs to satisfy in Proposition G.I.
Therefore, henceforth we can assume that m _ + +2 Since [S1] m/2 and ا1 S and S = L, U (S [ai, 31]) this implies that |Si [a1, B|]] 3 |s'| mm/ [Sz] using a subset S' Sn [01, 81]).
[[]] > m/2 Thus, we can ensure that
If [Sa]] we only need choose S' satisfy |S'| [m/2] |S&1 and ei (S') (1 ()53))/2.
First of all, since every element in L1 is larger than any element in S n [ai, 31]), we see that this is also true average
Eies, vi( S
EeE (e)
<
(8)
Is [a1,
24

---

Then, applying Lemma G.3 to the set S n [a1, 311) we see that there exist disjoint subsets (as, Sy]
and [a4,, 3a] of [an, B1] such that n (la3, Sol Ulas, 3al)i = mm2
|
En B:1) (I(
Eresn( Ui R.))) (e)
S
(9)
[
01, B:11
Ssn (103, Bs] U0
04, Bal))]
Combing Equations 8 and 9, we see that taking 5 = S n (l03, 3a] Ul44, Ba]) satisfies en (5") vi (S1)/22 2 and the other requirements of Proposition G.I.
S
Now, suppose S22 > 1. Since by Proposition G.2, the set S does not contain the two largest elements j and j' of S1, as well as the fact that every element in L1 is at least as large as any element in S 2 [0n, Bi]), we see that every every element in Si \ (G,'') is either in S Sn [0n, .1]) or greater than every element S (a1, (B])). this implies that:
EnESM (I(()
ErESn(or (e)
(10)
|
1S [ai, B1)1
Then, can again apply applying Lemma G.3 to the set S [a1, B,])) see that there exist disjoint
subsets (a3, Ba] and (as, Ba] of [a1, 31] such that |S n (ja3, Aa] U[a Bal))| = [m/2] - S/2
Exeshan 9.1) (t)
Ecesn(ass 9,1 &.)) (()
(11)
|Sn (11,31)1
|sn ([as, Bs] 04 8al))
Combing Equations 10 and 11, that taking S = S ([a3, 8s] Ulo4; Ba]) satisfies en (S') S (Si)) \ (1)3)) as required in Proposition G.I. Note that this also implies that ii (S') S e (S1))/2
since j. 3 have the top two largest values of e1 in S1. Overall, this finishes the proof of Proposition G.I.
G.5 Proof of (2 + ccoonssstt
It remains show that the algorithm is 2 + e-consistent. We will be referencing the variables Je. J1: 82. Ti and T2 within the Plant-And-Steal framework (Algorithm 1).
We first reason about agent 2. First, notice that since agent 2 has higher value for Siz-
02 (2( 2 P2.
Since the mechanism had chance to pick item j2 from Tj as j2. it must be the case that 12 (z())) 2 (2())) (and possibly J/- = -2). If J1 = J1, then T2 \ j1 = Si, \2z, and
#2 S uz((), = (a, \22) + 22(2) s (2 \āx + #2(22) = =x22))
Otherwise, 3n E Siz. and
1.2 c N3, (5, N22 \31) S 22 \51).
(12)
Since j2 is the item with the highest value for agent 2 in Sig, v2(22) 2 v2(12) 2 w2(ki). Combining with Eq. (12), we get that
(2 1 U Go 2 (8, (.2).
Moreover,
22 (T \i U (f2)) 2 v2(22) 2 mz(22).
Thus,
(X2) = (2 11 U (22) 2 v2(3.)/2 = p2/2,
as desired.
is left to show that U1 (X1) 2 12/(22 + c). If i = 2, then
v1(š,) v1(55) > (1 2 (1 E/4)/r.
25

---

In this case, the same exact arguments used for agent 2 can be harnessed to show that ti (X1) 2
(1 - (0-4/)))//3 /2 2 p1/(2 + e). Thus, is left consider the case where i 1.
Consider the (S1, 52) partition that is set in the first step of Cut-and- Bal ance- ancc--ond- Since (S') S v (51) we have
v5() 2 0i(S1)/2 2 (1- (1-/4))/122
M1
2+6
If f2 = =s2, we have that
en (x = (3 U (Ā)) \ (i:) 2 (1(()) 2
#1
2 2+c²
where the first inequality follows since v1 1 (1))
Note also that if [S2] = 1 i.e. S = {a), if j2 * then 21 (X1) 2 dj (52) since E T2, similarly if
je * then (X1) 2 1i (S2), finally we have j2 122 and e (X1) 11/(2 e) an in the first case.
Therefore, we assume 3/2 + 8/2 and [S2] > 1, and let i E arg max J88
2i (X1)
= =1())))((())1
(22)
-1)+
e1(S1 ((1)) - -1 (122
e1 + en (i1)
(S S \ +
where the first inequality is since, 21J, maxje7, Vij 2 1i11 The second inequality is since
in (fz) 2 O, the third inequality is by hí definition since j2 E 31 \i by our assumption that kg # je. Finally, we have have [S| \ S') \\ 31 H 2 |8"| since
|S 1 2 - |s = | 2 - (m/2 - S = |Si| - 2 - (m//2 - (m - ()) = m/2 - 2 2 |S
where the last inequality is since ||₂ > 1. Since we handles the case |S2| = 1 earlier, we can here assume |S2| > in which case the set S' is required to satisfy (S() S (. (,,3))/2 Therefore, we have (S, \ S² (1.31 2 (S').
(1 c/4))) S (S1)
mi(S \ (5 \ (h,311) +z + +i) vsS
I (i (S (6.31)) +2 + (S')
2 (S \8 (1- +1))
S 2 (X1),
which implies that 01 (xx))) 2 in
2 finishing the proof.
H Mechanisms for n agents
In this section we provide learning-augmenter mechanism for > 2 agents, Learning- SoineenteddMNS--fo-n-----
The mechanism we devise ensures that if the predictions are accurate, then each agent gets an allocation with value at least μ /2 (2 consistency). On the other hand, we show that for any prediction, every agent gets at least pf /a for î [3n/2] and a = max m - ñ - 1,1) (robustness).
Theorem H.1 The -aarmiin-Augmenteede -Mr-------f-------- Mechanism (Mechanism 6) is truthful, 2-consistent and (H.) /a) roobuut for î [3n/2] and max(m ât - 1, 1).
26

---

H.1 An Overview
The Mechanism. The mechanism works in three phases. In the first phase, uses the predictions in order to obtain partial allocation to agents with high predicted items (which are then removed from the of active agents, so that we can now that for all agents, all predicted values are small). Then, in the second stage, the mechanism uses the predictions in order to obtain a lentative allocation, by running Round-Robin procedure, where items are tentatively allocated to agents according to their predictions. In the third and final phase, the tentative allocation is used to implement recursive plant and steal procedure, where the "planting" is done from the tentative allocations according to predictions, but the "stealing" is done according to the agents' reports and results in a final allocation.
MECHANISM 6: haaprrang---ueeettdd------------
Input :et of agents set of items M, reports rN. predictions pv
Output: A partition of the items UieN X;
Invoke Algorithm/ 7, X Allocate-Large(N, M, MN, pN)
Invoke Algorithm 9, A <- Tentative- -aaa---ooonnddnnnnndd PN)
Invoke Algorithm 10, X Split-Plant-Steal Recurse A.first-levellflag True, X,
FN. px)
planting
(at a.)
(a), az.... ...)
(ah) af.
(at as.
(a}, ag.... ...
(a), az
(a), ab....
(al ab
(oh-1 1nd
(ah af
(ah a a
(ah ...
No
After tentative allocation. Each plants pf (A,) in the tentative set of the corresponding agent
After planting, before stealing
Stealing
(ab, af....
(at, az ...)
(at {af)
(ag...) (ab)
(ath as....
(att af ..)
(aā (at)
(af ..) (at)
(at, an-
(a ag
(an- [ah-1]
(ah . {ah
Ng
No
Each agent & e No steals vi (AN,) Each i E N2 steals (Av.)
Partial allocation (purple) after first round of stealing
Figure 3: Illustration of a single round the recursive planting and stealing phase (Algorithm 10), for the where predictions are accurate (so that each agent steals back their planted item). Note that the stealing is done from the union of items of agents in the opposite set (and not just from the corresponding agent).
Consistency. In the case the predictions are accurate, the initial allocation phase will take care of agents with high valued items (of value larger than μu /2). Then, in the second phase, the tentative allocation will be exactly identical to Round-Roud -ound-Robin allocation (made according to true valuations). Finally, the third phase, since agents steal in the same order they were allocated the items in the Bound-Robin allocation, and since the predictions are accurate, the agents "steal" back the same item the mechanism plants. Since Bound-Robing allocation achieves nu,' /2 when there are no agents with high valued items [8], conrectness follows.
27

---

Robustness. In the case the predictions are inaccurate, we show that every agent still gets at least /. /a. Here we rely on the plant-and and-steal phase to ensure that each agent gets least their [3n/2] highest-valued item according to their true valuation. This property provides our robustness guarantee. We notice that reversing the order between the first and subsequent rounds of the Round-Robin procedure (and thus, the stealing phases) gives enhanced robustness guarantee.
Prediction. In the description of the mechanism, we assume the mechanism is given a prediction of agents valuations. We note that in order implement the mechanism it is enough to be given access to agents' preference order over items, and an additional information indicating which items worth more than μu /2 for each agent i.
Due to space constraints the proof of Theorem H.l deferred to Appendix H.3, and we now provide detailed description of the different phases.
H.2 Implementation Details
As discussed, in order to utilize the Round- Rohnn mechanism, we first allocate single item to each agent with high predicted value.
ALGORITHM 7: Allocate-Large
Input :Stt of agents
of items M, reports rv. predictions pw Output A partial allocation Usea X,, updated sets of agents and items N, M, respectively
foreach i E N do
Compute yr," based on Ps
while exists ė E N such that p (M) 2 /2/2 do
X; +- {r] (M)
M M X
N {1)
Before describing the tentative allocation mechanism, we first give procedure, Allocate-Bess which performs a single round of Round-Robin according to a specific order, and preferences (either predictions reports), denote
PROCEDURE 8: Allocate-Best (One-Round-RR)
Input Ordered set of agents N, set of items M, valuation Output:| singletons X; E M
foreach do
X, + V. (M)
M + M X
The tentative allocation mechanism repeatedly invokes Allocate- -eett according to given pre- dictions, until all items tentatively allocated. As previously mentioned, the first round of the tentative allocation is performed according to the given order, and in all subsequent rounds, the order reversed (recall that reversing the order enhances the robustness guarantees).
ALGORITHM 9; crntraaiiee-lllocaaioo---oooo Robin
Input :Odeered set of agents N = (fn...., set of items M, predictions pm Output A tentative allocation UIEN A M
+ Allocate-Best(N, M,PN)
M < M \ A,
/* Reverse the order for the allocation of the reat of the items +/
(i ((....)
for ..... [m/n] do Allocate-Best(NV) M,PN~) A; A, U A, i
M M UiEN A;
28

---

The final phase in the mechanism is recursive plant and steal algorithm. The input to this algorithm an ordered of agents N. along with their predictions, reports, and tentative allocation for each agent. At each recursive invocation, the algorithm splits the set of agents into two (almost) equal-size ordered sets No and Ni. Then the mechanism "plants" for the 7th agent in each set N₂ their highest (according to predictions) valued item in their tentative allocation in the tentative set of the 1dh agent in N-B. Then we perform one round No 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 for an illustration and steal. The algorithm then recurses each of the sets No and N1, until all sets of size 1. At this point, the single agent in the set is further allocated its remaining tentatively allocated items, and the process terminates.
Hound-Robin, where the items available to the agents of set
single round of plant
ALGORITHM 10:
-Stal -Rccurse
Input :Ordered set agents N (f1,..., i tentative allocations A, partial allocations XN, first-level-fag indicating this the first level the recursion, reports rx, predictions pa
/* Halting condition Allocate all remaining items */
if N {1] then set X, X, U A, and halt
/* Split the agents into two almost-equal parts */
[N] mod? 2
No (f,, 2 (11 Ni (12,14..... NI-pa))
/* Plant according to predictions */
for i= I.... [|N]/2] do
Let 1", denote the hh agent in No, N₂ respectively.
J6 = (Aig)
Jí (Ai,)
A₁ Aoo + + -0 + j -1 Ji
Ap = Ap
Plant in's favorite item tentative set
par then
10 inst'
J0 (A,
Aa Aa + Jo. A,o A,, - -ā
Steal from opposite set according to reports
foreach b E (0, do
X=Allocate-Best (Ne, AN
foreach: N do
X. +- X; X,
/t Reverse the order after the first level of recursion */
if first-level-faa then No -4par 18,
N₂ ( parr- pars 12)
Recursively invoke Splitt-llatt-ttal--Reerre each */
foreach b (0, do Split-Plant- Searr-Sttaa--ReeeeeMMMMM RecurleeecraeeeN, AN,, fistt-st-leeel False)
Given the above implementation details, remains to prove Theorem H.1 regarding truthfulness, consistency and robustness of the mechanism. The proof is given in Appendix H.3.
H.3 Missing Details from Section H
In this section we prove Theorem H.I, which we now recall.
Theorem H.1. The Sww.einggnugmeeee---W.... tett-foo-n-Ageneee Mechanism (Mechanism 6) is truthful, 2-consistent and (H.) /a)//arrrobst/ for â [3n/2] and max nt 1,
First, we give simple observation regarding Algorithm 7.
29

---

Observation H.1. The followings hold for Algorithm Allocate-Larg
If the reports equal the true valuations, and agent i is allocated an item j. then v,(i) 2 12/2
2. After the algorithm completes its run, there are no remaining agents in N with large predicted values for the remaining items in M.
We continue to prove each of the properties specified in Theorem H.1 separately, starting with truthfulness.
Lemma H.1 (Truthfulness). Mechanism -eonsing- pore (Mechanism 6) is truthful.
(Algorithm 9) only depends on agents predictions and not their reports. Hence, we only need to consider the use of the reports in Algo- rithms 9 and 10.
Proof. Algorithm
For every agent i, either they are allocated single item in Algorithms 9, or i participates in the recursive plant ant steal, and this determined according to the predictions, so in particular r; has no affect on this. Thus, is allocated a single item, it is the item that maximizes their report over remaining items at that point, so that has incentive to lic.
consider the two independent events separately. In the first case, where i
In the second case, participates the plant and steal phase. Observe that in this case, whenever i chooses an item from some set A', it will have no future interaction with this set. That is, fix recursive call and assume without loss of generality that E No- Then after the planting step, is allocated the item in AN, that maximizes their reports. Then, in following recursive steps, only continues to interact with items AN,, so i's choice does not affect the identity of the items from which i will be able to choose from in future rounds. Hence, i's only incentive is to maximize the value of its allocated value in each round, implying truthfulness.
Due to the above lemma, from now on we assume agents report truthfully, i.c., that for every agent i, Us. We turn to show the mechanism is consistent, we rely on the following theorem.
Theorem H.2 (Lemma 2 in [10] (based on Theorem 3.5 in [8])). If for every i E N and j M, v((i) S 12" then the Round- Round-Robin algorithm returns an allocation that is 2-approximation the MMS.
Furthermore, their analysis holds when changing the order of allocation between the different rounds of the Round-Robin
We are now ready to prove the mechanism is consistent.
Lemma H.2 (Consistency). If the set of predictions is accurate, then for every i, (x())) 2 12//2.
Proof. First consider agents that were allocated an item in Algorithm Allocate-Large (Algo- rithm 7). If the predictions are accurate, then each such agent i is allocated an item such that va(i) Z μu /2 and so the statement holds. Moreover, at the end of this step, there are no remaining agents with large predicted values, hence, agents with large values remain.
If the of predictions is accurate, then the tentative allocation determined according to agents' predictions in Algorithm Round-Robin Robin mechanism according to valuations, with reversing the order between the first and all subsequent rounds. Furthermore, by the above, there are no agents with large values when the Kound-Robin invoked. Therefore, by Theorem H.2, it holds that for every (A,)) 2 μ /2. We shall prove that for every agent i, its final allocation equals its tentative allocation, X; = A., concluding the proof.
Rowiionn--oood---ee RRbinn ( Algorithm 9) is identical to a
We prove that in depth & of the recursion, every agent is allocated the 1tth item in A₁. We prove the claim by induction on the depth & of the recursion, and the ft agent in that round that is allocated some value.
We first prove for k 1, f= = 1. In the plant phase, e 1) plants j pio (Ago) in Ag. Then, in the stealing phase, during the invocation of Algorithm 8, agent e is the first choose item from AN
30

---

which in particular contains j. Hence, the first item in A₁ is allocated into X1. We now assume the claim holds for i and é - and prove it for L. Assume without loss of generality that é is odd so that dg E No-
In step of the planting phase, the mechanism plants S (the proof for e is identical) first (according to value p item in Ago. Then, during the tentative allocation phase, agent Ed is the tdh to choose among the items in AN, minus the items that were allocated 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 e is still available. Moreover, let M denote the set of items after é é- rounds of the tentative Round-Robin in Algorithm 9. Further let A', denote the set of items after L rounds of the Allocate-Ber Best algorithm invoked in the stealing phase with the set No. i.e. A AN, \ \ NU (X,). 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 1 C M Since j p/ (M and pro rya, it holds that ro ( equals j. Therefore 6 will choose j to X as claimed.
Proving the claim for general k is almost identical. At the planting phase of the hthh round, the mechanism plants for every agent l E N² their :thh item of A; in Ay and vice versa. A similar argument 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-Rohi will select the items the mechanism planted for them. Hence, the hd item in Ago will be allocated to X
Finally, once the set agent belongs to becomes a singleton, by our halting condition, X; + X; U U so together with the previous argument, we get that for every &, X, A; as needed.
We continue to prove that the mechanism is robust. Since when m < â. μ for every agent i, and each agent trivially gets their MMS value, we assume from now on that 2 â and show the mechanism achieves (m - 1)-robustness for μ.- We first prove in Lemma H.3 that for each agent i, uy (x,)) 2 o [3n/2] and then prove in Lemma H.5 that the value of this item is not too small compared to 14;
[3n/2]
Lemma H.3. For every agent i, 0z (X.))) 2 o [3n/2]
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 1 items were previously allocated to other agents. Hence, she can always choose her n highest valued item. Therefore, we have v; (X,) 2 of 2 o. [3m/2] as claimed.
We continue to prove the claim for the set of agents with no large predicted values. Consider the hhh agent in N, it, and consider the following coloring process. Initially, color all items in M black. We will then color all items it 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 it '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] /2 1 have turned gray, implying that at some point during the recursion, ig could have chosen their
3m th highest valued item (according to ri.). 2
We let & denote the set of agents to which it belongs to at depth le of the recursion, starting with N = N. At each recursive call, N is partitioned into No. Nf.. We further let b E 1) denote the index of the set to which ig belongs to: ig E Ný. We will separately bound the number of items turned gray due to agents in N² and N by
In the first iteration, for k = 1, let A AN1 . No denote the tentative sets allocated to the agents of No and N1 after the planting phase (i.e., at the beginning of the stealing phase).
The number of items that turn gray due to agents in NJ. is GJ,, = [f/2] - 1, since in has access to all items Ahe, excluding the [e/2] items that were allocated to the agents in her set preceding her in the ordering. (The rest of the items in 1 N turn green.)
31

---

Turning to G' bi each agent in the opposite set to hers, N bi is allocated a single item (from A ANz. before continuing the next round of the recursion. Therefore, G' .6 = | da (and no item turns green).
The recursion then continues with N = NrJ and in reversed order (due to the order being reversed).
Therefore, at the beginning of the second iteration, ip is in location [N - [e/2] in N After the
[ 1 Hence, G = MM2 1 - due to 2 agents in her set preceding here in the ordering. Also, G = I. due to allocations to agents in the opposite set to hers.
partition phase, ig in set N and in location
2
1. Σ [ugn] | Observe that if N is even then Σk=1 Ngg. = N dt = N² /2, and if 2 is odd, then either Nith is odd and N is even or vice versa. the first case, G = [N /2] and we recurse with NYt, which is of size |N*/2] In the second case, Gh |N*K2 /2] and we recurse with NE. of size [N Hence, we have the following recursion formula. For even f. T(E) 2/2 + T(e/2). and for odd É, either (a) T()) = [2/2] + (Le/2]) or (b) (()) = [e/2] + T((e/2)). In Claim H.4 below, we prove that for such function, if it also holds
From now on, the order is preserved, so for every t: 2 3, G.
I 84 and G
| |- '/2
2
We continue by bounding Σ Ilea [log G Gh
that (11) and T(2) 1. then T()) S 1. Therefore, we get that Ek=1
[lg G G=yy S
We continue to bound
Σ [log Ghaa+ k=
Σ
10ng Iog m] k=
IN 1 1. The sum Eler [log x1
can be
2
2
bounded by EE [logX1
X1
+ L. where L is the number of indices &s for which the fraction X/2 is
km
2"
rounded up. Observe that for every X, L can be bounded above by [log X] as L exactly equals the number of I bits in the binary representation of X. Hence, the overall number of items that turn gray can be bounded as follows:
1n
G [log nl =
Σ k=1
(G + G.y.a)
llg n
[n/2] [E/2]
5 n 1 [E/2] 1
Σ
2h-1
k=
S n - 1+ [2/2] - 1+ + [n/2] - [e/2] + [logn] - [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 ie get their [3n/2] highest valued item 1/, /2/
We now prove the claim regarding the cost the recursion that was used the previous lemma.
Lemma H.4. Let T(n) be such that T(n) n/2 + T(n/2) if n is even and either (a) T(m) [n/2] + [[mm2]) or (b) (nn) = n/2 + T(nn/21) for odd n. Also assume T(1) = 0, T(2) = 1. Then ((n)
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
If is even then T(n) = n/2 + T < n/2 n/2
1, so the claim holds.
If n is odd, then in case (a), T(n) = [n/2] + ((mm22 < [n/2] | - = n 1, and in case
(b), T(n) [n/2] ([[n/2)) 1 [n/2] [n/2] -
Finally, we prove that the highest valued item allocated each agent 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. Then
v((i)) 2 p [3n/21 /3n/21/a /a
for m [3nn22 - 1.
32

---

Proof. Consider an MMS allocation of M for k = [3n/2], and let A, be the set such that (A,,)) y.. By the assumption on j", its value is higher then the highest valued item in A,, vz(5") 2
2 (A.). Therefore, (A,) _ |Aal ve(i"), implying vx(i") 2 vi (A.)/AAA = μ /|Aa]- Since [A,] S - k- 1 (as at least lo 1 items must be allocated to the k additional agents, it holds 3n/2 /(m [3n/2 /2] 1). that 0;(j*) 2 14
Proof of Theorem H.l. The theorem follows by Lemmas H.1, H.2, H.3, and H.5.
33

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract is high-level description of the results of the paper. The intro introduces a more detailed dive into the results, with "our results and techniques" section, where we try to give a detailed overview of our technical contributions. Moreover, Table is given to provide an easy-to-ume easy-to-understand understand summary of our theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
34

---

Answer: [No]
Justification:
This is mainly theoretical paper, and all the assumptions are clearly stated.
Guidelines:
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 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 the scope of the claims made, e.g., if the approach was only tested on few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 fairesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
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 cross- referenced.
All assumptions should be clearly stated or referenced 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 provide 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.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
35

---

Justification:
Using the code provided, it is possible to reproduce the main experimental
results.
Guidelines:
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 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make 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 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
new model (e.g.. large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The
code
can
be
accessed
via
the
link:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ aublic/guides Sttp///ooSSuuiiiionnnono oolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: httpe//pwlcggggdd//eeeeeeeeeeeee //nips. wwippscccppuuiii httpccccppppccceeeeecc wttpppppppppgeepeeelp wttgggude////// wewiiieee/oooouummieeeece Setooesuumiissioooll...... ssinooolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
36

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the core the paper to level 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, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi- dence intervals, statistical significance tests, 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
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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
37

---

Justification:
The experiments were done on a standard PC (Intel 19, 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 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 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp///eerppp.///ee cc aec/public/Etiiie hetpi///Ehhiiiuuieeeeeee cwcuidelueilliii ines?
Answer: [Yes]
Justification: The paper studies mechanism design problem with the objective outputting a fair allocation, which is highly desirable goal. We study generalization of the widely studied proportionality objective for discrete settings. We note that this objective is well motivated in settings like course-allocatio [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 faimess, 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 NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration 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 Ceamning-uggmentn 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 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 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 disinfornation. 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.
38

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No third-party packages used, and the data used for experiments is syn- thetic.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- e-packaaed, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
39

---

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 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
40


Reviews:
[{"review_id": "OXlRN2LR6Z", "reviewer": "Reviewer_EdC1", "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.\n\nMost 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). \n\nNext, 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.\n\nThe paper ends with synthetic experiments with two agents. \nIn 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.\n\nThere are some other results in the appendix as well exploring pointwise tradeoffs in the Pareto frontier.", "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?\n- Are there any matching lower bounds for the $\\sqrt{d}$ Kendall-tau result?\n- Have you thought about identical utilities? Can we achieve better guarantees assuming that agents have identical utilities?", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem of designing learning augment algorithms for approximate MMS allocations is new.\n- The results for the two agents are almost tight given the priorly known hardness results. The Kendall tau parameterized results show a nice trade-off.\n- The paper claims and proofs seem correct to me (though, I have not checked most of the proofs in the appendix.)\n- The plant-and-steal mechanism is simple.\n- The paper is overall easy to understand. (The writing and organization could be improved considerably, more on this below.)", "weaknesses": "- The predictions are either the entire valuation matrix or all the rankings, which contain a lot of information.\n- 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.\n- 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].\n- 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.\n- 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.\n- 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? \n\n\nMinor points:\n- 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.\n- 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$.\n- line 58, “With probability $2$”, should it be $½$?\n- line 50, “959 / 720 > 4/3$”, the reverse inequality is true\n- 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”. \n- You could save precious space by presenting algorithm 2 and mechanism 1 next to each other.\n- line 122, one can “ran” -> run\n- line 125, more “then” -> than\n- table 1, $\\hat{n}$ is undefined, please revise that part\n- line 158, an $(1+\\epsilon/2)$  -> change an to a. (I think a one is correct not an one.)\n- lines 183 and 184, related “works” -> work\n- line 291, thenB-RR-Plant-and-Steal -> add space between “then” and “B-RR-…”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* \"The predictions are either the entire valuation matrix or all the rankings, which contain a lot of information.\"\n\n-- The predictions used are:\n1) Rankings, which we think are much more plausible than the exact valuations – it’s easier to predict that item A is more valuable than item B than to accurately predict their exact valuations. For this type of predictions, we can even handle inaccurate predictions, when the inaccuracy is bounded.\n2)  Small space predictions. Here we use predictions of size O(log(m)/\\epsilon) which are significantly smaller than the O(mㆍlog(m)) space needed to represent rankings, not to mention the much larger spaced needed to represent valuation functions..\n3) For the n agent mechanisms, we use rankings as predictions, plus indicators indicating which are the “large” items, and not the entire valuation matrix, as stated in line 961, P. 28.\n\nIn conclusion, we never need to use the entire valuation matrix as prediction, since we aim to use realistic and robust predictions. We thank the reviewer for raising our awareness that this is not emphasized enough, and will add a discussion to the final version of the paper to make sure this point comes across.\n\n* \"Most of the paper is focused on two agents.\"\n\n-- Since strong impossibilities for truthful fair division already arise for two agents, this setting is well studied in the literature (see [1,2,3,4] for instance), as better understanding in this limited setting might be later generalized to multiagent settings. Indeed, we show that our mechanism can be generalized to $n$ players (while becoming much more involved). In this setting we get weaker, yet non-trivial, robustness guarantees.\n\n* \"Are there any matching lower bounds for the 𝑑 Kendall-tau result?\"\n\n-- We can show that the analysis of the O(\\sqrt{d}) approximation is tight up to a constant for the mechanism at hand. We don’t give a general parameterized lower bound for every truthful mechanism. Showing general lower bound is highly non trivial for fair division and has been the focus of several papers on fair division, including specifically for approximate MMS allocation [2]. We leave this for future work.\n\n* “The main body of the paper isn’t very well organized for a NeurIPS paper…”\n\n-- Thank you for your suggestions, we’ll implement these changes in the final version.\n\n* \"I couldn’t find the definition of “success rate” in the experiments. The y-label in Figure 2 is set to 𝜖 which should have been the subcaption of the subfigures.\"\n\n-- In L.350, we define our benchmark as “the percentage of instances where both players receive at least (1-𝜖) of their MMS values for different values of 𝜖,” which corresponds to the success rate. To improve clarity, we will explicitly mention this and add it to the subcaption.\n\n* \"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. .../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?\"\n\n-- We thank the reviewer for the relevant reference. We will look into the proposed model and other studied models to generate ranking predictions.\n\nRegarding valuations, we observed that some sampling methods, such as I.I.D. sampling and the proposed random unit-sum vectors with an arbitrary balanced partition, perform quite well. However, we believe these do not represent most real-life instances. Therefore, we chose to use a relatively simple yet non-trivial model to generate valuations with three types of items: low, medium, and high. In this model, there are more low-valued items than medium-valued items, and more medium-valued items than high-valued items. We believe this phenomenon matches many real-life scenarios and illustrates the importance of the different components of our mechanisms.\n\n\n* \"Have you thought about identical utilities? Can we achieve better guarantees assuming that agents have identical utilities?\"\n\n-- That’s a very interesting question! For identical utilities, round robin allocations, or any turn-based picking mechanisms^, are ex-post Incentive compatible^^ (EPIC). In this case, when an agent picks an item, they should always pick the best available item, which is what is implemented if agents report their true valuations/ranking and the mechanism uses a turn-based mechanism to determine the allocation. Thus, we are able to get ⅔ approximation to the MMS for two agents without any predictions for this truthfulness notion. For more than two players, it follows from [3] that we can get EPIC mechanisms with approximation ratios that depend on the number of players, but not the number of items, truthfully. If we get indicators for the large items as predictions, even without rankings, then now we can get constant factor approximation EPIC mechanisms.\n\n^ In turn-based picking mechanisms, each turn an agent picks a number of items from the set of remaining items, where the number of items is picked in advance.\n^^ In Ex-post Incentive compatible (EPIC), bidding truthfully is a Nash Equilibrium. \n\n[1] Benjamin Plaut and Tim Roughgarden. Almost Envy-Freeness with General Valuations, SODA 2018.\n[2] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness, EC 2017.\n[3] G. Amanatidis, G. Birmpas, and E. Markakis. On Truthful Mechanisms for Maximin Share Allocations, IJCAI 2016.\n[4] Biaoshuai Tao. On existence of truthful fair cake cutting mechanisms, EC 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VPPRWEOQKr", "reviewer": "Reviewer_dEcz", "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. \n\nThe 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. \n\nFor 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. \n\nThe 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. \n\nBeyond 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.", "questions": "n/a", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "While the Maximin-Share allocation problem has been well-studied in the literature, the authors are the first to study the role of predictions in this problem, to the best of my knowledge. The introduction of predictions is well-motivated, as it is natural for the algorithm designer to have some guess about the preferences of the agents. Moreover, the authors present a very comprehensive set of results for this setting - the depth and breadth of results in this submission is impressive.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "“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”\n\n-- We will make an effort to improve readability in the camera-ready version of the paper, including a clearer explanation of what agents report. Specifically, we will discuss how mechanisms can be implemented by requiring agents to report their full valuation vectors or, alternatively, only their favorite item from a bundle of items (for mechanisms involving two agents) or multiple favorite items (for mechanisms involving n agents). This point will be clarified in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZLxHnVTit3", "reviewer": "Reviewer_iNp4", "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. \n\nIn 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.\n\nFor 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$.\n\nFinally, they also have experiments showing how well their framework works in practice.", "questions": "Could you please address the raised concern in the last section? \n\nComments and Suggestions:\n\nL 22: For the case of two agents ... : the sentence does not read well. Maybe replace \"which\" with \"what\"\n\nL 40: ... over goods.For ... $\\rightarrow$ .. over goods. For ...\n\nL 58: with probability $2$ $\\rightarrow$ with probability $1/2$\n\nL 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.\n\nL 92: $\\lceil \\frac{m}{2} \\rceil$ $\\rightarrow$ $\\lfloor \\frac{m}{2} \\rfloor$\n\nL 122: ran $\\rightarrow$ run\n\nL 125: then $\\rightarrow$ than\n\nL 163: use \\boldmath in the paragraph title\n\nL 209, 213: $\\ell$th $\\rightarrow$ $\\ell$-th\n\nL 254: present present $\\rightarrow$ present\n\nL 264: espace before \"for\"\n\nL 271: show prove prove $\\rightarrow$ prove\n\nL 291: space after \"then\"\n\nL 320: allocated $\\rightarrow$ allocate", "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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow and I did enjoy reading it. Looking at fair division problems through the lens of learning augmented algorithms is definitely an interesting approach. At least for the case of two agents, the paper presents an almost optimal result that one can hope for.", "weaknesses": "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. \n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* \"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 𝛼-MMS allocations and currently the best known 𝛼 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 𝛼\n fraction of her MMS value. In particular for two agents, 𝛼=1. Now, what is the use of having truthful mechanism which guarantee only 2/𝑚 fraction of MMS values of the agents? In particular, the proposed mechanism incentivises 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\n 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.\"\n\nMechanism design has been a fruitful and central research area in Economics. The philosophy behind this approach is that if the mechanism is not truthful, the input for the mechanism might be strategic, and not representing the real parameters of the problem, thus the algorithms won’t be optimizing the objective it’s designed to optimize. Even if agents are to get better utility by coordinating, if each agent locally optimizes their utility, both agents might end up in a suboptimal solution, as demonstrated by the prisoner’s dilemma, while the optimal solution is not stable in a game-theoretic sense. The tension between truthfulness and the performance of the algorithm has been a central theme in the Algorithmic Game Theory literature, where the much desired truthfulness property often comes at the expense of the algorithm’s performance. Like the reviewer, we also were not satisfied with the $\\lfloor m/2\\rfloor$ lower bound from [2]. We also believe that many of the relevant settings for fair division, such as course allocation, data is abundant, and can be used to improve the performance of the truthful mechanism. We believe that this point was thoroughly demonstrated by our comprehensive set of results.\n\nWhile the privacy concern expressed by the reviewer is not the focus of our paper, we note that our mechanisms only require agents to minimally expose information, as they are only required to choose a single item from a predetermined set of items, which does not depend on their reports. Thus, they only need to reveal which is the most valuable item from a set of items, while not even exposing their value for the item. We will stress this point in the final version of the paper.\n\n[2] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness, EC 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qWZzmkTUyA", "reviewer": "Reviewer_CcvG", "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).\n\nThe 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.\n\nFor $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.", "questions": "Can you further explain why studying space-efficient predictions is important and interesting?", "limitations": "Some of the results are not sufficiently motivated or not promising.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The paper studies an important problem. Given that strong impossibility results exist when facing strategic agents, it's natural to bridge the gap between the strategic and non-strategic settings via predictions.\n\n(2) The paper is well-written and carefully structured.\n\n(3) The results are interesting, and the techniques are non-trivial. In particular, for two agents, the approximation ratios match the best achievable bounds up to a constant factor when the prediction is perfectly correct or completely incorrect.", "weaknesses": "(1) The motivation for studying space-efficient predictions is not convincing enough.\n\n(2) Most of the results only hold for two agents.\n\n(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$.\n\n(4) Minor:\n- Line 28: \"probability 2\"\n- Line 60: Should briefly explain what it means by \"ex-post\" guarantees.\n- Line 121: $\\mu_i$ is not defined before.\n- Line 212: \"over agents items\"\n- Line 228: \"according predictions\"\n- Line 254: \"present present\"\n- Line 271: \"show prove prove\"\n- Line 291: \"thenB\"\n- Line 320: \"to allocated\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\"Can you further explain why studying space-efficient predictions is important and interesting?\"\n\n-- Our motivation for succinct predictions comes from the works of [5,6,7], where they show that \nsuccinct predictions are crucial for learning the parameters from a few samples and for incorporating a PAC-learnable component in the learning-augmented framework under plausible distributional assumptions. We believe that combining our results on small space predictions with an adequate distributional assumption will yield such a result. We plan to formalize this in subsequent work.\n\n[5] Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation, ICALP 2023.\n\n[6] T Lavastida, B Moseley, R Ravi, and C Xu. Learnable and instance-robust predictions for online matching, flows and load balancing, ESA 2021.\n\n[7] Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited, ICML 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their thoughtful and thorough reviews. We will address all their comments and edit suggestions to improve the final manuscript. We address each reviewer’s comments/questions in the individual rebuttal sections below.

Meta-review: 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!
Decision: Accept (poster)