Competitive Analysis for Online Fair Division under Multiple Fairness Notions
(Extended Abstract)
January 01, 1970
We study the online fair division of indivisible items with additive utilities, where items arrive sequentially and must be irrevocably allocated upon arrival. Considering various fairness notions, we focus on designing online algorithms that produce fair or approximately fair allocations for any instance. We measure algorithm performance using the competitive ratio, defined as the worst-case ratio between the fairness guarantee achieved by the online algorithm and that of an optimal offline allocation with full knowledge of future arrivals. We examine a broad spectrum of models, including the allocation of goods or chores, normalized versus non-normalized utilities, and identical versus general utility functions. We address the majority of the unresolved cases by providing online algorithms or proving the limits of the competitive ratio achievable by online algorithms. In most cases, the algorithms are shown to be optimal.
Keywords: Fair division, Online algorithms, Competitive ratio, Scheduling
Fair division studies how to allocate a set of \(m\) indivisible items among \(n\) agents in a fair manner. Each agent is endowed with a utility function over subsets of items, and they all wish for the allocation to be relatively fair. A wide range of fairness notions has been proposed to evaluate allocations, including envy-freeness (EF) [1], proportionality (PROP) [2], and maximin share (MMS) [3], as well as their relaxations, such as EF1 [4], EFX [5], PROP1 [6], and PROPX [7], among others.
Exact fairness guarantees are often unattainable with indivisible items, even for relaxations of classical fairness notions. As a result, researchers have shifted their focus toward approximate fair division and established metrics quantifying the closeness to exact fairness [8].
While the majority of existing literature addresses fair division in the offline setting, where all items are known in advance, many real-world applications involve items arriving sequentially and requiring immediate, irrevocable allocation decisions. This motivates the study of online fair division, which has been actively investigated in recent years [9]–[11].
Our Contribution In this paper, we study online fair division of indivisible items with additive utilities. Items arrive one by one. When allocating an item, only the utilities of the arrived items for all agents are known, while the utilities of future items are unknown. Depending on the nature of the items, we distinguish between goods, which yield positive utilities (values), and chores, which incur negative utilities (costs). We further consider both identical utilities, where all agents share the same utility function, and general utilities, where agents may have heterogeneous preferences. To better understand the role of information in online fair division, we consider the normalized setting, in which the total utility of all items is known in advance. If the total utility is not known a priori, the setting is referred to as non-normalized.
We design online algorithms to allocate items and measure their performance via the competitive ratio, defined as the worst-case multiplicative gap between the fairness guarantee achieved by the online algorithm and that of an optimal offline allocation with full knowledge of future arrivals. This differs from some prior work on online fair division (e.g., [9], [10]), which evaluates fairness guarantees without normalizing by the optimal offline benchmark.
To provide a more in-depth analysis of the properties of online fair division and their connections to other problems, we establish several structural properties of the problem, focusing on settings with identical utility functions or two agents. In particular, we clarify the connection between fair division and parallel machine scheduling, formalize the relationship between goods and chores allocation, and derive links between different fairness notions such as EF and PROP. These results provide a unifying perspective and serve as a foundation for our subsequent analysis.
Our main results are summarized in the following two tables, Table [tab:goods95results] and Table [tab:chores95results]. For goods allocation, we design online algorithms and derive tight competitive ratio bounds under various fairness notions, achieving optimal guarantees in all considered cases, with the exception of PROP1 under general utilities which remains largely unexplored. For chores allocation, we obtain competitive ratio bounds that are optimal in most cases. Compared to the goods setting, chores exhibit both similarities and notable differences across fairness notions. For instance, under EF, EF1, and EFX, the competitive ratios in goods and chores allocation are closely related and often reciprocal. On the other hand, chores can be strictly easier in certain cases. Under identical utilities, PROPX can be achieved for any number of agents \(n\) in the normalized setting, whereas in the goods allocation this is only possible when \(n=2\). At the same time, several cases for chores remain open or not fully resolved, particularly under general utilities and for fairness notions such as PROP and PROPX.
|l|c|c|cc|cc| & &
& & & &
& & & & \(n\geq 3\) & & \(n\geq 3\)
EF & \(\frac{1}{n+1}^{(*)}\) & \(0^{(*)}\) & & & \(0^{(*)}\)
EFX & \(0^{\text{\cite{NPT25}}}\) & \(0^{\text{\cite{NPT25}}}\) & & \(0^{\text{\cite{NPT25,MP25}}}\) &
EF1 & \(1^{\text{\cite{ELL25}}}\) & \(0^{\text{\cite{NPT25}}}\) & & & \(0^{\text{\cite{NPT25}}}\)
PROP & \(\frac{1}{n}^{\text{\cite{Woeginger97}}}\) & \(0^{(*)}\) & & \(\frac{1}{n-1}^{\text{\cite{TW07}}}\) & & \(0^{(*)}\)
PROPX & \(0^{(*)}\) & \(0^{(*)}\) & & \(0^{(*)}\) &
PROP1 & \(1^{\text{\cite{ELL25}}}\) & \(<1 ^{\text{\cite{BKP18}}}\) & &
MMS & \(\frac{1}{n}^{\text{\cite{Woeginger97}}}\) & \(0^{\text{\cite{ZBW23}}}\) & & \(\frac{1}{n-1}^{\text{\cite{TW07}}}\) & & \(0^{\text{\cite{ZBW23}}}\)
|l|c|c|cc|cc| & &
& & & &
& & & & \(n\geq 3\) & & \(n\geq 3\)
EF & \(n+1^{(*)}\) & \(\infty^{(*)}\) & & & \(\infty^{(*)}\)
EFX & \(\infty^{(\ref{thm:goods-chores-reciprocal}), \;\text{\cite{NPT25}}}\) & \(\infty^{(*)}\) & & \(\infty^{(\ref{thm:goods-chores-reciprocal}),
\;\text{\cite{NPT25,MP25}}}\) &
EF1 & \(1^{(\ref{thm:goods-chores-reciprocal}), \;\text{\cite{ELL25}}}\) & \(\infty^{(\ref{thm:chores_online_general_ef}, \;\ref{thm:chores_semi-online_general_ef1_ngeq3})}\) &
& & \(\infty^{(*)}\)
PROP & \([1.85358^{\text{\cite{GRT00}}}, 1.9201^{\text{\cite{FW00}}}]\) & \(n^{(*)}\) & & \(1.585^{\text{\cite{AH12,KKG15}}}\) & &
\([2,n]^{(*)}\)
PROPX & \(n^{(*)}\) & \(n^{(*)}\) & &
PROP1 & \(1^{(\ref{thm:goods-chores-reciprocal}), \;\text{\cite{ELL25}}}\) & \(>1 ^{\text{\cite{BKP18}}}\) & &
MMS & \([1.85358^{\text{\cite{GRT00}}}, 1.9201^{\text{\cite{FW00}}}]\) & \(n^{\text{\cite{STW25}}}\) & & \(1.585^{\text{\cite{AH12,KKG15}}}\)
& & \([1.585^{\text{\cite{AH12}}},2-\frac{1}{n}^{\text{\cite{ZBW23}}} ]\)
Related Works Early work on online fair division primarily focused on qualitative fairness properties or efficiency objectives, rather than on approximating fairness guarantee. Aleksandrov et al. [12] were among the first to study online fair division, proposing a model motivated by food bank allocation that emphasizes axiomatic fairness properties such as envy-freeness and strategy-proofness, together with efficiency measures like competitive ratio and the price of anarchy. Benade et al. [13] considered online fair division with indivisible goods under sequential arrivals and evaluated performance via the maximum envy accumulated over time, designing algorithms with asymptotically vanishing envy. Relatedly, Banerjee et al. [14] studied the online allocation of sequentially arriving \(T\) divisible goods with the social objectives of maxmin and Nash social welfare, respectively, assuming that each agent’s total utility over all goods is predictable. For a broader overview of early work on online fair division, we refer the reader to the survey [15].
A more recent line of work studies online fair division through the lens of approximate fairness guarantees and competitive analysis. This approach was initiated by Zhou et al. [9], who analyzed online fair division with respect to the MMS guarantee. Building on this line of research, Neoh et al. [10] established tight competitive ratios of goods for several fairness notions, including EF1, EFX, and PROP1. In the context of chores, Song et al. [11] derived improved lower bounds for MMS guarantees.
Several recent studies have explored extensions and variations of the aforementioned models. For instance, Choo et al. [16] investigated online goods allocation where the maximum value of any item for each agent is known in advance. They proved that no online algorithm can achieve a strictly positive approximation guarantee with respect to EF1, PROPX, or MMS. In contrast, for PROP1, an algorithm achieving an approximation guarantee of at least \(\frac{1}{n}\) exists. Furthermore, even when the known maximum value is only a prediction, the resulting approximation guarantee can be expressed as a function of the prediction error. They also studied the performance of randomized algorithms under the PROP1 notion. Melissourgos and Protopapa [17] investigated online EFX allocations incorporating predictions of future item values. Wang and Wei [18] addressed the online allocation of goods or chores under personalized bi-valued utilities, which are not necessarily additive. Furthermore, Amanatidis et al. [19] examined online goods allocation with personalized bi-valued utilities, evaluating the approximate fairness guarantee based on the worst value achieved at any point during the sequential allocation process.
Fair division is closely related to scheduling problems, especially under additive and identical utilities. Motivated by this connection, we briefly review relevant results from online and semi-online scheduling.
Online scheduling on parallel machines has been extensively studied, with two fundamental objective functions: minimizing the maximum load and maximizing the minimum load. The former objective, commonly known as minimizing the makespan, was initiated by Graham [20], who designed the famous List Scheduling (LS) algorithm, which is the optimal algorithms for two and three machines [21]. For four or more machines, however, the optimal competitive ratio remains open, despite a long line of work providing progressively improved bounds (e.g., [22]–[25]). The latter objective, maximizing the minimum load, was first studied by [26] and was later shown by [27] to admit an optimal competitive ratio for an arbitrary number of machines.
Beyond the fully online model, a rich line of work studies semi-online scheduling, where limited global information about the instance is revealed in advance. Such models interpolate between offline and online scheduling and help quantify the value of partial information; see the surveys [28], [29]. The online fair allocation problem in the normalized setting studied in this paper is closely related to semi-online scheduling with total processing time is known in advance [30]–[33]. The assumption in [16] that each agent’s maximum item value is known or predictable extends the semi-online scheduling framework where the maximum job processing time is either fully known or bounded within an interval [33]–[35].
We investigate a fair division problem with a set \(M = \{e_1,e_2,\dots,e_m\}\) of \(m\) indivisible items and a set \(N\) of \(n\) agents. Each agent \(i \in N\) has a non-negative additive utility function \(u_i:2^{M}\rightarrow \mathbb{R}_{\geq 0}\), defined by \(u_i(S) = \sum_{e \in S} u_i(\{e\})\) for any subset \(S \subseteq M\). For convenience, we abuse notation and write \(e\) for the singleton set \(\{e\}\). We consider two cases based on whether the utility functions of different agents are identical. In the identical case, all agents share the same utility function, i.e., \(u_i = u_j\) for all \(i,j \in N\). In the general case, agents may have different utility functions. Alternatively, we classify the problem based on whether the total utility for each agent is the same. In the normalized case, \(u_i(M)\) is constant for all \(i \in N\). We assume w.l.o.g. that \(u_i(M) = n\) for all \(i \in N\). In the non-normalized case, the values of \(u_i(M)\) may differ across agents.
We consider two types of items. For goods, \(u_i(e)\) denotes the value of item \(e\) to agent \(i\), and we write \(v_i\) for the valuation function. For chores, \(u_i(e)\) denotes the cost incurred by agent \(i\) for item \(e\), and we write \(c_i\) for the cost function. Under identical utilities, we omit the subscript \(i\).
In the online allocation model, items arrive sequentially. Upon the arrival of each item, it must be irrevocably assigned to one of the agents based only on the information revealed so far. Reallocation of previously assigned items is not allowed. However, for the normalized case, the total utility \(n\) is known in advance and can be regarded as additional information.
An \(n\)-partition of \(M\) is a set of \(n\) bundles \({\cal A} = (A_1, \dots, A_n)\) such that \(\cup_{i=1}^n A_i=M\) and \(A_i\cap A_j =\emptyset\) for \(i\neq j\). The set of all \(n\)-partitions of \(M\) is denoted \(\Pi_n(M)\). An allocation corresponds to a \(n\)-partition \({\cal A} \in \Pi_n(M)\) where agent \(i\) receives bundle \(A_i\). Let \(A_i^j\) denote the bundle held by agent \(i\) after the first \(j\) items have been allocated. In particular, \(A_i^0 = \emptyset\) and \(A_i^m = A_i\).
We now formally define the fairness notions considered in this paper, namely EF, EFX, EF1, PROP, PROPX, PROP1, and MMS, for both goods and chores.
Definition 1 (Envy-freeness). An allocation \({\cal A}\) is called \(\alpha\)-approximate envy-free (\(\alpha\)-EF)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i,j\in N\), \[v_i(A_i)\ge \alpha\, v_i(A_j),\] while for chores, \(\alpha\ge 1\) and for all \(i,j\in N\), \[c_i(A_i)\le \alpha\, c_i(A_j).\] When \(\alpha=1\), the allocation is called EF.*
Definition 2 (Envy-freeness up to Any Item). An allocation \({\cal A}\) is called \(\alpha\)-approximate envy-free up to any item (\(\alpha\)-EFX)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i,j\in N\) and any \(e\in A_j\), \[v_i(A_i)\ge \alpha\, v_i(A_j\setminus e),\] while for chores, \(\alpha\ge 1\) and for all \(i,j\in N\) and any \(e\in A_i\), \[c_i(A_i\setminus e)\le \alpha\, c_i(A_j).\] When \(\alpha=1\), the allocation is called EFX.*
Definition 3 (Envy-freeness up to One Item). An allocation \({\cal A}\) is called \(\alpha\)-approximate envy-free up to one item (\(\alpha\)-EF1)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i,j\in N\), there exists \(e\in A_j\) such that \[v_i(A_i)\ge \alpha\, v_i(A_j\setminus e),\] while for chores, \(\alpha\ge 1\) and for all \(i,j\in N\), there exists \(e\in A_i\) such that \[c_i(A_i\setminus e)\le \alpha\, c_i(A_j).\] When \(\alpha=1\), the allocation is called EF1.*
Definition 4 (Proportionality). An allocation \({\cal A}\) is called \(\alpha\)-approximate proportional (\(\alpha\)-PROP)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i\in N\), \[v_i(A_i)\ge \frac{\alpha}{n}\, v_i(M),\] while for chores, \(\alpha\ge 1\) and for all \(i\in N\), \[c_i(A_i)\le \frac{\alpha}{n}\, c_i(M).\] When \(\alpha=1\), the allocation is called PROP.*
Definition 5 (Proportionality up to Any Item). An allocation \({\cal A}\) is called \(\alpha\)-approximate proportional up to any item (\(\alpha\)-PROPX)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i\in N\) and any \(e\in M\setminus A_i\), \[v_i(A_i\cup e)\ge \frac{\alpha}{n}\, v_i(M),\] while for chores, \(\alpha\ge 1\) and for all \(i\in N\) and any \(e\in A_i\), \[c_i(A_i\setminus e)\le \frac{\alpha}{n}\, c_i(M).\] When \(\alpha=1\), the allocation is called PROPX.*
Definition 6 (Proportionality up to One Item). An allocation \({\cal A}\) is called \(\alpha\)-approximate proportional up to one item (\(\alpha\)-PROP1)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i\in N\), there exists \(e\in M\setminus A_i\) such that \[v_i(A_i\cup e)\ge \frac{\alpha}{n}\, v_i(M),\] while for chores, \(\alpha\ge 1\) and for all \(i\in N\), there exists \(e\in A_i\) such that \[c_i(A_i\setminus e)\le \frac{\alpha}{n}\, c_i(M).\] When \(\alpha=1\), the allocation is called PROP1.*
Definition 7 (Maximin Share Fairness). An allocation \({\cal A}\) is called \(\alpha\)-approximate maximin share fair (\(\alpha\)-MMS)* if the following holds. For goods, \(0\le\alpha\leq 1\) and for all \(i\in N\), \[v_i(A_i)\ge \alpha\, \mathrm{MMS}_i,\] where \[\mathrm{MMS}_i = \max_{{\cal X}\in\Pi_n(M)} \min_{j\in N} v_i(X_j)\] is the maximin share of agent \(i\). For chores, \(\alpha\ge 1\) and for all \(i\in N\), \[c_i(A_i)\le \alpha\, \mathrm{MMS}_i,\] where \[\mathrm{MMS}_i=\min_{{\cal X}\in\Pi_n(M)} \max_{j\in N} c_i(X_j)\] is the maximin share of agent \(i\). When \(\alpha=1\), the allocation is called MMS.*
From the above definitions, it can be seen that if an allocation is \(\alpha\)-EF (resp. \(\alpha\)-PROP), then it must also be \(\alpha\)-EFX (resp. \(\alpha\)-PROPX), but the converse does not hold. Similarly, if an allocation is \(\alpha\)-EFX (resp. \(\alpha\)-PROPX), then it must also be \(\alpha\)-EF1 (resp. \(\alpha\)-PROP1), but the converse does not hold. Moreover, if an allocation is \(\alpha\)-EF (resp. \(\alpha\)-EF1), then it must also be \(\alpha\)-PROP (resp. \(\alpha\)-PROP1), but the converse does not hold. However, the implication that an \(\alpha\)-EFX allocation must also be \(\alpha\)-PROPX holds only for chores allocation. More intricate relationships among different notions of approximately fair allocations can be found in [8].
We now formalize the notions of approximation guarantees with respect to fairness and the competitive ratio used in this paper. Our definition refines the standard competitive analysis framework to accommodate approximate fairness objectives, making precise the comparison between online allocations and optimal offline benchmarks.
Given an instance \(I\) of goods allocation, let \(\mathrm{F}_{\mathrm{g}}^{\cal A}(I) = \alpha\), where \(\alpha\) is the maximum value such that allocation \({\cal A}\) is \(\alpha\)-approximate with respect to fairness notion F. Similarly, for an instance \(I\) of chores allocation, we define \(\mathrm{F}_{\mathrm{c}}^{\cal A}(I) = \alpha\), where \(\alpha\) is the minimum value such that \({\cal A}\) is \(\alpha\)-approximate with respect to F. We refer to \(\alpha\) as the approximation guarantee of allocation \({\cal A}\) with respect to \(\mathrm{F}\). When the context is clear, it is abbreviated as \(\mathrm{F}^{\cal A}(I) = \alpha\). The expressions of approximation guarantees under different fairness notions are summarized in Table 1.
| Fairness | Goods | Chores |
|---|---|---|
| \(\mathrm{EF}^{\cal A}(I)\) | \(\min\left\{1, \min\limits_{i,j\in N} \frac{v_i(A_i)}{ v_i(A_j)}\right\}\) | \(\max\left\{1, \max\limits_{i,j\in N} \frac{c_i(A_i)}{c_i(A_j)} \right\}\) |
| \(\mathrm{EFX}^{\cal A}(I)\) | \(\min\left\{1, \min\limits_{i,j\in N}\frac{ v_i(A_i)}{v_i(A_j)-\min\limits_{e\in A_j} v_i(e)}\right\}\) | \(\max\left\{1, \max\limits_{i,j\in N}\frac{c_i(A_j)-\min\limits_{e\in A_j} c_i(e)}{ c_i(A_i)} \right\}\) |
| \(\mathrm{EF1}^{\cal A}(I)\) | \(\min\left\{1, \min\limits_{i,j\in N}\frac{ v_i(A_i)}{v_i(A_j)-\max\limits_{e\in A_j} v_i(e)}\right\}\) | \(\max\left\{1, \max\limits_{i,j\in N}\frac{ c_i(A_j)-\max\limits_{e\in A_j} c_i(e)}{ c_i(A_i)} \right\}\) |
| \(\mathrm{PROP}^{\cal A}(I)\) | \(\min\left\{1,\min\limits_{i\in N} \frac{nv_i(A_i)}{v_i(M)}\right\}\) | \(\max\left\{1,\max\limits_{i\in N} \frac{nc_i(A_i)}{c_i(M)} \right\}\) |
| \(\mathrm{PROPX}^{\cal A}(I)\) | \(\min\left\{1,\min\limits_{i\in N} \frac{n\left( v_i(A_i)+\min\limits_{e\in M\setminus A_i}v_i(e)\right) }{v_i(M)}\right\}\) | \(\max\left\{1,\max\limits_{i\in N} \frac{n\left( c_i(A_i)-\min\limits_{e\in A_i}c_i(e)\right) }{c_i(M)} \right\}\) |
| \(\mathrm{PROP1}^{\cal A}(I)\) | \(\min\left\{1,\min\limits_{i\in N} \frac{n\left( v_i(A_i)+\max\limits_{e\in M\setminus A_i}v_i(e)\right) }{v_i(M)}\right\}\) | \(\max\left\{1,\max\limits_{i\in N} \frac{n\left( c_i(A_i)-\max\limits_{e\in A_i}c_i(e)\right) }{c_i(M)} \right\}\) |
| \(\mathrm{MMS}^{\cal A}(I)\) | \(\min\limits_{i\in N}\frac{v_i(A_i)}{\max\limits_{{\cal X}\in\Pi_n(M)} \min\limits_{j\in N} v_i(X_j)}\) | \(\max\limits_{i\in N}\frac{c_i(A_i)}{\min\limits_{{\cal X}\in\Pi_n(M)} \max\limits_{j\in N} c_i(X_j)}\) |
For each instance \(I\), let \(\mathrm{F}^*(I)\) be the optimal approximation guarantee among all allocations with respect to \(\mathrm{F}\). That is, \[\mathrm{F}_{\mathrm{g}}^*(I) = \sup_{ {\cal A} \in\Pi_n(M)} \mathrm{F}_{\mathrm{g}}^{\cal A}(I) , \quad \mathrm{F}_{\mathrm{c}}^*(I) = \inf_{ {\cal A} \in\Pi_n(M)} \mathrm{F}_{\mathrm{c}}^{\cal A}(I).\] Clearly, \(\mathrm{F}^*(I)=1\) implies that there exists an allocation for instance \(I\) that exactly satisfies the fairness notion \(\mathrm{F}\). For goods allocation, \(\mathrm{F}_{\mathrm{g}}^*(I) < 1\) means that exact fairness is unattainable and only approximate fairness can be achieved, whereas for chores allocation, this corresponds to \(\mathrm{F}_{\mathrm{c}}^*(I) > 1\). Allocations whose approximation guarantee are exactly \(\mathrm{F}^*(I)\) are called optimal allocations with respect to F. For the same instance, optimal allocations under different fairness notions are not necessarily the same. For a given instance \(I\) of goods allocation, \(\mathrm{F}^*(I)=0\) indicates that there exists no non-trivial allocation under the fairness notion \(\mathrm{F}\). For chore allocation, such instances are characterized by \(\mathrm{F}^*(I)=\infty\) when \(\mathrm{F}\in\{\mathrm{EF},\mathrm{EFX},\mathrm{EF1}\}\) and \(\mathrm{F}^*(I)=n\) when \(\mathrm{F}\in\{\mathrm{PROP},\mathrm{PROPX},\mathrm{PROP1}, \mathrm{MMS}\}\).
The optimal fairness approximation guarantee varies across instances. For a fixed fairness notion, finding the worst optimal approximation guarantee among all instances is a hot research topic in the field of fair division. Table 2 summarizes the the best known results so far.
| Fairness | Goods | Chores | ||
| Identical | General | Identical | General | |
| EF | 0 | 0 | 0 | 0 |
| EFX | 1 | |||
| \((4\le n \le 7)\) \(\frac{2}{3}\) [36] | ||||
| \((n\ge 8)\) \(\frac{\sqrt{5}-1}{2}\) [37] | 1 | |||
| \((n\ge 3)\) \(4\) [38] | ||||
| EF1 | 1 | 1 [39] | 1 | 1 [39] |
| PROP | 0 | 0 | 0 | 0 |
| PROPX | ||||
| \((n\ge 3)\) 0 | ||||
| \((n\ge 3)\) 0 | 1 | 1 [40] | ||
| PROP1 | 1 | 1 [39] | 1 | 1 [39] |
| MMS | 1 | |||
| \((n = 3)\) \(\frac{11}{12}\) [41] | ||||
| \((n = 4)\) \(\frac{4}{5}\) [42] | ||||
| \((n\ge 5)\) \(\frac{3}{4}+\frac{3}{3836}\) [43] | 1 | |||
| \((n = 3)\) \(\frac{15}{13}\) [44] | ||||
| \((4\le n \le 7)\) \(\frac{20}{17}\) [44] | ||||
| \((n\ge 8)\) \(\frac{13}{11}\) [44] | ||||
In this paper, we focus on designing online algorithms to obtain allocations for any instance with the goal of optimizing the fairness approximation guarantee. The performance of an online algorithm is measured by its competitive ratio. Let \(H\) be an online allocation algorithm, and the allocation generated by \(H\) is denoted as \({\cal H}\). We now give the formal definition of the competitive ratio. For instances with \(\mathrm{F}_{\mathrm{g}}^*(I) = 0\) or \(\mathrm{F}_{\mathrm{c}}^*(I) = \infty\), it must be that \(\mathrm{F}_{\mathrm{g}}^{\cal H}(I) = 0\) or \(\mathrm{F}_{\mathrm{c}}^{\cal H}(I) = \infty\), and we conventionally set \(\frac{\mathrm{F}^{\cal H}(I)}{\mathrm{F}^*(I)}=1\).
Definition 8 (Competitive Ratio). The competitive ratio* of algorithm \(H\) with respect to a fairness notion \(\mathrm{F}\) is defined as \[\mathrm{CR}_{\mathrm{g}}^{\mathrm{F}}(H) = \inf_I \frac{\mathrm{F}_{\mathrm{g}}^{\cal H}(I)}{\mathrm{F}_{\mathrm{g}}^*(I)}\] for goods allocation, and \[\mathrm{CR}_{\mathrm{c}}^{\mathrm{F}}(H) = \sup_I \frac{\mathrm{F}_{\mathrm{c}}^{\cal H}(I)}{\mathrm{F}_{\mathrm{c}}^*(I)}\] for chores allocation.*
When the context is clear, we use \(\text{CR}^{\mathrm{F}}(H)\) to denote the competitive ratio of algorithm \(H\). The closer the competitive ratio of an algorithm is to 1, the better its performance. If no online algorithm exists with a competitive ratio better than \(r\), and the competitive ratio of \(H\) is exactly \(r\), then \(H\) is referred to as optimal. Obviously, if under a certain fairness notion, no algorithm achieves a competitive ratio better than \(r\) with identical utility functions, then no such algorithm exists with general utility functions either. Similarly, if no algorithm achieves a competitive ratio better than \(r\) in the normalized setting, then none exists in the non-normalized setting either.
Zhou et al. [9] studied online allocation under the fair notion of MMS, and more fair notions such as EF1, EFX, and PROP1 were investigated in [10]. They also use competitive ratio to measure performance of online algorithms, with a definition that differs slightly from ours. They directly take the worst of the approximation guarantee achievable by the algorithm over all instances, i.e., \(\inf\limits_I \mathrm{F}_{\mathrm{g}}^{\cal H}(I)\) or \(\sup\limits_I \mathrm{F}_{\mathrm{c}}^{\cal H}(I)\), as its competitive ratio. In fact, if under a specific fairness notion F, \(\mathrm{F}^*(I)=1\) for any instance \(I\), the two definitions are equivalent. We have listed corresponding results of [9] and [10] in Tables [tab:goods95results] and [tab:chores95results].
However, there are indeed other cases where \(\mathrm{F}^*(I)\neq 1\) for some instance \(I\) (Ref. Table 2). For these cases, the optimal approximation guarantee may vary across different instances under a specific fairness notion, let alone across different notions. In a more extreme case, if there exists an instance \(I\) of goods allocation such that under a specific fairness notion F, \(\mathrm{F}^*(I)=0\), then the worst-case approximation guarantee of any algorithm can only be \(0\). Since this instance admits no non-trivial allocation, one cannot expect any algorithm to achieve this. Hence, measuring and comparing algorithm performance based on the approximation guarantee seems somewhat unreasonable. For this reason, in this paper, we adopt the standard approach commonly used in competitive analysis to define the competitive ratio of an online algorithm.
Parallel machine scheduling is also an optimization problem related to resource allocation, and thus it is closely connected to fair division, particularly in the case of identical utilities. By regarding agents as machines and items as jobs, the utility of an item to an agent corresponds to the processing time of the job on that machine. Each allocation corresponds to a feasible schedule. The total utility of the items obtained by an agent corresponds to the completion time of the machine. Therefore, the maximum and minimum utilities among all agents correspond to the makespan and the minimum completion time of all machines, respectively.
Specifically, in the case of identical utilities, the utility of any set of items is the same for all agents. A similar connection between MMS and parallel machine scheduling in this setting was previously observed by Zhou et al. [9]. For completeness, we provide a formal treatment, where a similar connection also extends to the refined definition of the competitive ratio under PROP. Let \(u_{\max}^{\cal A}=\max_{i\in N}u(A_i)\) and \(u_{\min}^{\cal A}=\min_{i\in N}u(A_i)\). Then \[\mathrm{EF}_{\mathrm{g}}^{\cal A}(I)= \frac{v_{\min}^{\cal A}}{v_{\max}^{\cal A}}, \, \mathrm{EF}_{\mathrm{c}}^{\cal A}(I)= \frac{c_{\max}^{\cal A}}{c_{\min}^{\cal A}}\] and \[\mathrm{PROP}_{\mathrm{g}}^{\cal A}(I)=\frac{nv_{\min}^{\cal A}}{v(M)} , \, \mathrm{PROP}_{\mathrm{c}}^{\cal A}(I)=\frac{nc_{\max}^{\cal A}}{c(M)}.\] Furthermore, for goods allocation and chores allocation, the maximin share of each agent equals to the optimal minimum machine completion time and optimal makespan, respectively. Therefore, for any allocation \({\cal A}\), \[\frac{\mathrm{PROP}_{\mathrm{g}}^{\cal A}(I)}{\mathrm{PROP}_{\mathrm{g}}^*(I)} = \frac{v_{\min}^{\cal A}}{\max_{{\cal X}\in \Pi_n(M)}v_{\min}^{\cal X}} = \mathrm{MMS}_{\mathrm{g}}^{\cal A}(I),\] and \[\frac{\mathrm{PROP}_{\mathrm{c}}^{\cal A}(I)}{\mathrm{PROP}_{\mathrm{c}}^*(I)} = \frac{c_{\max}^{\cal A}}{\min_{{\cal X}\in \Pi_n(M)}c_{\max}^{\cal X}} = \mathrm{MMS}_{\mathrm{c}}^{\cal A}(I).\] Recall that \(\mathrm{MMS}^*(I)=1\) for any instance \(I\) in the identical case, and thus \[\label{prop61mms} \frac{\mathrm{PROP}^{\cal A}(I)}{\mathrm{PROP}^*(I)} =\frac{\mathrm{MMS}^{\cal A}(I)}{\mathrm{MMS}^*(I)}.\tag{1}\] It follows that the competitive ratio of any online algorithm \(H\) with respect to MMS equals that with respect to PROP.
Therefore, finding the optimal approximation guarantee under PROP for goods and chores allocation are equivalent to parallel machine scheduling problems \(Pn||C_{\min}\) and \(Pn||C_{\max}\), respectively, which have been extensively studied in scheduling literature [20], [26]. For online allocation with identical utilities under PROP, results from the online scheduling problems \(Pn||C_{\min}\) [27] and \(Pn||C_{\max}\) [20], [22]–[25] can be directly applied. In particular, the normalized case corresponds to the semi-online variant where the total processing time of all jobs is known as a priori. Consequently, we can leverage existing results on corresponding semi-online scheduling problem with known total processing time [30]–[33].
Although \(\mathrm{EF}^{\cal A}(I)\) can also be interpreted as the ratio between the makespan and the minimum machine load [45], similar objectives have been less studied in online scheduling. The other fairness notions, such as EFX, EF1, PROPX, PROP1, etc., do not have obvious significance in the context of scheduling and, consequently, have not been investigated. Nevertheless, we can still utilize some results obtained from scheduling. For example, it is well known that for any allocation \({\cal A}\), \[\label{eq:cmax} u_{\max}^{\cal A}\geq \max\left\{\frac{1}{n}\sum_{j=1}^mu(e_j),\;\max_{1\leq j \leq m}u(e_j)\right\},\tag{2}\] and for each \(0 \le s \le n-1\), \[\label{eq:cmin} u_{\min}^{\cal A} \le \frac{u(M) - \sum_{k=1}^{s} u(e_{j_k})}{n-s},\tag{3}\] where \(e_{j_1}, e_{j_2}, \dots, e_{j_{n-1}}\) are arbitrary \(n-1\) items in \(M\) [46], [47].
It is worth noting that in scheduling, the problem where jobs require different processing times on different machines is referred to as unrelated machine scheduling [48], [49]. However, this does not directly correspond to fair division in the general case. This is because, in most cases, determining whether a fairness requirement is satisfied depends on comparing the utilities of different bundles within each agent, rather than comparing the utilities of bundles obtained among different agents.
Moreover, for the general utilities case, 1 does not necessarily hold, even if \(n=2\) and \(\mathrm{MMS}^*=1\). For example, consider an instance of goods allocation with \(3\) items. The values of items are \[v_1(e_1)=v_2(e_1)=0.5,\;v_1(e_2)=1.4,\;v_2(e_2)=1.3,\;v_1(e_3)=0.1,\;v_2(e_3)=0.2.\] We can verify that \(\text{MMS}_1=0.6\) from allocation \({\cal A}'\) with \(A'_1=\{e_1,e_3\}\) and \(A'_2=\{e_2\}\), and \(\text{MMS}_2=0.7\) from allocation \({\cal A}''\) with \(A''_1=\{e_2\}\) and \(A''_2=\{e_1,e_3\}\). Both allocations are optimal MMS allocations, and \(\text{MMS}^*=1\). \({\cal A}''\) is also an optimal PROP allocation, and \(\text{PROP}^*=0.7\). Let \({\cal H}\) with \(H_1=\{e_3\}\) and \(H_2=\{e_1, e_2\}\) be the allocation produced by some algorithm \(H\). We have \(\text{MMS}^{\cal H}=\min\{\frac{v_1(H_1)}{\text{MMS}_1},\frac{v_2(H_2)}{\text{MMS}_2}\}=\frac{0.1}{0.6}=\frac{1}{6}\) and \(\text{PROP}^{\cal H}=\min\{\frac{2v_1(H_1)}{v_1(M)},\frac{2v_2(H_2)}{v_2(M)}\}=0.1\). Hence, \(\frac{\text{MMS}^{\cal H}}{\text{MMS}^*}=\text{MMS}^{\cal H}\neq \frac{\text{PROP}^{\cal H}}{\text{PROP}^*}\).
While goods allocation and chore allocation typically exhibit divergent characteristics, we observe strong connections between the algorithms and their competitive ratios under the EF, EFX, and EF1 notions in the identical case.
It can be observed from Table 1 that for any fairness notion \(\mathrm{F}\in\{\mathrm{EF},\mathrm{EFX},\mathrm{EF1}\}\), if \(v(e)=c(e)\) for any \(e\in M\), then \[\label{reciprocal} \mathrm{F}^{\cal A}_\mathrm{g}(I)=\frac{1}{\mathrm{F}^{\cal A}_\mathrm{c}(I)}\tag{4}\] for any \({\cal A}\in \Pi_n(M)\).
Theorem 1. For the online fair allocation of goods and chores with identical utility functions, under any fairness notion \(\mathrm{F}\in\{\mathrm{EF},\mathrm{EFX},\mathrm{EF1}\}\), the competitive ratio of any algorithm for chores is the reciprocal of that for goods, that is, \[\mathrm{CR}_{\mathrm{c}}^{\mathrm{F}}(H) = \frac{1}{\mathrm{CR}_{\mathrm{g}}^{\mathrm{F}}(H)}.\]
Proof. For any instance \(I\) of chores allocations, we construct a corresponding instance of goods allocations such that \(c(e)=v(e)\) for any \(e\in M\). For any fairness notion \(\mathrm{F}\in\{\mathrm{EF},\mathrm{EFX},\mathrm{EF1}\}\) and for any algorithm \(H\), \(\mathrm{F}^{\cal H}_\mathrm{g}(I)=\frac{1}{\mathrm{F}^{\cal H}_\mathrm{c}(I)}\) by (4 ). Again by (4 ), \(\mathrm{F}^*_\mathrm{g}(I)=\frac{1}{\mathrm{F}^*_\mathrm{c}(I)}\). Thus \[\mathrm{CR}_{\mathrm{c}}^{\mathrm{F}}(H)=\sup_{I}\frac{\mathrm{F}^{\cal H}_{\mathrm{c}}(I)}{\mathrm{F}^*_{\text{c}}(I)}=\left( \inf_{I}\frac{\mathrm{F}^{\cal H}_{\mathrm{g}}(I)}{\mathrm{F}^*_{\text{g}}(I)} \right)^{-1} \leq \frac{1}{\mathrm{CR}_{\mathrm{g}}^{\mathrm{F}}(H)}.\] Similarly, we can also prove that \(\mathrm{CR}_{g}^{\mathrm{F}}(H)\leq \frac{1}{\mathrm{CR}_{c}^{\mathrm{F}}(H)}\). Hence, \(\mathrm{CR}_{c}^{\mathrm{F}}(H)= \frac{1}{\mathrm{CR}_{g}^{\mathrm{F}}(H)}\). ◻
As a result, for the case of identical utilities under the EF, EFX, and EF1 notion, we restrict our discussion to goods allocation.
In this subsection, we present the relationship between the competitive ratios of online algorithms for fair allocation with two agents under the EF and PROP notions.
Theorem 2. (i) For goods allocation in the normalized setting with two agents, an online algorithm that achieves a competitive ratio of \(r_1\) under PROP* guarantees a competitive ratio of at least \(\frac{r_1}{2 - r_1}\) under EF.*
(ii) For chores allocation in the normalized setting with two agents, an online algorithm that achieves a competitive ratio of \(r_2\) under EF* guarantees a competitive ratio of at most \(\frac{2 r_2}{1 + r_2}\) under PROP.*
Proof. (i) From Table 1, we have \[\label{t63} \mathrm{EF}_{\mathrm{g}}^{\cal A}(I)=\min\left\{1, \frac{v_1(A_1)}{2-v_1(A_1)}, \frac{v_2(A_2)}{2-v_2(A_2)}\right\}=\frac{\min\{1, v_1(A_1), v_2(A_2)\}}{2-\min\{1, v_1(A_1), v_2(A_2)\}}=\frac{\text{PROP}_{\mathrm{g}}^{\cal A}(I)}{2-\text{PROP}_{\mathrm{g}}^{\cal A}(I)}\tag{5}\] Note that for any \(\alpha \le \beta \le 1\), \[\label{eq:goods95cr95prop95ef952} \frac{\frac{\alpha}{2-\alpha}}{\frac{\beta}{2-\beta}}-\frac{\frac{\alpha}{\beta}}{2-\frac{\alpha}{\beta}}=\frac{\alpha}{\beta}\left(\frac{2-\beta}{2-\alpha}-\frac{\beta}{2\beta-\alpha}\right)=\frac{2\alpha(\beta-\alpha)(1-\beta)}{\beta(2-\alpha)(2\beta-\alpha)} \ge 0.\tag{6}\] Suppose that \(H\) is an online algorithm for goods allocation with a competitive ratio of \(r_1\) under PROP. Since \(\text{PROP}_{\mathrm{g}}^{\cal H}(I)\leq \text{PROP}_{\mathrm{g}}^{*}(I)\leq 1\), by 5 and 6 , \[\begin{align} \text{CR}^{\text{EF}}_{\mathrm{g}}(H) &=\inf_I\frac{\text{EF}_{\mathrm{g}}^{\cal H}(I)}{\text{EF}_{\mathrm{g}}^*(I)} =\inf_I \frac{\frac{\text{PROP}_{\mathrm{g}}^{\cal H}(I)}{2-\text{PROP}_{\mathrm{g}}^{\cal H}(I)} }{\frac{\text{PROP}_{\mathrm{g}}^{*}(I)}{2-\text{PROP}_{\mathrm{g}}^{*}(I)}}\ge \inf_I \frac{\frac{\text{PROP}_{\mathrm{g}}^{\cal H}(I)}{\text{PROP}_{\mathrm{g}}^*(I)}}{2-\frac{\text{PROP}_{\mathrm{g}}^{\cal H}(I)}{\text{PROP}_{\mathrm{g}}^*(I)}} \\ &= \frac{\inf_I \frac{\text{PROP}_{\mathrm{g}}^{\cal H}(I)}{\text{PROP}_{\mathrm{g}}^*(I)}}{2-\inf_I\frac{\text{PROP}_{\mathrm{g}}^{\cal H}(I)}{\text{PROP}_{\mathrm{g}}^*(I)}}=\frac{\text{CR}^{\text{PROP}}_{\mathrm{g}}(H)}{2-\text{CR}^{\text{PROP}}_{\mathrm{g}}(H)}=\frac{r_1}{2-r_1}. \end{align}\] Hence, \(H\) is an online algorithm with a competitive ratio at least \(\frac{r_1}{2-r_1}\) under EF.
(ii) From Table 1, we have \[\mathrm{EF}_{\mathrm{c}}^{\cal A}(I)=\max\left\{1, \frac{c_1(A_1)}{2-c_1(A_1)}, \frac{c_2(A_2)}{2-c_2(A_2)}\right\}=\frac{\max\{1, c_1(A_1), c_2(A_2)\}}{2-\max\{1, c_1(A_1), c_2(A_2)\}}=\frac{\text{PROP}_{\mathrm{c}}^{\cal A}(I)}{2-\text{PROP}_{\mathrm{c}}^{\cal A}(I)}.\] Thus \[\label{t64} \text{PROP}_{\mathrm{c}}^{\cal A}(I)=\frac{2\mathrm{EF}_{\mathrm{c}}^{\cal A}(I)}{1+\mathrm{EF}_{\mathrm{c}}^{\cal A}(I)}.\tag{7}\] Note that for any \(\alpha \ge \beta \ge 1\), \[\label{eq:goods95cr95prop95ef953} \frac{\frac{2\alpha}{1+\alpha}}{\frac{2\beta}{1+\beta}}-\frac{2\cdot\frac{\alpha}{\beta}}{1+\frac{\alpha}{\beta}} =\frac{\alpha}{\beta}\left(\frac{1+\beta}{1+\alpha}-\frac{2\beta}{\alpha+\beta}\right) =\frac{\alpha(\alpha-\beta)(1-\beta)}{\beta(1+\alpha)(\alpha+\beta)} \le 0.\tag{8}\] Suppose that \(H\) is an online algorithm for chores allocation with a competitive ratio of \(r_2\) under EF. Since \(\text{EF}_{\mathrm{c}}^{\cal H}(I)\geq \text{EF}_{\mathrm{c}}^{*}(I)\geq 1\), by 7 and 8 , \[\begin{align} \text{CR}^{\text{PROP}}_{\mathrm{c}}(H) &=\sup_I\frac{\text{PROP}_{\mathrm{c}}^{\cal H}(I)}{\text{PROP}_{\mathrm{c}}^*(I)} =\sup_I \frac{\frac{2\text{EF}_{\mathrm{c}}^{\cal H}(I)}{1+\text{EF}_{\mathrm{c}}^{\cal H}(I)} }{\frac{\text{EF}_{\mathrm{c}}^{*}(I)}{1+\text{EF}_{\mathrm{c}}^{*}(I)}}\le \sup_I \frac{2\cdot\frac{\text{EF}_{\mathrm{c}}^{\cal H}(I)}{\text{EF}_{\mathrm{c}}^*(I)}}{1+\frac{\text{EF}_{\mathrm{c}}^{\cal H}(I)}{\text{EF}_{\mathrm{c}}^*(I)}} \\ &= \frac{2\sup_I \frac{\text{EF}_{\mathrm{c}}^{\cal H}(I)}{\text{EF}_{\mathrm{c}}^*(I)}}{1+\sup_I\frac{\text{EF}_{\mathrm{c}}^{\cal H}(I)}{\text{EF}_{\mathrm{c}}^*(I)}}=\frac{2\text{CR}^{\text{EF}}_{\mathrm{c}}(H)}{1+\text{CR}^{\text{EF}}_{\mathrm{c}}(H)}=\frac{2r_2}{1+r_2}. \end{align}\] Hence, \(H\) is an online algorithm with a competitive ratio at most \(\frac{2r_2}{1+r_2}\) under PROP. ◻
However, the converse of Theorem 2 may not hold, even in the identical utilities case. For example, consider an instance of goods allocation with \(3\) items. The values of items are \(v(e_1)=1.1\), \(v(e_2)=0.5\) and \(v(e_3)=0.4\). We can verify that \(\text{EF}^*=\frac{9}{11}\) and \(\text{PROP}^*=\frac{9}{10}\) from allocation \({\cal A}^*\) with \(A^*_1=\{e_1\}\) and \(A^*_2=\{e_2, e_3\}\). Let \({\cal H}\) with \(H_1=\{e_3\}\) and \(H_2=\{e_1, e_2\}\) be the allocation produced by some algorithm \(H\). We have \(\text{EF}^{\cal H}=\frac{1}{4}\) and \(\text{PROP}^{\cal H}=\frac{2}{5}\). Hence, \(\frac{\text{EF}^{\cal H}}{\text{EF}^*}=\frac{11}{36}\) and \[\frac{\text{PROP}^{\cal H}}{\text{PROP}^*}=\frac{4}{9}<\frac{22}{47}=\frac{2\frac{\text{EF}^{\cal H}}{\text{EF}^*}}{1+\frac{\text{EF}^{\cal H}}{\text{EF}^*}}.\]
In this paper, we revisit online fair division from the perspective of competitive analysis with respect to approximation guarantees. We refine the definition of competitive ratio for online fair division to align it with the classical definition in online algorithms, while remaining consistent with existing results in the online fair division literature. This refined framework enables a systematic and comparable study of approximation guarantees across different fairness notions. To the best of our knowledge, our results provide the first comprehensive characterization of competitive ratios for online fair division, covering both goods and chores within a unified framework.
Several directions remain open for future work. A natural step is to bridge the existing gaps where current upper and lower bounds do not match. It would also be worthwhile to explore alternative fairness notions, such as EFk [5], EFkX [50], Avg-EFX [51], PROPm [51], and PROPavg [52]. Furthermore, these problems can be extended to the setting of weighted fair division.
In this paper, we investigate the normalized setting in which the total utility of all items is known in advance. This framework can be viewed as a semi-online model, a paradigm that has been extensively studied in the scheduling literature. While various semi-online models incorporating different types of partial information have been proposed, many of these can be naturally adapted to the context of online fair division.
Finally, online algorithms with predictions, which bridge machine learning and online problems, constitute an active area of research. In fair division with predictions, predicted values for item utilities can be obtained, and these predictions are subject to quantifiable errors. The goal is to leverage these predictions to achieve an allocation that outperforms that obtained without any utility information.