1 Introduction↩︎

Modern machine learning systems routinely make sequential allocation decisions: for instance, routing ad impressions to advertisers, dispatching jobs to workers in cloud platforms, allocating service requests in online marketplaces, and matching drivers to riders. These decisions are inherently online (items arrive over time), irrevocable (decisions must be committed immediately), and increasingly prediction-driven (platforms rely on forecasts of demand, value, or future arrivals). A central challenge is to provide fairness guarantees in this setting: the system must commit to allocations without knowing the future, while any predictive signal may be noisy or biased. This tension between irrevocable online decisions, imperfect predictions, and fairness is now a recurring theme across work on online optimization and learning-augmented algorithms [1], [2]. Motivated by this perspective, we ask which individual level fairness benchmarks remain meaningfully approximable under irrevocability and weak predictive side-information.

We study this problem through the online fair division model: indivisible goods arrive sequentially and must be allocated immediately and irrevocably to an agent based on their reported values for the current good. The model has gained visibility in the ML literature through several complementary lenses: (i) prediction-augmented online allocation and scheduling [3]–[7], (ii) learning-augmented mechanism design and allocation constraints [8]–[10], and (iii) learning-based approaches to fair division from partial/bandit feedback [11]. A key conceptual point in this line of work is that the relevant performance benchmarks are not purely utilitarian: platform designers often seek individual level fairness guarantees that remain meaningful even when the instance is adversarial.

In offline fair division, widely used benchmarks include envy-freeness up to one good (EF1) and maximin share fairness (MMS) [12]–[15]. In adversarial online settings, however, recent work has established stark impossibilities: for three or more agents, no finite approximation is possible for MMS [5], and similarly no finite approximation is possible for EF1 under comparable informational assumptions [16]. These results suggest that, under irrevocability and limited information, many “gold standard” offline notions may be fundamentally unattainable online.

In this work, we ask whether proportionality-type guarantees can serve as a meaningful and achievable alternative in the online model. Proportionality requires that each agent obtain at least her proportional fair share of the total value, but with indivisible goods this benchmark can fail even in offline settings. A standard relaxation is proportionality up to one good (PROP1), which requires that each agent can reach their proportional share after adding one good outside their own bundle. PROP1 has a long history in offline fair division and related allocation problems [17]–[21]. Crucially, PROP1 is implied by EF1 and MMS, so it remains a principled fairness target even when stronger notions are unattainable.

Despite this appeal, the approximability landscape for PROP1 in the online setting has remained unclear. Prior work shows that exact PROP1 may fail to exist online [16], [22]. Moreover, existing positive results for online PROP1 rely on comparatively strong side-information (e.g., normalization/total-value information) [16]. This leaves open a basic question that is central from an ML perspective: under realistic online constraints and weak predictive signals, can we obtain any nontrivial approximation to PROP1?

Motivated by learning-augmented online optimization, we study algorithms that can leverage weak predictions while still targeting provable guarantees. Concretely, we focus on maximum item value (MIV) predictions: for each agent, we are given a prediction of the maximum value this agent has for any good. This is substantially weaker than knowing normalization information or the future sequence, yet captures the kind of coarse “scale” information that is routinely produced by forecasting pipelines. We also analyze one-sided (conservative) prediction error, which aligns with the widespread use of upper confidence bounds and safety margins in sequential decision-making [23].

1.1 Our Contributions and Paper Outline↩︎

We initiate a systematic study of approximate PROP1 in online fair division under two settings that are standard in online algorithms and ML: adaptive adversary (worst-case feedback/adversarial dependence) and non-adaptive adversary (oblivious sequences), and we quantify what is and is not achievable under weak predictions.

1. Greedy allocation against adaptive adversaries (3). We show that three natural greedy allocation strategies (representing common heuristics) cannot guarantee any positive approximation to PROP1 against an adaptive adversary. This is notable (and surprising) because greedy rules are pervasive in both theoretical fair division and deployed allocation systems, and because a natural greedy approach can achieve PROP1 under stronger informational assumptions [16]. Our results reveal fundamental limits of greedy methods in adversarial online environments: without either randomness against oblivious inputs or predictive information against adaptive adversaries, even the weakest standard proportionality benchmark can be driven to zero.

2. Random allocation against non-adaptive adversaries (4). Against a non-adaptive adversary (which commits to the entire input sequence in advance, independent of the algorithm’s realized randomness),¹ we prove that the simple algorithm that allocates each good uniformly at random to \(n\) agents achieves an \(\alpha\)-PROP1 guarantee with probability at least \(1-\delta\), where \(\alpha=\Theta(1/\log(n/\delta))\) (Theorem 4). This is the first known result for the random allocation against non-adaptive adversaries in this setting, requiring neither asymptotic assumptions nor structural constraints. We complement this with a matching lower bound showing this logarithmic dependence is essentially tight for uniform random allocation (Proposition 5). Finally, in the common “small items” setting (i.e., when each agent’s maximum item value is small relative to their proportional share), the uniformly random allocation achieves near-proportionality: a \((1-\varepsilon)\)-PROP1 guarantee with probability at least \(1-\delta\) (Theorem 6). These results provide a useful positive insight: randomness alone, under oblivious inputs, gives us nontrivial and quantifiable fairness guarantees.

3. Algorithm with MIV predictions against adaptive adversaries (5). We design an online algorithm that, given MIV predictions, guarantees a \(1/n\)-PROP1 allocation even against adaptive adversaries (Theorem 8). We then show a general graceful degradation guarantee under one-sided prediction error: any \(\alpha\)-PROP1 algorithm for perfect predictions can be transformed to achieve \(\alpha(1-\varepsilon)/(1-\alpha\varepsilon/n)\)-PROP1 under error \(\varepsilon\) (Theorem 9), giving us an explicit robustness bound for our algorithm (Corollary 1). This positions PROP1 as a fairness objective that is compatible with the learning-augmented paradigm: weak predictions materially improve what is achievable in the worst case.

To complete the picture, we prove that three natural and widely studied stronger fairness notions (EF1, MMS, and the stronger proportionality notion PROPX) admit no positive approximation in the online model even with perfect MIV predictions (Proposition 7). This strengthens and broadens known impossibilities and underscores that PROP1 is not merely a convenient relaxation: it is a uniquely viable fairness benchmark under weak predictive information.

2 Preliminaries and Related Work↩︎

We use the notation \(\mathbb{N}_+ = \{ 1, 2, 3, \ldots \}\) to denote the set of positive integers (excluding zero), and \(\mathbb{R}_{\geq 0}\) for the set of non-negative real numbers. For any positive integer \(z\), we write \([z] := \{ 1, \dots, z \}\). For any set \(A\), we denote its powerset, the set of all subsets of \(A\), by \(2^A\).

Our setting involves \(n \geq 2\) agents and a sequence of \(m \geq 1\) indivisible goods \(G = \{ g_1, \dots, g_m \}\) that arrive online, one at a time. Each good must be allocated immediately and irrevocably to one of the agents upon arrival. Crucially, the total number of goods \(m\) is not known in advance and is implicitly revealed only retrospectively once all goods have arrived. We label the goods in their arrival order, and for any time step \(t \in [m]\), we define \(G^{(t)} := \{ g_1, \dots, g_t \}\) to be the set of the first \(t\) goods observed. Thus, \(G^{(m)} = G\) denotes the full set once all goods have arrived. Each agent \(i \in [n]\) has a non-negative valuation function \(v_i : 2^G \to \mathbb{R}_{\geq 0}\), which assigns a value to any bundle of goods. Following standard assumptions in fair division, we assume that valuations are additive: for any subset \(S \subseteq G\), we have \(v_i(S) = \sum_{g \in S} v_i(\{g\})\). For convenience, we write \(v_i(g)\) as shorthand for \(v_i(\{g\})\).

An allocation is a tuple \(\mathcal{A} = (A_1, \dots, A_n)\), where each \(A_i \subseteq G\) is the bundle allocated to agent \(i\). The allocation must form a partition of the goods: the \(A_i\) are pairwise disjoint and their union equals \(G\).

2.1 Fairness Notions↩︎

For any time step \(t \in [m]\) and agent \(i \in [n]\), let \(A_i^{(t)}\) denote the bundle held by agent \(i\) after the allocation of good \(g_t\), with \(A_i^{(0)} = \varnothing\) as the initial allocation and \(A_i^{(m)} = A_i\) as the final bundle. We are interested in online algorithms that produce allocations satisfying approximate fairness guarantees. In particular, we focus on proportionality up to one good (PROP1) and its multiplicative relaxations.

A classical proportional allocation ensures that each agent receives utility at least \(v_i(G)/n\), but such guarantees are often unachievable even in the offline setting with two agents and one good. We thus focus on the more permissive relaxation of PROP1 in this work, defined as follows.

Unfortunately, it is known that even PROP1 is not always achievable in online settings [16], [22]. This motivates the study of multiplicative approximations to PROP1 as a more attainable fairness benchmark. Following prior work, we define the notion of \(\alpha\)-PROP1 for \(\alpha \in [0,1]\): an allocation is \(\alpha\)-PROP1 if, for each agent \(i \in [n]\), either \(A_i = G\), or there exists \(g \in G \setminus A_i\) such that \(v_i(A_i \cup \{g\}) \ge \alpha \cdot \frac{v_i(G)}{n}\). Note that \(1\)-PROP1 is equivalent to PROP1.

We also briefly consider three well-studied, stronger fairness notions: EF1, MMS, and PROPX; note that these are not the focus of this paper, but we define them in order to (later) establish impossibility results and delineate the boundary of what is achievable. These notions are pairwise incomparable but each implies PROP1.

While these stronger fairness notions are attractive, they are known to be inapproximable in online settings under minimal assumptions [5], [16].² We denote the approximate versions of these fairness notions as \(\alpha\)-EF1, \(\alpha\)-MMS, and \(\alpha\)-PROPX in a similar fashion as \(\alpha\)-PROP1.

2.2 Maximum Item Value (MIV) predictions↩︎

Later in 5, we study learning-augmented algorithms that have access to useful predictive information about the instance. In particular, we focus on maximum item value (MIV) predictions. Given the set of all goods \(G\), let \(v_i^{\max} = \max_{g \in G} v_i(g)\) denote the maximum value agent \(i \in [n]\) assigns to any single good. We assume access to predictions \(p_i \approx v_i^{\max}\), and let \(\mathbf{p} = (p_1, \dots, p_n)\) denote the vector of MIV predictions for all agents.

This form of predictive input is considerably weaker than full knowledge of valuations or normalized value vectors, yet it can still meaningfully guide allocation decisions. We refer to the case where \(p_i = v_i^{\max}\) for all \(i \in [n]\) as having perfect predictions. This model is in line with prior work that assumes oracle access to predicted information in online fair division [5], [16]. We also consider settings with one-sided bounded prediction error. Specifically, we assume that the predictions overestimate the true maximum value by at most a factor of \(\frac{1}{1 - \varepsilon}\) for some \(\varepsilon\in [0,1)\), and never underestimate it.

This conservative (upper-biased) approach to prediction is motivated by both theory and practice. In online learning and bandit algorithms, for example, upper confidence bounds (UCB) are a common strategy for exploration under uncertainty [23]. Similarly, in inventory planning and demand forecasting, safety margins are often introduced to guard against shortfalls, favoring overestimation over underestimation. In such settings, underestimating future values or demand is typically more costly than overestimating, making one-sided prediction errors both natural and desirable.

2.3 Types of Adversaries in Online Algorithms↩︎

In analyzing online algorithms, it is standard to distinguish between two types of adversaries: adaptive and non-adaptive. An adaptive adversary can observe the algorithm’s internal randomness and past decisions, and respond dynamically by selecting future inputs to undermine performance. While adaptive adversaries model worst-case behavior, they often make meaningful fairness guarantees impossible in online allocation settings. In contrast, a non-adaptive adversary commits to the full input sequence in advance, before any of the algorithm’s random decisions are made. This restriction allows for meaningful probabilistic guarantees and is widely adopted when studying randomized algorithms.

2.4 Other Related Work↩︎

We already discussed the two most directly relevant papers, [16] and [5], which study online fair division with predictive information in essentially the same model as ours. These works assume perfect predictive information. Here we briefly situate our work within broader lines of work that are related to the model more generally.

Learning-Augmented Online Fair Division. There is a growing body of work on learning-augmented algorithms,³ which leverage predictive information about future arrivals and analyze the extent to which desirable fairness properties can be achieved, even when predictions may be inaccurate. However, most such works in the context of online fair division consider a model with divisible goods. It is important to note that fairness concepts and the structure of the model differ significantly between divisible and indivisible goods.

In the setting with indivisible goods (which is the focus of our work), [7] study the allocation of advertising impressions (goods) to advertisers (agents), subject to cardinality constraints on agents’ bundle sizes, and with utilitarian social welfare as the objective. Other works such as [6] and [10] explore learning-augmented approaches focused on MMS and incentive-compatibility as desirable properties.

Online Fair Division. A separate line of work studies online fair division as a purely adversarial online problem. [24] study the online fair division problem modeled after a food bank charity problem, where agents are assumed to have binary valuations. They examine fairness properties such as envy-freeness as well as incentive compatibility. [22] focus on minimizing envy as an objective, while [25] build on this by analyzing the trade-off between approximate envy-freeness and a notion of economic efficiency. [26] explore a variant of the online model whereby past allocations can be revisited and swapped. Several other works consider an online fair division model with divisible goods [27]–[30]. For a broader overview of earlier works in online fair division, see the survey by [31].

3 Greedy Fails in General↩︎

In this section, we study the natural class of greedy algorithms, which aim to allocate each arriving good in a way that attempts to satisfy a given fairness criterion as much as possible at the current timestep. In the classic online setting without predictive information, the greedy approach is both intuitive and arguably the only viable strategy. The key question then is: what properties or (non-predictive) information can be leveraged to guide the greedy algorithm’s decisions?

Prior work that incorporates predictive information typically uses it to guide greedy algorithms that achieve approximate fairness guarantees. For instance, [5] proposed a greedy algorithm for \(n=2\) that guarantees \(1/2\)-MMS under normalized valuations. Building on this, [16] introduced a different greedy algorithm that satisfies EF1 (and thus also \(1/2\)-MMS) for \(n=2\), and achieves PROP1 for all \(n\).

Given the intuitive appeal and historical success of greedy approaches in related settings, it is natural to consider them as a potential means of achieving PROP1. However, we show that such strategies generally fail to provide any non-trivial approximation to the PROP1 ratio. Specifically, we analyze three natural greedy allocation strategies and demonstrate that none of them can guarantee \(\alpha\)-PROP1, for any constant \(\alpha > 0\).

To simplify the description of the greedy allocation strategies, we introduce some useful notation. For any timestep \(t \in [m]\) and agent \(i \in [n]\), let \(A_i^{(t)} \subseteq G^{(t)}\) denote the set of goods allocated to agent \(i\) after good \(g_t\) has been allocated. Let \(c_i^{(t)} := \max\{v_i(g) : g \in G^{(t)} \setminus A_i^{(t)}\}\), with \(c_i^{(t)}=0\) if \(G^{(t)} \setminus A_i^{(t)}=\varnothing\). Thus, \(c_i^{(t)}\) is the value, for agent \(i\), of the most valuable arrived good that is not in \(i\)’s current bundle. We then define the (unnormalized) \(\alpha\)-PROP1 value for agent \(i\) at timestep \(t\) as: \[\alpha^{(t)}_i = \frac{v_i(A^{(t)}_i) + c^{(t)}_i}{v_i(G^{(t)})} \,\, (\text{or } \infty \text{ if } v_i(G^{(t)}) = 0).\] In other words, the PROP1 ratio at timestep \(t\) is simply \(\min \{1, n\cdot \min_{i \in [n]} \alpha_i^{(t)} \}\). For the initial state when \(t = 0\), we let \(G^{(0)} = \varnothing\), \(c^{(0)}_i = 0\), and define \(\alpha^{(-1)}_i = \infty\). Then, the three greedy allocation strategies considered are as follows.

Greedy Strategy 1: At timestep \(t\), allocate good \(g_t\) to an agent from \(\mathop{\mathrm{arg\,max}}_{i \in [n]} \frac{v_i(g_t)}{v_i(G^{(t)})}\).

Greedy Strategy 2: At timestep \(t\), allocate good \(g_t\) to an agent from \(\mathop{\mathrm{arg\,min}}_{i \in [n]} \frac{v_i(A_i^{(t-1)})}{v_i(G^{(t)})}\).

Greedy Strategy 3: At timestep \(t\), allocate good \(g_t\) to an agent from \(\mathop{\mathrm{arg\,min}}_{i \in [n]} \frac{v_i(A^{(t-1)}_i) + \max\{ c^{(t-1)}_i, v_i(g_t) \}}{v_i(G^{(t)})}\).

Intuitively, the first strategy allocates the arriving good \(g_t\) to the agent which values it the most, and is commonly used for utilitarian welfare-maximizing guarantees. Meanwhile, the second strategy allocates \(g_t\) to the agent which is currently most unsatisfied and is common in offline fair division (e.g., to achieve EFX when valuations are identical in the offline setting [32], in the online setting to achieve EF1 for any number of agents when valuations are identical [16], [33]; in the fully-informed online fair division setting to get temporal EF1 under generalized binary valuations [33]; and in many other fair division settings). Finally, the third strategy directly attempts to greedily optimize the PROP1 objective itself by allocating \(g_t\) to the agent who would become the most unsatisfied if not given \(g_t\).

The following three results show that all of these natural greedy strategies fail to achieve any non-zero approximation ratio to PROP1.

These negative results highlight the fundamental limitations of greedy allocation strategies when facing adaptive adversaries. Thus, in the next two sections, we explore two approaches to overcome these barriers. In 4, we show that a random allocation strategy can achieve a non-trivial PROP1 approximation against non-adaptive adversaries. In 5, we show that access to MIV predictions enables non-trivial PROP1 approximations even against adaptive adversaries.

4 Random Allocations↩︎

We investigate the approximate PROP1 guarantee achieved by the simple algorithm Rand, which allocates each arriving good to an agent uniformly at random. [12] analyzed this algorithm in the offline fair division setting, for its incentive-compatible property (i.e., no agent will have the incentive to misreport their valuations so as to obtain a strictly better outcome). Moreover, the uniformly random allocation rule is also frequently used as a benchmark in the fair division literature, either as a point of comparison for fairness guarantees or as a baseline for empirical evaluation [11], [34]–[37]. Given the limited understanding of how to guarantee PROP1 in the online setting, this baseline provides especially valuable insights.

As mentioned earlier in the paper, to the best of our knowledge, this is the first multiplicative approximation bound for PROP1 in the online setting that holds without any additional assumptions (such as asymptotic behavior, specific valuation classes, or constraints on the arrival order of items). Achieving such a guarantee is inherently challenging under adaptive adversaries (who tailor their inputs based on the algorithm’s random decisions), often forcing worst-case outcomes that render fairness guarantees vacuous. In contrast, studying non-adaptive adversaries offers a realistic and tractable framework for evaluating randomized allocation rules in adversarial environments.

We analyze the performance of Rand against a non-adaptive adversary. By linearity of expectation, for each agent \(i \in [n]\), we have \(\mathbb{E}[v_i(A_i)] = v_i(G)/n\), i.e., Rand is proportional. However, this does not give us meaningful guarantees for the realized allocation. A more meaningful perspective is to study the tail guarantee of Rand: fixing a failure probability \(\delta > 0\), we ask: what is the largest \(\alpha\) such that Rand guarantees an \(\alpha\)-PROP1 allocation with probability at least \(1 - \delta\)?

We complement the above result with a matching upper bound which shows that this logarithmic dependence is essentially unavoidable for Rand.⁴

The above result shows that the logarithmic dependence on \(\log(n/\delta)\) in Theorem 4 is essentially tight for Rand.⁵ Intuitively, the lower bound exploits the possibility that, with non-negligible probability, some agent receives too little total value for any single additional good to compensate. On the other hand, when every individual good is sufficiently small relative to an agent’s proportional share, Rand exhibits much stronger concentration around its expectation. The following theorem formalizes this “small items” setting and shows that Rand then achieves an almost proportional outcome with high probability.

5 Maximum Item Value (MIV) Predictions↩︎

In this section, we study how maximum item value (MIV) predictions can help achieve approximate PROP1 allocations online. Prior work obtains online PROP1 under stronger informational assumptions, such as normalization information about agents’ total values [16]. Such information can be difficult to obtain in online settings, since it requires estimating an agent’s total value over the whole future sequence. In contrast, MIV predictions require significantly less information. For each agent, we assume access only to a (possibly approximate) prediction of the value of their most-preferred good among the entire sequence of arriving goods. This represents a more “lightweight” and realistic informational assumption in the online setting.

We note that MIV predictions are less demanding than normalization information. The results of [16] imply that while PROP1 is always achievable under normalization information, it is not always achievable under MIV predictions; the latter is a conclusion that can be derived from their analysis following Theorem 3.3. Similarly, while EF1 and \(1/2\)-MMS are achievable for \(n = 2\) given normalization information [5], [16], the following proposition shows that neither EF1 nor MMS can be approximated (even for \(n=2\)) when only MIV predictions are available. For completeness, we also include results for PROPX, a natural strengthening of PROP1 and another relaxation of proportionality (see Definition 4).

Given these relatively lightweight predictions, we first show that under accurate MIV predictions, it is possible to design an online algorithm that achieves a finite approximation ratio for PROP1, which scales inversely with the number of agents. Without loss of generality⁶, we assume \(\mathbf{p} = (p_1,\dots,p_n) = (1,\dots,1)\); for arbitrary \(\mathbf{p}\), one can normalize the valuations by dividing each \(v_i(g_t)\) by \(p_i\), which preserves the structure of the problem. We introduce the following algorithm (Algorithm [alg:MIV]) that is based on the following potential function, for each agent \(i \in [n]\): \[\phi_i^t = \frac{a_i^{(t)}}{(n^2+n+1)\cdot a_i^{(t)} + n^2\cdot v_i(A_i \setminus \{g_{r_i}\})\cdot a_i^{(t)} - 1}.\]

Before presenting the guarantee, we explain the role of the variables in the potential function. The variable \(r_i\) is the first time at which agent \(i\) sees a good whose normalized value is \(1\); before this happens, \(r_i=\infty\). The good \(g_{r_i}\), once it arrives, accounts for the “one good” allowed in the PROP1 comparison: if it is outside \(A_i\), it can be added to \(i\)’s bundle, and if it is already in \(A_i\), then \(i\)’s bundle already contains that value.

The term \(a_i^{(t)}\) scales the total value that must be covered after allowing for this one good. Before \(r_i\) occurs, the algorithm reserves room for a future value-\(1\) good by using \(a_i^{(t)} = 1/(1+v_i(G^{(t)}))\). After \(r_i\) occurs, that good is known, and the potential uses \(A_i^{(t)}\setminus\{g_{r_i}\}\). A smaller potential means that agent \(i\) is farther from violating the \(1/n\)-PROP1 target. Next, the potential function \(\phi_i^t\) measures how close agent \(i\) is to violating the \(\frac{1}{n}\)-PROP1 guarantee. A lower potential value indicates a more favorable state. We visualize how \(\phi_i^t\) behaves with respect to different values of \(a_i^{(t)}\) and the product \(v_i(A_i \setminus\{r_i\})\cdot a_i^{(t)}\).

This potential function captures two key intuitions: (1) when \(v_i(A_i \setminus\{r_i\})\cdot a_i^{(t)}\) is large, it is better for \(a_i^{(t)}\) to be small, indicating that future goods are relatively small compared to \(v_i(G)\), and thus will not significantly reduce agent \(i\)’s surplus; (2) conversely, when \(v_i(A_i \setminus\{r_i\})\cdot a_i^{(t)}\) is small, it is preferable for \(a_i^{(t)}\) to be large, ensuring that the algorithm does not need to allocate a low-valued good to agent \(i\) merely to avoid violating the \(\frac{1}{n}\)-PROP1 condition.

Then, our result is as follows.

To the best of our knowledge, the above result gives the first finite multiplicative approximation guarantee known for any proportionality-type benchmark in this adversarial online setting under such weak predictive information. Determining the optimal dependence on \(n\), even with access to these predictions, remains an interesting open problem.

Next, we extend our results to account for one-sided error⁷ in the MIV predictions, i.e., when each agent’s predicted MIV overestimates their true maximum value. The following theorem shows that any algorithm designed for perfect predictions can be made robust to such errors, while degrading gracefully in its guarantees. Note that the approximation ratio achieved is non-trivial as long as \(\varepsilon<1\) and smoothly recovers the original approximation ratio when \(\varepsilon=0\).

By combining Theorem 8 and Theorem 9, we obtain the following corollary, which provides a robustness guarantee for our algorithm under one-sided prediction error.

Discussion. Standard lower bound constructions in online fair division rely on hiding whether a large future item exists [5], [16]. However, MIV predictions reveal precisely the scale of any future item value, which breaks standard hardness constructions for PROP1. Any tight lower bound would therefore need to fix the entire MIV vector while encoding hardness in the residual tail and arrival order, which is substantially more subtle. Thus, 7 provides a strong partial lower bound that even with perfect MIV predictions, stronger notions (EF1, MMS, PROPX) remain inapproximable, suggesting that our positive result is highly specific to PROP1.

Empirical comparisons. In addition to our theoretical analysis, we empirically compared [alg:MIV] with the three greedy baselines described in 3.⁸

We first normalize each agent’s values by her maximum item value, as in the MIV-normalized view of Algorithm 1. For an allocation \(A\), we measure fairness by the realized PROP1 ratio \(\min_{i \in [n]} \min \{1, n (v_i(A_i)+\max_{g \in G\setminus A_i} v_i(g) )/{v_i(G)} \}\), with ratio \(1\) for agents with \(v_i(G)=0\) or \(A_i=G\), and measure efficiency by utilitarian welfare normalized by the ex-post optimum, \(\sum_i v_i(A_i)/\sum_{g\in G}\max_i v_i(g)\). We use \(n=8\), \(m=40\), and \(500\) independent trials for each of four instance families: iid uniform values; dense binary-interest instances, where each agent values each good with probability \(0.6\) and positive values lie in \([0.8,1]\); correlated values of the form \(0.5U_g+0.5U_{i,g}\); and specialist instances, where each good has one high-value specialist and all other agents have small residual values. Error bars in Figure 2 are 95% confidence intervals.

The results are consistent with our theory. Algorithm [alg:MIV] achieved PROP1 on every sampled instance. Its normalized welfare was \(0.892\), \(0.960\), \(0.905\), and \(0.781\) on the uniform, dense, correlated, and specialist families, respectively. Greedy-1 achieved welfare \(0.946\), \(0.954\), \(0.965\), and \(0.967\) on the same families, but with realized PROP1 ratios \(0.775\), \(0.423\), \(0.730\), and \(0.977\). Thus, Greedy-1 often attains high welfare, but its PROP1 ratio can fall substantially; in the uniform and correlated families this reflects a welfare–fairness tradeoff, while in the dense family Algorithm [alg:MIV] slightly improves both welfare and fairness. On easy specialist instances, Greedy-1 has higher welfare with little fairness loss. Greedy-2 and Greedy-3 were at or near PROP1 on these benign random instances, but their welfare was substantially lower: \(0.639/0.711\) on uniform instances, \(0.677/0.747\) on dense instances, \(0.746/0.770\) on correlated instances, and \(0.300/0.400\) on specialist instances. We also stress-tested the explicit counterexample families from Section 3. On prefixes of length roughly \(500\), the targeted greedy baselines have realized PROP1 ratios \(0.008\), \(0.008\), and \(0.385\) for the Greedy-1, Greedy-2, and Greedy-3 constructions, respectively, while Algorithm 1 obtains \(0.920\), \(1.000\), and \(1.000\) on the same prefixes.

6 Conclusion↩︎

In this work, we initiate a study of approximate proportionality in online fair division, a setting where many classic fairness notions admit strong impossibility results. Our results present a clear boundary between impossibility under adversarial uncertainty, and what becomes achievable with modest relaxations. On the negative side, we show that several natural greedy baseline algorithms can fail to guarantee any multiplicative approximation to PROP1 against an adaptive adversary, highlighting the challenges of online decision making under worst-case arrivals. On the positive side, we identify two complementary paths to robust guarantees: (i) under a non-adaptive adversary, we show that the randomized allocation gives us meaningful PROP1 guarantees with high probability against non-adaptive adversaries; (ii) lightweight predictions such as estimates of maximum item values can admit robust PROP1 approximations against adaptive adversaries. These results position PROP1 as a fairness notion that is both theoretically informative and algorithmically tractable in online settings, relative to EF1, MMS, and PROPX.

Several questions remain open. Most notably, can one obtain any nontrivial approximation to PROP1 without predictive or structural assumptions? Beyond known impossibility results, no approximation bounds are currently established in this setting, and resolving this remains a key challenge.

Acknowledgments↩︎

Nicholas Teh was supported by the Advanced Research + Invention Agency (ARIA) as part of the ASPAI project.

Impact Statement↩︎

This paper presents work whose goal is to advance the theory of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

7 Further Related Work↩︎

7.0.0.1 Learning-Augmented Algorithms.

Since the seminal work of [1], there has been a surge of interest in incorporating unreliable advice into algorithm design and analyzing performance as a function of advice quality across various areas of computer science. This framework has been especially successful in online optimization, where the core challenge lies in handling uncertainty about future inputs. In this context, advice can serve as a useful proxy for the unknown future. Most previous works in this setting are in the context of online algorithms, e.g.for the ski-rental problem [38]–[40], non-clairvoyant scheduling [3], scheduling [4], [41], [42], augmenting classical data structures with predictions (e.g.indexing [43] and Bloom filters [44]), online selection and matching problems [45]–[48], online TSP [49], [50], and a more general framework of online primal-dual algorithms [51]. However, there have been some recent applications to other areas, e.g.graph algorithms [52], [53], causal learning [54], mechanism design [8], [9], distribution learning [55], [56], and approval elicitation [57]. For an overview of this growing area, we refer the reader to the survey by [2].⁹

7.0.0.2 Online Voting.

Beyond fair division, online and temporal models have also been studied in voting, which can be viewed as a public goods setting since the selected outcomes are shared by all voters. For instance, the multiwinner voting literature contains a growing body of work on online and temporal candidate or committee selection [58]–[70].

8 Omitted Proofs from Section 3↩︎

8.1 Proof of Proposition 3↩︎

9 Omitted Proofs from Section 4↩︎

9.1 Proof of Theorem 4↩︎

Fix an agent \(i \in [n]\). Let \(\alpha := \frac{3}{32\log{(n/\delta)}}\). We will first show that for \(g := \mathop{\mathrm{arg\,max}}_{g' \in G \setminus A_i}v_i(g)\), \[\label{eqn:thm:random951} \Pr\left[v_i(A_i \cup \{g\}) < \alpha \cdot \frac{v_i(G)}{n} \right] \leq \frac{\delta}{n}.\tag{4}\] Once the above is proved, a union bound over all \(n\) agents will imply that the probability the allocation is \(\alpha\)-PROP1 is at least \(1-\delta\).

Then, since there exists a \(g \in G \setminus A_i\) such that \(v_i(A_i \cup \{g\}) \geq \max_{j \in [m]} v_i(g_j)\), if \(\max_{j \in [m]} v_i(g_j) \geq\alpha \cdot \frac{v_i(G)}{n}\), we get that \[v_i(A_i \cup \{g\}) \geq \max_{j \in [m]} v_i(g_j) \geq\alpha \cdot \frac{v_i(G)}{n}\] and equivalently, \(\Pr\left[v_i(A_i \cup \{g\}) < \alpha \cdot \frac{v_i(G)}{n}\right] = 0\), giving us (4 ) as desired. Thus, it suffices to consider the case when \(\max_{j \in [m]} v_i(g_j) < \alpha \cdot \frac{v_i(G)}{n}\).

Consider any agent \(i \in [n]\). Define \(X_j := \mathbf{1}\{g_j \in A_i\}\) and \(X'_j := 1 - X_j = \mathbf{1}\{g_j \notin A_i\}\). Then, we have that \(X_1,\dots,X_m \sim \text{Bernoulli}(1/n)\) and \(X'_1,\dots,X'_m \sim \text{Bernoulli} \left(\frac{n-1}{n} \right)\). Let \(S_i = \sum_{j \in [m]} \left( v_i(g_j) \cdot X_j \right)\) be a random variable representing \(v_i(A_i)\); and let \(S'_i = \sum_{j \in [m]} \left( v_i(g_j) \cdot X'_j \right)\). Now, for each \(i \in [n]\), \(S_i = v_i(G) - S'_i\), \[\begin{align} \Pr\left[v_i(A_i \cup \{g\}) < \frac{\alpha \cdot v_i(G)}{n} \right] & \leq \Pr\left[v_i(A_i) < \frac{\alpha \cdot v_i(G)}{n} \right] \\ &= \Pr\left[S_i < \frac{\alpha \cdot v_i(G)}{n} \right] \\ &= \Pr\left[S'_i > \frac{(n-1) \cdot v_i(G)}{n} + \frac{(1-\alpha) \cdot v_i(G)}{n} \right] \end{align}\]

We now prove several properties of the random variable \(S'_i\), relating to its expectation, variance, and the individual terms \(v_i(g_j) \cdot X'_j\) in the summation.

We now state Bernstein’s inequality, which we will use for the proof.

We can then apply Bernstein’s inequality to \(S'_i\). By setting \(t = \frac{(1-\alpha) \cdot v_i(G)}{n}\) and \(b = \alpha \cdot \frac{v_i(G)}{n}\), we get \[\begin{align} \Pr\left[S'_i > \frac{(n-1) \cdot v_i(G)}{n} + \frac{(1-\alpha) \cdot v_i(G)}{n} \right] = \Pr\left[S'_i > \mathbb{E}[S'] + t \right] \leq \exp\left( -\frac{t^2}{2\sigma^2 + 2bt/3} \right), \end{align}\] where the equality follows from property (i) of Lemma 2. We also note that Bernstein’s inequality is applicable due to property (iii) of Lemma 2.

Since our goal is to find an upper bound to our expression, it suffices to use a lower bound on the numerator \(t^2\), and an upper bound for the denominator \(2\sigma^2 + 2bt/3\).

For the numerator \(t^2\), since \(\alpha = \frac{3}{32\log{(n/\delta)}} < \frac{1}{2}\) for all \(n\geq 2\), we have that \[t^2 = \frac{(1-\alpha)^2 \cdot v_i(G)^2}{n^2} \geq \frac{v_i(G)^2}{4n^2}\]

For the denominator \(2\sigma^2 + 2bt/3\), by bounding our variance with property (ii) of Lemma 2, we have that \[\begin{align} 2\sigma^2 + \frac{2bt}{3} &\leq \frac{2\alpha \cdot v_i(G)^2}{n^2} + \frac{2\alpha(1-\alpha) \cdot v_i(G)^2}{3n^2} < \frac{2\alpha \cdot v_i(G)^2}{n^2} + \frac{2\alpha \cdot v_i(G)^2}{3n^2} = \frac{8\alpha \cdot v_i(G)^2}{3n^2} , \end{align}\] where the second inequality follows from the fact that \(\alpha >0\) and hence \(1-\alpha < 1\). Thus, we get that \[\begin{align} \exp\left( -\frac{t^2}{2\sigma^2 + 2bt/3} \right) \leq \exp\left( -\frac{\frac{v_i(G)^2}{4n^2}}{ \frac{8\alpha \cdot v_i(G)^2}{3n^2} } \right) = \exp\left( -\frac{3}{32\cdot\alpha} \right) = \exp\left( - \ln(n/\delta)\right) = \frac{\delta}{n}, \end{align}\] giving us (4 ). Then, by summing the bound in (4 ) over the \(n\) agents: the probability that any agent violates the \(\alpha\)-PROP1 condition is at most \(n \cdot \frac{\delta}{n} = \delta\). Therefore, with probability at least \(1-\delta\), for every agent \(i \in [n]\) and \(g := \max_{g' \in G \setminus A_i} v_i(g')\), \[v_i(A_i \cup \{g\}) \geq \alpha \cdot \frac{v_i(G)}{n},\] and the allocation returned is \(\alpha\)-PROP1.

9.2 Proof of 5↩︎

Let \[\label{eq:def95m95tight} m := \left\lfloor \frac{\log\left(\frac{n}{2\delta}\right)}{\log\left(\frac{n}{n-1}\right)} \right\rfloor \quad\text{and}\quad \alpha := \frac{2n}{m}.\tag{5}\]

Consider the instance with \(m\) goods \(G=\{g_1,\dots,g_m\}\) where all agents have identical additive valuations \[v_i(g_j)=1 \text{ for all } i\in[n] \text{ and } j\in[m].\] Assume a non-adaptive adversary. Run Rand, which allocates each good independently and uniformly at random to one of the \(n\) agents. Let \(\mathcal{A}=(A_1,\dots,A_n)\) denote the (random) final allocation. For each agent \(i\in[n]\), define the event \[E_i := \{A_i=\varnothing\},\] i.e., agent \(i\) receives no goods. For a fixed agent \(i\), \[\Pr[E_i] = \left(1-\frac{1}{n}\right)^m,\] and for distinct \(i\neq j\), \[\Pr[E_i\cap E_j] = \left(1-\frac{2}{n}\right)^m.\] Let \(p_1 := (1-\frac{1}{n})^m\) and \(p_2 := (1-\frac{2}{n})^m\). By the first two terms of Bonferroni inequalities, \[\label{eq:bonferroni} \Pr\left[\bigcup_{i=1}^n E_i\right]\ge \sum_{i=1}^n \Pr[E_i] - \sum_{1\le i<j\le n} \Pr[E_i\cap E_j] = n p_1 - \binom{n}{2} p_2.\tag{6}\] Moreover, since \((1-\frac{1}{n})^2 = 1-\frac{2}{n}+\frac{1}{n^2} \ge 1-\frac{2}{n}\), we have \(p_2 \le p_1^2\). Plugging this into 6 gives us \[\label{eq:bonferroni2} \Pr\left[\bigcup_{i=1}^n E_i\right] \geq n p_1 - \binom{n}{2} p_1^2 = n p_1\left(1-\frac{(n-1)p_1}{2}\right).\tag{7}\] We now lower bound \(p_1\). Define \[m_0 := \frac{\log\left(\frac{n}{2\delta}\right)}{\log\left(\frac{n}{n-1}\right)}.\] By definition, \(m=\lfloor m_0\rfloor\), so \(m\le m_0 < m+1\). Since \(1-\frac{1}{n}\in(0,1)\), the function \(f(x) = (1-\frac{1}{n})^x\) is decreasing. Thus, \[p_1 = \left(1-\frac{1}{n}\right)^m \;\ge\;\left(1-\frac{1}{n}\right)^{m_0}.\] Using \(1-\frac{1}{n}=\frac{n-1}{n}=\left(\frac{n}{n-1}\right)^{-1}\), we get \[\left(1-\frac{1}{n}\right)^{m_0} = \left(\frac{n}{n-1}\right)^{-m_0} = \exp\left(-\log\!\left(\frac{n}{n-1}\right)\cdot \frac{\log(\frac{n}{2\delta})}{\log(\frac{n}{n-1})}\right) = \exp\left(-\log\left(\frac{n}{2\delta}\right)\right) = \frac{2\delta}{n}.\] Therefore, \[\label{eq:p195lower} p_1 \ge \frac{2\delta}{n}.\tag{8}\] Similarly, since \(m_0 < m+1\), \[\left(1-\frac{1}{n}\right)^{m+1} < \left(1-\frac{1}{n}\right)^{m_0} = \frac{2\delta}{n},\] and thus \[\label{eq:p195upper} p_1 = \left(1-\frac{1}{n}\right)^m = \frac{\left(1-\frac{1}{n}\right)^{m+1}}{1-\frac{1}{n}} < \frac{\frac{2\delta}{n}}{\frac{n-1}{n}} = \frac{2\delta}{n-1}.\tag{9}\] Plugging 8 and 9 into 7 , we get \[\Pr\left[\bigcup_{i=1}^n E_i\right] \ge n\cdot \frac{2\delta}{n}\left(1-\frac{(n-1)}{2}\cdot \frac{2\delta}{n-1}\right) = 2\delta(1-\delta) \ge \delta,\] where the last inequality uses \(\delta\le 1/2\).

Now condition on the event \(\bigcup_{i=1}^n E_i\): there exists an agent \(i\) with \(A_i=\varnothing\). For that agent, \(v_i(G)=m\) and for any good \(g\in G\setminus A_i\) we have \(v_i(A_i\cup\{g\}) = 1\). But by the choice of \(\alpha\) in 5 , \[\alpha \cdot \frac{v_i(G)}{n} = \frac{2n}{m}\cdot \frac{m}{n} =2.\] Hence \(v_i(A_i\cup\{g\})=1 < 2 = \alpha\cdot \frac{v_i(G)}{n}\) for all \(g\in G\setminus A_i\), so the allocation is not \(\alpha\)-PROP1. Therefore, the probability that Rand outputs an allocation that is not \(\alpha\)-PROP1 is at least \[\Pr\left[\bigcup_{i=1}^n E_i\right] \ge \delta.\] Finally, we show \(\alpha=\Theta(1/\log(n/\delta))\). Since for \(x\in(0,1)\), \(x \le -\log(1-x) \le \frac{x}{1-x}\), plugging in \(x=\frac{1}{n}\) gives us \[\frac{1}{n} \le \log\left(\frac{n}{n-1}\right) \le \frac{1}{n-1}.\] Thus, \(m_0=\frac{\log(n/(2\delta))}{\log(n/(n-1))}\) satisfies \[(n-1)\log\left(\frac{n}{2\delta}\right) \le m_0 \le n\log\left(\frac{n}{2\delta}\right),\] and therefore \(m=\lfloor m_0\rfloor=\Theta(n\log(n/\delta))\) (since \(\delta\le 1/2\) implies \(\log(n/(2\delta))=\Theta(\log(n/\delta))\)). Consequently, \[\alpha=\frac{2n}{m}=\Theta\left(\frac{1}{\log(n/\delta)}\right),\] as claimed.

9.3 Proof of 6↩︎

Fix an agent \(i\in[n]\). If \(v_i(G)=0\), then \(v_i(A_i)=0=(1-\varepsilon)\cdot v_i(G)/n\) always, and the claim holds trivially for this agent. Thus, assume \(v_i(G)>0\).

Under Rand, each good is allocated independently and uniformly at random to one of the \(n\) agents. For each \(j\in[m]\), let \(X_{j}\sim\mathrm{Bernoulli}(1/n)\) indicate that \(g_j\) is allocated to agent \(i\). Define \(X'_j := 1-X_j\), so \(X'_j\sim\mathrm{Bernoulli}((n-1)/n)\) indicates that \(g_j\) is not allocated to \(i\). Define \[S_i := \sum_{j=1}^m v_i(g_j)X_j = v_i(A_i) \quad\text{and}\quad S'_i := \sum_{j=1}^m v_i(g_j)X'_j.\] Since \(X'_j = 1-X_j\), we have that \[\label{eq:Si95complement} S'_i = v_i(G) - S_i.\tag{10}\] Moreover, \[\mathbb{E}[S'_i] = \sum_{j=1}^m v_i(g_j) \mathbb{E}[X'_j] = \frac{n-1}{n}\sum_{j=1}^m v_i(g_j) = \frac{n-1}{n} v_i(G).\]

We will upper bound the probability that agent \(i\) receives less than a \((1-\varepsilon)\) fraction of their proportional share: \[\Pr\left[S_i < (1-\varepsilon)\cdot \frac{v_i(G)}{n}\right].\] Using 10 , this event is equivalent to \[S'_i > v_i(G) - (1-\varepsilon)\cdot \frac{v_i(G)}{n} = \frac{n-1+\varepsilon}{n}v_i(G) = \mathbb{E}[S'_i] + \varepsilon\cdot \frac{v_i(G)}{n}.\] Thus, letting \(t := \varepsilon\cdot \frac{v_i(G)}{n}\), \[\label{eq:reduce95to95upper95tail} \Pr\left[S_i < (1-\varepsilon)\cdot \frac{v_i(G)}{n}\right] = \Pr\left[S'_i > \mathbb{E}[S'_i] + t\right].\tag{11}\] Because the adversary is non-adaptive, the values \(v_i(g_j)\) are fixed in advance (deterministic). Rand assigns each good independently, so the random variables \(Y_j = v_i(g_j)X'_j\) are independent, allowing us to apply Bernstein’s inequality. Thus, we now apply Bernstein’s inequality (refer to 3) to the sum \(S'_i=\sum_{j=1}^m Y_j\) where \(Y_j:=v_i(g_j)X'_j\). First, each summand satisfies \[Y_j - \mathbb{E}[Y_j] \le Y_j \le v_i(g_j) \le \max_{g\in G} v_i(g),\] so Bernstein applies with \(b:=\max_{g\in G} v_i(g)\). Second, since the \(X'_j\) are independent Bernoulli\(((n-1)/n)\), \[\mathrm{Var}(Y_j) = v_i(g_j)^2 \mathrm{Var}(X'_j) = v_i(g_j)^2 \cdot \frac{n-1}{n}\cdot\frac{1}{n} = v_i(g_j)^2\cdot \frac{n-1}{n^2} \le \frac{v_i(g_j)^2}{n}.\] By independence, \[\sigma^2 := \mathrm{Var}(S'_i) = \sum_{j=1}^m \mathrm{Var}(Y_j) \le \frac{1}{n}\sum_{j=1}^m v_i(g_j)^2 \le \frac{\max_{g\in G} v_i(g)}{n}\sum_{j=1}^m v_i(g_j) = \frac{\max_{g\in G} v_i(g) \cdot v_i(G)}{n},\] where we used \(v_i(g_j)^2 \le \max_{g\in G} v_i(g) \cdot v_i(g_j)\) (and \(v_i(g_j)\ge 0\)).

Applying Bernstein’s inequality with this \(b\) and \(\sigma^2\) gives us \[\Pr\left[S'_i > \mathbb{E}[S'_i] + t\right] \leq \exp\left(-\frac{t^2}{2\sigma^2 + 2bt/3} \right).\] Substituting \(t=\varepsilon\cdot \frac{v_i(G)}{n}\) and using \(\sigma^2 \le \frac{\max_{g\in G} v_i(g) \cdot v_i(G)}{n}\) and \(b=\max_{g\in G} v_i(g)\), \[2\sigma^2 + \frac{2}{3}bt \le 2\cdot \frac{\max_{g\in G} v_i(g) \cdot v_i(G)}{n} + \frac{2}{3} \max_{g\in G} v_i(g)\cdot \varepsilon\cdot \frac{v_i(G)}{n} \le \frac{8}{3}\cdot \frac{\max_{g\in G} v_i(g) \cdot v_i(G)}{n},\] where we used \(\varepsilon\le 1\) in the last inequality. Therefore, \[\Pr\left[S'_i > \mathbb{E}[S'_i] + t\right] \le \exp\left( -\frac{\varepsilon^2 \cdot \frac{v_i(G)^2}{n^2}}{\frac{8}{3}\cdot \frac{\max_{g\in G} v_i(g) \cdot v_i(G)}{n}} \right) = \exp\left( -\frac{3\varepsilon^2}{8}\cdot \frac{\frac{v_i(G)}{n}}{\max_{g\in G} v_i(g)} \right).\] Since \(\max_{g \in G} v_i(g) \leq \frac{3 \varepsilon^2}{8 \log(n/\delta)} \cdot \frac{v_i(G)}{n}\), \[\frac{3\varepsilon^2}{8}\cdot \frac{\frac{v_i(G)}{n}}{\max_{g\in G} v_i(g)} \ge \log\left(\frac{n}{\delta}\right),\] so \[\Pr\left[S'_i > \mathbb{E}[S'_i] + t\right] \le \exp\left(-\log\left(\frac{n}{\delta}\right)\right) = \frac{\delta}{n}.\] Combining with 11 , we get \[\Pr\left[v_i(A_i) < (1-\varepsilon)\cdot \frac{v_i(G)}{n}\right] \le \frac{\delta}{n}.\] A union bound over all agents \(i\in[n]\) implies that with probability at least \(1-\delta\), \[\label{eq:near95proportional95stronger} v_i(A_i) \ge (1-\varepsilon)\cdot \frac{v_i(G)}{n} \quad\text{for all } i\in[n].\tag{12}\]

Finally, 12 implies \((1-\varepsilon)\)-PROP1: for any agent \(i\), if \(A_i=G\) we are done; otherwise pick any \(g\in G\setminus A_i\), and \[v_i(A_i\cup\{g\}) \;\ge\;v_i(A_i) \;\ge\;(1-\varepsilon)\cdot \frac{v_i(G)}{n}.\] Thus the allocation is \((1-\varepsilon)\)-PROP1 with probability at least \(1-\delta\).

10 Omitted Proofs from Section 5↩︎

10.1 Proof of Proposition 7↩︎

Suppose for a contradiction that there exists an online algorithm that achieves an approximation ratio of \(\alpha\) for EF1, MMS, or PROPX. Let \(v_i(g_1) = 1\) for all \(i \in [n]\), and assume without loss of generality that agent \(1\) is allocated \(g_1\).

We now define an instance with \(m\) goods. Let \(v_i(g_1) = 1\) for all \(i \in [n]\), and for each \(t \in \{2,\dots,m\}\), the valuations are as follows:

\[v_1(g_t) = \begin{cases} 1 \quad \text{if |A_1^t| = 1 or t \leq n} \\ 0 \quad \text{otherwise} \end{cases}\] \[v_i(g_t) = \begin{cases} \varepsilon K^{t-2}\quad \text{if |A_1^t| = 1 or t \leq n} \\ 0 \quad \text{otherwise} \end{cases}\] where \(m = \lceil \frac{n}{\alpha}\rceil+n+2\), \(K = \lceil\frac{3}{\alpha}\rceil\), and \(\varepsilon = \frac{1}{K^{m-2}}\). Since every good has value at most 1 for all agents, this construction is consistent with the MIV prediction with \(\mathbf{p} = (1,\dots,1)\).

We split our analysis into two cases.

Case 1: \(|A_1| = 1\).

Then, by the assumption that agent \(1\) is allocated \(g_1\), agents’ valuations for incoming goods must be as follows:

\(\mathbf{v}\)	\(g_1\)	\(g_2\)	\(g_3\)	\(\dots\)	\(g_{m}\)
\(1\)	\(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {1};}\)	\(1\)	\(1\)	\(\dots\)	\(1\)
\(2\)	\(1\)	\(\varepsilon\)	\(\varepsilon K\)	\(\dots\)	\(\varepsilon K^{m-2}\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(n\)	\(1\)	\(\varepsilon\)	\(\varepsilon K\)	\(\dots\)	\(\varepsilon K^{m-2}\)

Note that since \[\label{eqn:impossibility95m} m = \left\lceil \frac{n}{\alpha} \right\rceil + n + 2 \geq \frac{n}{\alpha} + n + 2,\tag{13}\] we have that \[\label{eqn:impossibility95alpha} \alpha \geq \frac{n}{m-n-2}> \frac{n}{m-n-1}.\tag{14}\] Furthermore, as \(|A_1|=1\), we get that \(v_1(A_1) = v_1(g_1) = 1\). We first show a contradiction to \(\alpha\)-EF1. Since \(|A_1| = 1\), by the pigeonhole principle, there must exist an agent \(i \neq 1\) that receives at least \(\lceil\frac{m-1}{n-1}\rceil \geq \frac{m-1}{n-1} > \frac{m-1}{n}\) goods. Thus, there exists a good \(g \in A_i\) such that \[v_1(A_i \setminus\{g\})\geq \frac{m-1}{n} - 1 = \frac{m-n-1}{n}.\] Consequently, we get that \[\frac{v_1(A_1)}{v_1(A_i\setminus\{g\})} \leq \frac{n}{m-n-1} < \alpha,\] where the rightmost inequality follows from (14 ), giving us \[v_1(A_1) < \alpha \cdot v_1(A_i \setminus \{g\}),\] a contradiction.

Next, we show a contradiction to \(\alpha\)-MMS. Note that \[\textsf{MMS}_1 = \left\lfloor \frac{m}{n} \right\rfloor \geq \frac{m}{n} -1 = \frac{m-n}{n}.\] Then, \[\frac{v_1(A_1)}{\textsf{MMS}_1} \leq \frac{n}{m-n} < \alpha,\] where again, the rightmost inequality follows from (14 ), giving us \[v_1(A_1) < \alpha \cdot \textsf{MMS}_1,\] a contradiction.

Finally, we show a contradiction to \(\alpha\)-PROPX. From (13 ) and the fact that \(\alpha \leq 1\), we get that \(m \geq 2n+2\).

Observe that for \(g \in \mathop{\mathrm{arg\,min}}_{g' \in G \setminus A_1} v_1(g')\), we have that \[v_1(A_1 \cup \{g\}) = 1+1=2.\] Together with the fact that \(v_1(G) = m\), we obtain \[\begin{align} \frac{n}{v_1(G)} \cdot v_1(A_1 \cup \{g\}) = \frac{2n}{m} & \leq \frac{2n}{2n+2} \\ & = \frac{n}{n+1} \\ & \leq \frac{n}{m-n-1} < \alpha, \end{align}\] where the last inequality follows from (14 ). This gives us \(v_i(A_1 \cup \{g\}) < \alpha \cdot \frac{v_1(G)}{n}\), a contradiction.

Case 2: \(|A_1| > 0\).

Let \(g_t\) be the first good after \(g_1\) that agent \(1\) receives. We further split our analysis into two sub-cases: (a) \(t \leq n\) and (b) \(t \geq n+1\).

Case 2(a): \(t \leq n\).

Then agents’ valuations for incoming goods must be as follows:

\(\mathbf{v}\)	\(g_1\)	\(g_2\)	\(\cdots\)	\(g_t\)	\(\cdots\)	\(g_{n}\)
\(1\)	\(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {1};}\)	\(1\)	\(\cdots\)	\(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {1};}\)	\(\cdots\)	\(1\)
\(2\)	\(1\)	\(\varepsilon\)	\(\cdots\)	\(\varepsilon K^{t-2}\)	\(\cdots\)	\(\varepsilon K^{n-2}\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(n\)	\(1\)	\(\varepsilon\)	\(\cdots\)	\(\varepsilon K^{t-2}\)	\(\cdots\)	\(\varepsilon K^{n-2}\)

and if \(n < m\), \(v_i(g_j) = 0\) for all \(i \in [n]\) and \(j \in \{n+1,\dots, m\}\). Since agent \(1\) receives two goods out of the first \(n\) goods, by the pigeonhole principle, there necessarily exists an agent \(i \in [n] \setminus \{1\}\) that does not receive any good out of the first \(n\) goods, and \(v_i(A_i) = 0\). Also, as \(v_i(A_1\setminus\{g\}) \geq \varepsilon K^{t-2}\) (for \(g := \mathop{\mathrm{arg\,max}}_{g \in A_1} v_i(g)\)), we have that \[\frac{v_i(A_i)}{v_i(A_1\setminus\{g\})} \leq \frac{0}{\varepsilon K^{t-2}}< \alpha,\] giving us \(v_i(A_i) < \alpha \cdot v_i(A_1 \setminus \{g\})\), a contradiction to \(\alpha\)-EF1.

Furthermore, as \(\textsf{MMS}_i = v_i(g_2) = \varepsilon\), we have that

\[\frac{v_i(A_i)}{\textsf{MMS}_i} \leq \frac{0}{\varepsilon} < \alpha,\] giving us \(v_i(A_i) < \alpha \cdot \textsf{MMS}_i\), a contradiction to \(\alpha\)-MMS.

Next, we prove a contradiction to \(\alpha\)-PROPX. Again let \(i\) be the agent that does not receive any good out of the first \(n\) goods (as reasoned above). First observe that \[v_i(G) = 1 + \sum_{j=2}^n \varepsilon K^{j-2} = 1+\frac{\varepsilon (K^{n-1} - 1)}{K-1}.\] Also, since \(K = \lceil \frac{3}{\alpha} \rceil\), it implies \(\alpha > \frac{3}{K}\). Since \(\alpha \leq 1\), it also means \(K > 3\). Consequently, we have that \[3 K^{n-3} \geq 3 \cdot 3^{n-3} = 3^{n-2} \geq n,\] giving us \(n \leq 3 K^{n-3}\), which is equivalent to \[\frac{n}{K^{n-2}} \leq \frac{3}{K} < \alpha.\]

Moreover, for \(g:= \mathop{\mathrm{arg\,min}}_{g' \in G \setminus A_i} v_i(g')\), we have \(v_i(A_i\cup \{g\}) = 0 + v_i(g_2) = \varepsilon\).

Combining all the facts above, we get that \[\begin{align} \frac{n \cdot v_i(A_i \cup \{g\})}{v_i(G)} & = \frac{n \cdot \varepsilon}{1+\frac{\varepsilon (K^{n-1}-1)}{K-1}} \\ & \leq \frac{n \cdot \varepsilon}{\frac{\varepsilon (K^{n-1}-1)}{K-1}} \\ & = \frac{n(K-1)}{K^{n-1}-1} \\ & \leq \frac{n(K-1)}{K^{n-2}(K-1)} \\ & = \frac{n}{K^{n-2}} \\ & < \alpha, \end{align}\] giving us \(v_i(A_i \cup \{g\}) < \alpha \cdot \frac{v_i(G)}{n}\), a contradiction.

Case 2(b): \(t > n+1\).

Then agents’ valuations for incoming goods must be as follows:

\(\mathbf{v}\)	\(g_1\)	\(g_2\)	\(\cdots\)	\(g_t\)
\(1\)	\(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {1};}\)	\(1\)	\(\cdots\)	\(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {1};}\)
\(2\)	\(1\)	\(\varepsilon\)	\(\cdots\)	\(\varepsilon K^{t-2}\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(n\)	\(1\)	\(\varepsilon\)	\(\cdots\)	\(\varepsilon K^{t-2}\)

and if \(t < m\), \(v_i(g_j) = 0\) for all \(i \in [n]\) and \(j \in \{t+1,\dots,m\}\).

Consider the set \(\{g_{t+2-n}, \dots, g_t\}\). Since the set contains \(n-1\) goods and agent \(1\) is allocated \(g_t\), by the pigeonhole principle, there exists an agent \(i \in [n] \setminus \{1\}\) that does not receive any good in \(\{g_{t+2-n}, \dots, g_t\}\). Hence, \[\begin{align} v_i(A_i) \leq \sum_{j = 2}^{t+1-n} \varepsilon \cdot K^{j-2} = \sum_{j' = 0}^{t-1-n} \varepsilon \cdot K^{j'} \leq \frac{\varepsilon (K^{t-n}-1)}{K-1} \leq \frac{2\varepsilon (K^{t-n}-1)}{K} \leq \frac{2}{K} \left(\varepsilon K^{t-n} \right). \end{align}\] Moreover, since \(K = \lceil\frac{3}{\alpha}\rceil \geq \frac{3}{\alpha}\) and \(\alpha\leq 1\), we know that \(K \geq 2\), \(\frac{1}{K-1} \leq \frac{2}{K}\), and \(\alpha \geq \frac{3}{K} > \frac{2}{K}\).

We now show a contradiction to \(\alpha\)-EF1. Since \(v_i(g_1) \geq v_i(g_t)\), we have that \[v_i(A_1 \setminus \{g_1\}) = v_i(g_t) = \varepsilon K^{t-2} \geq \varepsilon K^{t-n},\] where the last inequality follows from the fact that \(n \geq 2\). This means there exists a \(g \in A_1\) whereby \[\frac{v_i(A_i)}{v_i(A_1\setminus\{g\})} \leq \frac{ \frac{2}{K} \left(\varepsilon K^{t-n} \right)}{\varepsilon K^{t-n}} = \frac{2}{K}< \alpha,\] and implies \(v_i(A_i) < \alpha \cdot v_i(A_i \setminus \{g\})\), a contradiction.

Furthermore, consider the set of \(n\) goods \(G' = \{g_{t+2-n}, \dots, g_t\} \cup \{g_1\}\). We have that \[\textsf{MMS}_i \geq \min_{g \in G'} v_i(g) = v_i(g^{t_2-n}) = \varepsilon K^{t-n}.\] Thus, we get \[\frac{v_i(A_i)}{\textsf{MMS}_i} \leq \frac{ \frac{2}{K} \left(\varepsilon K^{t-n} \right)}{\varepsilon K^{t-n}} \leq \frac{2}{K}< \alpha,\] giving us \(v_i(A_i) < \alpha \cdot \textsf{MMS}_i\), a contradiction.

Finally, for \(g:= \mathop{\mathrm{arg\,min}}_{g' \in G \setminus A_i} v_i(g)\), we have that \[\begin{align} v_i(A_i \cup \{g\}) & \leq \frac{2}{K} \left(\varepsilon K^{t-n} \right) + \varepsilon K^{t-n} = \varepsilon K^{t-n} \left( \frac{2}{K}+1 \right) \end{align}\] and \[v_i(G) = 1 + \frac{\varepsilon (K^{n-1}-1)}{K-1}\]

Then, \[\begin{align} \frac{n \cdot v_i(A_i \cup \{g\})}{v_i(G)} = \frac{n \varepsilon K^{t-n} \left( \frac{2}{K}+1 \right)}{1 + \frac{\varepsilon (K^{n-1}-1)}{K-1}} & \leq \frac{n\varepsilon K^{t-n} \left( \frac{2}{K}+1 \right)}{\frac{\varepsilon (K^{n-1}-1)}{K-1}} \\ & = \frac{n K^{t-n} \left(\frac{2}{K} +1\right)(K-1)}{K^{n-1}-1} \\ & \leq \frac{n K^{\lceil n/\alpha \rceil + 2} \left(\frac{2}{K} +1\right)(K-1)}{K^{n-1}-1}, \end{align}\] where the last inequality follows from the fact that \(n+1 < t \leq m\) and hence \[K^{t-n} \leq K^{m-n} \leq K^{\lceil n/\alpha \rceil + 2}.\] Now, \[\begin{align} \frac{n K^{\lceil n/\alpha \rceil + 2} \left(\frac{2}{K} +1\right)(K-1)}{K^{n-1}-1} & < \frac{n K^{\lceil n/\alpha \rceil + 3}}{K^{n-1}-1} \quad \text{(since \left( \frac{2}{K}+1\right)(K-1) < K)}\\ & \leq 2nK^{\lceil n/\alpha \rceil + 3-(n-1)} \quad \text{(since K^{n-1} - 1 \geq \frac{1}{2} K^{n-1} )}\\ & = 2nK^{\lceil n/\alpha \rceil + 4-n} \\ & \leq 2nK^{n/\alpha +5-n} \quad \text{(since \lceil n/\alpha \rceil \leq n/\alpha + 1)} \\ & = \frac{2n}{K^{n(1-1/\alpha)-5}} \\ & < 2n \left( \frac{\alpha}{3} \right)^{n(1-1/\alpha) -5}\quad \text{(since K > \frac{3}{\alpha})} \\ & < \alpha. \end{align}\] This gives us \(v_i(A_i \cup \{g\}) < \alpha \cdot v_i(G)\), which is a contradiction to \(\alpha\)-PROPX.

In both cases, we get a contradiction, and hence our result follows.

10.2 Proof of Theorem 8↩︎

For each agent \(i \in [n]\), note that \(r_i\) is the earliest iteration (of the while loop in Line [alg:MIV:line:while] of Algorithm [alg:MIV]) whereby agent \(i\) values a good at \(1\), i.e., \(v_i(g_{r_i}) = 1\) and for each \(1 \leq t < r_i\), \(v_i(g_t) < 1\).

Recall that for each \(i \in [n]\) and \(t \in \{1,\dots, m\}\), \(A_i^t\) denotes the bundle of agent \(i\) after \(g_t\) has been allocated. To simplify the analysis, we introduce new variables in place of those used in the algorithm (from Line [alg:MIV:line:xit95start] onwards). For each \(t \in \{0,\dots, m\}\), we denote \[x_i^t = \begin{cases} \frac{1}{1+v_i(G^t)} &\text{if t < r_i}\\ \frac{1}{v_i(G^t)} &\text{otherwise}\\ \end{cases}\] and \[y_i^t = \begin{cases} \frac{v_i(A_i^t)}{1+v_i(G^t)} &\text{if t < r_i}\\ \frac{v_i(A_i^t \setminus \{g_{r_i}\})}{v_i(G^t)} &\text{otherwise}\\ \end{cases}\] Note that \(x_i^0 = 1\) and \(y_i^0 = 0\) for all \(i \in [n]\). Also, for each \(i \in [n]\) and \(t \in [m]\), we let \[\label{eqn:MIV95Prop95phi} \phi_i^t := \frac{x^t_i}{(n^2 + n + 1)\cdot x^t_i + n^2 \cdot y^t_i - 1}\tag{15}\] and \[\label{eqn:MIV95Prop95Phi} \Phi^t = \sum_{i \in [n]} \phi_i^t.\tag{16}\] Then, it is easy to observe that Algorithm [alg:MIV] is essentially an online algorithm that minimizes \(\Phi^t\) at each round. We first present a lemma, which will be useful in our proof.

Next, we prove that the algorithm has two invariants.

Thus, the invariants hold, and our result follows.

10.3 Proof of Theorem 9↩︎

Without loss of generality, we can assume that \(p_i = 1\) for each \(i \in [n]\). Also let \(r_i\) be the earliest timestep whereby agent \(i\) values a good at least \(1-\varepsilon\), i.e., \(v_i(g_{r_i}) \geq 1 - \varepsilon\) and for each \(1 \leq t < r_i\), \(v_i(g_t) < 1 - \varepsilon\).

Now, for each agent \(i \in [n]\), define \(\delta_i := 1 - v_i(g_{r_i})\) (so that \(0 \leq \delta_i \leq \varepsilon\)) and create the augmented valuation function \(v'_i\) defined as follows: \[\begin{align} v_i'(g_t) = \begin{cases} 1 \quad &\text{if t = r_i}\\ v_i(g_t) \quad &\text{otherwise.}\\ \end{cases} \end{align}\] This also means \[\label{eqn:error951} v'_i(g_{r_i}) = 1 = v_i(g_{r_i}) + \delta_i.\tag{24}\]

Run the \(\alpha\)-PROP1 algorithm on this sequence of goods, but using the augmented valuation functions \(v'_1,\dots,v'_n\) instead. This returns an \(\alpha\)-PROP1 allocation with respect to the augmented valuation functions. Let \(\mathcal{A} = (A_1,\dots,A_n)\) be the returned allocation. By definition, for each agent \(i \in [n]\), there exists some good \(g \in G\setminus A_i\) such that \[\label{eqn:error952} v'_i(A_i \cup \{g\}) \geq \alpha \cdot \frac{v'_i(G)}{n}.\tag{25}\] For each agent \(i \in [n]\), we have that \(v'_i(g_t) = v_i(g_t)\) for all \(t \in [m] \setminus \{r_i\}\) and \(v'_i(g_{r_i}) = v_i(g_{r_i}) + \delta_i\) (by (24 )). This gives us \[\label{eqn:error953} v'_i(G) = v_i(G) + \delta_i\tag{26}\] and for any \(g \in G \setminus A_i\), \[\label{eqn:error954} v'_i(A_i \cup \{g\}) \leq v_i(A_i \cup \{g\}) + \delta_i,\tag{27}\] with the above being an equality if \(g_{r_i} \notin A_i \cup \{g\}\). Together with the fact that \(\delta_i \leq \varepsilon < 1\), this also implies there exists a \(g \in G \setminus A_i\) such that \[\label{eqn:error955} \frac{v_i(A_i \cup \{g\})}{1 - \delta_i} \geq \frac{v'_i(A_i \cup \{g\}) - \delta_i}{1 - \delta_i} \geq 1.\tag{28}\] The rightmost inequality follows from the fact that \(v'_i(A_i \cup \{g\}) \geq 1\), which is true if \(g_{r_i} \in A_i\), otherwise we can choose \(g\) to be \(g_{r_i}\).

Also, since \(\delta \leq \varepsilon\), we get that \(\frac{1}{1-\delta_i} \leq \frac{1}{1-\varepsilon}\) and \[\label{eqn:error956} \frac{\delta_i}{1-\delta_i} \leq \frac{\varepsilon}{1-\varepsilon}.\tag{29}\]

Now, for each \(i \in [n]\), there exists a \(g \in G \setminus A_i\) such that \[\begin{align} \alpha \cdot \frac{v_i(G)}{n} & = \frac{\alpha}{n} \cdot \left( v'_i(G) - \delta_i \right) \quad \text{(by (\ref{eqn:error953}))} \\ & \leq v'_i(A_i \cup \{g\}) - \frac{\alpha}{n} \cdot \delta_i \quad \text{(by (\ref{eqn:error952}))} \\ & \leq \left( v_i(A_i \cup \{g\}) + \delta_i\right)- \frac{\alpha}{n} \cdot \delta_i \quad \text{(by (\ref{eqn:error954}))} \\ & = v_i(A_i \cup \{g\}) +\left(1 - \frac{\alpha}{n} \right) \cdot \delta_i \\ & \leq v_i(A_i \cup \{g\}) + \left( 1 - \frac{\alpha}{n} \right) \cdot \frac{v_i(A_i \cup \{g\}) \cdot \delta_i}{1 - \delta_i} \quad \text{(by (\ref{eqn:error955}))} \\ & =\left( 1 + \left( 1 - \frac{\alpha}{n} \right) \cdot \frac{\delta_i}{1-\delta_i} \right) \cdot v_i(A_i \cup \{g\}) \\ & \leq \left( 1 + \left( 1 - \frac{\alpha}{n} \right) \cdot \frac{\varepsilon}{1-\varepsilon} \right) \cdot v_i(A_i \cup \{g\}) \quad \text{(by (\ref{eqn:error956}))} \\ & = \frac{1 - \frac{\alpha \varepsilon}{n}}{1-\varepsilon} \cdot v_i(A_i \cup \{g\}) = \frac{\alpha}{\beta} \cdot v_i(A_i \cup \{g\}). \end{align}\] This gives us \[v_i(A_i \cup \{g\}) \geq \beta \cdot \frac{v_i(G)}{n},\] as desired.

References↩︎

---

1. Such a weakened adversary is commonly studied in online algorithms and enables meaningful probabilistic guarantees.↩︎

2. PROPX was not explicitly considered in prior work, but the EFX impossibility results from [16] extend naturally to PROPX as well.↩︎

3. See Appendix 7 for additional background on this area.↩︎

4. Note that only for the following result, we will use \(\alpha\)-PROP1 for \(\alpha > 1\). This would only correspond to a stronger benchmark than PROP1.↩︎

5. This does not preclude other online algorithms from achieving stronger high-probability guarantees against a non-adaptive adversary; indeed, even in the online setting, [33] showed that exact EF1 (and hence PROP1) is achievable under identical valuations. Characterizing the optimal high-probability approximation achievable by general online algorithms against non-adaptive adversaries remains an interesting direction.↩︎

6. This is because \(\alpha\)-PROP1 is homogeneous in each agent’s valuation scale. Dividing all of agent \(i\)’s valuations by \(p_i\) scales both sides of the \(\alpha\)-PROP1 inequality by the same factor and simultaneously normalizes the predicted maximum to \(1\), so the guarantee, feasibility and approximation ratio are unchanged.↩︎

7. Our one-sided results can be viewed as the calibrated form of bounded two-sided noise via the following reduction. Suppose the raw predictor satisfies \(p_i \in [(1-\rho) v_i^{\max}, (1+\rho) v_i^{\max}]\) for each agent \(i\). Conservatively inflating the prediction to \(\tilde{p}_i = p_i / (1 - \rho)\) yields a one-sided error with \(\varepsilon= 2 \rho / (1 + \rho)\).↩︎

8. Our code is available at https://github.com/nicteh/Approx-Prop-Online-Fair-Division.↩︎

9. See also https://algorithms-with-predictions.github.io/.↩︎

10. The set \(\{t, t+1, \cdots, t+\tau_j'-1\}\) is the empty set when \(\tau_j = 0\) and is the infinite set \(\{t, t+1, t+2, \cdots\}\) when \(\tau_j = \infty\).↩︎

11. Note that \(3-i\) is the element in \(\{1,2\}\) different from \(i\).↩︎