Online Fair Division Meets Reordering Buffers

arXiv:2607.01159 · cs.GT, cs.DM, cs.DS · Submitted 2026-07-01 · Read on arXiv

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

Where the paper says it

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.

The use of appropriately sized buffers can greatly help bypassing the strong negative results of traditional online algorithms. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

The target fairness notions are envy-freeness (EF) and its relaxation, envy-freeness up to one item (EF1). p. 1
Where the paper says it

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

Temporal fairness is desired, meaning allocations are EF or EF1 in every time step during execution. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

Theorem 3.2 shows that no deterministic online algorithm with a lookahead size l ≤ 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. p. 5
Where the paper says it

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.

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

Where the paper says it

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.

The approach relies on novel combinatorial arguments leveraging Hall’s Theorem for constructing a sequence of envy-free matchings. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

Furthermore, Theorem 5. p. 1
Where the paper says it

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.

4 shows that there is no deterministic online algorithm without a buffer that can always compute (1/√ρ + ε)-temporal-EF1 allocations for additive instances with a max ratio ρ > 0. p. 7
Where the paper says it

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

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

Where the paper says it

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.

Corollary 5.3 shows that Algorithm 1 with a buffer of size Θ(n log ρ) on the corresponding Θ(log ρ)-auxiliary instance computes a omega(1)-temporal-EF1 allocation in the SAS model, and a omega(1)-temporal-EF/EF1 allocation in the DAB model, with respect to the original valuation functions. p. 8
Where the paper says it

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.

Corollary 5.6 suggests that large buffers are necessary to obtain strong guarantees, even for just two agents. p. 0
Where the paper says it

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.

The work extends results to general additive goods-only or chores-only instances via a reduction to a k-value instance with an additional multiplicative factor of ρ−1/(k−1). p. 1
Where the paper says it

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.

The paper concludes by showing that the allocation computed by Algorithm 1 is temporal-EF/EF1 and EF every n steps for the first m − (n − 1)k time steps when using a buffer of size (n − 1)k. p. 8
Where the paper says it

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.

The final part discusses the necessity of large buffers in Corollary 5. p. 8
Where the paper says it

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.

5. The discussion suggests future work on relaxing fairness requirements or combining buffers with lookahead. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

7 shows that among k + 1 available items, there is at least one pair to expand the allocation and keep it EF. p. 9
Where the paper says it

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.

For general n, Lemma 4. p. 9
Where the paper says it

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.

8 provides a matching for a set of (n − 1)k + 1 items to ensure an EF-partial allocation. p. 9
Where the paper says it

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

Where the paper says it

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.

8, which guarantees an EF-partial allocation for any set of (n − 1)k + 1 items in a personalized k-value instance. p. 8
Where the paper says it

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 leads to the final result that Algorithm 1 computes a temporal-EF/EF1 allocation. p. 9
Where the paper says it

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.

The analysis of the Double Round-Robin algorithm proves that every prefix of the allocation sequence is EF1. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

The results extend to general additive goods-only or chores-only instances, at the cost of some instance-dependent loss. p. 1
Where the paper says it

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.

The paper concludes by showing that large buffers are necessary in order to obtain strong guarantees, even for just two agents. p. 4
Where the paper says it

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.

The discussion suggests future work on relaxing fairness requirements or combining buffers with lookahead. The paper has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2. p. 0
Where the paper says it

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.

0 funded by the European Union under the NextGenerationEU Program. The disclaimer notes that this paper was prepared for information purposes and is not a product of HSBC Bank Plc. or its affiliates. The references list includes works on online fair division, reordering buffers, and related approximation algorithms. p. 0
Where the paper says it

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.

The proof of Theorem 4. p. 4

Where the paper says it

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.

p. 4
Where the paper says it

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.

2 for general n is nearly identical to the case for two agents, relying on Lemma 4. p. 9
Where the paper says it

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.

8 to ensure a left-perfect matching exists. p. 9
Where the paper says it

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.

The analysis of Algorithm 1 shows that during the allocation phase, EF is maintained in every step until items stop arriving. p. 4
Where the paper says it

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.

The finalization phase uses the Double Round-Robin algorithm to achieve an EF1 allocation for the remaining items. p. 1
Where the paper says it

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.

p. 1
Where the paper says it

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.

p. 1
Where the paper says it

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.

The proof of Theorem 4.2 for general n is a simpler version of the proof of Theorem 4. p. 9
Where the paper says it

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

p. 9
Where the paper says it

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

1 and is nearly identical to the proof we gave for the case of two agents. p. 8
Where the paper says it

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.

p. 8
Where the paper says it

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.

The analysis shows that during the allocation phase, EF is maintained in every step until items stop arriving. p. 4
Where the paper says it

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.

p. 4
Where the paper says it

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.

The finalization phase uses the Double Round-Robin algorithm to achieve an EF1 allocation for the remaining items. The proof of Theorem 4.2 for general n is a simpler version of the proof of Theorem 4.1 and is nearly identical to the proof we gave for the case of two agents. The analysis shows that during the allocation phase, EF is maintained in every step until items stop arriving. The finalization phase uses the Double Round-Robin algorithm to achieve an EF1 allocation for the remaining items.

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

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

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

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

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

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

Related papers