# repeated_fair_allocation_of_indivisible_items__3a5ede8a.pdf

Repeated Fair Allocation of Indivisible Items

Ayumi Igarashi1, Martin Lackner2, Oliviero Nardi2, Arianna Novaro3

1The University of Tokyo 2DBAI, TU Wien 3CES, University of Paris 1 Panth eon-Sorbonne igarashi@mist.i.u-tokyo.ac.jp, lackner@dbai.tuwien.ac.at, oliviero.nardi@tuwien.ac.at, arianna.novaro@univ-paris1.fr

The problem of fairly allocating a set of indivisible items is a well-known challenge in the ﬁeld of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and economic efﬁciency (such as Paretooptimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In this paper, we show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Paretooptimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to ﬁnd a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisﬁes some relaxation of envyfreeness. Finally, in case that the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal allocations are achievable for any number of agents.

1 Introduction

In a variety of real-life scenarios, a group of agents has to divide a set of items among themselves. These items can be desirable (goods) or undesirable (chores) and agents have (heterogeneous) preferences concerning them. In the case of goods, we can think, for instance, of employees having to share access to some common infrastructure, like computing facilities. In the case of chores, we can think of roommates having to split household duties or teams having to split admin tasks. We may even have a set of mixed items, where the agents may consider some items good and others bad: for instance, when assigning teaching responsibilities, some courses may be desirable to teach for some while undesirable (negative) for others. The examples above are all instances of problems of fair allocation of indivisible items (see the recent survey by

Copyright c 2024, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Amanatidis et al. (2022)). One of the challenges of fair division problems is that often, given the agents preferences, it is impossible to ﬁnd an allocation of the items which is both fair (e.g., no agent envies another agent s bundle) and efﬁcient (e.g., no other allocation would make some agents better off, without making anyone worse off). However, a crucial feature which has so far received little attention, is that many fair allocation problems occur repeatedly, in the sense that the same items will need to be assigned multiple times to the agents. For instance, university courses are usually offered every year, computing facilities may be needed daily or weekly by the same teams of employees, and household chores need to be done regularly. In this paper, we thus focus precisely on those settings where a set of items has to be repeatedly allocated to a set of agents. This opens the ﬁeld to new and exciting research directions, revolving around the following central question:

Can some fairness and efﬁciency notions be guaranteed when taking a global perspective on the overall sequence of repeated allocations? Can we additionally achieve fairness and efﬁciency guarantees at each individual repetition?

Contribution and outline. Our main contribution is the deﬁnition of a new (ofﬂine) model for the repeated fair allocation of goods and chores, which we present in Section 2. In particular, we specify how sequences of allocations will be evaluated with respect to classical axioms of fairness and efﬁciency: we distinguish between sequences satisfying some axioms per-round (i.e., for every allocation composing them), or overall (i.e., when considering the collection of all the bundles every agent has received in the sequence). We consider two general cases: one where the number of repetitions is predetermined and given as part of the input and one where the number of repetitions can be chosen freely based on the instance. In the sequel, we refer to these as the ﬁxed and variable cases, respectively. In Section 3, we study our model for a ﬁxed number of rounds (k) with n agents. We show that: if the number of rounds is a multiple of n, we can always guarantee the existence of a sequence of allocations that is envy-free overall in (Proposition 4), and a sequence of allocations that is proportional and Pareto-optimal (Theorem 7). This is essentially optimal in two respects. First, for any number n 2 of

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

agents and any ﬁxed number k of rounds which is not a multiple of n, a sequence of allocations that is proportional overall may not exist (Proposition 5). Moreover, for any number n > 2 of agents and any ﬁxed number k of rounds, there is an instance of chore allocation where an envy-free and Pareto-optimal sequence of allocations may not exist (Theorem 6). In Section 4, we will stay in the ﬁxed-k setting but focus our model on the case of two agents. This scenario is fundamental in fair division, with numerous applications, including inheritance division, house-chore division, and divorce settlements (Brams and Fishburn 2000; Brams, Kilgour, and Klamler 2014; Kilgour and Vetschera 2018; Igarashi and Yokoyama 2023). Here, we show that if the number of rounds is even, we can always ﬁnd a sequence of allocations which is envy-free and Pareto-optimal overall, as well as per-round weak envy-free up to one item (Corollary 14). Moreover, for two rounds, we can strengthen the per-round fairness guarantee to envy-freeness up to one item (EF1) (Corollary 12). At the cost of sacriﬁcing the efﬁciency requirement, we also show that we can always ﬁnd a sequence of allocations which is envy-free and per-round EF1 in polynomial time (Theorem 15). These results turn out to be the best we can hope for. In Proposition 10, we show that there is an instance with two agents and k > 2 rounds where no sequence of allocations is envy-free and Pareto-optimal overall, as well as per-round EF1. In Section 5, we investigate the model with a variable number of rounds. Within this model, we can in fact achieve overall and per-round fairness guarantees for the case of n agents. Speciﬁcally, we establish the existence of a sequence of allocations that satisﬁes envy-freeness and Pareto-optimality overall, while also meeting the perround PROP[1,1] criterion (a weakening of proportionality). For scenarios involving goods only or chores only, we can achieve even per-round PROP1. To show this, we establish the connection between our model and the divisible and probabilistic fair division problems. An overview of our results can be found in Table 1. All the omitted proofs are presented in the full version of our paper (Igarashi et al. 2023).

Related work. Aziz et al. (2022) analyze fairness concepts for the allocation of indivisible goods and chores. Based on some of these results, Igarashi and Yokoyama (2023) have also developed an app to help couples divide household chores fairly. Another relevant application is that of the fair allocation of papers to reviewers in peer-reviewed conferences (Meir et al. 2021; Payan and Zick 2022), as well as the allocation of students to courses under capacity constraints (Othman, Sandholm, and Budish 2010). These articles focus however on one-shot (non-repeated) problems. Repetitions have been studied in the context of matchings (Hosseini, Larson, and Cohen 2015; Gollapudi, Kollias, and Plaut 2020; Caragiannis and Narang 2022). This line of work uses models similar to ours. However, results do not carry over due to differences between matchings and arbitrary multi-unit assignments (as we consider). Repeated fair allocation is also related to probabilistic fair division (Budish et al. 2013; Aziz et al. 2023). We make this connection

precise in Section 5. Various settings fall under the umbrella of dynamic or online fair decision-making (Aleksandrov and Walsh 2020; Kohler et al. 2014; Kash, Procaccia, and Shah 2014; Freeman et al. 2018; Benade et al. 2018; Zeng and Psomas 2020). Guo, Conitzer, and Reeves (2009) and Cavallo (2008) focus on a repeated setting, where a single item must be allocated in every round. We work in an ofﬂine setting, where agents have static and heterogeneous preferences over multiple items instead of demands, and the sets of agents and items is ﬁxed. Balan, Richards, and Luke (2011) also study repeated allocations of items, but they focus on the average of utilities received by the agents for an allocation sequence. In the context of elections, a closely related framework is that of perpetual voting, introduced by Lackner (2020), where the agents participate in repeated elections to select a winning candidate and classical fairness axioms (as well as new ones) are introduced to evaluate aggregation rules with respect to sequences of elections. A similar approach has also been taken to analyze repeated instances of participatory budgeting problems (Lackner, Maly, and Rey 2021). Freeman, Zahedi, and Conitzer (2017) consider a setting where at each round one alternative is selected, and agents preferences may vary over time. A related model of simultaneous decisions, closer to fair division, has been studied by Conitzer, Freeman, and Shah (2017).

2 The Model

In this section, we present the model used throughout the paper. Furthermore, we recall some familiar concepts from the theory of fair division, and adapt them to our scenario. We denote by N a ﬁnite set of n agents, who have to be assigned a set of m items in the ﬁnite set I. An allocation π N I consists of agent-item pairs (i, o), indicating that agent i is assigned item o. We denote by πi = {o I : (i, o) π} the set of items that an agent i receives in allocation π. We assume that the allocation must be exhaustive: all items must be assigned to some agent (and no two agents may receive the same item). Thus, S i N πi = I and, for all distinct i, j N, πi πj = . We write [k] to denote {1, . . . , k}. Finally, given a positive integer ℓ, we denote by ℓN the set of positive integers multiples of ℓ.

Utilities. Each agent i N is associated with a (dis)utility function ui : I R, which indicates how much they like or dislike each item. Namely, we consider a setting where each agent may view each item as a good, a chore, or a null item. In particular, we say that an item o I is an objective good (resp. chore or null) if, for all i N, ui(o) > 0 (resp. ui(o) < 0 or ui(o) = 0). Otherwise, we say that o is a subjective item. We focus on additive utility functions and with a slight abuse of notation we write ui(S) = P o S ui(o) for the utility that agent i gets from set S I. Thus, the utility of agent i for an allocation π is given by ui(πi). We denote by u = (u1, . . . , un) the proﬁle of utilities for the agents.

Fairness. We introduce several fairness concepts, as deﬁned by Aziz et al. (2022) and by Amanatidis et al. (2022).

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

condition result #agents (n) #rounds (k) fairness guarantee reference n 2 k n N EF overall Prop. 4 n 2 k / n N PROP overall Prop. 5 n > 2 k N EF+PO overall Thm. 6 n 2 k n N PROP+PO overall Thm. 7 n 2 variable k EF+PO overall and per-round PROP[1,1] (PROP1 for only goods/chores) Thm. 16

n = 2 k > 2 EF+PO overall and per-round EF1 Prop. 10 n = 2 k = 2 EF+PO overall and per-round EF1 Cor. 12 n = 2 even EF+PO overall and per-round weak EF1 Cor. 14 n = 2 even EF overall and per-round EF1 Thm. 15

Table 1: Overview of our results regarding envy-freeness (EF), envy-freeness up to one item (EF1), weak EF1, proportionality (PROP), and Pareto-optimality (PO). Crossed-out results cannot be guaranteed under the stated conditions. We write k n N to denote that the number of rounds is a (ﬁxed) multiple of n. The main positive results are highlighted with .

A classical notion of fairness is that of envy-freeness: an allocation is envy-free if no agent ﬁnds that the bundle given to someone else is better than the one they received.

Deﬁnition 1 (EF). For agents N, items I, and proﬁle u, allocation π is envy-free (EF) if for any i, j N, ui(πi) ui(πj).

It is easy to see that this notion is too strong and cannot always be achieved (consider the case of one objective good and two agents desiring it). Thus, it has then been relaxed to envy-freeness up to one item, which has been further generalized to take into account both goods and chores.

Deﬁnition 2 (EF1). For agents N, items I, and proﬁle u, an allocation π is envy-free up to one item (EF1) if for any i, j N, either π is envy-free, or there is o πi πj such that ui(πi \ {o}) ui(πj \ {o}).

Yet another concept is that of proportionality of an allocation, where each agent receives their due share of utility.

Deﬁnition 3 (PROP). For agents N, items I, and proﬁle u, an allocation π satisﬁes proportionality if for each agent i N we have ui(πi) ui(I)/n.

Note that envy-freeness implies proportionality when assuming additive utilities see, e.g., Aziz et al. (2022, Prop. 1). Finally, in a similar spirit to EF1, we can weaken proportionality to the notion of proportionality up to one item (PROP1) as well as its relaxed version (PROP[1,1]), to guarantee that agents receive a share of utility close to their proportional fair share. The notion of PROP1 has been proposed by Conitzer, Freeman, and Shah (2017) and later extended to the mixed setting by Aziz et al. (2022).

Deﬁnition 4. An allocation π is said to satisfy

PROP1 if for each i N, ui((πi \X) Y ) ui(I)/n for some X πi and Y I \ πi with |X Y | 1. PROP[1,1] if for each i N, ui((πi \X) Y ) ui(I)/n for some X πi and Y I \ πi with |X|, |Y | 1.

We note that PROP1 and PROP[1,1] coincide with each other when all items have non-negative values, since removing an item from an envious agent s bundle does not increase

his or her utility. The same relation holds when all items have non-positive values. Note that Shoshan, Hazon, and Segal-Halevi (2023) recently introduced EF[1,1], which is an analogous version of our PROP[1,1] for envy-freeness.

Efﬁciency. Alongside fairness, it is often desirable to distribute the items as efﬁciently as possible. One way to capture efﬁciency is via the notion of Pareto-optimality, meaning that no improvement to the current allocation can be made without hurting some agent.

Deﬁnition 5 (PO). For agents N, items I, and proﬁle u, an allocation π is Pareto-optimal (PO) if there is no other allocation ρ such that for all i N, ui(ρi) ui(πi) and for some j N it holds that uj(ρj) > uj(πj). If such a ρ exists, we say that it Pareto-dominates π.

Repeated setting. In our paper, we will be interested in repeated allocations of the items to the agents, i.e., sequences of allocations. We denote by π(k) = (π1, π2, . . . , πk) the repeated allocation of the m items in I to the n agents in N over k time periods (or rounds). More formally, we will consider k copies of the set I, such that I1 = {o1 1, . . . , o1 m}, . . . , Ik = {ok 1, . . . , ok m}. Then, each πℓcorresponds to an allocation of the items in Iℓto the agents in N. For all agents i N, all items o I and all ℓ [k], we let the utility be unchanged: i.e., ui(o) = ui(oℓ). When clear from context, we will drop the superscript ℓfrom the items. As a ﬁrst approach, we will assess fairness over time by considering the global set of items that each agent has received across the k rounds. We denote by π k the allocation of k m (copies of the) items to the n agents, where π k i = π1 i πk i for each i N. Namely, we consider the allocation π k where each agent gets the bundle of (the copies of) items that they have received across all the k time periods in π(k). We say that a sequence of allocations π(k) for some k satisﬁes an axiom overall, if π k satisﬁes it (when clear from context, we omit the term overall ). Similarly, we say that π(k) Pareto-dominates ρ(k) overall if π k

Pareto-dominates ρ k, and that π(k) is Pareto-optimal overall if no ρ(k) dominates it. Since envy-freeness implies proportionality, we get:

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Proposition 1. For additive utilities, if π(k) is envy-free overall, then it is proportional overall. As a second approach, we will assess fairness over time by checking whether each repetition satisﬁes some desirable property. For an axiom A, we say that a sequence of allocations π(k) (for some k) satisﬁes per-round A, if for every j [k], the allocation πj satisﬁes the axiom. For example, an allocation π(k) = (π1, . . . , πk) is per-round EF1 if every allocation πj for all j [k] is EF1.

Proposition 2. If π(k) is Pareto-optimal overall, then it is per-round Pareto-optimal. The converse direction does not hold, namely, per-round Pareto-optimality may not imply overall Pareto-optimality, as the following example shows. Example 1. Consider a utility proﬁle over two agents and two items where u1(o1) = 4, u1(o2) = 5, u2(o1) = 3 and u2(o2) = 9. Now consider a four-round allocation where agent 1 gets both items in the ﬁrst and second round, and agent 2 gets both items in the remaining two rounds. It is easy to verify that such an allocation sequence is per-round PO. However, it is not PO overall. Indeed, this gives utilities 18 for agent 1 and 24 for agent 2. Instead, an allocation sequence where agent 1 always gets o1 and gets o2 once (thus, agent 2 takes o2 thrice and no item in one round) yields utilities 21 to agent 1 and 27 to agent 2. Observe that we could obtain a similar example where all items are chores by just multiplying all utilities by 1. On the other hand, for envy-freeness and proportionality, we get the following.

Proposition 3. For additive utilities, if π(k) is per-round envy-free (resp. proportional), then it is envy-free (resp. proportional) overall. We can see that the converse does not necessarily hold. Indeed, consider a two-agent, two-round scenario with one objective good, where we give the good to one agent in the ﬁrst round, and to the other agent in the second round. This is envy-free (resp. proportional) overall, but not per-round. Finally, note that our overall results would also hold in the framework of one-shot allocations with k clones of each item. However, the latter model cannot capture the perround results. Thus, our model cannot be reduced to the standard fair division setting with cloned items.

3 The Case of n Agents In this section, we study the possibility of ﬁnding fair and efﬁcient sequences of allocations for the general case of any number of agents. We start by looking at envy-freeness. First of all, observe that, whenever k is a multiple of n, then we can always guarantee an EF allocation. Proposition 4. If k n N, there exists a sequence π(k) which satisﬁes envy-freeness overall.

Proof. Start from an arbitrary initial allocation. Then, let each agent give their current bundle to the next agent in the next allocation (agent n gives theirs to agent 1). As each

agent i receives each bundle exactly k/n times, allocation π k is envy-free. Thus, π(k) is envy-free overall.

Note that this is not always possible if k is not a multiple of n, irrespective of m. Proposition 5. For every n 2, every k N \ n N and every m N, an allocation that is proportional overall is not guaranteed to exist, even if the items are all goods or all chores. Intuitively, in a proﬁle where every agent has utility 1 for every item, except for a desirable item o for which all agents have high utility k(n 1)(m 1) + 1, there must be some agent i receiving o less times than k/n (as k is not divisible by n). If we also require Pareto-optimality, we get the following. Theorem 6. For all n > 2 and k N, there exist a set of items I and a proﬁle u such that no allocation is envyfree and Pareto-optimal overall. The set I can be chosen to contain only two objective chores.

Proof (sketch). First, observe that, by Propositions 1 and 5, if k is not a multiple of n, we are done. Now let k be a multiple of n. Consider a proﬁle with a small chore s and a big chore b, such that every agent i N has ui(s) = 1, while un(b) = k/n and uj(b) = k for every j N \{n}. One can show that in every overall EF sequence of allocations, all agents must receive s and b the same amount of times (namely k/n times). However, any such allocation always has a Pareto-improvement. Indeed, suppose that agent 1 gives one of her allocations of b to agent n and agent n gives back to agent 1 all of her allocations of s. Then, agent 1 will be happier (she increased her utility by k k/n), and all other agents will be equally happy (for i {2, . . . , n 1} nothing changes, while n gains k/n but also loses k/n). However, agent 2, e.g., now envies agent 1.

In light of Theorem 6, envy-freeness seems too strong of a requirement, even in the repeated setting. However, we can at least always ﬁnd a proportional and Pareto-optimal sequence of allocations. Theorem 7. For every n 2 and k n N, an allocation sequence that is proportional and Pareto-optimal overall always exists, and can be computed in time O(nmk m).

Proof. Consider any proportional sequence of allocations π(k) (which must exist, by Propositions 1 and 4). Clearly, any Pareto-improvement over π(k) must also be proportional. We get the following algorithm:

1. Initialize a variable r as π(k), as deﬁned previously. 2. Iterate over all possible k-round allocations ρ(k), and do: if ρ(k) Pareto-dominates r, set r to ρ(k). 3. Return r.

This algorithm runs in O(nmk m). Indeed, every iteration at Step 2 of the algorithm requires time O(m), as we just need to sum up the utilities for the items received by each agent to compare the total utilities of r and ρ(k). Furthermore, there are nmk possible allocations, as for any round

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

j [k] and every object o I, we could assign object o in round j to n different agents. It remains to be shown that the algorithm is correct. Let us call η(k) the allocation in r returned by the algorithm. As argued above, η(k) must be proportional overall, since it is either equal to π(k) or a Pareto-improvement of it. Thus, suppose toward a contradiction that η(k) is not PO. Then, there must be some Pareto-optimal ρ(k) dominating η(k) that is encountered before η(k) in the iteration since, if it is encountered after, the variable r would be updated to ρ(k). But since Pareto-dominance is transitive, we know that ρ(k) Pareto-dominates all the allocations corresponding to the values that the variable r took before being updated to η(k), and hence r is updated to ρ(k) during iteration. However, this means that r cannot be updated to η(k), as ρ(k) dominates it: a contradiction. This concludes the proof.

Note that the existence guarantee in Theorem 7 is tight because of Proposition 5. Moreover, we can deﬁne an integer linear program (ILP) to compute such a proportional and PO allocation (Figure 1). Based on this, in the full version (Igarashi et al. 2023), we present some ﬁxed-parameter tractability results.

o I ui(o) xi o

subject to: xi o {0, . . . , k} for o I, i N X

i N xi o = k for o I

o I ui(o) xi o k/n ui(I) for i N

Figure 1: An ILP for ﬁnding a proportional and PO allocation sequence for n agents. In this ILP, we maximize the social welfare and thus guarantee PO. Variable xi o indicates how often agent i receives item o. If k / n N, this ILP may be unsatisﬁable due to Proposition 5.

4 The Case of Two Agents In this section, we consider the case of repeated fair division among two agents. Several authors have focused on this special but important case (see, e.g., the papers by Brams, Kilgour, and Klamler (2012), Brams, Kilgour, and Klamler (2014), Kilgour and Vetschera (2018), Aziz et al. (2022), Shoshan, Hazon, and Segal-Halevi (2023), and the references therein). This captures some practically relevant problems, for example, house chore division among couples (Igarashi and Yokoyama 2023), or divorce settlements (Brams and Taylor 1996). A ﬁrst intuitive idea for the repeated setting could be to apply twice the Generalized Adjusted Winner algorithm introduced by Aziz et al. (2022), as in the one-shot setting it returns efﬁciently a PO and EF1 allocation of the goods

and chores, by alternating the roles of the winner and the loser. However, this approach may fail (see the full version (Igarashi et al. 2023)). Despite this, we will show that, whenever the number of rounds is even, we can still always ﬁnd an allocation that is PO and EF overall. However, we lose the guarantee of an efﬁcient computation. First, we need the following fact:

Proposition 8. If n = 2, for additive utilities, proportionality implies envy-freeness.

Now, we can show the following.

Theorem 9. If n = 2 and k 2N, an allocation sequence that is envy-free and Pareto-optimal overall always exists, and can be computed in time O(m (k + 1)m).

Proof. From the algorithm in the proof of Theorem 7 and from Proposition 8 we get an envy-free and Pareto-optimal allocation. Since n = 2, there are (k + 1)m possible allocations (up to symmetry-breaking), as each agent receives each of the m items either 0, 1, . .., or k times. Thus, we obtain a run time of O(m (k + 1)m).

Theorem 9 provides strong overall fairness and efﬁciency guarantees, but it does not ensure per-round fairness. Indeed, an envy-free and PO allocation that is per-round EF1 may not exist, even if all items are goods or chores.

Proposition 10. If n = 2 and k > 2, an allocation that is per-round EF1, Pareto-optimal overall, and envy-free is not guaranteed to exist, even when all items are goods or chores.

Proof (sketch). First, observe that the number of rounds k needs to be even (Proposition 5). Next, consider the following utility proﬁle over two items, where u1(o1) = u2(o1) = 1, u1(o2) = 3 and u2(o2) = 2. One can show that, for k > 2, in any per-round EF1 and overall EF allocation sequence, both agents should receive each item k/2 times. However, any such allocation is dominated by the sequence where agent 1 gets only o1 exactly k/2 2 times, only o2 exactly k/2 + 1 times, and no items once.

Nevertheless, for two agents and two rounds, i.e., n = k = 2, it is always possible to achieve PO and EF as well as per-round EF1. Indeed, in this case, we can always transform an allocation that is PO and EF overall (which is guaranteed to exist for two agents) to an allocation that is per-round EF1 while preserving the PO and EF guarantees. A similar idea (i.e., exchanging items among two agents while preserving some initial property) was also used by Shoshan, Hazon, and Segal-Halevi (2023).

Theorem 11. Suppose k = n = 2. Given an allocation sequence that is Pareto-optimal and envy-free, an allocation sequence which is Pareto-optimal, envy-free, and per-round EF1 can be computed in polynomial time.

Proof (sketch). Consider an overall PO and EF allocation sequence π(2) for two agents. Let I1 = π1 1 π2 1 (and similarly for I2) be the items assigned to agent 1 (resp. 2) in both rounds. Moreover, let O = I \ (I1 I2) be the items that each agent receives once. Observe that, by PO, we can assume that every subjective item o is always assigned to

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

the agent i {1, 2} for whom ui(o) > uj(o) (where j is the other agent). Furthermore, we can remove objective null items from consideration. Hence, all items in O are objective goods or chores. Let O+ O be the objective goods in O, and let O O be the objective chores in O. Clearly, O+ O = . Update the allocation π(2) such that π1 1 = I1 O , π1 2 = I2 O+, π2 1 = I1 O+ and π2 2 = I2 O . We then reﬁne this sequence via the following procedure:

1. For each o in O, do the following: (a) If π(2) is per-round EF1, break the loop. (b) Else, transfer item o as follows: if o is an objective chore, remove o from π1 1 and π2 2, and add it to π1 2 and π2 1; if o is an objective good, remove o from π1 2 and π2 1, and add it to π1 1 and π2 2. 2. Return π(2).

O o π2 1 π2 2

Figure 2: Exchanges of goods and chores between agents in Step 1(b) of the algorithm.

In other words, we start by assigning all chores in O to agent 1 in the ﬁrst round (and to agent 2 in the second round), and conversely for the goods. Then, we progressively move the chores from agent 1 to agent 2 in the ﬁrst round, and vice versa in the second round, and conversely for the goods. We stop when the overall allocation is per-round EF1. This runs in polynomial time: it remains to show that it is correct. First, observe that during the execution of the algorithm, π(2) remains an allocation that is PO and EF overall, since we never change the total amount of times an agent receives an item w.r.t. the initial allocation. Thus, if the initial allocation is per-round EF1, we are done. We assume in the following that the initial allocation is not per-round EF1, which implies that at least one agent envies another in some round. By overall EF, 2u1(I1) + u1(O) 2u1(I2) + u1(O), which implies u1(I1) u1(I2). Similarly, we can show u2(I2) u2(I1). This implies u1(I1 O+) u1(I2 O ) and u2(I2 O+) u2(I1 O ) since all items in O+ are objective goods and all items in O are objective chores. Since u1(I1 O+) u1(I2 O ), if the algorithm moves all the objective chores in O from agent 1 to agent 2 and all the objective goods in O+ from agent 2 to agent 1 in the ﬁrst round, then agent 1 does not envy agent 2 with respect to the ﬁrst round. Moreover, her utility in the ﬁrst round never decreases, so that once agent 1 becomes envy-free in the ﬁrst round, she remains envy-free in the latter steps. Similarly, if the algorithm moves all the objective chores in O from agent 2 to agent 1 and all the objective goods in O+ from agent 1 to agent 2 in the second round, agent 2 does not

envy agent 1 with respect to the second round. In addition, once agent 2 becomes envy-free with respect to the second round, she remains envy-free in the latter steps. Thus, there exists an item o such that after transferring o, agent 1 does not envy agent 2 in the ﬁrst round, and agent 2 does not envy agent 1 in the second round. Let o be the ﬁrst such item. By a case-analysis, one can show that at least one of the two allocations (produced by the algorithm) obtained before and after transferring o is per-round EF1. Thus, the algorithm correctly ﬁnds a desired allocation.

Combining the above with Theorem 9, we obtain the following corollary. Corollary 12. If k = n = 2, then an allocation which is Pareto-optimal, envy-free, and per-round EF1 always exists. Moreover, it can be computed in time O(m 3m). As we have seen in Proposition 10, we cannot guarantee per-round EF1 together with PO and EF overall for a more general number of rounds k 2N with k > 2. Nevertheless, these properties become compatible if we relax a perround fairness requirement to the following (weaker) version of EF1, where the envy of i toward j can be eliminated by either giving a good of j to i, or imposing a chore of i on j. Deﬁnition 6 (Weak EF1). An allocation π is weak EF1 if for all i, j N, either ui(πi) ui(πj) or there is an item o πi πj such that ui(πi {o}) ui(πj \ {o}) or ui(πi \ {o}) ui(πj {o}). Again, to prove the following theorem, we show that it is always possible to transform an allocation that is PO and EF overall to an allocation that is per-round weak EF1 while preserving the PO and EF guarantees. Theorem 13. Suppose n = 2. Given a k-round allocation that is Pareto-optimal and envy-free, an allocation which is Pareto-optimal, envy-free, and per-round weak EF1 can be computed in polynomial time. Corollary 14. If n = 2 and k 2N, then an allocation which is Pareto-optimal, envy-free, and per-round weak EF1 always exists, and can be computed in time O(m (k+1)m). In order to obtain Corollary 14, it sufﬁces to prove Theorem 13, since we can apply Theorem 9 to get an allocation sequence π(k) that is PO and envy-free overall when k 2N. To do so, suppose that we are given a PO and EF k-round allocation. Looking into each individual round, there may be an allocation πℓthat is not fair. Similarly to the proof of Theorem 11, we thus repeatedly transfer an item between envious rounds and envy-free rounds while preserving the property that the overall allocation π(k) is PO and EF over the course of the algorithm. We can show that this process terminates in polynomial time and eventually yields a perround weak EF1 allocation. A formal description of our algorithm is presented in the full version (Igarashi et al. 2023). Finally, we show that, if we do not require PO, an allocation that is EF and per-round EF1 can always be found (when k is even) in polynomial time. Theorem 15. If n = 2 and k 2N, then an allocation which is envy-free overall and per-round EF1 always exists, and can be computed in polynomial time.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

We do not know whether EF and per-round EF1 can be simultaneously achieved for n > 2 agents and k n N rounds (EF overall is possible in this case by Proposition 4). We leave it as an interesting open problem for future work.

5 Variable Number of Rounds In the previous sections, we have assumed that k (the number of rounds) is predetermined. In this section, we study the case when k can be variable. We have seen that, whenever k is ﬁxed, overall EF and PO become incompatible in general (Theorem 6). This raises the question of whether this is possible if k is not predetermined. More precisely, we ask the following: given a utility proﬁle, is there a number k of rounds for which there is a sequence of allocations π(k) that satisﬁes desirable overall and perround guarantees? We answer this question afﬁrmatively.

Theorem 16. If for all i N and o I we have ui(o) Q, then there exists k N and a π(k) such that π(k) is envy-free, Pareto-optimal, and per-round PROP[1,1].

Recall that PROP[1,1] and PROP1 coincide for the case of non-negative value items and for the case of non-positive value items; thus, in such cases, the above theorem holds with a per-round guarantee of PROP1. To show Theorem 16, we establish a connection between our setting and the divisible (Bogomolnaia et al. 2017) and probabilistic settings (Aziz et al. 2023; Budish et al. 2013). More precisely, we utilize a proof technique similar to that of Aziz et al. (2023), who used a decomposition lemma by Budish et al. (2013) for divisible item allocations to construct a randomized allocation that satisﬁes desirable efﬁciency and fairness notions when all items are goods. We prove that there exists a randomized allocation satisfying similar desirable guarantees for the mixed case of goods and chores and translate it into our repeated setting. Before we proceed, we provide some preliminary deﬁnitions. Consider a set of n agents N = [n] and of items I. A randomized allocation is a set of ordered pairs (pt, πt)t [h], such that for every t [h], πt is an allocation implemented with probability pt [0, 1], where P t [h] pt = 1; the allocations π1, π2, . . . , πh are referred to as the support of a randomized allocation. Given a randomized allocation (pt, πt)t [h] with pt Q for each t [h], we deﬁne its repeated translation as follows. Since all pt are rational numbers, there exists a k N such that, for all t [h], pt = ℓt/k (for some ℓt N). In other words, all fractions deﬁned by (pt)t [h] are expressed in terms of the same denominator, k. The repeated translation of (pt, πt)t [h] is the allocation sequence π(k) of form:

π(k) = (π1, . . . , π1 | {z } ℓ1 times

, π2, . . . , π2 | {z } ℓ2 times

, . . . , πh, . . . , πh | {z } ℓh times

In other words, for each t [h], πt appears exactly ℓt times (where pt = ℓt/k). We can now prove the theorem.

Proof (sketch) of Theorem 16. A fractional allocation is a vector x = (x1, . . . , xn) where each xi = (xi,o)o I Qm +

and, for all o I, P i N xi,o = 1. Given a utility vector u, the utility of agent i for allocation x is deﬁned as ui(xi) = P o I xi,oui(o). The notions of envy-freeness and Pareto-optimality (w.r.t. all other fractional allocations) naturally translate to this setting. Next, a randomized allocation (pt, πt)t [h] is said to implement a fractional allocation x if

t=1 pt1[o πt i] for each i N and o I.

Here, 1[o πt i] is an indicator function which takes value 1 if o πh i , and 0 otherwise. When all agents utilities are rational-valued, a PO and EF fractional allocation always exists (Bogomolnaia et al. 2017; Chaudhury et al. 2022). Moreover, using the decomposition lemma of Budish et al. (2013), we can show that any PO and EF fractional allocation x admits a randomized allocation (pt, πt)t [h] that implements x with these properties:

1. p1, p2, . . . , ph Q+, 2. πt i {o I | xi,o > 0} for each i N and t [h], and 3. πt is PROP[1,1] for each t [h].

See the full version (Igarashi et al. 2023) for details. Finally, one can show that the repeated translation of (pt, πt)t [h] is PO and EF overall. Moreover, since πt is PROP[1,1] for all t [h], this translation is per-round PROP[1,1].

Note that due to Theorem 6, we know that this result is impossible for a ﬁxed number of rounds, and thus highlights the difference between ﬁxed and variable k.

6 Conclusion We have seen that in our model of repeated allocations the (necessary) trade-off between fairness and efﬁciency is much more favorable than in the standard setting without repetitions. In the case of two agents, we presented some algorithms guaranteeing overall envy-freeness and Paretooptimality (as well as per-round approximate envy-freeness) for any even number of rounds. As some of our algorithms require exponential time, it would be of interest to study the computational complexity of related decision problems, investigating whether and where polynomial-time results are obtainable. Our n-agent algorithm yields slightly weaker guarantees (proportionality and Pareto-optimality), which are still an improvement over the one-shot setting. It remains for future work to determine whether this result can be strengthened by additional per-round guarantees, as for the 2-agent case. When the number of rounds k can be chosen freely, we have shown that (for any number of agents) an envy-free, Pareto-optimal and per-round PROP[1,1] allocation always exists. We have done so by establishing a connection between our setting and the probabilistic and divisible settings. However, our approach gives no guarantee on the number of rounds it requires. As future work, it would be interesting to investigate the complexity of ﬁnding the smallest k for which an envy-free and Pareto-optimal allocation exists.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgments This paper developed from ideas discussed at the Dagstuhl Seminar 22271 Algorithms for Participatory Democracy. Martin Lackner was supported by the Austrian Science Fund (FWF): P31890. Oliviero Nardi was supported by the European Union s Horizon 2020 research and innovation programme under grant agreement number 101034440, and by the Vienna Science and Technology Fund (WWTF) through project ICT19-065. Ayumi Igarashi was supported by JST PRESTO under grant number JPMJPR20C1.

References Aleksandrov, M.; and Walsh, T. 2020. Online Fair Division: A Survey. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI-2020), 13557 13562. Amanatidis, G.; Aziz, H.; Birmpas, G.; Filos-Ratsikas, A.; Li, B.; Moulin, H.; Voudouris, A. A.; and Wu, X. 2022. Fair Division of Indivisible Goods: Recent Progress and Open Questions. ar Xiv:2208.08782. Aziz, H.; Caragiannis, I.; Igarashi, A.; and Walsh, T. 2022. Fair Allocation of Indivisible Goods and Chores. Autonomous Agents and Multi-Agent Systems, 36(1): 1 21. Aziz, H.; Freeman, R.; Shah, N.; and Vaish, R. 2023. Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation. Operations Research. Published online in Articles in Advance. Balan, G.; Richards, D.; and Luke, S. 2011. Long-Term Fairness with Bounded Worst-Case Losses. Autonomous Agents and Multi-Agent Systems, 22(1): 43 63. Benade, G.; Kazachkov, A. M.; Procaccia, A. D.; and Psomas, C.-A. 2018. How to Make Envy Vanish Over Time. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC-2018), 593 610. Bogomolnaia, A.; Moulin, H.; Sandomirskyi, F.; and Yanovskaya, E. 2017. Competitive Division of a Mixed Manna. Econometrica, 85(6): 1847 1871. Brams, S. J.; and Fishburn, P. C. 2000. Fair Division of Indivisible Items Between Two People with Identical Preferences: Envy-Freeness, Pareto-Optimality, and Equity. Social Choice and Welfare, 17(2): 247 267. Brams, S. J.; Kilgour, D. M.; and Klamler, C. 2012. The Undercut Procedure: An Algorithm for the Envy-Free Division of Indivisible Items. Social Choice and Welfare, 39: 615 631. Brams, S. J.; Kilgour, M.; and Klamler, C. 2014. Two Person Fair Division of Indivisible Items: An Efﬁcient, Envy-Free Algorithm. Notices of the AMS, 61(2): 130 141. Brams, S. J.; and Taylor, A. D. 1996. A Procedure for Divorce Settlements. Mediation Quarterly, 13(3): 191 205. Budish, E.; Che, Y.-K.; Kojima, F.; and Milgrom, P. 2013. Designing Random Allocation Mechanisms: Theory and Applications. American Economic Review, 103(2): 585 623. Caragiannis, I.; and Narang, S. 2022. Repeatedly Matching Items to Agents Fairly and Efﬁciently. ar Xiv:2207.01589.

Cavallo, R. 2008. Efﬁciency and Redistribution in Dynamic Mechanism Design. In Proceedings of the 9th ACM Conference on Electronic Commerce, 220 229. Chaudhury, B. R.; Garg, J.; Mc Glaughlin, P.; and Mehta, R. 2022. A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna. Mathematics of Operations Research. Published online in Articles in Advance. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC-2017), 629 646. Freeman, R.; Zahedi, S. M.; and Conitzer, V. 2017. Fair Social Choice in Dynamic Settings. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI-2017), 4580 4587. Freeman, R.; Zahedi, S. M.; Conitzer, V.; and Lee, B. C. 2018. Dynamic Proportional Sharing: A Game-Theoretic Approach. In Proceedings of the ACM on Measurement and Analysis of Computing Systems (MACS-2018). Gollapudi, S.; Kollias, K.; and Plaut, B. 2020. Almost Envy Free Repeated Matching in Two-Sided Markets. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7 11, 2020, Proceedings, 3 16. Guo, M.; Conitzer, V.; and Reeves, D. M. 2009. Competitive Repeated Allocation without Payments. In International Workshop on Internet and Network Economics, 244 255. Hosseini, H.; Larson, K.; and Cohen, R. 2015. Matching with Dynamic Ordinal Preferences. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI2015). Igarashi, A.; Lackner, M.; Nardi, O.; and Novaro, A. 2023. Repeated Fair Allocation of Indivisble Items. ar Xiv:2304.01644. Igarashi, A.; and Yokoyama, T. 2023. Kajibuntan: A House Chore Division App. In Proceedings of the 37th AAAI Conference on Artiﬁcial Intelligence (AAAI-2023), 16449 16451. Kash, I.; Procaccia, A. D.; and Shah, N. 2014. No Agent Left Behind: Dynamic Fair Division of Multiple Resources. Journal of Artiﬁcial Intelligence Research, 51: 579 603. Kilgour, D. M.; and Vetschera, R. 2018. Two-Player Fair Division of Indivisible Items: Comparison of Algorithms. European Journal of Operational Research, 271(2): 620 631. Kohler, T.; Stegh ofer, J.-P.; Busquets, D.; and Pitt, J. 2014. The Value of Fairness: Trade-offs in Repeated Dynamic Resource Allocation. In 2014 IEEE Eighth International Conference on Self-Adaptive and Self-Organizing Systems (SASO-2014), 1 10. Lackner, M. 2020. Perpetual Voting: Fairness in Long-Term Decision Making. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI-2020), 2103 2110. Lackner, M.; Maly, J.; and Rey, S. 2021. Fairness in Long-Term Participatory Budgeting. In Proceedings of the 30th International Joint Conference on Artiﬁcial Intelligence (IJCAI-2021), 299 305.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Meir, R.; Lang, J.; Lesca, J.; Mattei, N.; and Kaminsky, N. 2021. A Market-Inspired Bidding Scheme for Peer Review Paper Assignment. In Proceedings of the 35th AAAI Conference on Artiﬁcial Intelligence (AAAI-2021), 4776 4784. Othman, A.; Sandholm, T.; and Budish, E. 2010. Finding Approximate Competitive Equilibria: Efﬁcient and Fair Course Allocation. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010), 873 880. Payan, J.; and Zick, Y. 2022. I Will Have Order! Optimizing Orders for Fair Reviewer Assignment. In Proceedings of the 31st International Joint Conference on Artiﬁcial Intelligence (IJCAI-2022), 440 446. Shoshan, H.; Hazon, N.; and Segal-Halevi, E. 2023. Efﬁcient Nearly-Fair Division with Capacity Constraints. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2023), 206 214. Zeng, D.; and Psomas, A. 2020. Fairness-Efﬁciency Tradeoffs in Dynamic Fair Division. In Proceedings of the 2020 ACM Conference on Economics and Computation (EC2020), 911 912.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)