Online Fair Division for Personalized 2 2 -Value Instances

Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, Victor Turmel · 2025

Read Online Fair Division for Personalized 2 2 -Value Instances by Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, Victor Turmel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22174.txt.

Introduction

Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, and Victor Turmel studied fair splits when goods land one by one. Their paper, from twenty twenty-five, deals with online fair division. A fixed set of agents waits as each good shows up. Its worth to each agent is told on the spot, and it must be given at once, for good. With no caps on worth, strong blocks say fair shares are near hopeless.

The team turns to a tight case: each agent rates each good at one of two set values, their own pair. In that world they prove worst case bounds for known fairness marks. Readers in fair systems get a map of what can be sworn to when taste is coarse.

Catalog record

CREATORGeorgios Amanatidis, Alexandros Lolos, Evangelos Markakis, Victor Turmel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22174

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Fair Division for Personalized 2 2 -Value Instances Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, Victor Turmel Abstract We study an online fair division setting, where goods arrive one at a time and there is a fixed set of n n agents, each of whom has an additive valuation function over the goods. Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents. It is known that without any assumptions about the values being severely restricted or coming from a distribution, very strong impossibility results hold in this setting ( He et al., 2019 ; Zhou et al., 2023 ) . To bypass the latter, we turn our attention to instances where the valuation functions are restricted. In particular, we study personalized 2 2 -value instances , where there are only two possible values each agent may have for each good, possibly different across agents, and we show how to obtain worst case guarantees with respect to well-known fairness notions, such as maximin share fairness and envy-freeness up to one (or two) good(s) . We suggest a deterministic algorithm that maintains a 1 / ( 2 ​ n − 1 ) 1/(2n-1) - MMS allocation at every time step and show that this is the best possible any deterministic algorithm can achieve if one cares about every single time step; nevertheless, eventually the allocation constructed by our algorithm becomes a 1 / 4 1/4 - MMS allocation. To achieve this, the algorithm implicitly maintains a fragile system of priority levels for all agents. Further, we show that, by allowing some limited access to future information, it is possible to have stronger results with less involved approaches. In particular, by knowing the values of goods for n − 1 n-1 time steps into the future, we design a matching-based algorithm that achieves an EF1 allocation every n n time steps, while always maintaining an EF2 allocation. Finally, we show that our results allow us to get the first nontrivial guarantees for additive instances in which the ratio of the maximum over the minimum value an agent has for a good is bounded. 1 Introduction The problem of fairly allocating a set of resources to a set of agents without monetary exchanges was mathematically formalized only in the 1940’s by Steinhaus (1949) —along with his students Banach and Knaster. Nevertheless, fair division is such a fundamental concept that the celebrated Cut & Choose protocol already appears in ancient literature. For this reason, since the formal introduction of the problem, numerous variants, each under different assumptions and constraints, have been studied in mathematics, economics, political science and, more recently, in computer science. Specifically, as far as the latter is concerned, the algorithmic nature of most questions one may ask about fair division problems has lead to a flourishing literature on the topic, often on variants that deal with discrete, indivisible resources. In the most standard variants of the problem a set of resources and a set of agents, each equipped with a valuation function, are given as an input and one would like to produce a, complete or partial, partition of the resources to the agents, so that some predetermined fairness criterion is satisfied. Here we study a version of the problem where the set of n agents is indeed given, but the indivisible goods arrive in an online fashion. That is, at each time step a new good appears, its value for the agents is revealed, and the good must be irrevocably assigned to a single agent before the next good arrives. Online fair division problems of similar nature appear in many real-world scenarios, like, e.g., the operation of food banks, donation distribution in disaster relief, limited resource allocation within an organization like a hospital or a university, or memory and CPU management in cloud computing. Despite their wide applicability, however, online fair division settings have not been studied nearly as much as their offline counterparts. And admittedly, there is a good reason for the relative scarcity of such works. Namely, it is relatively easy to show strong impossibility worst-case results, even if one aims for rather modest fairness guarantees. For example, when the agents have additive valuation functions and the items are goods (i.e., they do not have a negative value for any agent) that arrive adversarially—as is the case here—there is no deterministic algorithm that achieves any positive approximation factor with respect to maximin share fairness ( MMS ) ( Zhou et al., 2023 ) or to envy-freeness up to one good ( EF1 ) ( He et al., 2019 ) . Even if one allows some item reallocations in order to fix that, the number of reallocations cannot be bounded by any function of n ( He et al., 2019 ) . Of course, there are ways to bypass these results, like assuming that the item values are drawn from distributions ( Benade et al., 2018 ; Zeng and Psomas, 2020 ) , restricting the valuation functions ( Aleksandrov et al., 2015 ) or the number of distinct agent types ( Kulkarni et al., 2025 ) , allowing items to be reallocated ( He et al., 2019 ) , relaxing the requirement for fairness guarantees at the intermediate time steps ( Cookson et al., 2025 ) , augmenting the input with predictions ( Banerjee et al., 2022 ) or even with full knowledge of the whole instance ( Elkind et al., 2024 ; Cookson et al., 2025 ) . Here the main approach we take is to focus on designing deterministic algorithms for instances with restricted valuation functions, although we also explore how information about the future allows for stronger results with simpler algorithms. In particular, we mostly consider instances where each agent i has two values for the goods: a low value \beta_{i} and a high value \alpha_{i} . These instances, which we call personalized 2 -value instances , generalize the binary case and the setting where there are only two types of goods; until now, these were the only cases where positive worst-case results were known (by Aleksandrov et al. (2015) and Elkind et al. (2024) , respectively). Consequently, personalized 2 -value instances capture the natural dichotomy between highly desirable and less desirable goods in a more nuanced way which also varies across agents. Moreover, there is a natural way of approximating any additive instance via a 2 -value instance by just setting a threshold for each agent i and rounding everything up (to the “high value” \alpha_{i} ) or down (to the “low value” \beta_{i} ) accordingly. Although this approximation is not always meaningful, it does give nontrivial guarantees for agents whose values are bounded by lower and upper bounds that do not differ by too much, as we argue in Section 6 . It should be noted that this type of restriction has drawn significant attention in the fair division literature recently. The study of k -value instances (often called k -valued or, in the case where k=2 , bi-valued ), where there are at most k possible common values that can represent the value an agent has for

Read the complete text