Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees

In this subsection, we review previous works that are most closely related to ours. An extensive review of other related works is provided in Appendix 0.A.

Consider a problem instance with $n$ agents and $T$ items. For $i\in[n]$ and $t\in[T]$, let $v_{i}^{t}\geq 0$ be agent $i$’s value for a unit of item $t$. The input of our problem is a sequence of agent valuations $\bm{v}=(v_{i}^{t})^{n\times T}$. We assume that for each item $j$ at least one agent values it, i.e. there exists an agent $i$ such that $v_{i}^{t}>0$. Each agent $i\in[n]$ has a non-negative weight $B_{i}$, which can also be interpreted as a budget of faux currency in a Fisher market (Varian, 1974). An allocation $\bm{x}=(x_{i}^{t})^{n\times T}$ distributes each item to an agent, where $x_{i}^{t}$ is the amount of item $t$ that is allocated to agent $i$ gets item $t$. We assume each item has a unit supply. An allocation is feasible if $\sum_{i\in[n]}x_{i}^{t}\leq 1$ for each $t$. An allocation is integral if $x_{i}^{t}\in\{0,1\}$. For a feasible, integral allocation $x$, let $A_{i}=\{t:x_{i}^{t}=1\}$ be the set of items allocated to agent $i$.

We assume additive, linear utility for all agents. That is to say, $U_{i}^{t}=\sum_{s=1}^{t}x_{i}^{s}v_{i}^{s}$, where $U_{i}^{t}$ is the utility agent $i$ derives from the first $t$ items. For a subset of items $A\subseteq[T]$, agent $i$’s total value on the bundle $A$ is denoted as $U_{i}(A)=\sum_{s\in A}v_{i}^{s}$. Agent $i$’s monopolistic utility $V_{i}$ is defined as his total value for all items $V_{i}=U_{i}([T])=\sum_{t=1}^{T}v_{i}^{t}.$

We focus on the online setting where items arrive sequentially, while the set of agents is fixed. An online allocation algorithm is one that makes an irrevocable choice to distribute the item in each round based only on the information of past rounds. Concretely, it maps the history $\mathcal{H}^{t}=\left\{(v_{i}^{s})_{s=1}^{t},(x_{i}^{s})_{s=1}^{t-1}\right\}_{i=1}^{n}$ to a decision $(x_{1}^{t},\cdots,x_{n}^{t})$ such that $\sum_{i=1}^{n}x_{i}^{t}=1$.

In this paper, we are interested in envy and Nash welfare (NW) as measures of fairness. The multiplicative envy of agent $i$ to agent $j$ is defined as the ratio between the utility that agent $i$ would get from the allocation $x_{j}$ of agent $j$ to the utility of their own allocation $x_{i}$, adjusted by their respective budget. As a criterion for fairness, it measures the extent to which an agent prefers someone else’s bundle to his own.

Notice that when the allocation is integral, the above definition becomes ${U_{i}(A_{j})}/{U_{i}(A_{i})}$.

The Nash welfare of an allocation is defined as the weighted geometric mean of all agents’ utilities:

Maximizing the geometric mean is a well-studied proxy for balancing fairness and efficiency in fair allocation problems. It is also equivalent to maximizing the objective of the Eisenberg-Gale convex program in a Fisher market. For a Nash welfare maximizing allocation $\bm{x}^{\star}=\{x^{\star,t}_{i}\}$, let $U_{i}^{\star}=\sum_{t=1}^{T}x^{\star,t}_{i}v_{i}^{t}$ be the utility of agent $i\in[n]$. Notice that the optimal allocation might not be unique. In this paper, we measure the performance in terms of Nash welfare maximization based on the competitive ratio of our allocation, which is defined as the supremum of the ratio between the online allocation and an optimal offline NW-maximizing allocation, over the space of all possible inputs.

While we allow the input sequence to be adversarial, we restrict our attention to a subset of adversarial input sequences, where we use $\mathcal{V}^{T}$ to denote the space of valid length $T$ input sequences. Concrete assumptions on $\mathcal{V}^{T}$ will be specified in Section 3 and Section 4 before analyzing specific algorithms.

We consider the asymptotic worst-case envy and competitive ratio (w.r.t. Nash welfare) over all possible inputs $\mathcal{V}^{T}$ when $T\rightarrow\infty$. Concretely, we will investigate

In our analysis, we will show that with proper assumptions, both measures converge with an asymptotic upper bound which is independent of $T$. Our upper bounds will be either constant or with a near-optimal order dependence on $n$.

We emphasize that both measures adopted in this paper, multiplicative envy, and competitive ratio, are defined as ratios, not differences. This is mainly because of the scale invariant property of fair division, which is an important and desirable property for allocation algorithms: if an agent’s values for all items are multiplied by a constant factor, the resulting allocation stays the same. The algorithms that we are interested in, together with NW-maximizing allocations, are all scale invariant. Hence, it is more useful to consider multiplicative performance measures, which are also invariant to valuation scaling.

We introduce the two major algorithms that we study in this paper: the PACE (Pace According to Current Estimated Utility) algorithm (Gao et al., 2021; Liao et al., 2022), and the integral greedy algorithm. Moreover, we will discuss the “greedy-based” nature of PACE by showing its equivalence to the integral greedy algorithm under certain conditions.

Pseudocode for PACE is shown in Algorithm 1. In each round $t$, the agent utilities are revealed. Each agent then places a bid for the item, which is equal to their value for the item multiplied by the current pacing multiplier $\beta_{i}^{t}$. The whole item is allocated to the highest bidder, preferring the bidder with the smallest index when a tie occurs. Each agent then observes their realized utility at this round, and updates their current estimated utility. The pacing multiplier is updated to be the weight $B_{i}$ divided by the estimated utility, then projected to an interval $[a,b]$.

We begin with introducing the assumptions on the input space, as well as the necessity of doing so. We focus on input space $\mathcal{V}_{\varepsilon}^{T}$, which is parametrized by $\varepsilon\in(0,1]$ and defined as follows:

For each integer $T$, $\mathcal{V}_{\varepsilon}^{T}$ is the set of inputs which satisfy the following requirements:

• •

  The monopolistic utility of each agent is infinite: $V_{i}=\infty\ (T\rightarrow\infty).$

• •

  For each $i\in[n]$ and $t\in[T]$, $v_{i}^{t}\in\{0\}\cup[\varepsilon,1]$.

The first requirement helps to avoid allocating nothing to some agent, since the decision is integral. We further require the number of nonzero valuations of each agent is not upper-bounded by a constant, so it is meaningful to consider the asymptotic sense in $T$. For the second requirement, we note that it is equivalent to assuming a constant bound on the ratio of the minimum nonzero item value and the maximum:

This equivalence is due to the scale-invariant property of integral greedy allocation, as well as the NW maximizing allocation.

If we do not include any extra assumptions on the input space, the worst-case envy and the competitive ratio is infinite, which makes the analysis of the integral greedy algorithm trivial and uninteresting.

The above hard instance features exponential growth in agent $2$’s valuation. Hard instances with similar spirit for the continuous problem have previously been given by Banerjee et al. (2022). The vulnerability of allocation algorithms under such instances can be explained by their non-anticipating nature: it does not know the future, so it fails to recognize that agent $2$’s valuation up to current rounds is only a negligible fraction of the entire horizon. More generally, it is difficult for online algorithms to distinguish agents that are hard to satisfy in the future, with those who are easily satisfied.

However, we note that such adversarial instances are arguably not “natural.” For allocation problem in a real-world market, items are usually similar in nature, e.g., they are all food or ad slots. It is unlikely for an agent to have exponentially diverging nonzero values on these items. By requiring the ratio of minimal and maximal nonzero value to be bounded by $\varepsilon$, section 3.1 rules out extreme cases where values from a single agent diverge drastically. In the rest of this section, we will show that once the above assumptions are introduced, both multiplicative envy and competitive ratio of the greedy algorithm are independent of $T$ asymptotically, i.e., converge to a constant (which depends only on $n$ and $\varepsilon$).

In this subsection we analyze the worst-case envy of agents in integral greedy allocation. We observe that, the envy between any pair of agents can be reduced to the case $n=2$ by the following lemma, which characterized an “induction” structure of the integral greedy allocation.

We show that the multiplicative envy of the integral greedy algorithm is upper bounded by $1$ plus a logarithmic term in $1/\varepsilon$, which also generalizes to unequal weights.

We give an upper bound on the asymptotic competitive ratio w.r.t. Nash welfare for the integral greedy algorithm.

As an extension for our analysis on the integral greedy algorithm, we show how it can be adapted when Section 3.1 does not hold. Despite the $\Omega(T)$ lower bound, we show that, when each agent begins with a seed utility $\delta$, the competitive ratio of integral greedy algorithm is of order $O(\log T)$. The performance is measured w.r.t. to the ratio of seeded welfare.

The seeded integral greedy algorithm is identical to Algorithm 2, except that all agents are given an initial seed utility $\delta$, which is taken into account when deciding the winning agent:

The full pseudocode for the seeded algorithm is presented in Algorithm 3.

For the seeded algorithm, we study the criterion $R_{\delta}(\bm{v})$ which is also defined w.r.t. the seeded utility:

where the supremum runs over all feasible hindsight allocations, with resulting utility $\widetilde{U}_{1},\cdots,\widetilde{U}_{n}.$ Notice that by the AM-GM inequality, $R_{\delta}$ is also competitive w.r.t. the geometric mean. However, due to the presence of the seed utility $\delta$, it is not directly comparable to the criterion $(\prod_{i=1}^{n}{U^{\star}_{i}}/{U_{i}})^{1/n}$.

The ratio is of order $\log T$, similar to the result given by Azar et al. (2016). Unlike our previous results, here the ratio is unbounded as $T\to\infty$ since we are considering a broader range of inputs beyond Section 3.1. Also, there is a trade-off in choosing seed utility $\delta$. Although a larger $\delta$ brings a better bound in (7), it is less able to tell us how the algorithm compares to the offline optimal, since $R_{\delta}(v)\rightarrow 1$ as $\delta$ grows large.

To analyze PACE in the adversarial setting, it is necessary to adopt more assumptions than for the integral greedy algorithm. This is because PACE projects the average utility up to round $t$ to $[\ell,r]$ in its decision, or equivalently, projects the total utility in round $t$ to $[\ell t,rt]$. In the stationary and non-stationary setting of Liao et al. (2022), the expected utility of each agent grows uniformly with time; in that case the projection helps PACE achieve theoretical guarantees on its performance. However, in the adversarial setting, the input may vary drastically over time, which makes the projection operation more problematic. In the worst case, adversarial input might cause extreme behavior of the projection, such as not allocating any item to a certain agent.

In their most generic form, our assumptions require that each agent achieves infinite utility as $T\rightarrow\infty$ and bounded non-zero valuation ratios; see Assumption 4.1. Notice that unbounded utility is necessary if we hope to derive meaningful convergence guarantees for worst-case envy and Nash welfare. {assumption} For each integer $T>0$, ${\mathcal{V}}_{\varepsilon}^{T}(\ell,r)$ is the set of inputs which satisfy:

• •

  The utility of each agent under PACE is infinite when the projection bounds are set to be $[\ell,r]$.

• •

  For each $i\in[n]$ and $t\in[T]$, $v_{i}^{t}\in\{0\}\cup[\varepsilon,1]$.

Since section 4.1 is potentially hard to verify, we next identify sufficient conditions under which PACE guarantees infinite utility for each agent. {assumption} For integer $T>0$, and $c\in(0,1]$, ${\mathcal{V}}_{\varepsilon,c}^{T}$ is the set of inputs which satisfy:

• •

  For each $i\in[n]$, $V_{i}\geq cT$, that is, the monopolistic utility of each agent under PACE is $\Theta(T)$.

• •

  For each $i\in[n]$ and $t\in[T]$, $v_{i}^{t}\in\{0\}\cup[\varepsilon,1]$.

Assumption 4.1 strengthens Assumption 3.1 by requiring the monopolistic utility of each agent to be linear in $T$. Intuitively, this matches the linear projection bounds $[\ell t,rt]$ on utility. We will show in Lemma 6 that, with appropriate initialization of the projection bounds, Assumption 4.1 with any $c>0$ leads to infinite agent utilities, and thus implies Assumption 4.1 for some $\ell$ and $r$.

Conversely, if an agent’s inputs have $o(T)$ agent monopolistic utility, the following example shows that problems may occur, see Example 2.

We remark that in order to initialize $\ell$ and $r$, PACE requires knowing a lower bound on $\varepsilon$. In contrast, the integral greedy algorithm does not require such knowledge. A minimal requirement is to set $\ell\leq\varepsilon$:

Next we show that the PACE algorithm, as long as it is appropriately initialized and section 4.1 holds, achieves $1+2\log 1/\varepsilon$ multiplicative envy bound asymptotically. Our proof is performed by reducing the adversarial envy-maximizing problem in PACE to the canonical program (3) by showing that PACE with our assumptions lead to a weakly harder problem than (3) for the adversary.

Next we focus on establishing a worst-case guarantee for the asymptotic competitive ratio of Nash Welfare for PACE under Assumption 4.1. To begin with, we show that Assumption 4.1 implies infinite agent utilities with appropriate initialization.

The proof of Lemma 6 is also by a reduction from the canonical problem (3). We remark that Lemma 6 yields more than infinite agent utilities: it also tells us that the utilities are linear in $T$. Moreover, from $d/c=\Omega\left(n^{-1}\right)$ we know that PACE computes an asymptotic approximate proportional allocation, which helps to derive a bounded competitive ratio w.r.t. Nash welfare. The bound can be furthermore refined using the envy results.

Theorem 4.2 gives an upper bound depends only on parameters $\varepsilon$ and $c$, which are both independent of $T$. We remark that the constant $1/c$ might not be tight.

We also remark that in both Theorem 4.1 and Theorem 4.2 $\ell$ is at most the order of $1/n$, which is aligned with the stationary and non-stationary setting (projecting utilities to an $\Omega(1/n)$ bound is unreasonable since there are $n$ agents). However with adversarial input $\ell$ decreases as $\varepsilon\rightarrow 0$, which means that PACE requires a wider projection interval when its input becomes potentially more extreme.