CS Paper Radar

Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings

Kui-Wang Choi, Minming Li, Nicholas Teh

cs.GT ·submitted 2026-08-20 13:41 UTC · v1
highly cited

Abstract

We study temporal fair division of indivisible mixed manna. Items arrive over time and must be allocated irrevocably; an item may be a good for some agents, a chore for others, and neutral for the rest. We require the cumulative allocation after every round to be envy-free up to one item (TEF1). Although deciding whether a TEF1 allocation exists is NP-hard even for goods, we identify several tractable settings. First, with at most $k$ item types, an online cyclic rule guarantees EF$\lceil k/2\rceil$ after every item arrival. Thus, every instance with at most two types admits an online TEF1 allocation; moreover, when the numbers of agents and types are fixed, TEF1 existence can be decided in polynomial time. Second, under agreement after agent-specific scaling, provided that the scaling factors are known before arrivals begin, an online rule produces an allocation that is EF1 and Pareto optimal after every item arrival. Third, for a two-part arrival sequence with common rankings, we give a rule that is EF1 after every item arrival. Fourth, when the number of agents is fixed and values are bounded integers, we give an exact pseudo-polynomial algorithm for deciding TEF1 existence. Finally, for goods, every TEF1 allocation gives each agent at least $1/n$ of her maximin share after every round; this factor is tight even for identical valuations and two rounds. Deciding whether an exact temporal maximin-share allocation exists is NP-hard for both goods and chores, even with identical valuations, two agents, and two rounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Temporal Fair Division: Simultaneous Guarantees for Goods and Chores

cs.GT ·2026-11-18 ·Tianqi Chen
similarity 0.75
Abstract

We study temporal fair division of indivisible items in both the goods and chores settings, with $n \ge 2$ agents and nonnegative additive values or costs. Items arrive one at a time and must be assigned immediately and irrevocably. The arrival order and all agents' values or costs are known in advance, and the cumulative allocation must satisfy the fairness requirements after each arrival. For goods, we give a polynomial-time algorithm that simultaneously achieves exact temporal proportionality up to one item (TPROP1), a $1/n$ approximation to temporal maximin share (TMMS), and a $1/(n-1)$ approximation to temporal envy-freeness up to one item (TEF1). The TMMS factor is optimal. For chores, we give a polynomial-time algorithm that simultaneously achieves exact TPROP1 and a $2-1/n$ approximation to TMMS. Classical scheduling lower bounds based on fixed sequences carry over to chores TMMS, establishing the optimality of this factor for $n=2,3$. For every $n \ge 2$, we further show that $2-1/n$ is the optimal TMMS factor subject to exact TPROP1. For every fixed $n \ge 3$ and every finite $β\ge 1$, we construct an instance of chores admitting no $β$-TEF1 allocation.

0.12

Closing Gaps in Online Fair Division

cs.GT ·2026-09-04 ·Tzeh Yuan Neoh, Nicholas Teh
theoryhighly cited similarity 0.75
Abstract

We study the online fair division of indivisible items, where items arrive one at a time and must be allocated immediately and irrevocably. We address three central open questions in the literature. First, we show that for every $n\ge 2$ agents, every fixed $k\ge 1$, and every $α\in(0,1]$, no online algorithm can guarantee $α$-PROP$k$ against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in $[0,1]$, and every good is positively valued by at most two agents. The impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based fairness notions. We also establish an analogous impossibility for chores. Second, in the setting with predictions, a lightweight form of future information, the maximum item value, was previously known to guarantee only $1/n$-PROP1, leaving open whether the dependence on $n$ is necessary. We give a deterministic $19/30$-PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound $κ\in[2,n]$ on the number of agents who value any good positively, the guarantee improves to $\max \{ 19/30, n/(n+κ) \}$. The guarantee remains a positive constant under any fixed one-sided prediction error below one. When predictions are exact and the total number of goods $m\ge n\log n$ is known in advance, a deterministic algorithm achieves the same $19/30$-PROP1 factor together with $O(\sqrt{m\log n/n})$ maximum additive envy after normalizing each agent's values by their maximum item value. Third, against a non-adaptive adversary, we determine the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively. Its guarantee improves when fewer agents value the same good, unlike uniform random allocation.

0.43

Minimizing Cumulative Envy in Allocating a Sequence of Items

cs.GT cs.MA ·2026-10-07 ·Paul W. Goldberg, Isaac Robinson, Nicholas Teh
publishedhighly cited similarity 0.75
Abstract · 40 pages. Preliminary version of this paper was presented at the 19th SAGT (Sept. 2026)

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed $n$ under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a $3/2$-approximation for $n=2$ agents, an $n/(n-1)$-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.

0.59

Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees

cs.GT ·2026-09-02 ·Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
hot direction similarity 0.74
Abstract

We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For additive valuations, we establish that weighted envy-free up to one item (WEF1) allocations always exist and can be computed in polynomial time. We also study fair and efficient allocation and show that weighted envy-freeness up to one transfer (WEF1T) is compatible with fractional Pareto optimality (fPO) for every mixed-manna instance. This relaxation from WEF1 to WEF1T is tight, as demonstrated by our impossibility result. We further show a best-of-both-worlds result via a finite lottery that guarantees weighted envy-freeness (WEF) in expectation, with every realized allocation satisfying WEF1T and achieving the tight characterization complemented by the existing impossibility result.

0.43

Online Fair Division with Upgrade Recourse

cs.GT ·2026-10-12 ·Yichen Huang, Nicholas Teh
highly cited similarity 0.73
Abstract

We study the online fair division of indivisible goods. In the standard model, where assignments are irrevocable, no algorithm can guarantee any positive fraction of the maximin share (MMS). Reassigning earlier goods can restore fairness, but it may take value away from agents who already hold them. We ask how much fairness can be maintained if every reassignment must leave each affected agent at least as well off. We consider two forms of such upgrade recourse. Under item-level upgrades, each good an agent holds must be kept or replaced by a distinct good she values at least as much; under bundle-level upgrades, only her total value must not decrease. For item-level upgrades, we show that the optimal MMS factor is essentially $1/H_n \approx 1/\ln n$, where $H_n$ is the $n$-th harmonic number, and that fixed picking sequences nearly attain it. Since these sequences use only the agents' rankings of individual goods, knowing the actual values cannot improve the optimal factor for up to 33 agents, and improves it by at most a vanishing margin as $n$ grows. Bundle-level upgrades allow substantially stronger guarantees. By permitting several-for-one exchanges, they turn this vanishing factor into a constant: we achieve exact MMS for two agents and more than half of MMS for any number of agents, in both cases together with relaxations of envy-freeness. Finally, we show that predictions about future goods let online algorithms inherit any offline MMS guarantee, losing only an additive term bounded by the prediction error. Under item-level upgrades, however, insisting on exact MMS when predictions are correct leaves no positive guarantee when they are wrong.

0.33

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.72
Abstract · 43 pages

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

0.23

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.72
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.35

Reconfiguration in Fair Division Revisited

cs.GT cs.DM ·2026-09-14 ·Fabian Frank, Warut Suksompong
theory similarity 0.72
Abstract

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1 allocations with the same size vector need not admit a reconfiguration path whose intermediate allocations satisfy EF$k$. This impossibility persists even when the two allocations arise from standard EF1 approaches: the envy cycle elimination algorithm or the maximum Nash welfare solution. In contrast, we prove that allocations with the same size vector produced by recursively balanced picking sequences, including round-robin, are always connected via a path that maintains EF2. We also show that deciding whether an EF1 reconfiguration path exists is NP-hard for any fixed number of agents. Furthermore, we complement these exchange-based results by studying a more permissive model that also allows transfers, establishing additional connectivity guarantees.

0.11