Online Fair Division Meets Reordering Buffers
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Online Fair Division Meets Reordering Buffers".
Jane: Here's the gist of the paper. We study the online fair division of indivisible mixed manna among agents with additive valuation functions to maintain fairness guarantees using reordering buffers.
Tom: The use of appropriately sized buffers can greatly help bypassing the strong negative results of traditional online algorithms.
Jane: Problem Setting and Fairness Notions The work concerns the fair allocation of indivisible items to a set of interested agents in an online scenario where items arrive sequentially.
Tom: The focus is on mixed manna, where an item can be valued either non-negatively or non-positively by an agent.
Title and authors: Tom: So, we're looking at this paper called "Online Fair Division Meets Reordering Buffers". It's about online fair division of items that can be either good or chore for different agents.
Jane: That sounds complicated. Basically, they're trying to figure out how to give people things fairly when they have to decide right away without knowing everything ahead of time.
Lu: Exactly. The paper focuses on mixed manna, where an item can be valued either positively or negatively by an agent, which makes it tricky compared to just standard goods.
Meng: So, what's the main problem they're trying to solve here? Is it just getting *some* fairness guarantee?
Tom: It's not just some guarantee; they are aiming for temporal fairness, meaning the allocation has to be envy-free or envy-free up to one item at every single time step.
Jane: That means as soon as an item arrives, the current assignment needs to be fair right then and there. That's a really strong requirement in an online setting.
Lalam: The paper tackles this by using something called reordering buffers, which are like storage areas where they can hold items temporarily to rearrange them later for a better allocation.
Tom: Right, so the core idea is that having these buffers helps them bypass some really strong negative results they found in traditional online algorithms.
Lu: They show that without these buffers, there are severe impossibility results for temporal envy-freeness up to one item even if you have a pretty large lookahead.
Jane: So what's the practical takeaway for someone listening who isn't deep into the math? It suggests that just reacting instantly isn't enough when you want strong fairness guarantees over time.
Tom: The paper then moves into showing that with a buffer of size n minus one times k, they can actually achieve this temporal envy-freeness up to one item in the Sustained Allocation of Singletons or SAS model for n agents with k-valued preferences.
Meng: Okay, so what does that buffer size mean in practice? Is it just a big number we need to set aside at the start?
Lu: It's linear in k and the number of agents, which is actually quite good because it shows that these buffers are sufficient for achieving this temporal guarantee.
Jane: That's promising because it gives us a concrete size. But they also explore whether they can do better, and they show that in another model, you need a dependence of the square root of k to get the same result.
Tom: So, it's not just one solution; depending on the specific setup—the model—you might need different buffer sizes for optimal performance.
Jane: It sounds like they are being very honest about where their results hold up and where they hit a wall, which is important information to have.
Title and authors: Lalam: They also look at limitations, showing that in the Deferred Allocation of Batches or DAB model, a buffer size of n minus one times k minus one might not work for every single time step.
Tom: That's a caveat we need to keep in mind; it means the guarantee isn't always perfect across all time steps depending on which specific model you are running.
Lu: But they also show that there is no deterministic online algorithm without any buffer that can *always* compute those temporal envy-freeness up to one item results for additive instances with a max ratio greater than zero.
Jane: That's a big statement because it sets the limit on what standard online methods can achieve without this extra storage mechanism.
Meng: From an engineering standpoint, if we're deploying this, we have to consider the cost of maintaining that buffer and the complexity of reordering things every time a new item comes in.
Tom: Right, so there's a trade-off between getting strong fairness guarantees and managing the computational overhead of these buffers.
Lu: But they show that they can achieve certain guarantees by using combinatorial arguments to construct sequences of envy-free matchings, which is how they prove the positive results.
Jane: So the mechanism isn't just some clever trick; it relies on building a sequence of allocations that are good for specific subsets of items.
Tom: And when you look at the conclusion, they show that with this buffer size n minus one times k, you get a temporal envy-free up to one item allocation in the SAS model and a temporal envy-free up to one item allocation in the DAB model.
Jane: That's the main win—a concrete result for both models under these conditions. But they also show that with a buffer size related to n log rho, you can get an allocation that is not just EF1 every step, but actually has a certain level of quality, Omega one temporal envy-free up to one item in both models.
Lu: And they extend this idea to general additive goods or chores-only instances by using a reduction technique involving a k auxiliary instance, though this introduces some instance-dependent loss related to rho minus one over k minus one.
Tom: So, the main implication is that for online fair division with mixed manna, buffers are not just helpful; they are necessary to achieve temporal fairness guarantees in many cases.
Jane: It's important context because it shows us that we can design algorithms that maintain fairness guarantees sequentially rather than just hoping for a fair final outcome.
Meng: For me, the part about the buffer size being linear in k is what matters most for deployment; if we can keep that size manageable, we have a path forward.
Lalam: I think the real significance of this paper, "Online Fair Division Meets Reordering Buffers", is showing how to move past those strong impossibility results by adding just a little bit of extra memory and some clever matching construction.
The paper's summary: Tom: So, we're looking at the summary of this paper called "Online Fair Division Meets Reordering Buffers". It basically says they took an online fair division problem with mixed items—things that can be good or bad for different agents—and they added a clever storage buffer to make sure things stay fair over time.
Jane: That's right. They show that in this online setting, where you get items one by one, having a buffer allows the system to reorder those items strategically so it can achieve temporal fairness, meaning the allocation is good every single time step.
Lu: The authors are pushing back against some really strong impossibility results they found before—those results showed that without any storage at all, even with a huge lookahead of items, you just couldn't guarantee that temporal fairness up to one item.
Meng: So what does this actually change for someone who is building a system? It means we can stop thinking that the only way to get good fairness online is by having perfect knowledge or waiting until the end.
Tom: Exactly. They find a way around those strong negative results by using buffers sized in relation to n, which is the number of agents, and k, which relates to how many different values an agent has. The size they suggest, that linear in n times k, is what helps them bypass those roadblocks.
Jane: That buffer size—linear in the number of agents and linearly related to the valuation values—is what gives them the guarantee. It shows that if you allocate enough temporary space, you can construct a sequence of envy-free matchings that works for most items.
Lu: The methodology they use involves building a sequence of top choice graphs and iteratively removing contested vertices to find these envy-free matchings; it’s a solid combinatorial approach to constructing the allocation.
Tom: And the positive result they show is pretty concrete: with this buffer, Algorithm one guarantees an allocation that is envy-free at least every n steps in the Sustained Allocation of Singletons model.
Jane: That's a win for sequential decision-making because it means you don't just hope for a good final outcome; you get fairness maintained repeatedly during the process.
Meng: But they also flag some limitations, and that’s important. They show that in another model, the Deferred Allocation of Batches, the buffer size might not be enough to guarantee envy-freeness at every single time step.
Tom: And they also point out that for general valuation functions—when items can be anything, not just simple goods or chores—they have to use a reduction technique based on a k auxiliary instance.
Jane: That reduction means they can apply their results to real-world data, but you lose some guarantee quality; the loss depends on the ratio rho and the value of k.
Lu: It’s interesting how they manage that trade-off, showing that for additive instances, no deterministic algorithm without a buffer can always compute those temporal guarantees if there's a certain ratio rho involved.
Meng: So it sounds like the main message is this: if you want to guarantee fairness every step in a complex online system, you need to invest in storage space and clever combinatorial matching techniques.
Tom: Right. It’s about moving past those impossibility results by just adding the right amount of memory and using structural arguments to keep things balanced.
The paper's improvements: Tom: We're looking at the improvements section now for this paper on fair division and those buffers. It seems like they aren't just stopping there; they are actually suggesting ways to make the system even stronger or more adaptable than what they first showed.
Jane: So, what do these suggested improvements actually mean for a practical application? Is it just tweaking the buffer size, or is it changing how the whole allocation process works?
Lu: It seems like they explore scenarios where you might need a different kind of buffer depending on the specific constraints of your problem. For instance, they mention that in some models, you might need a dependence of the square root of k to get those same results.
Meng: A square root dependence sounds like it might be computationally expensive at scale if k gets very large because you're dealing with non-linear scaling instead of just linear. What does that mean for deployment costs?
Tom: It means that for certain scenarios, the simpler linear buffer size we discussed earlier isn't enough, and you have to pay a higher price in terms of memory or processing time to maintain the same level of temporal guarantee.
Jane: And they also look at how you can generalize these findings. They take those results and apply them to more general settings, like when the items aren't just simple goods or chores but any additive valuation function.
Lu: That generalization involves a reduction technique using a k auxiliary instance, which means they are showing that the core idea of using buffers is robust across different types of valuation problems.
Tom: It’s interesting because they show that even in these more general cases, you still get a guarantee, but there’s an instance-dependent loss tied to that ratio rho and k. So it's not a perfect result everywhere.
Jane: That loss is the caveat; it tells us exactly how much of a fairness guarantee we are sacrificing when moving from the ideal scenario to the real world.
Meng: From an engineering standpoint, knowing that you can get these guarantees in general, even with some loss, is useful because it sets a realistic expectation for what your system can achieve without massive overhead.
Lu: And they highlight that large buffers are necessary for achieving really strong results, even when you're looking at just two agents. That suggests the need to keep those buffers substantial if you want high confidence in the outcome.
Tom: So, to recap, the improvements show that while linear buffers are a good starting point for SAS models, other models require different scaling—sometimes square root dependence—and generalizing it introduces a measurable loss based on instance parameters rho and k.
Jane: And they end by suggesting future work on relaxing these fairness requirements or maybe combining these buffers with lookahead mechanisms to see if we can get even better performance without the heavy cost.
Conclusion: Tom: So we're wrapping up this paper, "Online Fair Division Meets Reordering Buffers". It boils down to this: adding those reordering buffers lets us get strong fairness guarantees, specifically temporal envy-freeness up to one item every single time step.
Jane: That means for online systems dealing with mixed items—things that can be good or bad—we can design them so they are fair at every moment, not just at the very end of the process.
Lu: The authors prove that a buffer size linear in n times k is sufficient to get this temporal envy-freeness up to one item in models like Sustained Allocation of Singletons. It’s a solid result from a combinatorial standpoint.
Meng: From my side, I see the practical implication as something we can actually deploy if we can manage the storage cost associated with that linear size, which is good because it shows a concrete resource requirement.
Lalam: I'm confident in this conclusion; the paper demonstrates that these buffers are necessary tools to bypass those strong impossibility results for temporal fairness when you don't have perfect foresight.
Tom: Exactly. It changes how we design online allocation algorithms by providing a specific mechanism—the buffer—to guarantee sequential fairness instead of just aiming for a fair final state.
Jane: It shows that the limitations on traditional online algorithms are not unbreakable, provided we give the system enough temporary storage to reorder things correctly.
Lu: And they extend this idea to more general additive valuation functions, even though it brings an instance-dependent loss tied to the ratio rho and k. That’s important context for anyone trying to apply this generally.
Meng: So, we can get these results on real data, but we have to be aware that the performance depends on how complex the preference structure is and what kind of items you are dealing with.
Tom: Right. It’s a trade-off between strong guarantees and managing the computational overhead of keeping those buffers in check.
Jane: Overall, this paper confirms that for online fair division with mixed manna, we need those reordering buffers to achieve temporal fairness in many cases.
Lu: So the main implication is that if you want sequential fairness, you have to budget for linear memory relative to the number of agents and the value structure.
Meng: For us, it’s a reminder that we shouldn't just rely on standard online baselines without considering this storage mechanism when building systems that need high reliability.
Lalam: I’m sure of this; "Online Fair Division Meets Reordering Buffers" gives us a clear path forward for achieving sequential fairness in complex online environments.
Georgios Amanatidis, Giulio Giaconi, Evangelos Markakis, Nicos Protopapas
Athens University of Economics and Business · Archimedes/Athena RC · HSBC Holdings Plc. · Input Output Global
cs.GT, cs.DM, cs.DS
Submitted: 2026-07-01
Updated: 2026-11-13
Comments: A conference version of this work appears in the Proceedings of the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 78/100
The gist: We study the online fair division of indivisible mixed manna among agents with additive valuation functions to maintain fairness guarantees using reordering buffers.
Key concepts
- Mixed Manna
- This refers to items that agents value differently; some agents might value an item positively (like a good), while others might value it negatively (like a chore). The paper deals with allocating these mixed items fairly in an online setting where item arrival is sequential.
- Temporal Fairness
- This means that fairness must be maintained not just at the end of the process, but at every single time step as new items arrive. The goal is to ensure that after any allocation decision, the resulting state remains envy-free or envy-free up to one item.
- Reordering Buffer
- This is a temporary storage mechanism used in online algorithms. Instead of immediately allocating an item, the algorithm stores it in a buffer. This allows the system to look ahead and rearrange items optimally, storing contested items until a better allocation sequence can be constructed.
Terminology
Summary
We study the online fair division of indivisible mixed manna among agents with additive valuation functions to maintain fairness guarantees using reordering buffers. p. 0 Online Fair Division Meets Reordering Buffers
Georgios Amanatidis1,2, Giulio Giaconi3
, Evangelos Markakis1,2,4
,
and Nicos Protopapas1,2
1Athens University of Economics and Business, Athens, Greece
2Archimedes/Athena RC, Athens, Greece
3HSBC Holdings Plc. , United Kingdom
4
Input Output Global (IOG), Athens, Greece
July 2, 2026
Abstract
We study the online fair division of indivisible mixed manna among agents with additive valuation
functions. We note that the model of buffers interpolates naturally between the fully online case (no buffer) and the
fully offline case (a buffer large enough to hold all items). Our main takeaway message is that the use
of appropriately sized buffers can greatly help bypassing the strong negative results of traditional online
algorithms.Where the paper says it
Where the paper says it
Problem Setting and Fairness Notions
The work concerns the fair allocation of indivisible items to a set of interested agents in an online scenario where items arrive sequentially. The focus is on mixed manna, where an item can be valued either non-negatively or non-positively by an agent. p. 1 Therefore, an algorithm under this model needs to maintain a partial allocation that is
being updated as time progresses, until there are no further arrivals. Furthermore, regarding the type of
goods, we focus on the most general setting that is commonly referred to as mixed manna, where an item
can be valued either non-negatively (perceived as a good) or non-positively (perceived as a chore) by an
agent. Furthermore, regarding the type of
goods, we focus on the most general setting that is commonly referred to as mixed manna, where an item
can be valued either non-negatively (perceived as a good) or non-positively (perceived as a chore) by an
agent. Finally, our target fairness notions are envy-freeness (EF) and one of its most prominent relaxations,
envy-freeness up to one item (EF1). Given these considerations, ideally we would like to have algorithms
that maintain temporal fairness, i. , the allocations they produce are EF or EF1 in every time step during
their execution.Where the paper says it
Where the paper says it
Where the paper says it
Impossibility Results and Buffers
Strong impossibility results show that one cannot hope for any reasonable approximation guarantees on EF1 without additional assumptions. Specifically, there are strong impossibility results showing that without buffers, there are severe impossibility results for temporal-EF1 allocations even with lookahead almost as large as the total number of items. p. 1 For the fully online case, this is already known even for 3-valued instances. We prove that even with a lookahead almost as large as the total number of items, we cannot have
algorithms that produce temporal-EF1 allocations. Let c ≥ 2 and ε > 0. No deterministic online algorithm with a lookahead ℓ ≤ k − 3 can
always compute (1/c + ε)-temporal-EF1 allocations for k-value instances, even when n = 2 and all items are
only goods or only chores.Where the paper says it
Where the paper says it
Positive Results with Buffers
The main positive results show that a buffer of size (n − 1)k suffices to obtain a temporal-EF1 allocation in the SAS model for n agents with k-valued preferences. Algorithm 1 guarantees that the allocation is EF at least every n steps. p. 1 In both models, we show that for n agents with k-valued preferences, a buffer of size (n − 1)k
suffices to obtain a temporal-EF1 allocation. Our Algorithm 1 also guarantees that the allocation is EF at
least every n steps. Our Algorithm 1 also guarantees that the allocation is EF at
least every n steps. Our approach relies on novel combinatorial arguments, leveraging Hall’s Theorem
for constructing a sequence of envy-free matchings that allocates most items.Where the paper says it
Where the paper says it
Limitations and Generalization
The analysis shows that the buffer size can be improved in certain models, with a dependence of √k being necessary in another model. Theorem 4.9 demonstrates that for the DAB model and temporal-EF/EF1, a buffer of size (n − 1)k − 1 may fail to produce an EF allocation in at least half of the time steps. p. 5 Suppose we have a deterministic allocation algorithm A with a lookahead of size ℓ ≤ k − 3 that always
computes a (1/c + ε)-temporal-EF1 allocation when given a k-value instance with only goods. We are
going to construct a sequence of items that forces A to fail to produce such an allocation within at most
ℓ + 4 time steps. Therefore, an algorithm under this model needs to maintain a partial allocation that is
being updated as time progresses, until there are no further arrivals. Furthermore, regarding the type of
goods, we focus on the most general setting that is commonly referred to as mixed manna, where an item
can be valued either non-negatively (perceived as a good) or non-positively (perceived as a chore) by an
agent. , when ℓ = m − 1), it is known that a temporal-EF1 allocation can always be computed for two agents,
even when they have general additive valuation functions [He et al. No deterministic online algorithm with a lookahead ℓ ≤ m − 4 can always compute a
temporal-EF1 allocation for 3-value instances, even when n = 2 and all items are only goods or only chores.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion and Corollaries
Corollary 5.2 states that Algorithm 1 with a buffer of size (n − 1)k on the k-auxiliary instance computes a ρ−1k−1-temporal-EF1 allocation in the SAS model, and a ρ−1k−1-temporal-EF/EF1 allocation in the DAB model, with respect to the original valuation functions. p. 8 We resolve
this question positively via our algorithm Store-and-Match (Algorithm 1) for both modes of allocation we
considered here, SAS, where at most one item can be allocated per time step, and DAB, where any number
of available items can be allocated at once. For any personalized k-value instance, Store-and-Match (Algorithm 1) with a buffer of size
(n − 1)k efficiently computes a temporal-EF1 allocation in the SAS model. We resolve
this question positively via our algorithm Store-and-Match (Algorithm 1) for both modes of allocation we
considered here, SAS, where at most one item can be allocated per time step, and DAB, where any number
of available items can be allocated at once. For any personalized k-value instance, Store-and-Match (Algorithm 1) with a buffer of size
(n − 1)k efficiently computes a temporal-EF1 allocation in the SAS model. This setting interpolates naturally between the fully online case (no buffer) and the fully
offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably
sized buffers can achieve strong guarantees for personalized k-value instances, i. Our approach relies on novel combinatorial arguments, leveraging Hall’s Theorem
for constructing a sequence of envy-free matchings that allocates most items. In Section 5, we extend
our results to general additive valuations for goods or for chores, at the expense of a multiplicative loss,
dependent on the ratio between the maximum and minimum value of the items. For any personalized k-value instance, Store-and-Match (Algorithm 1) with a buffer of size
(n − 1)k efficiently computes a temporal-EF1 allocation in the SAS model. Moreover, this allocation is EF every
n steps during the first m − (n − 1)k time steps in which an item is allocated. 4 A Matching-Inspired Framework
In light of the negative results of the previous section, it is natural to explore stronger online algorithm
models that not only know part of the future but can manipulate it too. Augmenting our algorithms with
buffers that can store and reorder some of the items is clearly an approach in this direction. At the same time, we also wish to maintain some fairness guarantee, and in this work
we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item
(EF1). Given the strong negative and the scarce positive results for this problem without additional
assumptions, we augment our algorithms with buffers that can store and rearrange a limited number
of items. At the same time, we also wish to maintain some fairness guarantee, and in this work
we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item
(EF1). Given the strong negative and the scarce positive results for this problem without additional
assumptions, we augment our algorithms with buffers that can store and rearrange a limited number
of items.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The authors augment their algorithms with buffers that can store and rearrange items, interpolating naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). The main takeaway message is that the use of appropriately sized buffers can greatly help bypassing the strong negative results of traditional online algorithms. p. 1 We note that the model of buffers interpolates naturally between the fully online case (no buffer) and the
fully offline case (a buffer large enough to hold all items). Our main takeaway message is that the use
of appropriately sized buffers can greatly help bypassing the strong negative results of traditional online
algorithms.Where the paper says it
How the training signal is built
The core mechanism involves constructing a sequence of top choice graphs G(Rl) where Rl form a decreasing sequence, and iteratively removing contested vertices to find a left-perfect matching. For two agents, Lemma 4. p. 0 Finally, we extend our results to general additive
valuation functions, with a dependence on the largest per-agent ratio between two values of the same
sign, and we also identify limitations of our approach via impossibility results on the use of buffers with
smaller size. 1 Introduction
Our work concerns the fair allocation of indivisible items to a set of interested agents. Note that in G(S) every i ∈ N has degree at least one, since Ti(S) ̸= ∅. As a first step, the following simple
lemma says that a left-perfect matching in the above graph is enough to expand an EF partial allocation,
maintaining envy-freeness. Up to Lemma 4. 7, we state and prove
everything for the general case, as there is no particular difference between n = 2 and n ≥ 3. , An) be an EF partial allocation over a set N of agents, S be a set of items,
and let G(S) be the induced top choice graph. If there exists a left-perfect matching µ : N → S in G(S), then
the (partial) allocation A′ = (A′
1
, .Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The gains come from leveraging combinatorial arguments and constructing a sequence of envy-free matchings that allocates most items. The positive results rely on Lemma 4. p. 0 At the same time, we also wish to maintain some fairness guarantee, and in this work
we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item
(EF1). Given the strong negative and the scarce positive results for this problem without additional
assumptions, we augment our algorithms with buffers that can store and rearrange a limited number
of items. We resolve
this question positively via our algorithm Store-and-Match (Algorithm 1) for both modes of allocation we
considered here, SAS, where at most one item can be allocated per time step, and DAB, where any number
of available items can be allocated at once. For any personalized k-value instance, Store-and-Match (Algorithm 1) with a buffer of size
(n − 1)k efficiently computes a temporal-EF1 allocation in the SAS model. For any personalized k-value instance, Store-and-Match (Algorithm 1) with a buffer of size
(n − 1)k efficiently computes a temporal-EF/EF1 allocation in the DAB model. 1 The Illustrative Case of Two Agents
To illustrate the high-level idea behind our main technical result, which leads to Theorems 4. Our Algorithm 1 also guarantees that the allocation is EF at
least every n steps. Our approach relies on novel combinatorial arguments, leveraging Hall’s Theorem
for constructing a sequence of envy-free matchings that allocates most items.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper systematically studies the problem of fair division of indivisible mixed manna among agents with additive valuations in an online setting where algorithms are equipped with buffers that can store and rearrange items. The focus is on k-value instances and showing that buffers of size linear in k and in the number of agents suffice to obtain strong guarantees via novel combinatorial arguments. p. 0 In particular, we construct allocations that are
EF1 at every time step and EF at most time steps, using a buffer of size linear in k and in the number
of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence
of envy-free matchings that allocates most items. Our approach relies on novel combinatorial arguments, leveraging Hall’s Theorem
for constructing a sequence of envy-free matchings that allocates most items. In Section 5, we extend
our results to general additive valuations for goods or for chores, at the expense of a multiplicative loss,
dependent on the ratio between the maximum and minimum value of the items. 3 Impossibility Results Leading to the Use of Buffers
In this section, we provide justification on why one needs to go beyond the standard model of online
algorithms in order to have fairness guarantees in online fair division. We have already mentioned in the
introduction that there are strong impossibility results not only for general additive valuation functions
[He et al. Online Fair Division Meets Reordering Buffers
Georgios Amanatidis1,2, Giulio Giaconi3
, Evangelos Markakis1,2,4
,
and Nicos Protopapas1,2
1Athens University of Economics and Business, Athens, Greece
2Archimedes/Athena RC, Athens, Greece
3HSBC Holdings Plc. , United Kingdom
4
Input Output Global (IOG), Athens, Greece
July 2, 2026
Abstract
We study the online fair division of indivisible mixed manna among agents with additive valuation
functions. Online Fair Division Meets Reordering Buffers
Georgios Amanatidis1,2, Giulio Giaconi3
, Evangelos Markakis1,2,4
,
and Nicos Protopapas1,2
1Athens University of Economics and Business, Athens, Greece
2Archimedes/Athena RC, Athens, Greece
3HSBC Holdings Plc. , United Kingdom
4
Input Output Global (IOG), Athens, Greece
July 2, 2026
Abstract
We study the online fair division of indivisible mixed manna among agents with additive valuation
functions.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The proof of Theorem 4. p. 4 No deterministic online algorithm
can always compute (1/
√
c + ε)-temporal-EF1 allocations for 3-value instances with values 1,
√
c, c, or
−c, −
√
c, −1, even when n = 2. For the proof of Theorem 3. No deterministic online algorithm
can always compute (1/
√
c + ε)-temporal-EF1 allocations for 3-value instances with values 1,
√
c, c, or
−c, −
√
c, −1, even when n = 2. For the proof of Theorem 3. Up to Lemma 4. 7, we state and prove
everything for the general case, as there is no particular difference between n = 2 and n ≥ 3. For any subset S ⊆ L, define the neighborhood of S, Γ(S) = { r ∈ R | ∃ ℓ ∈ S such that (ℓ, r) ∈ E }. Then there exists a left-perfect matching if
and only if |Γ(S)| ≥ |S| for every S ⊆ L. We make no distributional assumptions about the arrival of the items, and follow a worst-case analysis. In
some of our results, in Section 3, the algorithm can view some of the arriving items ahead of time. We
consider two allocation models, based on whether the algorithm can allocate items in batches or one by
one. In both models, we show that for n agents with k-valued preferences, a buffer of size (n − 1)k
suffices to obtain a temporal-EF1 allocation. We
consider two allocation models, based on whether the algorithm can allocate items in batches or one by
one. In both models, we show that for n agents with k-valued preferences, a buffer of size (n − 1)k
suffices to obtain a temporal-EF1 allocation. We
consider two allocation models, based on whether the algorithm can allocate items in batches or one by
one. In both models, we show that for n agents with k-valued preferences, a buffer of size (n − 1)k
suffices to obtain a temporal-EF1 allocation. We say that µ is left-perfect if every vertex v ∈ L is incident to exactly one edge in µ. We will use the graph-theoretic version of Hall’s Theorem [Hall, 1935]. We say that µ is left-perfect if every vertex v ∈ L is incident to exactly one edge in µ. We will use the graph-theoretic version of Hall’s Theorem [Hall, 1935]. In any case, by the time gm is
given, the allocation fails to be EF1. When m is odd, the only difference is that the values of gm−2 and gm−1 are swapped, so that v1(gm−1) =
v2(gm−2) = c
2
and v2(gm−1) = v1(gm−2) = c; the analysis is essentially identical. In any case, by the time gm is
given, the allocation fails to be EF1. When m is odd, the only difference is that the values of gm−2 and gm−1 are swapped, so that v1(gm−1) =
v2(gm−2) = c
2
and v2(gm−1) = v1(gm−2) = c; the analysis is essentially identical. We make no distributional assumptions about the arrival of the items, and follow a worst-case analysis. In
some of our results, in Section 3, the algorithm can view some of the arriving items ahead of time. We make no distributional assumptions about the arrival of the items, and follow a worst-case analysis. In
some of our results, in Section 3, the algorithm can view some of the arriving items ahead of time.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop online fair division algorithms that maintain temporal envy-freeness up to one item (EF1) in every time step using a reordering buffer of size linear in k and the number of agents. This allows systems to produce allocations that are EF1 at every step, which is a strong guarantee for sequential decision-making.
-
Implement Store-and-Match algorithms that can compute temporal EF1 allocations in both Sustained Allocation of Singletons (SAS) and Deferred Allocation of Batches (DAB) models by utilizing a buffer size of (n - 1)k. This capability enables the system to handle item arrivals sequentially while maintaining high fairness guarantees.
-
Design systems capable of achieving strong fairness guarantees for personalized k-value instances by leveraging combinatorial arguments based on constructing a sequence of envy-free matchings, as described in Section 4.2 and Algorithm 1's proof structure. This will allow the AI to produce allocations that are EF every n steps during the initial allocation phase.
-
Adapt algorithms to handle general additive valuation functions for goods or chores by using a reduction technique based on constructing a k-auxiliary instance, translating EF or EF1 guarantees with an instance-dependent loss of rho - 1/(k - 1). This allows the AI to operate effectively on real-world preference data rather than restricted k-value approximations.
-
Create robust online fair division frameworks that can provide impossibility results for standard online algorithms without buffers, specifically showing that no deterministic algorithm with limited lookahead can compute temporal EF1 allocations in certain scenarios (Theorem 3.2). This helps in benchmarking the performance limits of existing allocation strategies.
Abstract
We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized k-value instances, i.e., instances in which each agent assigns at most k distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in k and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.
Sources
- Temporal Fair Division of Indivisible Goods with Scheduling
- Approximate Proportionality in Online Fair Division
- Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?
- Online EFX Allocations with Predictions
- Online Fair Division with Additional Information
- Online MMS Allocation for Chores
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments