# Temporal fair division > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Temporal_fair_division > Markdown URL: https://mediated.wiki/source/Temporal_fair_division.md > Source: https://en.wikipedia.org/wiki/Temporal_fair_division > Source revision: 1352447947 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Cleanup section|date=July 2025|reason=Dense technical content needs lead and improved structure}} {{Too detailed|date=July 2025|reason=Algorithmic details may overwhelm readers}} '''Temporal fair division'''{{Citation |last1=Elkind |first1=Edith |title=Temporal Fair Division of Indivisible Items |date=2024-10-18 |place=To appear in the Proceedings of AAMAS 2025 |arxiv=2410.14593 |last2=Lam |first2=Alexander |last3=Latifian |first3=Mohamad |last4=Neoh |first4=Tzeh Yuan |last5=Teh |first5=Nicholas}} is a sequence of [fair division](/source/fair_division) instances among the same set of agents. Some examples are: * A group of housemates that have to divide the house-chores among them, day after day. * Dividing equipment between departments in a university, where various pieces of equipment arrive at different times. The standard fair division setting considers a one-shot division; but in reality, the same set of agents usually participate in several consecutive fair division instances. This adds more complexity to the fairness requirements. In some cases, the resources to allocate are not known in advance. Each day, a new resource (or set of resources) arrives, and must be immediately and irrevocably allocated. Fairness becomes much harder to attain, as the allocator might make an allocation decision that will in hindsight appear very unfair. This setting is explained in the page on '''[online fair division](/source/online_fair_division).''' This article focuses on the setting in which the resources to allocate are all known in advance: we know exactly what is going to arrive and when. The challenge here is that, in a sequence of fair division instances, people have higher fairness expectations. While they agree to tolerate a slightly unfair allocation in a single day, they expect the fairness to be restored in following days. This gives rise to stronger fairness notions, that take the temporal nature of the problem into consideration. == Terminology == === Rounds === It is common to call each instance in the sequence a "round" or a "day", though of course it is possible that the instances occur at different time-intervals. === Fairness notions === Fairness notions. Let F be any fairness notion defined for a one-shot division setting. For example, F can be [envy-freeness](/source/envy-freeness) (EF), envy-freeness up to one item (EF1), [proportionality](/source/Proportional_item_allocation) (PROP), and so on. F can be generalized to temporal fair division in three different ways:{{Cite journal |last1=Cookson |first1=Benjamin |last2=Ebadian |first2=Soroush |last3=Shah |first3=Nisarg |date=2025-04-11 |title=Temporal Fair Division |url=https://ojs.aaai.org/index.php/AAAI/article/view/33500 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=39 |issue=13 |pages=13727–13734 |doi=10.1609/aaai.v39i13.33500 |issn=2374-3468 |doi-access=free}} * '''Local''' ("per-day" or "per-round") - for each day t, the allocation in day t should satisfy F; * '''Cumulative''' ("up-to each day" or "temporal") - for each day t, the combined allocation in days 1,...,t should satisfy F; * '''Overall''' - the combined allocation in days 1,...,T should satisfy F. Note that Cumulative-F implies Overall-F. However, Local-F is independent of these two. Local-F alone and Overall-F alone can be obtained by any standard (non-temporal) allocation that obtains F; the challenges are threefold: # Guarantee Local-F and Overall-F simultaneously; # Guarantee Cumulative-F alone or in combination with Local-F; # Guarantee Overall-F when F itself cannot be attained. '''Remark'''. When studying cumulative fairness, it is usually assumed that there is a single item per day.{{Rp|location=Lem.3.1}}This is because, for any instance with e.g. ''k'' items per day, one can create an instance with a single item per day (essentially "split" each day into ''k'' consecutive days), and if the new instance admits a cumulative-F allocation, then so does the original instance. == Identical days: Repeated fair division{{Anchor|repeated}} == '''Repeated fair division''' is a special case of temporal fair division in which the items are the same in each period. This setting allows for stronger fairness guarantees. === Repeated matching === '''Repeated matching''' is a special case of repeated fair division in which there are ''n'' items in each round, and each agent should exactly one item per round. An example of this setting is housechore allocation: each day, each housemate must do exactly one chore, and the chores are the same each day. Some fairness notions are easy to attain in this setting: * Local-EF1 is trivially attained by any matching, as each agent only gets one item. * Overall-EF1 can be found by creating T copies of each item and using the Biswas-Barman algorithm for fair allocation with [partition matroid](/source/partition_matroid) constraints,{{Rp|page=6}} or simply by [round-robin item allocation](/source/round-robin_item_allocation). This guarantees that each agent receives exactly T item-copies. This allocation can then be converted to a sequence of T matchings using an [edge-coloring](/source/Edge_coloring) algorithm.{{Cite journal |last1=Cole |first1=Richard |last2=Ost |first2=Kirstin |last3=Schirra |first3=Stefan |date=2001-01-01 |title=Edge-Coloring Bipartite Multigraphs in O(E logD) Time |url=https://doi.org/10.1007/s004930170002 |journal=Combinatorica |language=en |volume=21 |issue=1 |pages=5–12 |doi=10.1007/s004930170002 |issn=1439-6912|url-access=subscription }} ==== Time-dependent valuations and Overall-EF1 ==== Caragiannis and Narang{{Cite journal |last1=Caragiannis |first1=Ioannis |last2=Narang |first2=Shivika |date=2024-01-04 |title=Repeatedly matching items to agents fairly and efficiently |url=https://www.sciencedirect.com/science/article/abs/pii/S0304397523005595 |journal=Theoretical Computer Science |volume=981 |article-number=114246 |arxiv=2207.01589 |doi=10.1016/j.tcs.2023.114246 |issn=0304-3975}} study a generalized repeated matching setting in which the value of an agent for an item may depend on the number of rounds the item was previously used by the same agent. In this setting, attaining overall-EF1 becomes more challenging, and the round-robin technique does not work. For example, suppose there are two agents, two items and three rounds. Suppose that: * Alice always values x at 2; she values the first use of y at 1, and the second and third uses at 10. * George always values y at 2; he values the first use of x at 1, and the second and third uses at 10. In round-robin, Alice will choose three copies of x and George will choose three copies of y; both agents end up envying each other, and the overall allocation is not even EF1. They show that: * Computing a [utilitarian item allocation](/source/utilitarian_item_allocation) (maximizing the sum of utilities) is NP-hard for T ≥ 3, by reduction from [3-dimensional matching](/source/3-dimensional_matching) (for T=1 it is equivalent to maximum-weight perfect matching, which is polynomial). However, when the valuations are monotone w.r.t. time (i.e., vi(g,t) either increases with t or decreases with t), it can be solved in polynomial time, even with mixtures of goods and bads, by reduction to b-matching.''''''{{Rp|location=Sec.3}} * For agents with identical non-negative valuations, there is a polytime algorithm that computes an overall-EF1 allocation.''''''{{Rp|location=Alg.1}} * For agents with general non-negative valuations, when ''T'' mod ''n'' is in {0, 1, 2, ''n''-1}, there is a polytime algorithm that computes an overall-EF1 allocation.''''''{{Rp|location=Alg.2,3}} In particular, this holds for every instance with at most 4 agents. The existence of overall-EF1 allocations for n≥5 agents remains open. * Even with constant valuations, it is NP-hard to approximate the optimal utilitarian welfare of overall-EF1 allocations to a factor better than O(min(''n''1/3 ''T'')), by reduction from [maximum independent set](/source/maximum_independent_set).''''''{{Rp|location=Sec.5}} * WIth a mixture of goods and bads, EF1 might be impossible to satisfy in a matching, so they relax it to ''swap-envy-freeness.'' They prove that, with identical valuations, their Algorithm 1 compues an overall-swapEF allocation. For general valuations, when ''T'' mod ''n'' is in {0, 1, 2, ''n''-2, ''n''-1}, there is a polytime algorithm that computes an overall-swapEF allocation. In particular, this holds for every instance with at most 5 agents. The existence of overall-swapEF allocations for n≥6 agents remains open.''''''{{Rp|location=Sec.6}} ==== Past allocations, Cumulative-EF1 and Pareto-efficiency ==== Micheel and Wilczynski{{Cite book |last1=Micheel |first1=Karl Jochen |last2=Wilczynski |first2=Anaëlle |title=27th European Conference on Artificial Intelligence (ECAI 2024) |chapter=Fairness in Repeated House Allocation |series=Frontiers in Artificial Intelligence and Applications |date=October 2024 |chapter-url=https://hal.science/hal-04880340/ |publisher=IOS Press |doi=10.3233/faia240909 |isbn=978-1-64368-548-9 |doi-access=free}} also study repeated matching (which they call "repeated house allocation"). They assume that agents have [ordinal preferences](/source/ordinal_preferences) over the houses, which do not change between rounds. They measure the cumulative envy - the envy after each time-step (not just at the end). They also require that the allocation at each round be [Pareto efficient](/source/Pareto_efficient). They also take into account past rounds - rounds that occurred before the algorithm starts. They study three fairness notions: * '''Mirrored envy:'''{{Rp|location=Sec.4}} if some agent envies another agent a certain number of times, then the latter envied them the same number of times. They prove that, if there is only one future step (in addition to any number of past steps), then deciding whether a mirror-EF and PO allocation exists is polynomial. The same holds if there are at most two future steps (in addition to any number of past steps), and the agents have the same preferences. But if there are two or more future steps (even with no past steps), and agents have different preferences, then the decision problem is NP-complete, by reduction from [exact-3-cover](/source/Exact_cover). * '''Equal treatment of equals (ETE):'''{{Rp|location=Sec.5}} agents with the same preferences get exactly the same received objects. They prove that an ETE and PO allocation always exists when the past is empty and the size of every [equivalence class](/source/equivalence_class) of agents divides the number of future rounds. In that case, a solution can be found in polytime. But in general, deciding whether an ETE allocation exists, even with no past, is NP-complete (by reduction from the [partition problem](/source/partition_problem)). But if there is no past, and the number of equivalence classes, then the problem can be solved in [pseudo-polynomial time](/source/pseudo-polynomial_time). * '''Minimizing the number of times an agent is envious{{Rp|location=Sec.6}}''': If there are T future rounds, then there is always an allocation in which the maximum number of times each agent is envious is at most ceiling(T/2). We can find it by running [round robin item allocation](/source/Round-robin_item_allocation) for ceiling(T/2) rounds in one order, and for floor(T/2) rounds in the opposite order. This bound is tight, as if agents have identical strict preferences, for every pair of agents there is one agent who envies the other one for at least ceiling(T/2) rounds. Deciding if there exists an allocation with max number of envious rounds at most T/3 is NP-hard (in particular, if there are 3 future rounds, then deciding if there exists an allocation with max number of envious rounds at most 1 is NP-hard), by reduction from exact-3-cover. It remains open whether a cumulative-EF1 allocation always exists. Interestingly, in some cases there exists a cumulative-EF1 allocation but no ''repetitive'' cumulative-EF1 allocation. For any n≥3, it is NP-hard to decide whether there exists a repetitive cumulative-EF1 allocation, even for T=2 rounds, by reduction from [Multiway number partitioning](/source/Multiway_number_partitioning).{{Rp|location=Thm.5.2}} === Repeated allocation === In the more general repeated allocation setting, there can be more or fewer than n items each day, and every agent may receive any number of items each day. Igarashi, Lackner, Nardi and Novaro{{Cite journal |last1=Igarashi |first1=Ayumi |last2=Lackner |first2=Martin |last3=Nardi |first3=Oliviero |last4=Novaro |first4=Arianna |date=2024-03-24 |title=Repeated Fair Allocation of Indivisible Items |url=https://ojs.aaai.org/index.php/AAAI/article/view/28837 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=38 |issue=9 |pages=9781–9789 |arxiv=2304.01644 |doi=10.1609/aaai.v38i9.28837 |issn=2374-3468}} study both overall fairness and per-round (local) fairness. They consider two settings: the number of rounds can be either ''fixed'' in advance, or ''variable'' (can be chosen by the algorithm). The prove that: * When the number of rounds is fixed (T), if T is a multiple of n, then there is always a sequence that is overall [envy-free](/source/Envy-freeness) (EF), and a sequence that is overall [proportional](/source/Proportional_item_allocation) and [Pareto-efficient](/source/Pareto_efficiency) (PROP+PE). In contrast, if T is not a multiple of n, then there might not exist an overall-PROP sequence (this holds in particular for the one-shot division setting T=1). Moreover, for any T and any n>2, there might not exist an overall EF+PO sequence. * For n=2 agents and any even T, there always exists a sequence which is overall EF+PO and per-day weak EF1. * For n=2 agents and T=2 rounds, there always exists a sequence that is overall EF+PO and per-round EF1; and we can always find a sequence that is overall EF and per-round EF1. But for T>2, there may be no sequence that is overall EF+PO and per-round EF1. * When the number of rounds is variable (can be chosen by the algorithm), for any ''n'', there always exists a sequence that is overall EF+PO and per-round PROP[1,1] (if there are only goods or only chores, then PROP[1,1] becomes PROP1). They do not give an upper bound on the number of rounds required. Cookson, Ebadian and Shah'''''' strengthen their results to ''ordinal'' fairness (fairness that holds for any utility functions compatible with the rankings). They show polynomial time algorithms that guarantee the following combinations: * For n=2 agents: per-day ordinal-EF1 and cumulative ordinal-EF1, as well as cumulative ordinal-EF for each even day.''''''{{Reference page|location=Sec.4.3}} * For n agents: per-day ordinal-EF1 and overall ordinal-PROP1''''''{{Reference page|location=Sec.6}} (cumulative ordinal-EF1 cannot be guaranteed even with identical preferences.''''''{{Reference page|location=App.E}}) == Different days == The more general case of temporal division is when the items in each day may be different (but it still known in advance what items are coming). Cumulative-EF1 is the main fairness notion. A first solution that comes to mind is to use the [envy-graph procedure](/source/envy-graph_procedure), that is, each day, the daily item is allocated to an unenvied agent. The partial allocation is always EF1. However, in case there is envy-cycle, we must exchange bundles along the cycle, which destroys the cumulative-EF1 guarantee.{{Clarify|reason=Should add a numeric example to clarify|date=July 2025}} Still, the envy-graph procedure works when agents have identical valuations, as in this case no envy-cycles are formed. He, Procaccia and Psomas{{cite conference |last1=He |first1=Jiafan |last2=Procaccia |first2=Ariel D. |last3=Psomas |first3=Alexandros |last4=Zeng |first4=David |year=2019 |editor-last=Kraus |editor-first=Sarit |title=Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 |pages=343–349 |doi=10.24963/IJCAI.2019/49 |isbn=978-0-9992411-4-1 |contribution=Achieving a Fairer Future by Changing the Past|doi-access=free }} show a polytime algorithm that attains cumulative-EF1 for two agents with positive valuations (goods). It is similar to the envy-graph algorithm except that, when envy-cycles occur, only partial bundles are exchanged, in a way that maintains the cumulative-EF1 guarantee. An analogous algorithm works with negative valuations (chores).{{Rp|location=Sec.3.1}} With three or more agents, it may be impossible to attain cumulative-EF1 without reallocating previously-allocating items (moreover, Ω(''T'') reallocations might be required). There is an example with three agents and 23 goods; the example does not extend to chores, so the case of chores and 3 or more agents remains open.{{Rp|location=App.A}} Elkind, Lam, Latifian, Neoh and Teh{{Rp|location=Sec.3.2}} show some more cases (in addition to the case of two agents) in which a cumulative-EF1 (TEF1) allocation always exists, and can be found in polytime: * There are two types of items (goods or chores). * All agents have generalized binary valuations (goods or chores); this generalizes both identical valuations and binary valuations. The algorithm is greedy: the next item is given to an agent with the smallest value. They prove that this agent is always unenvied (as in the [envy-graph algorithm](/source/envy-graph_algorithm)). Note that the algorithm does not require any information about the future, besides the information that the agents' valuations are identical. * The preferences are [single-peaked](/source/Single_peaked_preferences) (for goods) or single-dipped (for chores). This means that, over time, the values of goods for every agent increases and then decreases (for chores it decreases and then increases). The algorithm is [round-robin item allocation](/source/round-robin_item_allocation). * There are two rounds (with possibly multiple items per round).{{Rp|location=Thm.5.1}} On the other hand, they show that a cumulative-EFx allocation might not exist for either goods or chores, even for two agents with identical valuations and two types of items, and even when the values are increasing with time (for goods) or decreasing with time (for chores).{{Rp|location=Sec.3.1}} For the general case, they prove several hardness results regarding cumulative-EF1:{{Rp|location=Sec.3.3}} * For goods, it is NP-hard to decide if a given instance has a cumulative-EF1 allocation, even for n=3 agents. * For chores, it is NP-hard to decide if a given instance with a given partial cumulative-EF1 allocation (up to some time ''t'') has a continuation that is cumulative-EF1, even for n=4 agents. There are also several hardness results regarding combining cumulative-EF1 with [Pareto-efficiency](/source/Pareto-efficiency):{{Rp|location=Sec.4}} * For either goods or chores, for any ''n'' ≥ 2, there might not exist an allocation that is both TEF1 and [Pareto-efficient](/source/Pareto-efficient). * Determining the existence of such an allocation is NP-hard even for n=2 agents. * SImilarly, determining the existence of an allocation that is both TEF1 and [utilitarian-optimal](/source/Utilitarian_item_allocation), or more generally, maximizes p-mean welfare, is NP-hard even for n=2 agents. Cookson, Ebadian and Shah'''''' study temporal fair division with an additional requirements of ''ordinal'' fairness (which means that the fairness notion should hold for any additive utility function that is compatible with the ranking). They show polytime algorithms for the following combinations of features: * Overall PROP1 and Per-day ordinal-EF1.''''''{{Reference page|location=Sec.3}} The algorithm first transforms the instance such that, in each day, all agents have the same ranking over the items; then they use the Biswas-Barman algorithm. They prove that the PROP1 guarantee is maintained under the identical-order transformation. * Cumulative EF1 and Per-day ordinal-EF1 for two agents.''''''{{Reference page|location=Sec.4}}(even for two agents, it is impossible to guarantee cumulative ordinal-EF1, and impossible to guarantee simultaneously per-day EF1 and overall ordinal-EF1). * Overall ordinal-EF1 and Per-day ordinal-EF1 for n agents with identical rankings.''''''{{Reference page|location=Sec.5}} (even with identical preferences and identical days, cumulative ordinal-EF1 cannot be guaranteed) == Related problems == * '''Reachability:'''{{Cite journal |last1=Igarashi |first1=Ayumi |last2=Kamiyama |first2=Naoyuki |last3=Suksompong |first3=Warut |last4=Yuen |first4=Sheung Man |date=2024-12-01 |title=Reachability of Fair Allocations via Sequential Exchanges |url=https://doi.org/10.1007/s00453-024-01271-y |journal=Algorithmica |language=en |volume=86 |issue=12 |pages=3653–3683 |doi=10.1007/s00453-024-01271-y |issn=1432-0541|arxiv=2312.07241 }} Sometimes it is required to move from one fair allocation to another one (e.g. a company redistributes its employees between departments, or a museum reallocates its exhibits among its branches). It is required to do the move gradually, one item at a time, such that the intermediate allocations are fair too. * '''Temporal fairness in multiwinner voting:'''{{Cite journal |last1=Elkind |first1=Edith |last2=Obraztsova |first2=Svetlana |last3=Teh |first3=Nicholas |date=2024-03-24 |title=Temporal Fairness in Multiwinner Voting |url=https://ojs.aaai.org/index.php/AAAI/article/view/30273 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=38 |issue=20 |pages=22633–22640 |doi=10.1609/aaai.v38i20.30273 |issn=2374-3468|doi-access=free }} study notions similar to cumulative-fairness, but in the context of [Multiwinner voting](/source/Multiwinner_voting). See also [Multi-issue voting](/source/Multi-issue_voting). * '''Fair resource allocation over time:'''{{Cite book |last1=Bampis |first1=Evripidis |last2=Escoffier |first2=Bruno |last3=Mladenovic |first3=Sasa |date=July 2018 |chapter=Fair resource allocation over time |chapter-url=https://hal.science/hal-01926989 |title=AAMAS 2018 - 17th International Conference on Autonomous Agents and MultiAgent Systems |location=Stockholm, Sweden |publisher=International Foundation for Autonomous Agents and Multiagent Systems |pages=766–773}} focuses on max-min fairness. * '''Sequential fair allocation''':{{Cite journal |last1=Sinclair |first1=Sean R. |last2=Banerjee |first2=Siddhartha |last3=Yu |first3=Christina Lee |date=2022-07-07 |title= Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve|url=https://dl.acm.org/doi/10.1145/3547353.3526951 |journal= ACM SIGMETRICS Performance Evaluation Review|volume=50 |issue=1 |pages=95–96 |doi=10.1145/3547353.3526951 |issn=0163-5999|url-access=subscription }} focuses on the fairness-efficiency curve. * '''Dynamic fair division with minimal disruptions'''.{{Cite book |last1=Friedman |first1=Eric |last2=Psomas |first2=Christos-Alexandros |last3=Vardi |first3=Shai |chapter=Dynamic Fair Division with Minimal Disruptions |date=2015-06-15 |title=Proceedings of the Sixteenth ACM Conference on Economics and Computation |chapter-url=https://dl.acm.org/doi/10.1145/2764468.2764495 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=697–713 |doi=10.1145/2764468.2764495 |isbn=978-1-4503-3410-5}} * Fair allocation with [Latin square](/source/Latin_square) constraints.{{Citation |last1=Kawase |first1=Yasushi |title=Resource Allocation under the Latin Square Constraint |date=2025-01-11 |arxiv=2501.06506 |last2=Roy |first2=Bodhayan |last3=Sanpui |first3=Mohammad Azharuddin}} == Summary of results == The following table summarizes results for indivisible item allocation. Results are presented by the characteristics of the '''single-day problem''' (what is done each day), and the '''temporal aspects''' (what relates problems solved in different days). Information on future can be: * '''0 None''' - totally uninformed algorithm (the [online fair division](/source/online_fair_division) setting). * '''1 Max value''' - algorithm has minimal information - only the maximum value of an item for an agent (this maximum value is usually normalized to 1); this setting is also sometimes called [online fair division](/source/online_fair_division). * '''1 Sum values''' - algorithm knows the sum of values for each agent (equivalently, the sum of values for each agent is normalized to 1); * '''2 Multiset''' - algorithm knows the multiset of values for each agent (but not their order). * '''3 Complete''' - algorithm has [complete information](/source/complete_information) (the "temporal fair division" setting; if the days are identical, then it is called "repeated fair division"). The Adversary models are based on Zeng and Psomas:{{Cite book |last1=Zeng |first1=David |title=Proceedings of the 21st ACM Conference on Economics and Computation |last2=Psomas |first2=Alexandros |date=2020-07-13 |publisher=Association for Computing Machinery |isbn=978-1-4503-7975-5 |series=EC '20 |location=Virtual Event, Hungary |pages=911–912 |chapter=Fairness-Efficiency Tradeoffs in Dynamic Fair Division |doi=10.1145/3391403.3399467 |chapter-url=https://doi.org/10.1145/3391403.3399467 |arxiv=1907.11672 |s2cid=198953099}} * '''1 IID''' - valuations are drawn independently at random from an identical distribution (easiest model); * '''5 Adaptive''' - valuations are adversarial and the adversary at each day can see the algorithm decisions at previous days (hardest model). {| class="wikitable" |+ !Name+Cite ! rowspan="12" | ! colspan="4" |Single-day problem ! rowspan="11" | ! colspan="5" |Temporal aspects ! rowspan="11" | !Comments |- ! !#Items !#Agents !Valuations !Per-day fairness !Information on future !Identical days? !Adversary !Overall fairness at round T !Cumulative fairness ! |- |LIKE{{Cite journal |last1=Aleksandrov |first1=Martin |last2=Aziz |first2=Haris |last3=Gaspers |first3=Serge |last4=Walsh |first4=Toby |date=2015-07-25 |title=Online fair division: analysing a food bank problem |url=https://dl.acm.org/doi/abs/10.5555/2832581.2832604 |journal=Proceedings of the 24th International Conference on Artificial Intelligence |series=IJCAI'15 |location=Buenos Aires, Argentina |publisher=AAAI Press |pages=2540–2546 |arxiv=1502.07571 |doi= |isbn=978-1-57735-738-4}} |1 |''n'' |Binary | - |1 Max value |0 Different |5 Adaptive | colspan="2" |ex-ante EF. |Truthful. Not ex-post EFc for any c. |- |BALANCED LIKE |1 |''n'' |Binary | - |1 Max value |0 Different |5 Adaptive | colspan="2" |ex-ante EF, ex-post EF1. |Truthful for n≥2 but not for n≥3. |- |Derandomized LIKE{{Cite book |last1=Benade |first1=Gerdus |title=Proceedings of the 2018 ACM Conference on Economics and Computation |last2=Kazachkov |first2=Aleksandr M. |last3=Procaccia |first3=Ariel D. |last4=Psomas |first4=Christos-Alexandros |date=2018-06-11 |publisher=Association for Computing Machinery |isbn=978-1-4503-5829-3 |series=EC '18 |location=Ithaca, NY, USA |pages=593–610 |chapter=How to Make Envy Vanish over Time |doi=10.1145/3219166.3219179 |doi-access=free |s2cid=3340196}} |1 |''n'' |Additive | - |1 Max value |0 Different |5 Adaptive |Envy ≤ sqrt(T/n). | - |Envy bound is tight. |- |Derandomized LIKE with batches{{Cite journal |last1=Benadè |first1=Gerdus |last2=Kazachkov |first2=Aleksandr M. |last3=Procaccia |first3=Ariel D. |last4=Psomas |first4=Alexandros |last5=Zeng |first5=David |date=July 2024 |title=Fair and Efficient Online Allocations |url=https://pubsonline.informs.org/doi/10.1287/opre.2022.0332 |journal=Operations Research |volume=72 |issue=4 |pages=1438–1452 |doi=10.1287/opre.2022.0332 |issn=0030-364X |url-access=subscription}}{{Rp|location=Sec.3.1-3.2}} |''m'' |''n'' |Additive | - |1 Max value |0 Different |5 Adaptive |Envy ≤ sqrt(T/(mn)). | - |Envy bound is tight. |- |Online Stripe Discrepancy{{cite arXiv |eprint=1910.01073 |class=cs.DS |first1=Haotian |last1=Jiang |first2=Janardhan |last2=Kulkarni |title=Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization |date=2019-10-02 |last3=Singla |first3=Sahil}} |1 |2 |Additive | - |1 Max value |0 Different |1 [IID](/source/IID) |Envy ≤ T^(const/log log T), [w.h.p.](/source/With_high_probability) | - |Holds even for ordinal envy. |- |Clique Rounding{{Rp|location=Alg.3}}{{Rp|location=Sec.4}} |1 |''n'' |Additive | - |1 Max value |0 Different |3 Correlated (hence also 1,2) |Ex-post [PE](/source/Pareto_efficiency); every pair (i,j) satisfies either EF1, or EF [w.h.p.](/source/With_high_probability) | - |Fairness guarantee cannot be improved even for adversary 1 (IID). |- |''***'' ''[Incompatibility result]{{Rp|location=Sec.5}}{{Rp|location=Sec.3.3}}'' |1 |''n'' |Additive | - |1 Max value |0 Different |4 Non-adaptive (hence also 5) |Envy in o(T); 1/n-PE. | - |''Impossible.'' |- |Envy Balancing{{cite conference |last1=He |first1=Jiafan |last2=Procaccia |first2=Ariel D. |last3=Psomas |first3=Alexandros |last4=Zeng |first4=David |year=2019 |editor-last=Kraus |editor-first=Sarit |title=Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 |pages=343–349 |doi=10.24963/IJCAI.2019/49 |isbn=978-0-9992411-4-1 |contribution=Achieving a Fairer Future by Changing the Past|doi-access=free }}{{Rp|location=Alg.2}} |1 |2 |Additive | - |3 Complete |0 Different |5 Adaptive |EF1 | - |Requires no adjustments. |- |Fractional Item Rounding{{Rp|location=Alg.1}} |1 |2 |Additive | - |0 None |0 Different |5 Adaptive |EF1 | - |Requires at most ''T'' adjustments. |- |Double Round Robin{{Rp|location=Alg.3}} |1 |''n'' |Additive | - ! |0 None |0 Different |5 Adaptive |EF1 | - ! |Requires O(''T''3/2) adjustments. |- |''***'' ''[Impossibility result]{{Rp|location=Thm.4.2}}'' ! |1 |''n'' |Additive | - ! |3 Complete (hence also 0,1,2) |0 Different |4 Non-adaptive (hence also 5) |EF1 | - ! |''Requires Omega(T) adjustments.'' |- |Repeated fair allocation for two agents{{Cite journal |last1=Igarashi |first1=Ayumi |last2=Lackner |first2=Martin |last3=Nardi |first3=Oliviero |last4=Novaro |first4=Arianna |date=2024-03-24 |title=Repeated Fair Allocation of Indivisible Items |url=https://ojs.aaai.org/index.php/AAAI/article/view/28837 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=38 |issue=9 |pages=9781–9789 |arxiv=2304.01644 |doi=10.1609/aaai.v38i9.28837 |issn=2374-3468}}{{Rp|location=Sec.4}} ! |''m'' |2 |Additive |Weak-EF1 ! |3 Complete |1 Identical | - | colspan="2" |EF+PE (when T is even). ! |Per-round EF1 for T=2 days |- |Repeated fair allocation for ''n'' agents{{Rp|location=Sec.3}} ! |''m'' |''n'' |Additive |None ! |3 Complete |1 Identical | - | colspan="2" |EF or PROP+PE (when ''T'' is a multiple of ''n''). ! |Impossible when T is not a multiple of ''n''. EF+PE impossible for ''n''>2. |- |Repeated matching - time-dependent valuations{{Cite journal |last1=Caragiannis |first1=Ioannis |last2=Narang |first2=Shivika |date=2024-01-04 |title=Repeatedly matching items to agents fairly and efficiently |url=https://www.sciencedirect.com/science/article/abs/pii/S0304397523005595 |journal=Theoretical Computer Science |volume=981 |article-number=114246 |arxiv=2207.01589 |doi=10.1016/j.tcs.2023.114246 |issn=0304-3975}} ! |''n'' |''n'' |Additive; Item value for ''i'' can depend on number of times it is used by ''i''. |EF1 (trivial) ! |3 Complete |1 Identical | - |EF1 |None ! | |- |Repeated matching ! |''n'' |''n'' |Additive |EF1 (trivial) ! |3 Complete |1 Identical | - |EF1 |None ! |Biswas-Barman algorithm for partition-matroid constraints |- |[Envy-graph](/source/Envy-graph_procedure){{Rp|location=Sec.3.2}} ! |''m'' |''n'' |Additive, Generalized-binary |None ! |0 None (hence also 1, 2, 3) |0 Different | - | colspan="2" |EF1 ! |There is always an unenvied agent; no need to remove cycles. |- |''*** [Impossibility result]{{Citation |last1=Neoh |first1=Tzeh Yuan |title=Online Fair Division with Additional Information |date=2025-05-30 |arxiv=2505.24503 |last2=Peters |first2=Jannik |last3=Teh |first3=Nicholas}}''{{Reference page|location=Sec.3}} ! |1 |≥ 2 |Additive | - ! |0 None |0 Different |5 Adaptive |EF1 | - ! |''Any multiplicative approximation of EF1 is impossible'' |- |''*** [Impossibility result]''{{Reference page|location=Sec.3}} ! |1 |2 |Additive | - ! |0 None |0 Different |5 Adaptive |PROP1 | - ! |''PROP1 is impossible'' |- |Satisficing algorithm''''{{Reference page|location=Sec.4}} ! |1 |''n'' |Additive | - ! |1 Sum values |0 Different |5 Adaptive |PROP1; EF1 for n=2 | - ! |EFx impossible for n≥2; EF1 impossible for n≥3. |- |Picking-sequence algorithm''''{{Reference page|location=Sec.5}} ! |1 |''n'' |Additive | - ! |2 Multiset |0 Different |5 Adaptive |Every share-based notion; and EFx for n=2 | - ! |Cannot guarantee EFx for n≥3. |} ==References== {{reflist}} Category:Fair division --- Adapted from the Wikipedia article [Temporal fair division](https://en.wikipedia.org/wiki/Temporal_fair_division) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Temporal_fair_division?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.