Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings

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 EFlceil k/2rceil 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.