The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Huang, Zhiyi; Lee, Chui Shan; Shu, Xinkai; Wang, Zhaozi

doi:10.4230/LIPIcs.ICALP.2025.98

The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Zhiyi Huang

The University of Hong Kong, Pokfulam, Hong Kong Chui Shan Lee

The University of Hong Kong, Pokfulam, Hong Kong Xinkai Shu¹¹1This work was done when the author was at the University of Hong Kong.

Max Planck Institute for Informatics, Saarbrücken, Germany Zhaozi Wang²²2This work was done when the author was at Shanghai Jiao Tong University.

New York University, NY, US

Abstract

We study the online allocation of divisible items to $n$ agents with additive valuations for $p$ -mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of $-\infty\leq p\leq 1$ . Surprisingly, our improved algorithms for all $p\leq\nicefrac{{1}}{{\log n}}$ are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.

Keywords and phrases:

Online Algorithms, Fair Division, Nash Welfare

Category:

Track A: Algorithms, Complexity and Games

Funding:

Zhiyi Huang: This work is supported by NSFC (No. 6212290003).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Online algorithms

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Resource allocation is a fundamental challenge in many domains of Computer Science, Economics, and beyond, such as cloud computing (e.g., [21]) and food banks (e.g., [1]). The primary objectives in these scenarios are efficiency and fairness. For $-\infty\leq p\leq 1$ , the $p$ -means of the agents’ utilities, known as the $p$ -mean welfare, form an axiomatically justified family of objectives [31, Chapter 3] with different tradeoffs between these two factors. On one extreme when $p=1$ , this is the utilitarian welfare, i.e., the sum of the agents’ utilities. On the other extreme when $p=-\infty$ , this is the egalitarian welfare, i.e., the minimum utility among the agents. In the middle when $p=0$ is the Nash welfare, which reconciles the two extremes and satisfies several notions of fairness including envy-freeness and proportionality [32].

This paper studies online resource allocation algorithms for maximizing the $p$ -mean welfare among $n$ agents when the items arrive sequentially and need to be allocated immediately upon arrival. This online $p$ -mean welfare maximization problem was proposed by Barman et al. [8], assuming that 1) the items are divisible, 2) the agents’ utilities are additive, and 3) each agent’s utility for receiving all items, a.k.a., its monopolist utility, is equal to $1$ . For the whole spectrum of $-\infty\leq p\leq 1$ , Barman et al. [8] gave competitive online algorithms and hardness results. However, there are gaps between their algorithmic and hardness results. For any negative constant $p$ , the gap is polynomially large in the number of agents.

By contrast, the non-negative regime is better understood. For any positive $p$ , the problem is equivalent to a special case of the online matching with concave returns problem introduced by Devanur and Jain [17]. Their online primal dual approach gave a $\nicefrac{{1}}{{p}}$ competitive algorithm even without the third assumption above about unit monopolist utilities. We include an exposition of this algorithm and an improvement for $0<p\leq\nicefrac{{1}}{{\log n}}$ using the third assumption in the full version of the paper. For Nash welfare ( $p=0$ ), Banerjee et al. [4] gave an $O(\log n)$ -competitive algorithm,³³3More precisely, their model assumes having predictions of the agents’ monopolist utilities, which can be used to normalize the agents’ utilities to restore the assumption of unit monopolist utilities. See also [24] for online algorithms that relaxed this assumption to allow the absence of predictions of agents’ monopolist utilities but still require the max-min ratio of monopolist utilities to be bounded. which is the best possible.

1.1 Our Contributions

1.1.1 Optimal Competitive Ratios (up to Lower-Order Terms)

We improve the upper and lower bounds for the competitive ratios of online $p$ -mean welfare maximization. These bounds characterize the optimal competitive ratios for all $-\infty\leq p\leq 1$ . See Table 1 for a summary.

For $p\geq\nicefrac{{1}}{{\log n}}$ , we prove that the $\nicefrac{{1}}{{p}}$ competitive ratio obtained by Devanur and Jain [17] is optimal up to a $\log\nicefrac{{1}}{{p}}$ term even if the instance satisfies the assumption of unit monopolist utilities.

For the Nashian regime, i.e., when $-\nicefrac{{1}}{{\log n}}\leq p\leq\nicefrac{{1}}{{\log n}}$ , we improve the $O(\log^{3}n)$ competitive ratio by Barman et al. [8] to $O(\log n)$ , and give a corresponding hardness result matching it up to a doubly logarithmic factor. Note that for Nash welfare ( $p=0$ ), our result matches the optimal ratio of $O(\log n)$ obtained by Banerjee et al. [4].

Between the Nashian regime and the harmonic mean, i.e., when $-1\leq p\leq-\nicefrac{{1}}{{\log n}}$ , we give an online algorithm that is $n^{\nicefrac{{|p|}}{{(|p|+1)}}}$ -competitive, omitting lower-order terms. This is better than the state-of-the-art by Barman et al. [8] by a polynomial factor for $p\geq-\nicefrac{{1}}{{4}}$ , and a poly-logarithmic factor for other values of $p$ . We complement the algorithmic result with a hard instance, showing that no online algorithm can do better up to a logarithmic term. This hardness result is a polynomial improvement compared to the existing $n^{\nicefrac{{|p|}}{{(2|p|+1)}}}$ for any negative constant $p$ .

Last but not least, from harmonic mean to egalitarian welfare, i.e., when $-\infty\leq p\leq-1$ , we show that the optimal competitive ratio is $\sqrt{n}$ up to a lower-order term. Our hardness result is a polynomial improvement on the existing $n^{\nicefrac{{|p|}}{{(2|p|+1)}}}$ bound by Barman et al. [8] for any finite $p$ ; on the other hand, our algorithmic result is slightly better than theirs by a $\sqrt{\log n}$ factor.

Table 1: Summary of Results. We omit constant and lower-order terms for brevity, and defer the precise bounds to the subsequent sections. The bounds on some rows were known for a special value of

p

: Banerjee et al. [4] gave

\log n

upper and lower bounds for

p=0

, and Barman et al. [8] showed a

\sqrt{n}

lower bound for

p=-\infty

.

			Algorithmic Results		Hardness Results
$\nicefrac{{1}}{{\log n}}\leq$	$p$	$\leq 1$	$\nicefrac{{1}}{{p}}$	Devanur and Jain [17]	$\nicefrac{{1}}{{p}}$	Theorem 15
$-\nicefrac{{1}}{{\log n}}\leq$	$p$	$\leq\nicefrac{{1}}{{\log n}}$	$\log n$	Corollary 4	$\log n$	Theorem 15
$-o(1)\leq$	$p$	$\leq-\nicefrac{{1}}{{\log n}}$ ⁴⁴4The omitted terms are of lower order for $p\leq-\omega(\nicefrac{{\log\log n}}{{\log n}})$ . For $-O(\nicefrac{{\log\log n}}{{\log n}})\leq p\leq-\nicefrac{{1}}{{\log n}}$ , our results show that the optimal competitive ratio is poly-logarithmic, but do not characterize the degree of the poly-logarithms.	$n^{\|p\|}$	Theorem 3	$n^{\|p\|}$	Theorem 16
$-1\leq$	$p$	$\leq-\Omega(1)$	$n^{\frac{\|p\|}{\|p\|+1}}$	Theorem 6	$n^{\frac{\|p\|}{\|p\|+1}}$	Theorem 17
$-\infty\leq$	$p$	$\leq-1$	$\sqrt{n}$	Theorem 10; Barman et al. [8]	$\sqrt{n}$	Theorem 18

1.1.2 Long Arm of Nashian Allocation

Besides the improved competitive ratios, we find it conceptually interesting that our algorithmic results for the whole spectrum of $-\infty\leq p\leq\nicefrac{{1}}{{\log n}}$ are obtained by just two algorithms, both based on the greedy algorithm for the Nash welfare. A priori, it is surprising that the greedy algorithm for $p=0$ also achieves nearly optimal competitive ratios for other values of $p$ , even those that are far from zero. This can be viewed as further evidence for the effectiveness of Nash welfare maximization for balancing efficiency and fairness in the context of online optimization, echoing the unreasonable fairness from offline Nash welfare maximization showed by Caragiannis et al. [13].

More precisely, the improvements for $-1\leq p\leq\nicefrac{{1}}{{\log n}}$ are obtained by combining the greedy algorithm for the Nash welfare with the common idea of distributing a constant fraction of each item uniformly to all agents to ensure an $\Omega(\nicefrac{{1}}{{n}})$ base utility for the agents (see, e.g., [4, 24], for previous analyses of this algorithm for $p=0$ ). The base utilities allow us to avoid the irregularity of $p$ -mean welfare when an agent has zero utility, for any $p\leq 0$ .

We further address the cases of $-\infty\leq p\leq-1$ by introducing an auxiliary component that considers the other extreme of the spectrum, greedily maximizing the egalitarian welfare with respect to the agents’ regularized utilities. An agent’s regularized utility is the sum of its utility and a regularization term that is linear in the agent’s monopolist utility for the remaining items. We stress that the greedy algorithm for the Nash welfare still plays the main role in this regime. In particular, it ensures that at most $\tilde{O}(\sqrt{n})$ agents may have low regularized utilities; the auxiliary component is designed to help these agents by making regularized egalitarian allocation.

1.1.3 Our Techniques

Next, we sketch the competitive analysis of the greedy algorithm for the Nash welfare. Consider the algorithm’s allocation and any alternative allocation. Denote each agent $a$ ’s utilities for these allocations as $U_{a}$ and $\tilde{U}_{a}$ respectively. We will prove that the ratio of these utilities, i.e., $\nicefrac{{\tilde{U}_{a}}}{{U_{a}}}$ , is at most $O(\log n)$ averaging over all agents $a$ . This is easy to prove in hindsight, based on 1) the greedy criteria with respect to the Nash welfare, and the fact that 2) the agents’ maximum and minimum utilities differ by at most an $O(n)$ multiplicative factor due to the $\Omega(\nicefrac{{1}}{{n}})$ base utilities from distributing a constant fraction of each item uniformly to all agents. Nonetheless, this is powerful enough to derive all subsequent lemmas and competitive ratios in this paper; we call it the Fundamental Lemma of Nashian Allocation (Lemma 5).

In particular, we will use this fundamental lemma to derive upper bounds for the number of agents whose utilities are smaller than a threshold (Lemma 9), and the number of agents whose regularized utilities are smaller than a threshold (Lemma 12). Intuitively, these bounds are useful because the $p$ -mean welfare for any negative $p<0$ may be seen as a softmin function over the agents’ utilities. Hence, lower bounding the $p$ -mean welfare of the algorithm’s allocation reduces to upper bounding the number of agents whose (regularized) utilities are too small.

Finally, our hardness results consider upper triangular instances that are prevalent in online resource allocation and online matching (e.g., [27, 26]). We supplement the upper triangular instances with items arriving at the end to satisfy the assumption of unit monopolist utilities.

1.2 Further Related Work

Online resource allocation problems have been studied extensively, including online packing [3, 12] and online matching [27, 30, 25]. Walsh [33] and Aleksandrov et al. [1] started the study of online fair division with agent and item arrivals respectively. See [2] for a survey.

Closest to this paper is the work by Barman et al. [8], which we have already discussed and compared against. Better results have been achieved in relaxed models of online allocation. Cohen and Panigrahi [16] studied the problem in a learning-augmented setting, i.e., where the algorithm has access to some extra (machine-learned) information. Hajiaghayi, Panigrahi, Khani, and Springer [23] considered the case of egalitarian welfare and indivisible items, assuming that the items arrive by a random order and the instance satisfies a large-market assumption.

Another line of work considered online resource allocation for other notions of fairness. Benade et al. [10] achieved envy-freeness in online allocation in the sense of no-regret learning. Zeng and Psomas [34] explored the fairness-efficiency tradeoffs in online fair division with respect to envy-freeness and Pareto optimality. Gkatzelis et al. [22] considered the online allocation of divisible items (to two agents) to satisfy envy-freeness and at the same time approximately maximize utilitarian welfare. Banerjee et al. [5] studied online allocation of public goods for proportional fairness, with predictions for the agents’ monopolist utilities.

Finally, offline maximization for $p$ -mean welfare has also been studied in a long line of work. Since the case of additive valuations and divisible items reduces to standard convex optimization, researchers focused on the harder case with indivisible items and non-additive valuations. For general $-\infty\leq p\leq 1$ , Barman et al. [7] and Chaudhury et al. [15] independently gave $O(n)$ -approximation algorithms for maximizing the $p$ -mean welfare when the valuations are subadditive.

For $p=0$ , maximizing the Nash welfare is APX-hard [28]. The state-of-the-art for additive valuations is an $e^{\nicefrac{{1}}{{e}}}$ -approximation algorithm by Barman et al. [9], which has been generalized to the weighted case by Feng and Li [19]. Li and Vondrák [29] obtained a constant approximation for submodular valuations while Garg et al. [20] showed an $\nicefrac{{e}}{{(e-1)}}$ lower bound. Recently, Dobzinski et al. [18] gave a constant approximation for subadditive valuations.

For $p=-\infty$ , maximizing the egalitarian welfare for additive valuations and indivisible items, a.k.a., the Santa Claus problem (e.g., [6]), is also APX-hard [11]. Chakrabarty et al. [14] gave an $\tilde{O}(n^{\varepsilon})$ -approximate algorithm that runs in $n^{O(\nicefrac{{1}}{{\varepsilon}})}$ time, for any $\varepsilon=\Omega(\nicefrac{{\log\log n}}{{\log n}})$ .

2 Preliminaries

We write $\log$ for the natural logarithm in this paper.

2.1 Model

2.1.1 Discrete Time

Consider the problem of online allocation of $m$ divisible items $I$ to $n$ agents $A$ . Agent $a$ has value $v_{ai}\geq 0$ for item $i$ . The items arrive one by one. The agents’ values for an item are unknown initially and revealed when the item arrives. Upon an item’s arrival, the algorithm must allocate it to some agent(s) immediately and irrevocably. Denote the algorithm’s allocation as $x=(x_{ai})_{a\in A,i\in I}$ , where $x_{ai}\geq 0$ is the portion of item $i$ allocated to agent $a$ . Agent $a$ ’s utility for allocation $x$ is:

U_{a}=\sum_{i\in I}v_{ai}\cdot x_{ai}\leavevmode\nobreak\ .

For some $p\leq 1$ , we want to maximize the $p$ -mean welfare:

\left(\frac{1}{n}\sum_{a\in A}U_{a}^{p}\right)^{\frac{1}{p}}\leavevmode% \nobreak\ .

(1)

When $p=1$ , this is the utilitarian welfare (up to a $\nicefrac{{1}}{{n}}$ factor). When $p=0$ , Equation 1 is defined as the geometric mean of the agents’ utilities, and is known as the Nash welfare. When $p=-1$ , this becomes the harmonic mean of the agents’ utilities; we therefore call it the harmonic welfare. Last but not least, when $p=-\infty$ , Equation 1 is the minimum utility among the agents, and is called the egalitarian welfare.

2.1.2 Continuous Time

It will be more convenient to present our algorithms and analyses in the more general continuous-time model. Next, we present the model and then explain the reduction from the discrete-time model to the continuous-time model. Consider a continuum of infinitesimal items arriving in time horizon $[0,T)$ with unit arrival rate. We will refer to the item arriving at time $t$ as item $t$ , and thus, let $I=[0,T)$ denote the set of items. Agent $a$ has unit value $v_{a}(t)$ for item $t$ ; we assume that $v_{a}(t)$ is piecewise constant, changing its value only a finite number of times. Denote the algorithm’s allocation as $x=\big{(}x_{a}(t)\big{)}_{a\in A,t\in I}$ where $x_{a}(t)$ is the portion of item $t$ allocated to agent $a$ . Correspondingly, agent $a$ ’s utility for allocation $x$ is:

U_{a}=\int_{0}^{T}v_{a}(t)x_{a}(t)\,\text{\rm d}t\leavevmode\nobreak\ .

Given any instance in the discrete-time model where we without loss of generality denote the set of $m$ divisible items as $\{1,2,\dots,m\}$ , we can reinterpret it in the continuous-time model with $T=m$ , such that agent $a$ ’s value for items $i-1\leq t<i$ is $v_{a}(t)=v_{ai}$ , for any $1\leq i\leq m$ .

2.1.3 Assumption of Unit Monopolist Utilities

Following [8], we assume that the agents have unit monopolist utilities. That is, for any agent $a\in A$ , we have:

\int_{0}^{T}v_{a}(t)\,\text{\rm d}t=1\leavevmode\nobreak\ .

Trivial hardness results exist if the algorithm has no information on the agents’ monopolist utilities. Banerjee et al. [4] provided a hard instance that prevents any algorithm from performing better than $\Omega(n)$ -competitive in online Nash welfare maximization ( $p=0$ ). The proof of $\Omega(n)$ hardness can be generalized to any $p\leq 0$ using the same hard instance.

Our results still hold under a weaker assumption that the monopolist utilities are known and within a constant factor of each other (see the full version of the paper). This corresponds to having predictions for the agents’ monopolist utilities, which could be derived from historical data and machine learning models. Moreover, the agents are of similar importance in the market. Further relaxing this assumption is an interesting research direction. See [4] and [24] for some related results for the Nash welfare.

2.2 Competitive Analysis

2.2.1 Offline Optimal Allocation

We will compare the $p$ -mean welfare of the algorithm’s allocation to the offline optimal benchmark, obtained from optimizing the allocation based on full knowledge of the instance. We can compute the offline optimal benchmark by solving a convex program:

maximize	$\displaystyle\bigg{(}\frac{1}{n}\sum_{a\in A}U_{a}^{p}\bigg{)}^{\frac{1}{p}}$
subject to	$\displaystyle\sum_{a\in A}x_{a}(t)\leq 1$	$\displaystyle\forall t\in I$
	$\displaystyle U_{a}=\int_{0}^{T}v_{a}(t)x_{a}(t)\,\text{\rm d}t$	$\displaystyle\forall a\in A$
	$\displaystyle x_{a}(t)\geq 0$	$\displaystyle\forall a\in A,\forall t\in I$

We denote the optimal allocation as $x^{*}=\big{(}x_{a}^{*}(t)\big{)}_{a\in A,t\in I}$ and the corresponding agents’ utilities and $p$ -mean welfare as $\{U_{a}^{*}\}_{a\in A}$ and $\mathrm{OPT}$ respectively. If there are multiple allocations that achieve the optimal $p$ -mean welfare, we will pick an arbitrary one as $x^{*}$ .

2.2.2 Competitive Online Algorithms

Denote the $p$ -mean welfare for the online algorithm’s allocation as $\mathrm{ALG}$ . An online algorithm is $\Gamma$ -competitive if for every instance of online $p$ -mean welfare maximization, we have:

\mathrm{OPT}\leq\Gamma\cdot\mathrm{ALG}\leavevmode\nobreak\ .

2.3 Relaxation of Online $𝒑$ -Mean Welfare Maximization

We can guarantee a simple lower bound for all agents’ utilities with the Uniform Allocation below.

Lemma 1.

Every agent $a\in A$ gets utility $\nicefrac{{1}}{{n}}$ from Uniform Allocation.

As a result of this simple bound, we can consider a relaxation of online $p$ -mean welfare maximization, in which each agent starts with $\nicefrac{{1}}{{n}}$ base utility for the algorithm’s allocation. In other words, an agent $a$ ’s utility for an allocation $x$ is:

U_{a}\stackrel{{\scriptstyle\textrm{\tiny def}}}{{=}}\frac{1}{n}+\int_{0}^{T}v% _{a}(t)x_{a}(t)\,\text{\rm d}t\leavevmode\nobreak\ .

We further write $U_{a}(t)$ for agent $a$ ’s utility for the items it received before time $t$ , i.e.:

U_{a}(t)\stackrel{{\scriptstyle\textrm{\tiny def}}}{{=}}\frac{1}{n}+\int_{0}^{% t}v_{a}(s)x_{a}(s)\,\text{\rm d}s\leavevmode\nobreak\ .

As for the benchmark, we will still compare against the original optimal $p$ -mean welfare without the $\nicefrac{{1}}{{n}}$ base utility.

Lemma 2.

If an online algorithm $A$ is $\Gamma$ -competitive for the relaxed online $p$ -mean welfare maximization problem, then allocating half of each item by Uniform Allocation and the other half by algorithm $A$ is $2\Gamma$ -competitive for the original problem.

3 Nashian Regime: $-o(1)\leq p\leq\nicefrac{{1}}{{\log n}}$

This section considers the Nashian regime where $p$ is close to zero. We will analyze the greedy algorithm for maximizing the Nash welfare and prove that it is competitive for all values of $p$ in this regime simultaneously.

Recall that the Nash welfare is the case of $p=0$ , defined as the geometric mean of the agents’ utilities. Equivalently, we may consider maximizing its logarithm (up to a factor $n$ ):

\sum_{a\in A}\log U_{a}\leavevmode\nobreak\ .

For each item $t$ , allocating it to agent $a$ would increase this objective by:

\frac{v_{a}(t)}{U_{a}(t)}\leavevmode\nobreak\ .

Hence, the Nashian Greedy algorithm allocates each item to an agent to maximize the above increment. We present below a formal definition of the algorithm.

The main results of this section are the following theorem and its corollary when $|p|\leq\nicefrac{{1}}{{\log n}}$ .

Theorem 3.

For any $|p|=o(1)$ , Nashian Greedy is $O\big{(}n^{|p|}\cdot\log n\big{)}$ -competitive for the relaxed online $p$ -mean welfare maximization problem.

Corollary 4.

For any $p$ such that $|p|\leq\nicefrac{{1}}{{\log n}}$ , Nashian Greedy is $O(\log n)$ -competitive for the relaxed online $p$ -mean welfare maximization problem.

Next, we present the most important lemma for the analysis of Nashian Greedy. Despite its simple form and proof, it is the foundation of all subsequent lemmas and competitive analyses in this paper.

Lemma 5 (Fundamental Lemma of Nashian Allocation).

Consider any allocation of the items $\tilde{x}=(\tilde{x}_{a}(t))_{a\in A,t\in I}$ . For any time $t\in I$ and the agents’ utilities for allocation $\tilde{x}$ up to time $t$ , denoted as $\tilde{U}(t)=(\tilde{U}_{a}(t))_{a\in A}$ , we have:

\frac{1}{n}\sum_{a\in A}\frac{\tilde{U}_{a}(t)}{U_{a}(t)}\leq\log(n+1)% \leavevmode\nobreak\ .

Proof.

Consider any item $s\in[0,t)$ . Suppose that Nashian Greedy allocates it to agent $a$ . By the definition of the algorithm, for any agent $\tilde{a}$ we have:

\frac{v_{a}(s)}{U_{a}(s)}\geq\frac{v_{\tilde{a}}(s)}{U_{\tilde{a}}(s)}% \leavevmode\nobreak\ .

The left-hand-side equals the increment of the logarithm of Nash welfare for Nashian Greedy’s allocation. Further, we relax the denominator of the right-hand-side to $U_{\tilde{a}}(t)$ . We get that:

\frac{\,\text{\rm d}missing}{\,\text{\rm d}s}\sum_{a\in A}\log U_{a}(s)\geq% \frac{v_{\tilde{a}}(s)}{U_{\tilde{a}}(t)}\leavevmode\nobreak\ .

Multiplying this inequality by $\tilde{x}_{a}(s)$ and summing over all agents $\tilde{a}\in A$ , we get that:

\frac{\,\text{\rm d}missing}{\,\text{\rm d}s}\sum_{a\in A}\log U_{a}(s)\geq% \frac{\,\text{\rm d}missing}{\,\text{\rm d}s}\sum_{a\in A}\frac{\tilde{U}_{a}(% s)}{U_{a}(t)}

Integrating over $s\in[0,t)$ gives:

\sum_{a\in A}\log\frac{U_{a}(t)}{U_{a}(0)}\geq\sum_{a\in A}\frac{\tilde{U}_{a}% (t)}{U_{a}(t)}\leavevmode\nobreak\ .

The lemma now follows by $1+\nicefrac{{1}}{{n}}\geq U_{a}(t)\geq U_{a}(0)=\nicefrac{{1}}{{n}}$ . $\hfill\blacktriangleleft$

Proof of Theorem 3.

For $p=0$ , the theorem follows by considering Lemma 5 with $\tilde{x}=x^{*}$ , i.e., the optimal allocation, and applying the AM-GM inequality to the left-hand-side.

Next, we consider the case when $p\neq 0$ . Define an auxiliary allocation $\tilde{x}$ that distributes half of each item uniformly to all agents, and the other half following the optimal allocation $x^{*}$ . That is, for any agent $a\in A$ and any item $t\in I$ :

\tilde{x}_{a}(t)\stackrel{{\scriptstyle\textrm{\tiny def}}}{{=}}\frac{1}{2n}+% \frac{1}{2}x^{*}_{a}(t)\leavevmode\nobreak\ .

Let $\tilde{U}_{a}$ be agent $a$ ’s utility for allocation $\tilde{x}$ . By definition, we have:

\frac{1}{2n}\leq\tilde{U}_{a}\leq\frac{1}{2}+\frac{1}{2n}\leavevmode\nobreak\ ,

(2)

and also:

\bigg{(}\frac{1}{n}\sum_{a\in A}\tilde{U}_{a}^{p}\bigg{)}^{\frac{1}{p}}\geq% \frac{\mathrm{OPT}}{2}\leavevmode\nobreak\ .

(3)

We write the $p$ -mean welfare of Nashian Greedy’s allocation as:

\mathrm{ALG}=\bigg{(}\frac{1}{n}\sum_{a\in A}U_{a}^{p}\bigg{)}^{\frac{1}{p}}=% \bigg{(}\frac{1}{n}\sum_{a\in A}\tilde{U}_{a}^{p}\cdot\Big{(}\frac{\tilde{U}_{% a}}{U_{a}}\Big{)}^{-p}\bigg{)}^{\frac{1}{p}}\leavevmode\nobreak\ .

(4)

Next, we introduce a set of auxiliary variables to denote:

z_{a}\stackrel{{\scriptstyle\textrm{\tiny def}}}{{=}}\frac{\tilde{U}_{a}^{p}}{% \sum_{a^{\prime}\in A}\tilde{U}_{a^{\prime}}^{p}}\leavevmode\nobreak\ .

Comparing Equations 3 and 4, it suffices to show that:

\bigg{(}\sum_{a\in A}z_{a}\cdot\Big{(}\frac{\tilde{U}_{a}}{U_{a}}\Big{)}^{-p}% \bigg{)}^{-\frac{1}{p}}\leq(n+1)^{|p|}\cdot\log(n+1)\leavevmode\nobreak\ .

By the definition of these auxiliary variables, we have $\sum_{a\in A}z_{a}=1$ . Hence, by applying the generalized mean inequality relating $(-p)$ -mean and $1$ -mean, where recall that $-p<1$ , we have:

\bigg{(}\sum_{a\in A}z_{a}\cdot\Big{(}\frac{\tilde{U}_{a}}{U_{a}}\Big{)}^{-p}% \bigg{)}^{-\frac{1}{p}}\leq\sum_{a\in A}z_{a}\cdot\frac{\tilde{U}_{a}}{U_{a}}% \leavevmode\nobreak\ .

Further, by the range of $\tilde{U}_{a}$ in Equation 2, we have:

z_{a}\leq\frac{1}{n}\bigg{(}\frac{\max_{a\in A}\tilde{U}_{a}}{\min_{a\in A}% \tilde{U}_{a}}\bigg{)}^{|p|}\leq\frac{1}{n}\cdot(n+1)^{|p|}\leavevmode\nobreak\ .

Combining the above with Lemma 5, we get that:

\bigg{(}\sum_{a\in A}z_{a}\cdot\Big{(}\frac{\tilde{U}_{a}}{U_{a}}\Big{)}^{-p}% \bigg{)}^{-\frac{1}{p}}\leq(n+1)^{|p|}\cdot\frac{1}{n}\sum_{a\in A}\frac{% \tilde{U}_{a}}{U_{a}}\leq(n+1)^{|p|}\cdot\log(n+1)\leavevmode\nobreak\ .\

$\hfill\blacktriangleleft$

4 From Nash to Harmonic Welfare: $-1\leq p\leq-\Omega(1)$

In this section, we continue to analyze the Nashian Greedy algorithm. Surprisingly, it remains competitive even when $p$ is bounded away from zero. The resulting competitive ratios are nearly optimal for all values of $p$ from Nash welfare to harmonic welfare.

Theorem 6.

For any $-1\leq p\leq-\Omega(1)$ , Nashian Greedy is:

O\Big{(}n^{\frac{|p|}{|p|+1}}(\log n)^{\frac{1}{|p|+1}}\Big{)}

competitive for the relaxed online $p$ -mean welfare maximization problem.

4.1 Further Properties of Nashian Allocation

Definition 7 (Bad Agents).

For any time $t\in I$ and any $\beta>0$ , let $B_{\beta}(t)$ be the set of $\beta$ -bad agents whose utilities at time $t$ are at most a $\beta$ fraction of the optimal $p$ -mean welfare, i.e.:

B_{\beta}(t)\stackrel{{\scriptstyle\textrm{\tiny def}}}{{=}}\Big{\{}a\in A:\,U% _{a}(t)\leq\beta\cdot\mathrm{OPT}\Big{\}}\leavevmode\nobreak\ .

Further, we write $B_{\beta}$ for $B_{\beta}(T)$ , the set of $\beta$ -bad agents at the end.

The next lemma considers a subset of $\beta$ -bad agents, and upper bounds the sum of their utilities for the optimal allocation by a linear combination of $\beta\cdot\mathrm{OPT}$ , the upper bound of these agents’ utilities for the algorithm’s allocation, and the sum of these agents’ remaining monopolist utilities.

Lemma 8.

For any time $t\in I$ , any $\beta>0$ , and any subset of $\beta$ -bad agents $S\subseteq B_{\beta}(t)$ , we have:

\frac{1}{n}\sum_{a\in S}U_{a}^{*}\leq\beta\log(n+1)\cdot\mathrm{OPT}+\frac{1}{% n}\sum_{a\in S}\Big{(}1-\int_{0}^{t}v_{a}(s)\,\text{\rm d}s\Big{)}\leavevmode% \nobreak\ .

Proof.

Recall that $x^{*}$ denotes the optimal allocation. The left-hand-side of the lemma’s inequality can be written as:

\frac{1}{n}\sum_{a\in S}\int_{0}^{T}v_{a}(s)x^{*}_{a}(s)\,\text{\rm d}s% \leavevmode\nobreak\ .

On one hand, observe that:

\int_{t}^{T}v_{a}(s)x^{*}_{a}(s)\,\text{\rm d}s\leq\int_{t}^{T}v_{a}(s)\,\text% {\rm d}s=1-\int_{0}^{t}v_{a}(s)\,\text{\rm d}s\leavevmode\nobreak\ .

On the other hand, by Lemma 5, we have:

\frac{1}{n}\sum_{a\in A}\frac{1}{U_{a}(t)}\int_{0}^{t}v_{a}(s)x^{*}_{a}(s)\,% \text{\rm d}s\leq\log(n+1)\leavevmode\nobreak\ .

We now drop all agents outside subset $S$ from the summation on the left-hand-side, and relax $U_{a}(t)$ to its upper bound $\beta\cdot\mathrm{OPT}$ for the remaining $\beta$ -bad agents $a\in S$ . We get that:

\frac{1}{n}\sum_{a\in S}\int_{0}^{t}v_{a}(s)x^{*}_{a}(s)\,\text{\rm d}s\leq% \beta\log(n+1)\cdot\mathrm{OPT}\leavevmode\nobreak\ .

Putting together these two parts proves the lemma. $\hfill\blacktriangleleft$

Lemma 9.

For any $\beta>0$ , the fraction of $\beta$ -bad agents at the end is at most:

\frac{|B_{\beta}|}{n}\leq\big{(}\beta\log(n+1)\big{)}^{\frac{|p|}{|p|+1}}% \leavevmode\nobreak\ .

Proof.

By Lemma 8 with $t=T$ and $S=B_{\beta}$ , we have:

\frac{1}{n}\sum_{a\in B_{\beta}}U_{a}^{*}\leq\beta\log(n+1)\cdot\mathrm{OPT}% \leavevmode\nobreak\ .

Further, recall that $p<0$ . We have:

\mathrm{OPT}^{p}=\frac{1}{n}\sum_{a\in A}(U_{a}^{*})^{-|p|}\geq\frac{1}{n}\sum% _{a\in B_{\beta}}(U_{a}^{*})^{-|p|}\leavevmode\nobreak\ .

Finally, by Hölder’s inequality:

\bigg{(}\frac{1}{n}\sum_{a\in B_{\beta}}U_{a}^{*}\bigg{)}^{\frac{|p|}{|p|+1}}% \bigg{(}\frac{1}{n}\sum_{a\in B_{\beta}}(U_{a}^{*})^{-|p|}\bigg{)}^{\frac{1}{|% p|+1}}\geq\frac{1}{n}\sum_{a\in B_{\beta}}1=\frac{|B_{\beta}|}{n}\leavevmode% \nobreak\ .

Combining these inequalities proves the lemma. $\hfill\blacktriangleleft$

4.2 Proof of Theorem 6

We compare the $p$ -mean welfare of Nashian Greedy to the optimal benchmark by:

\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}=\frac{1}{n}\sum_{a\in A}% \bigg{(}\frac{U_{a}}{\mathrm{OPT}}\bigg{)}^{p}\leavevmode\nobreak\ .

By $U_{a}\geq\nicefrac{{1}}{{n}}$ and $\mathrm{OPT}\leq 1$ , and recalling that $p<0$ , we have :

\bigg{(}\frac{U_{a}}{\mathrm{OPT}}\bigg{)}^{p}\leq n^{|p|}\leavevmode\nobreak\ .

Therefore, the above ratio can be written as:

$\displaystyle\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}$	$\displaystyle=\int_{0}^{n^{\|p\|}}\big{(}\text{fraction of agents with $\big{(}% \nicefrac{{U_{a}}}{{\mathrm{OPT}}}\big{)}^{p}\geq\alpha$}\big{)}\,\text{\rm d}\alpha$
	$\displaystyle\leq\int_{0}^{n^{\|p\|}}\big{(}\alpha^{\frac{1}{p}}\log(n+1)\big{)}% ^{\frac{\|p\|}{\|p\|+1}}\,\text{\rm d}\alpha$	(Lemma 9)
	$\displaystyle=\int_{0}^{n^{\|p\|}}\big{(}\log(n+1)\big{)}^{\frac{\|p\|}{\|p\|+1}}% \alpha^{-\frac{1}{\|p\|+1}}\,\text{\rm d}\alpha$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}\cdot n^{\frac{\|p\|^{2}}{\|p\|+1}}\big{(}\log(n+1)% \big{)}^{\frac{\|p\|}{\|p\|+1}}\leavevmode\nobreak\ .$

Taking $p$ -th root on both sides gives:

\frac{\mathrm{ALG}}{\mathrm{OPT}}\leavevmode\nobreak\ \geq\underbrace{\bigg{(}% \frac{|p|}{|p|+1}\bigg{)}^{\frac{1}{|p|}}}_{\text{$\Omega(1)$ for $|p|=\Omega(% 1)$}}\cdot\leavevmode\nobreak\ n^{-\frac{|p|}{|p|+1}}\big{(}\log(n+1)\big{)}^{% -\frac{1}{|p|+1}}\leavevmode\nobreak\ .

5 From Harmonic to Egalitarian Welfare: $-\infty\leq p\leq-1$

This section considers the regime between harmonic welfare and egalitarian welfare. In this case, we need to introduce an auxiliary component to obtain a new lower bound of the agents’ utilities that is better than the $\nicefrac{{1}}{{n}}$ base utility given by Uniform Allocation.

Although Nashian Greedy on its own fails to provide a better bound, we observe that the number of agents who are in trouble cannot exceed $\sqrt{n\log(n+1)}$ (see Corollary 13). Hence, we may reserve a constant fraction of each item to help these agents.

How can we identify the agents in trouble? Naïvely, it is natural to consider an egalitarian greedy algorithm that allocates the item to the agents who currently have the lowest utilities. However, an agent may have low utility just because its valuable items are yet to arrive. It would be a mistake to allocate items to such an agent purely based on egalitarian consideration. Instead, we introduce for each agent $a\in A$ a regularization term $R_{a}$ , which equals the agent’s remaining monopolist utility, i.e., its total utility for the items yet to arrived, scaled by a $\sqrt{n\log(n+1)}$ factor that is driven by the analysis. Our new component is the egalitarian greedy allocation with respect to the regularized utilities $U_{a}+R_{a}$ .

We remark that Barman et al. [8] also introduced an algorithmic sub-routine to identify the agents in trouble, and already observed the necessity to consider both the agents’ utilities and their remaining monopolist utilities. Our regularized egalitarian allocation gives an alternative, and in our opinion, more natural way to implement this idea. The resulting competitive ratios are also asymptotically better than those in [8].

Below we present the formal definition of this Mixed Greedy algorithm that combines Nashian Greedy and Regularized Egalitarian Greedy. For cleaner constants in the analysis, we further relax the problem by letting there be two copies of each item. This relaxation only affects the competitive ratio by a constant factor.

This algorithm achieves the same and nearly optimal competitive ratio simultaneously for all values of $p$ from harmonic welfare to egalitarian welfare.

Theorem 10.

For any $-\infty\leq p\leq-1$ , Mixed Greedy is $O\big{(}\sqrt{n\log n}\big{)}$ -competitive for the relaxed online $p$ -mean welfare maximization problem.

5.1 Properties of the Regularized Utilities

Definition 11 (Critical Agents).

For any time $t\in I$ , and for any $\beta\geq 0$ , let $C_{\beta}(t)$ be the set of $\beta$ -critical agents at time $t$ , whose regularized utilities are at most a $\beta$ fraction of the optimal $p$ -mean welfare, i.e.:

C_{\beta}(t)=\Big{\{}a\in A:\,U_{a}(t)+R_{a}(t)\leq\beta\cdot\mathrm{OPT}\Big{% \}}\leavevmode\nobreak\ .

Lemma 12.

For any time $t\in I$ and any $\beta>0$ , the fraction of $\beta$ -critical agents at time $t$ is upper bounded by:

\frac{|C_{\beta}(t)|}{n}\leq\max\Big{\{}\,\big{(}2\beta\log(n+1)\big{)}^{\frac% {|p|}{|p|+1}}\,,\,(2\Phi\beta)^{|p|}\,\Big{\}}\leavevmode\nobreak\ .

Proof.

On one hand, by the definition of $p$ -mean welfare and $p<0$ , we have:

\mathrm{OPT}^{p}=\frac{1}{n}\sum_{a\in A}\big{(}U_{a}^{*}\big{)}^{-|p|}\geq% \frac{1}{n}\sum_{a\in C_{\beta}(t)}\big{(}U_{a}^{*}\big{)}^{-|p|}\leavevmode% \nobreak\ .

On the other hand, all $\beta$ -critical agents are $\beta$ -bad. We have:

$\displaystyle\frac{1}{n}\sum_{a\in C_{\beta}(t)}U_{a}^{*}$	$\displaystyle\leq\beta\log(n+1)\cdot\mathrm{OPT}+\frac{1}{n}\sum_{a\in C_{% \beta}(t)}\Big{(}1-\int_{0}^{t}v_{a}(s)\,\text{\rm d}s\Big{)}$	(Lemma 8)
	$\displaystyle=\beta\log(n+1)\cdot\mathrm{OPT}+\frac{1}{n}\sum_{a\in C_{\beta}(% t)}\Phi\cdot R_{a}(t)$
	$\displaystyle\leq\bigg{(}\beta\log(n+1)+\frac{\|C_{\beta}(t)\|}{n}\cdot\Phi\beta% \bigg{)}\cdot\mathrm{OPT}\leavevmode\nobreak\ .$	( $R_{a}(t)\leq U_{a}(t)+R_{a}(t)\leq\beta\cdot\mathrm{OPT}$ )

By Hölder’s inequality:

\bigg{(}\frac{1}{n}\sum_{a\in C_{\beta}(t)}\big{(}U_{a}^{*}\big{)}^{-|p|}\bigg% {)}^{\frac{1}{|p|+1}}\bigg{(}\frac{1}{n}\sum_{a\in C_{\beta}(t)}U_{a}^{*}\bigg% {)}^{\frac{|p|}{|p|+1}}\geq\frac{1}{n}\sum_{a\in C_{\beta}(t)}1=\frac{|C_{% \beta}(t)|}{n}\leavevmode\nobreak\ .

Combining these inequalities gives:

\bigg{(}\beta\log(n+1)+\frac{|C_{\beta}(t)|}{n}\cdot\Phi\beta\bigg{)}^{\frac{|% p|}{|p|+1}}\geq\frac{|C_{\beta}(t)|}{n}\leavevmode\nobreak\ .

Rearranging terms, we have:

\beta\log(n+1)\cdot\bigg{(}\frac{n}{|C_{\beta}(t)|}\bigg{)}^{\frac{|p|+1}{|p|}% }+\Phi\,\beta\cdot\bigg{(}\frac{n}{|C_{\beta}(t)|}\bigg{)}^{\frac{1}{|p|}}\geq 1% \leavevmode\nobreak\ .

Hence, either the first part is at least a half, in which case:

\frac{|C_{\beta}(t)|}{n}\leq\big{(}2\beta\log(n+1)\big{)}^{\frac{|p|}{|p|+1}}% \leavevmode\nobreak\ ,

or the second part is at least a half, in which case:

\frac{|C_{\beta}(t)|}{n}\leq(2\Phi\beta)^{|p|}\leavevmode\nobreak\ .

In either case, the lemma follows. $\hfill\blacktriangleleft$

Corollary 13.

For any time $t\in I$ , and:

\beta^{*}=\frac{1}{2}\cdot n^{-\frac{1}{2}-\frac{1}{2|p|}}(\log(n+1))^{-\frac{% 1}{2}+\frac{1}{2|p|}}\leavevmode\nobreak\ ,

(5)

we have:

\big{|}C_{\beta^{*}}(t)\big{|}\leq\sqrt{n\log(n+1)}\leavevmode\nobreak\ .

Using Corollary 13, we derive a universal lower bound for all agents’ utilities.

Lemma 14.

For the choice of $\beta^{*}$ in Equation 5, and any agent $a\in A$ , we have:

U_{a}\geq\beta^{*}\cdot\mathrm{OPT}\leavevmode\nobreak\ .

Proof.

We will prove a stronger claim that for any agent $a\in A$ and any time $t\in I$ :

U_{a}(t)+R_{a}(t)\geq\beta^{*}\cdot\mathrm{OPT}\leavevmode\nobreak\ .

(6)

Then, the lemma holds as the special case when $t=T$ because $R_{a}(T)=0$ .

Initially at time $t=0$ , we have:

R_{a}(0)=\frac{1}{\Phi}>\beta^{*}\geq\beta^{*}\cdot\mathrm{OPT}\leavevmode% \nobreak\ .

To prove that Equation 6 holds at all time $t$ , it suffices to show that for any time $t\in I$ when there is at least one $\beta^{*}$ -critical agent $a\in C_{\beta^{*}}(t)$ , the allocation of the egalitarian copy of item $t$ weakly increases the regularized egalitarian welfare.

For any critical agent $a\in C_{\beta^{*}}(t)$ , we have:

\frac{\,\text{\rm d}missing}{\,\text{\rm d}t}R_{a}(t)=-\frac{v_{a}(t)}{\Phi}% \leavevmode\nobreak\ .

Further, Corollary 13 asserts that at most $\sqrt{n\log(n+1)}$ agents are $\beta^{*}$ -critical. Hence, allocating the egalitarian copy of item $t$ equally among these $\beta^{*}$ -critical agents would have yielded:

\frac{\,\text{\rm d}missing}{\,\text{\rm d}t}U_{a}(t)\geq\frac{v_{a}(t)}{\sqrt% {n\log(n+1)}}=\frac{v_{a}(t)}{\Phi}\leavevmode\nobreak\ ,

and weakly increased the regularized egalitarian welfare. The greedy allocation of the algorithm would only do better. $\hfill\blacktriangleleft$

5.2 Proof of Theorem 10

The proof is almost verbatim to that of Theorem 6, except that we will use the newly developed Lemma 14 to lower bound the agents’ utilities, replacing the basic bound $U_{a}\geq\nicefrac{{1}}{{n}}$ .

Consider the $p$ -th power of the Mixed Greedy algorithm’s $p$ -mean welfare, normalized by the $p$ -th power of $\mathrm{OPT}$ :

\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}=\frac{1}{n}\sum_{a\in A}% \bigg{(}\frac{U_{a}}{\mathrm{OPT}}\bigg{)}^{p}\leavevmode\nobreak\ .

By Lemma 14 and $p<0$ , we have:

\bigg{(}\frac{U_{a}}{\mathrm{OPT}}\bigg{)}^{p}\leq(\beta^{*})^{p}\leavevmode% \nobreak\ .

The above ratio can therefore be written as:

$\displaystyle\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}$	$\displaystyle=\int_{0}^{(\beta^{*})^{p}}(\text{fraction of agents with $\big{(% }\nicefrac{{U_{a}}}{{\mathrm{OPT}}}\big{)}^{p}\geq\alpha$)}\,\text{\rm d}\alpha$
	$\displaystyle\leq\int_{0}^{(\beta^{*})^{p}}\big{(}\alpha^{\frac{1}{p}}\log(n+1% )\big{)}^{\frac{\|p\|}{\|p\|+1}}\,\text{\rm d}\alpha$	(Lemma 9)
	$\displaystyle=\int_{0}^{(\beta^{*})^{p}}\big{(}\log(n+1)\big{)}^{\frac{\|p\|}{\|p% \|+1}}\alpha^{-\frac{1}{\|p\|+1}}\,\text{\rm d}\alpha$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}(\beta^{*})^{-\frac{\|p\|^{2}}{\|p\|+1}}\big{(}\log% (n+1)\big{)}^{\frac{\|p\|}{\|p\|+1}}$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}2^{{\frac{\|p\|^{2}}{\|p\|+1}}}\big{(}n\log(n+1)% \big{)}^{\frac{\|p\|}{2}}\leavevmode\nobreak\ .$

Taking $p$ -th root on both sides gives:

\frac{\mathrm{ALG}}{\mathrm{OPT}}\leavevmode\nobreak\ \geq\leavevmode\nobreak% \ \underbrace{\bigg{(}\frac{|p|}{|p|+1}\bigg{)}^{\frac{1}{|p|}}2^{-{\frac{|p|}% {|p|+1}}}}_{\text{$\Omega(1)$ for $p\leq-1$}}\leavevmode\nobreak\ \cdot% \leavevmode\nobreak\ {\Big{(}\sqrt{n\log(n+1)}\Big{)}}^{-1}\leavevmode\nobreak\ .

6 Hardness Results

In this section, we complement our algorithmic results with nearly-tight hardness results. The proofs are deferred to the full version of the paper.

6.1 Hardness for the Nashian and Positive Regimes: $p\geq-\nicefrac{{1}}{{\log n}}$

Recall that the online primal dual algorithm by Devanur and Jain [17] is $\nicefrac{{1}}{{p}}$ -competitive for $0<p\leq 1$ , and Nashian Greedy is $O(\log n)$ -competitive for $-\nicefrac{{1}}{{\log n}}\leq p\leq\nicefrac{{1}}{{\log n}}$ (Corollary 4). Theorem 15 complement these competitive ratios with hardness results that match them up to a lower-order term.

Theorem 15.

For any $p\leq 1$ and any online algorithm for online $p$ -mean welfare maximization, the competitive ratio is no smaller than:

\begin{cases}\Omega\big{(}\frac{1}{p}\big{)}&\mbox{if $p\geq\frac{\log\log n}{% \log n}$;}\\[4.30554pt] \Omega\big{(}\frac{\log n}{\log\log n}\big{)}&\mbox{otherwise,}\end{cases}

even when the agents have binary valuations (and unit monopolist utilities).

This asymptotic lower bound holds for a sufficiently large number of agents. It implicitly covers three cases. If $p$ is a positive constant independent of the number of agents $n$ , it characterizes how the competitive ratio changes as $p$ tends to $0$ . If $p(n)$ is a function of the number of agents $n$ that converges to zero as $n$ goes to infinity, e.g., $p(n)=\nicefrac{{1}}{{\log n}}$ , the theorem asserts that for the competitive ratio is no smaller than $\Omega(\nicefrac{{1}}{{p(n)}})$ if $p(n)$ converges to zero slower than function $\nicefrac{{\log\log n}}{{\log n}}$ , or no smaller than $\Omega(\nicefrac{{\log n}}{{\log\log n}})$ otherwise. The latter bound also applies when $p$ is a negative constant or a negative function $p(n)$ that converges to zero.

6.2 Hardness for the Negative Regime: $p\leq-\nicefrac{{1}}{{\log n}}$

Recall that Nashian Greedy is $n^{|p|}$ -competitive for $-o(1)\leq p\leq-\nicefrac{{1}}{{\log n}}$ and $n^{\nicefrac{{|p|}}{{(|p|+1)}}}$ -competitive for $-1\leq p\leq-\Omega(1)$ , up to lower-order and logarithmic factors (Theorem 3). Moreover, Mixed Greedy is $O(\sqrt{n\log n})$ -competitive for $-\infty\leq p\leq-1$ (Theorem 10). Theorems 16, 17, and 18 complement these algorithmic results with almost matching lower bounds.

Theorem 16.

For any $-o(1)\leq p\leq-\omega(\nicefrac{{\log\log n}}{{\log n}})$ and any online algorithm for online $p$ -mean welfare maximization, the competitive ratio is no smaller than $n^{|p|-o(|p|)}$ , even when the agents have binary valuations (and unit monopolist utilities).

Theorem 17.

For any $-1\leq p\leq\Omega(1)$ and any online algorithm for online $p$ -mean welfare maximization, the competitive ratio is no smaller than $n^{\frac{|p|}{|p|+1}-o(1)}$ , even when the agents have binary valuations (and unit monopolist utilities).

Theorem 18.

For any $-\infty\leq p\leq-1$ and any online algorithm for online $p$ -mean welfare maximization, the competitive ratio is no smaller than $n^{\frac{1}{2}-o(1)}$ , even when the agents have binary valuations (and unit monopolist utilities).

References

[1] Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: analysing a food bank problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 2540–2546, 2015. doi:10.5555/2832581.2832604.
[2] Martin Aleksandrov and Toby Walsh. Online fair division: A survey. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 13557–13562, 2020. doi:10.1609/aaai.v34i09.7081.
[3] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms, 2(4):640–660, 2006. doi:10.1145/1198513.1198522.
[4] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online Nash social welfare maximization with predictions. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1–19. SIAM, 2022. doi:10.1137/1.9781611977073.1.
[5] Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pages 20–28, 2023. doi:10.24963/ijcai.2023/3.
[6] Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 31–40, 2006. doi:10.1145/1132516.1132522.
[7] Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G Sundaram. Tight approximation algorithms for p-mean welfare under subadditive valuations. In Proceedings of the 28th Annual European Symposium on Algorithms, pages 11:1–11:17, 2020. doi:10.4230/LIPIcs.ESA.2020.11.
[8] Siddharth Barman, Arindam Khan, and Arnab Maiti. Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 4793–4800, 2022. doi:10.1609/aaai.v36i5.20406.
[9] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation, pages 557–574, 2018. doi:10.1145/3219166.3219176.
[10] Gerdus Benadè, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. In Proceedings of the 19th ACM Conference on Economics and Computation, pages 593–610, 2018. doi:10.1145/3219166.3219179.
[11] Ivona Bezáková and Varsha Dani. Allocating indivisible goods. ACM SIGecom Exchanges, 5(3):11–18, 2005. doi:10.1145/1120680.1120683.
[12] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009. doi:10.1287/moor.1080.0363.
[13] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1–32, 2019. doi:10.1145/3355902.
[14] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 107–116, 2009. doi:10.1109/FOCS.2009.51.
[15] Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and efficient allocations under subadditive valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5269–5276, 2021. doi:10.1609/aaai.v35i6.16665.
[16] Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for learning-augmented online allocation. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, pages 43:1–43:21, 2023. doi:10.4230/LIPIcs.ICALP.2023.43.
[17] Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 137–144, 2012. doi:10.1145/2213977.2213992.
[18] Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, and Jan Vondrák. A constant-factor approximation for nash social welfare with subadditive valuations. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 467–478, 2024. doi:10.1145/3618260.3649740.
[19] Yuda Feng and Shi Li. A note on approximating weighted nash social welfare with additive valuations. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming, 2024. doi:10.4230/LIPIcs.ICALP.2024.63.
[20] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash social welfare under submodular valuations through (un)matchings. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2673–2687, 2020. doi:10.1145/3613452.
[21] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, 2011. doi:10.5555/1972457.1972490.
[22] Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allocations with normalized valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5440–5447, 2021. doi:10.1609/aaai.v35i6.16685.
[23] MohammadTaghi Hajiaghayi, Debmalya Panigrahi, Mohammad Khani, and Max Springer. Online algorithms for the Santa Claus problem. In Proceedings of the 36th Annual Conference on Advances in Neural Information Processing Systems, pages 30732–30743, 2022. doi:10.5555/3600270.3602498.
[24] Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei. Online nash welfare maximization without predictions. In Proceedings of the 19th International Conference on Web and Internet Economics, pages 402–419. Springer, 2023. doi:10.1007/978-3-031-48974-7_23.
[25] Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online matching: A brief survey. ACM SIGecom Exchanges, 22:135–158, 2024. doi:10.1145/3699824.3699837.
[26] Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319–325, 2000. doi:10.1016/S0304-3975(99)00140-1.
[27] Richard Karp, Umesh Vazirani, and Vijay Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 352–358, 1990. doi:10.1145/100216.100262.
[28] Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items. Information Processing Letters, 122:17–20, 2017. doi:10.1016/j.ipl.2017.01.012.
[29] Wenzheng Li and Jan Vondrák. A constant-factor approximation algorithm for nash social welfare with submodular valuations. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 25–36, 2022. doi:10.1109/FOCS52979.2021.00012.
[30] Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013. doi:10.1561/0400000057.
[31] Hervé Moulin. Fair division and collective welfare. MIT press, 2004. doi:10.7551/mitpress/2954.001.0001.
[32] Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63–91, 1974. doi:10.1016/0022-0531(74)90075-1.
[33] Toby Walsh. Online cake cutting. In Proceedings of the 2nd International Conference on Algorithmic Decision Theory, pages 292–305. Springer, 2011. doi:10.1007/978-3-642-24873-3_22.
[34] David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 911–912, 2020. doi:10.1145/3391403.3399467.

[bib.bib1] [1] Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: analysing a food bank problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 2540–2546, 2015. doi:10.5555/2832581.2832604.

[bib.bib2] [2] Martin Aleksandrov and Toby Walsh. Online fair division: A survey. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 13557–13562, 2020. doi:10.1609/aaai.v34i09.7081.

[bib.bib3] [3] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms, 2(4):640–660, 2006. doi:10.1145/1198513.1198522.

[bib.bib4] [4] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online Nash social welfare maximization with predictions. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1–19. SIAM, 2022. doi:10.1137/1.9781611977073.1.

[bib.bib5] [5] Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, pages 20–28, 2023. doi:10.24963/ijcai.2023/3.

[bib.bib6] [6] Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 31–40, 2006. doi:10.1145/1132516.1132522.

[bib.bib7] [7] Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G Sundaram. Tight approximation algorithms for p-mean welfare under subadditive valuations. In Proceedings of the 28th Annual European Symposium on Algorithms, pages 11:1–11:17, 2020. doi:10.4230/LIPIcs.ESA.2020.11.

[bib.bib8] [8] Siddharth Barman, Arindam Khan, and Arnab Maiti. Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 4793–4800, 2022. doi:10.1609/aaai.v36i5.20406.

[bib.bib9] [9] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation, pages 557–574, 2018. doi:10.1145/3219166.3219176.

[bib.bib10] [10] Gerdus Benadè, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. In Proceedings of the 19th ACM Conference on Economics and Computation, pages 593–610, 2018. doi:10.1145/3219166.3219179.

[bib.bib11] [11] Ivona Bezáková and Varsha Dani. Allocating indivisible goods. ACM SIGecom Exchanges, 5(3):11–18, 2005. doi:10.1145/1120680.1120683.

[bib.bib12] [12] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009. doi:10.1287/moor.1080.0363.

[bib.bib13] [13] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1–32, 2019. doi:10.1145/3355902.

[bib.bib14] [14] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 107–116, 2009. doi:10.1109/FOCS.2009.51.

[bib.bib15] [15] Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and efficient allocations under subadditive valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5269–5276, 2021. doi:10.1609/aaai.v35i6.16665.

[bib.bib16] [16] Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for learning-augmented online allocation. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, pages 43:1–43:21, 2023. doi:10.4230/LIPIcs.ICALP.2023.43.

[bib.bib17] [17] Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 137–144, 2012. doi:10.1145/2213977.2213992.

[bib.bib18] [18] Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, and Jan Vondrák. A constant-factor approximation for nash social welfare with subadditive valuations. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 467–478, 2024. doi:10.1145/3618260.3649740.

[bib.bib19] [19] Yuda Feng and Shi Li. A note on approximating weighted nash social welfare with additive valuations. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming, 2024. doi:10.4230/LIPIcs.ICALP.2024.63.

[bib.bib20] [20] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash social welfare under submodular valuations through (un)matchings. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2673–2687, 2020. doi:10.1145/3613452.

[bib.bib21] [21] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, 2011. doi:10.5555/1972457.1972490.

[bib.bib22] [22] Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allocations with normalized valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5440–5447, 2021. doi:10.1609/aaai.v35i6.16685.

[bib.bib23] [23] MohammadTaghi Hajiaghayi, Debmalya Panigrahi, Mohammad Khani, and Max Springer. Online algorithms for the Santa Claus problem. In Proceedings of the 36th Annual Conference on Advances in Neural Information Processing Systems, pages 30732–30743, 2022. doi:10.5555/3600270.3602498.

[bib.bib24] [24] Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei. Online nash welfare maximization without predictions. In Proceedings of the 19th International Conference on Web and Internet Economics, pages 402–419. Springer, 2023. doi:10.1007/978-3-031-48974-7_23.

[bib.bib25] [25] Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online matching: A brief survey. ACM SIGecom Exchanges, 22:135–158, 2024. doi:10.1145/3699824.3699837.

[bib.bib26] [26] Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319–325, 2000. doi:10.1016/S0304-3975(99)00140-1.

[bib.bib27] [27] Richard Karp, Umesh Vazirani, and Vijay Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 352–358, 1990. doi:10.1145/100216.100262.

[bib.bib28] [28] Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items. Information Processing Letters, 122:17–20, 2017. doi:10.1016/j.ipl.2017.01.012.

[bib.bib29] [29] Wenzheng Li and Jan Vondrák. A constant-factor approximation algorithm for nash social welfare with submodular valuations. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 25–36, 2022. doi:10.1109/FOCS52979.2021.00012.

[bib.bib30] [30] Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013. doi:10.1561/0400000057.

[bib.bib31] [31] Hervé Moulin. Fair division and collective welfare. MIT press, 2004. doi:10.7551/mitpress/2954.001.0001.

[bib.bib32] [32] Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63–91, 1974. doi:10.1016/0022-0531(74)90075-1.

[bib.bib33] [33] Toby Walsh. Online cake cutting. In Proceedings of the 2nd International Conference on Algorithmic Decision Theory, pages 292–305. Springer, 2011. doi:10.1007/978-3-642-24873-3_22.

[bib.bib34] [34] David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 911–912, 2020. doi:10.1145/3391403.3399467.

$\displaystyle\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}$	$\displaystyle=\int_{0}^{n^{\|p\|}}\big{(}\text{fraction of agents with $\big{(}% \nicefrac{{U_{a}}}{{\mathrm{OPT}}}\big{)}^{p}\geq\alpha$}\big{)}\,\text{\rm d}\alpha$
	$\displaystyle\leq\int_{0}^{n^{\|p\|}}\big{(}\alpha^{\frac{1}{p}}\log(n+1)\big{)}% ^{\frac{\|p\|}{\|p\|+1}}\,\text{\rm d}\alpha$	(Lemma 9)
	$\displaystyle=\int_{0}^{n^{\|p\|}}\big{(}\log(n+1)\big{)}^{\frac{\|p\|}{\|p\|+1}}% \alpha^{-\frac{1}{\|p\|+1}}\,\text{\rm d}\alpha$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}\cdot n^{\frac{\|p\|^{2}}{\|p\|+1}}\big{(}\log(n+1)% \big{)}^{\frac{\|p\|}{\|p\|+1}}\leavevmode\nobreak\ .$

$\displaystyle\bigg{(}\frac{\mathrm{ALG}}{\mathrm{OPT}}\bigg{)}^{p}$	$\displaystyle=\int_{0}^{(\beta^{*})^{p}}(\text{fraction of agents with $\big{(% }\nicefrac{{U_{a}}}{{\mathrm{OPT}}}\big{)}^{p}\geq\alpha$)}\,\text{\rm d}\alpha$
	$\displaystyle\leq\int_{0}^{(\beta^{*})^{p}}\big{(}\alpha^{\frac{1}{p}}\log(n+1% )\big{)}^{\frac{\|p\|}{\|p\|+1}}\,\text{\rm d}\alpha$	(Lemma 9)
	$\displaystyle=\int_{0}^{(\beta^{*})^{p}}\big{(}\log(n+1)\big{)}^{\frac{\|p\|}{\|p% \|+1}}\alpha^{-\frac{1}{\|p\|+1}}\,\text{\rm d}\alpha$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}(\beta^{*})^{-\frac{\|p\|^{2}}{\|p\|+1}}\big{(}\log% (n+1)\big{)}^{\frac{\|p\|}{\|p\|+1}}$
	$\displaystyle=\frac{\|p\|+1}{\|p\|}2^{{\frac{\|p\|^{2}}{\|p\|+1}}}\big{(}n\log(n+1)% \big{)}^{\frac{\|p\|}{2}}\leavevmode\nobreak\ .$

The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contributions

1.1.1 Optimal Competitive Ratios (up to Lower-Order Terms)

1.1.2 Long Arm of Nashian Allocation

1.1.3 Our Techniques

1.2 Further Related Work

2 Preliminaries

2.1 Model

2.1.1 Discrete Time

2.1.2 Continuous Time

2.1.3 Assumption of Unit Monopolist Utilities

2.2 Competitive Analysis

2.2.1 Offline Optimal Allocation

2.2.2 Competitive Online Algorithms

2.3 Relaxation of Online 𝒑-Mean Welfare Maximization

Lemma 1.

Lemma 2.

3 Nashian Regime: −𝒐⁢(𝟏)≤𝒑≤𝟏/𝐥𝐨𝐠⁡𝒏

Theorem 3.

Corollary 4.

Lemma 5 (Fundamental Lemma of Nashian Allocation).

Proof.

Proof of Theorem 3.

4 From Nash to Harmonic Welfare: −𝟏≤𝒑≤−𝛀⁢(𝟏)

Theorem 6.

4.1 Further Properties of Nashian Allocation

Definition 7 (Bad Agents).

Lemma 8.

Proof.

Lemma 9.

Proof.

4.2 Proof of Theorem 6

5 From Harmonic to Egalitarian Welfare: −∞≤𝒑≤−𝟏

Theorem 10.

5.1 Properties of the Regularized Utilities

Definition 11 (Critical Agents).

Lemma 12.

Proof.

Corollary 13.

Lemma 14.

Proof.

5.2 Proof of Theorem 10

6 Hardness Results

6.1 Hardness for the Nashian and Positive Regimes: 𝒑≥−𝟏/𝐥𝐨𝐠⁡𝒏

Theorem 15.

6.2 Hardness for the Negative Regime: 𝒑≤−𝟏/𝐥𝐨𝐠⁡𝒏

Theorem 16.

Theorem 17.

Theorem 18.

References

2.3 Relaxation of Online $𝒑$ -Mean Welfare Maximization

3 Nashian Regime: $-o(1)\leq p\leq\nicefrac{{1}}{{\log n}}$

4 From Nash to Harmonic Welfare: $-1\leq p\leq-\Omega(1)$

5 From Harmonic to Egalitarian Welfare: $-\infty\leq p\leq-1$

6.1 Hardness for the Nashian and Positive Regimes: $p\geq-\nicefrac{{1}}{{\log n}}$

6.2 Hardness for the Negative Regime: $p\leq-\nicefrac{{1}}{{\log n}}$