Plant-and-Steal: Truthful Fair Allocations via Predictions

"Can you further explain why studying space-efficient predictions is important and interesting?"

-- Our motivation for succinct predictions comes from the works of [5,6,7], where they show that succinct 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.

[5] Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation, ICALP 2023.

[6] T Lavastida, B Moseley, R Ravi, and C Xu. Learnable and instance-robust predictions for online matching, flows and load balancing, ESA 2021.

[7] Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited, ICML 2021.

• "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 𝛼 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 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."

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

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

[2] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness, EC 2017.

“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”

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

• "The predictions are either the entire valuation matrix or all the rankings, which contain a lot of information."

-- The predictions used are:

1. 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.
2. 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..
3. 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.

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

• "Most of the paper is focused on two agents."

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

• "Are there any matching lower bounds for the 𝑑 Kendall-tau result?"

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

• “The main body of the paper isn’t very well organized for a NeurIPS paper…”

-- Thank you for your suggestions, we’ll implement these changes in the final version.

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

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

• "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?"

-- We thank the reviewer for the relevant reference. We will look into the proposed model and other studied models to generate ranking predictions.

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

• "Have you thought about identical utilities? Can we achieve better guarantees assuming that agents have identical utilities?"

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

^ 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. ^^ In Ex-post Incentive compatible (EPIC), bidding truthfully is a Nash Equilibrium.

[1] Benjamin Plaut and Tim Roughgarden. Almost Envy-Freeness with General Valuations, SODA 2018. [2] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness, EC 2017. [3] G. Amanatidis, G. Birmpas, and E. Markakis. On Truthful Mechanisms for Maximin Share Allocations, IJCAI 2016. [4] Biaoshuai Tao. On existence of truthful fair cake cutting mechanisms, EC 2024.