# Best Response Sequences and Tradeoffs in Submodular Resource Allocation
Games

Rohit Konda  Student Member, IEEE  Rahul Chandan Student Member, IEEE  David
Grimsman Member, IEEE  Jason R. Marden Fellow, IEEE R. Konda
(rkonda@ucsb.edu), R. Chandan, and J. R. Marden are with the Department of
Electrical and Computer Engineering at the University of California Santa
Barbara and D. Grimsman is with the Department of Computer Science at Brigham
Young University. Preliminary results of this work were presented at the
_American Control Conference_ , Atlanta GA, June 2022 [1]. This work is
supported by ONR grant #N00014-20-1-2359, AFOSR grants #FA9550-20-1-0054 and
#FA9550-21-1-0203, and the Army Research Lab through the ARL DCIST CRA
#W911NF-17-2-0181.

###### Abstract

Deriving competitive, distributed solutions to multi-agent problems is crucial
for many developing application domains; Game theory has emerged as a useful
framework to design such algorithms. However, much of the attention within
this framework is on the study of equilibrium behavior, whereas transient
behavior is often ignored. Therefore, in this paper we study the transient
efficiency guarantees of _best response processes_ in the context of
_submodular resource allocation games_ , which find application in various
engineering contexts. Specifically the main focus of this paper is on
characterizing the optimal short-term system-level behavior under the best-
response process. Interestingly, the resulting transient performance
guarantees are relatively close to the optimal asymptotic performance
guarantees. Furthermore, we characterize the trade-offs that result when
optimizing for both asymptotic and transient efficiency through various
utility designs.

Game Theory, Optimization, Utility Design, Distributed Algorithms, Resource
Allocation

##  1 Introduction

Multi-agent architectures have recently gained considerable attention due to
their widespread applications including, but not limited to, swarm formation
control [2], e-commerce [3], traffic control [4], and smart grid pricing [5].
The underlying goal of these distributed systems is to coordinate agents to
desirable system states, as measured by some global objective, through local
decision making processes. As such, _game theoretic methods_ have emerged as
an important design methodology in these settings. In this approach, each
agent is treated as a player in a non-cooperative game with their decision-
making governed by a local-objective or _utility_ function.

Figure 1: If a given multi-agent scenario with $n$ agents is modeled as a
game, the construction of distributed algorithms can be decoupled into two
domains: the design of local objectives (utilities) and the design of the
learning dynamics. In this paper, we fix the dynamics to the classical $k$
round-robin best response and study the effects of the utility design on the
efficiency bounds for the resulting decision trajectory. Moreover, we
characterize the guarantees as the number of rounds $k$ increases.

Endowed with a utility function, each agent can update its decisions in a
self-interested manner to dynamically respond to environmental changes,
including those induced by other agents. In this work, we consider when agents
use the classical update rule - the _round-robin best response_ algorithm.
Under this process, the decision updates are done in a sequential manner: at
each iteration, a single, chosen agent optimizes its decision against its
utility function with all of the other agents keeping their decisions fixed.
As such, the utility structure of the agents can significantly influence the
underlying dynamical behavior of the agents: this is highlighted in Figure 1.
Understanding this relationship is important in classifying the emergent
behavior, especially when a system operator would like to design or tune the
utility functions in an optimal fashion.

The resulting limit points from running the best response process are exactly
the set of _Nash equilibrium_ ; in fact, the limit points of many different
types of update rules correspond to Nash equilibrium [6]. Thus, within a game-
theoretic framework, Nash equilibrium can operate as the fundamental model for
characterizing end-behavior. This is the approach taken by much of the
literature, where the limiting behavior of the round-robin best response
algorithm against the global objective is characterized (and possibly
optimized) through established performance metrics on the Nash equilibrium
(for e.g., see [7, 8, 9, 10]).

While the many of the existing theoretical results on the Nash equilibrium
behavior are positive, these performance guarantees only emerge
asymptotically. In fact, arriving at Nash equilibrium may even take an
exponential time [11], rendering the resulting characterizations irrelevant in
many realistic multi-agent scenarios. For example, there may be an extremely
large number of agents in the multi-agent scenario or the relevant situational
parameters may be time-varying and volatile or there may be computational and
run-time restrictions on the agents. In these instances, expecting that the
agents will converge to Nash equilibrium may not be a reasonable assumption.

Therefore, in this paper, we shift focus to the transient behavior of the
round-robin best response algorithm. Specifically, we benchmark the iterative
process to be the round-robin best response algorithm and study the
performance guarantees that result from various designs of utility functions
in the context of the well-studied class of _submodular resource allocation
games_. This class of games can model many relevant engineering applications
[12] and have convergence guarantees of the best response algorithm. The main
results of this paper are as follows.

| $k=1$ | $k>1$ | $k=\infty$
---|---|---|---
$\Gamma^{*}$ | $1-\mathrm{C}/2$ | $1-\mathrm{C}/2$ | $1-\mathrm{C}/e$
$\Gamma_{\mathrm{id}}$ | $(1+\mathrm{C})^{-1}$ | $(1+\mathrm{C})^{-1}$ | $(1+\mathrm{C})^{-1}$
| From [13] | Theorem 1 | Proposition 1
Table 1: Comparison of Efficiency Results of the $k$-round algorithm under the
naive utility design $\Gamma_{\mathrm{id}}$ and the optimal design
$\Gamma^{*}$ under different curvatures $\mathrm{C}\in[0,1]$.

  * •

Our first main result in Theorem 1 provides the optimal transient performance
guarantees for any finite $k\geq 1$ rounds, which is summarized in Table 1.
Interestingly, we note that these performance guarantees do not increase past
the first round. This non-intuitive result suggests minimal benefit in
performance when allowing agents to alter their decisions in response to other
agents.

  * •

In general, utility designs that optimize transient guarantees may not be
optimal for the asymptotic behavior (and vice-versa). Our second result
confirms this trade-off in submodular resource allocation games; in fact, in
Theorem 2, it is shown that optimizing for asymptotic performance guarantees
can result in arbitrarily bad transient performance guarantees. Furthermore,
we delineate the exact Pareto-optimal frontier for the asymptotic and
transient performance guarantees in Theorem 3 for a subclass of set covering
games.

In previous work [13], the efficiency guarantees for $k=1$ rounds were
characterized for resource allocation games. In this work, we extend these
results to consider the efficiency guarantees for finite rounds $k\geq 1$ and
asymptotic efficiency $k=\infty$ as well as consider the trade-offs between
optimizing for one-round and asymptotic efficiency. The results of this work
suggest an acute diminishing return on the achievable performance guarantees
as agents make successive locally optimal decisions. While the current
literature is sparse on characterizing short-term behavior of game-processes,
the non-intuitive results in this work indicate the importance of analyzing
the interaction between local objective designs, asymptotic performance, and
transient performance as a whole.

Moreover, this work belongs to a larger research trend that aims to study game
theoretic models beyond their respective equilibrium. In contrast to the
traditional game-theoretic approach, the _game dynamics_ are embraced as a
valuable feature of the game, where a rigorous study of actualized play can
provide important insights about the game model (see, for e.g., [14, 15, 16]).
Furthermore, characterizing performance guarantees along these game dynamics
is valuable to understanding the transient behavior of the agents. In contrast
to the study of equilibrium quality, the literature on transient guarantees is
much less developed. However, we highlight an important subset of works that
characterize transient performance guarantees in different game-theoretic
contexts: such problem domains include affine congestion games [17, 18, 19,
20], market sharing games [17, 21], basic utility games [21], series-parallel
networks, and load-balancing games [22, 23].

##  2 Model

We consider distributed settings that are modeled as _submodular resource
allocation games_ [12]. Let $\mathcal{I}=\\{1,\dots,n\\}$ be the collection of
agents that can possibly utilize a portion of a given finite set of resources
$\mathcal{R}=\\{r_{1},\dots,r_{d}\\}$. Each resource $r\in\mathcal{R}$ is
associated with a _welfare rule_ $w_{r}:\mathbb{N}\to\mathbb{R}_{>0}$ that
defines the welfare accrued at each resource based on number of agents that
utilize it. In this work, we assume that the welfare rule $w_{r}$ is non-
decreasing and concave (or that $w_{r}(j+1)-w_{r}(j)$ is non-negative and non-
increasing in $j$) and use the denotation $w_{r}(0)=0$. In this way,
additional utilization of resources by the agents has positive but decreasing
marginal return for the global objective. The choice of resource utilization
for each agent is given by its action set $\mathcal{A}_{i}\subseteq
2^{\mathcal{R}}$. As such, the quality of a joint action
$a=(a_{1},\dots,a_{n})\in\mathcal{A}=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}$
is classified through a system-level objective function
$\mathrm{W}:\mathcal{A}\to\mathbb{R}_{>0}$ of the form

$\mathrm{W}(a)=\sum_{r\in\mathcal{R}}{w_{r}(|a|_{r})},$ (1)

where $|a|_{r}=|\\{i\in\mathcal{I}:r\in a_{i}\\}|$ is the number of agents
that utilize $r$ in the joint action $a$. These types of objectives are
commonplace in many engineering domains, with applications in information
gathering, image segmentation, statistical summarization (see [24]). We
include a sample of these applications below.

######  Example 1 (Weapon-Target Assignment).

Consider a weapon-target assignment problem [25], in which a set of agents
$\mathcal{I}$ defend against a set of $\mathcal{R}$ targets. Each agent
$i\in\mathcal{I}$ has to decide which targets $r\in\mathcal{R}$ to defend
against with a $p_{d}$ chance of defending against each target, where its
decision $a_{i}\subset\mathcal{R}$ is a subset of targets. Each target is also
characterized by its relative value $v_{r}\geq 0$. As a whole, the set of
agents would like to maximize the expected value of the targets defended. As
such, the nonlinear objective of the agent’s decisions is denoted by

$\mathrm{W}(a)=\sum_{r\in\mathcal{R}}v_{r}\cdot\left(1-(1-p_{d})^{|a|_{r}}\right).$
(2)

Example 1A (Set Covering). If the probability of defending $p_{d}$ is $1$,
then we recover the problem of set covering [26]. In this domain, there is no
benefit for more than agent to defend against a target, and as a whole, the
agents would like to maximize the value of the targets defended. Thus, the
welfare function simplifies to

$\mathrm{W}(a)=\sum_{r\in\bigcup_{i}a_{i}}v_{r}.$ (3)

######  Example 2 (Wireless Transmission over a Network).

Consider a group of communicating agents, as in [27], that send transmissions
through a shared network with nodes $V$ and edges $E$. Each agent would like
to send a wireless transmission over the network from a given start node
$s_{i}$ to an end node $t_{i}$, and it must choose one out of the possible
paths from $s_{i}$ to $t_{i}$ to transmit across. Thus, the resource set is
$E$ and the action set $\mathcal{A}_{i}\subset 2^{E}$ is the possible set of
paths from $s_{i}$ to $t_{i}$. An edge $e$ may experience congestion if
multiple transmissions utilize it; we assume that with each additional
transmission, the rate of transmission experiences a harmonic-like decay. As a
whole, the agents would like to send their transmissions with the highest
rate. As such, the system welfare is

$\mathrm{W}(a)=\sum_{e\in\bigcup_{i}a_{i}}\sum_{j=1}^{|a|_{e}}\frac{1}{j}.$
(4)

The global directive of the agents is to coordinate to a joint action that
maximizes the system welfare, i.e.
$a^{\mathrm{opt}}\in\arg\max_{a\in\mathcal{A}}\mathrm{W}(a)$. In order to
coordinate the agents in a distributed fashion, we assume a game-theoretic
setup, where each agent optimizes its decision with respect to a given local
objective, or utility function $\mathrm{U}_{i}:\mathcal{A}\to\mathbb{R}$ in a
self-interested process. To establish the learning procedure of the agents, we
focus attention to a class of best response processes known as _$k$ -round
walks_ (or $k$ round-robin best response), explicitly stated in Algorithm 1.
At each step of the algorithm, an agent is selected in a round-robin fashion
to perform a best response; this goes on until $k$ rounds have been completed.
For a given joint action $\alpha\in\mathcal{A}$, we say the action
$a^{\mathrm{br}}_{i}$ is a _best response_ for agent $i$ if

$a^{\mathrm{br}}_{i}\in\
\text{Br}_{i}(\alpha_{-i})=\arg\max_{a_{i}\in\mathcal{A}_{i}}\mathrm{U}_{i}(a_{i},\alpha_{-i}),$
(5)

where $a_{-i}=(a_{1},\dots,a_{i-1},a_{i+1},\dots a_{n})$ denotes the joint
action $a$ without the action of agent $i$. We also assume that the round-
robin walk begins with none of resources being utilized by any of the agents,
denoted by the null joint action $a^{\varnothing}:=\varnothing$.

Algorithm 1 $k$-Round Walk

$a(0)\leftarrow a^{\varnothing}$, $i\leftarrow 1$, $\tau\leftarrow 1$, $k$,
$n$

while $\tau\leq kn$ do

Modify action of agent $i$ to
$a_{i}(\tau)\leftarrow\text{Br}_{i}(a_{-i}(\tau-1))$;

Fix other agent actions to $a_{-i}(\tau)\leftarrow a_{-i}(\tau-1)$;

Increment $\tau$ by $1$;

Set the next agent $i\leftarrow\tau\mod n$ by round-robin;

end while

return $a(kn)$

Running the $k$-round walk algorithm induces the action trajectory
$a(0)=a^{\varnothing},a(1),\dots,a(kn-1),a(kn)$ with $a(kn)$ being the end
resulting joint action. The central goal of this work is to understand how the
utility functions of the agents affect the behavior of the $k$-round walk. To
this end, the performance of the joint action $a^{k}\doteq a(kn)$ after $k$
rounds can be characterized through the following metric 111We note that the
resulting action $a(kn)$ may not be unique if the best response
$\text{Br}_{i}(a_{-i}(\tau))$ is not unique for some $\tau$. In this case, we
overload $\mathrm{W}(a^{k})$ to mean the minimum welfare $\min_{\alpha\in
a^{k}}\mathrm{W}(\alpha)$ for the $k$-round walk.

$\mathrm{Eff}(\mathrm{G};k)=\frac{\mathrm{W}(a^{k})}{\max_{a\in\mathcal{A}}{\mathrm{W}(a)}}\in[0,1],$
(6)

where a ratio closer to $1$ implies the efficiency of the joint action after
$k$ rounds is closer to optimal. We use tuple
$\mathrm{G}\triangleq(\mathcal{I},\mathcal{A},\mathcal{R},\mathrm{W},\\{\mathrm{U}_{i}\\}_{i\in\mathcal{I}})$
to define the game instance under consideration. Furthermore, we characterize
the performance of the limit points 222Since resource allocation games are
_potential games_ [28], the limit points of $k$-round walks are necessarily a
subset of the set of Nash equilbrium. of the $k$-round walk as

$\mathrm{Eff}(\mathrm{G};\infty)=\frac{\mathrm{W}(\lim_{k\to\infty}a^{k})}{\max_{a\in\mathcal{A}}{\mathrm{W}(a)}}.$
(7)

Accordingly, the form of the utility functions has a significant impact on the
given metric $\mathrm{Eff}(\mathrm{G};k)$. One natural utility function to
consider is the _common-interest_ (CI) utility, where all the agents share the
same utility function $\mathrm{U}_{i}(a)\equiv\mathrm{W}(a)$ for all
$a\in\mathcal{A}$ and $i\in\mathcal{I}$. In line with literature on submodular
optimization [29], we demonstrate that common interest utilities exhibit
constant factor efficiency guarantees $\mathrm{Eff}(\mathrm{G};k)$. However,
as unveiled by subsequent results in this work, by finely adjusting the
utility functions, we can achieve superior efficiency guarantees. Following
this perspective, lets consider utility functions of the form

$\mathrm{U}_{i}(a_{i},a_{-i})=\sum_{r\in\mathcal{R}}\tilde{w}_{r}(|a|_{r}),$
(8)

where the _distribution rule_ $\tilde{w}_{r}:\mathbb{N}\to\mathbb{R}_{>0}$
defines the resource-specific agent utility determined by $|a|_{r}$. In
general, $\tilde{w}_{r}\neq w_{r}$ may not be equivalent 333It is possible to
introduce locality to Eq. (8), where value is summed across agent selections
$r\in a_{i}$ instead of $r\in\mathcal{R}$. We discuss this in the Appendix..
We also assume that $\tilde{w}_{r}$ is non-decreasing and concave with
$\tilde{w}_{r}(1)=w_{r}(1)$ for all $r\in\mathcal{R}$. Now, the choice of the
distribution rules $\tilde{w}_{r}$ influences the resulting joint action
trajectory, and in turn the resulting end joint action $a^{k}$.

In most scenarios of interest, a system designer is required to specify the
distribution rules $\tilde{w}_{r}$ without specific knowledge of the resource
allocation game parameters, such as the number of agent $\mathcal{I}$ or the
action set $\mathcal{A}$. To that end, let $\mathcal{W}$ be the set of
possible welfare rules that could be associated with any resource, i.e.,
$w_{r}\in\mathcal{W}$ for all $r\in\mathcal{R}$. Here, the system designer is
tasked with associating a distribution rule to each type of resource, i.e.,
the distribution rule for any resource $r\in\mathcal{R}$ with the welfare rule
$w_{r}$ is of the form $\tilde{w}_{r}=\Gamma(w_{r})$ where we refer to the map
$\Gamma:\mathcal{W}\to\mathbb{R}^{\mathbb{N}}_{\geq 0}$ as the _utility
design_. We refer to the common interest utility design as
$\Gamma_{\mathrm{id}}$, where $\Gamma_{\mathrm{id}}(w_{r})=w_{r}$ for all
$w_{r}\in\mathcal{W}$. Lastly, we define the set of resource allocation games
that are induced by $\mathcal{W}$ and $\Gamma$ as
$\mathcal{G}_{\mathcal{W},\Gamma}$, where a game
$\mathrm{G}\in\mathcal{G}_{\mathcal{W},\Gamma}$ if $w_{r}\in\mathcal{W}$ and
$\tilde{w}_{r}=\Gamma(w_{r})$ for all resources $r\in\mathcal{R}$.

######  Example 3 (Set Covering continued).

When we reconsider the set covering problem in Example 1A, the impact of
different utility designs on the resulting decision trajectories can be
highlighted through a simple game example, shown in Figure 2. Let $\mathrm{G}$
be a game with two agents and three resources
$\mathcal{R}=\\{r_{1},r_{2},r_{3}\\}$ with values $v_{1}=1$,
$v_{2}=1+\varepsilon$, and $v_{3}=\varepsilon$ for some $\varepsilon\ll 1$.
The action set for the first agent is
$\mathcal{A}_{1}=\\{\varnothing,\\{r_{1}\\},\\{r_{2}\\}\\}$ and
$\mathcal{A}_{2}=\\{\varnothing,\\{r_{2}\\},\\{r_{3}\\}\\}$ for the second.

Figure 2: Game example depicting resource values and agent selections.

Under the common interest utility design $\Gamma_{\mathrm{id}}$, the best
response process will produce the resource selection trajectory
$(\varnothing,\varnothing),(r_{2},\varnothing),(r_{2},r_{3}),(r_{2},r_{3}),\dots$,
resulting in a total welfare of $1+2\varepsilon$ as $k\to\infty$. If we use
instead the distribution rule $\tilde{w}\simeq[0,1,3/2,3/2,\dots]$, the
resource selection trajectory is then
$(\varnothing,\varnothing),(r_{2},\varnothing),(r_{2},r_{2}),(r_{1},r_{2}),(r_{1},r_{2}),\dots$,
resulting in a total welfare of $2+\varepsilon$ as $k\to\infty$. As displayed,
implementing the correct utility design (which may substantially differ from
$\Gamma_{\mathrm{id}}$) can result in significant improvements in the welfare
values along the decision trajectory.

The central focus of this paper is to understand how the choice of
distribution rules, derived from $\Gamma(\cdot)$, and the number of rounds $k$
impacts the efficacy of the emergent collective behavior in the $k$-round
walk. Therefore, we additionally extend the efficiency measure to the set of
games $\mathcal{G}_{\mathcal{W},\Gamma}$ and quantify the optimal efficiency
guarantees as

$\displaystyle\mathrm{Eff}(\mathcal{W},\Gamma;k)$
$\displaystyle=\inf_{\mathrm{G}\in\mathcal{G}_{\mathcal{W},\Gamma}}\mathrm{Eff}(\mathrm{G};k),$
(9) $\displaystyle\mathrm{Eff}^{*}(\mathcal{W};k)$
$\displaystyle=\sup_{\Gamma:\mathcal{W}\to\mathbb{R}^{\mathbb{N}}_{>0}}\mathrm{Eff}(\mathcal{W},\Gamma;k).$
(10)

We similarly extend the definitions of $\mathrm{Eff}(\mathrm{G};\infty)$. We
importantly highlight that
$\lim_{k\to\infty}\mathrm{Eff}(\mathcal{W},\Gamma;k)\neq\mathrm{Eff}(\mathcal{W},\Gamma;\infty)$
in general, as the limit $\lim_{k\to\infty}$ and the infimum
$\inf_{\mathrm{G}\in\mathcal{G}_{\mathcal{W},\Gamma}}$ cannot be interchanged.
We devote the next section to characterizing the introduced efficiency
metrics.

##  3 Main Results

Our work is concerned with classifying the guarantees associated with the
$k$-round walk. Before we introduce our results, we introduce a
parametrization for the class of submodular welfare rules, denoted as
_curvature_ [30, 31]. Curvature is a classical parametrization used
extensively in the submodular optimization literature to describe the degree
of submodularity of a given welfare function, where a curvature $\mathrm{C}=0$
indicates that a welfare rule is close to linear, and a curvature
$\mathrm{C}=1$ indicates that a welfare rule is maximally submodular. We
define curvature formally below.

######  Definition 1 (Curvature).

A submodular welfare rule $w$ has a curvature of $\mathrm{C}\in[0,1]$ if
$\mathrm{C}=1-\lim_{n\to\infty}(w(n+1)-w(n))/w(1)$.

With this, we can characterize the optimal efficiency guarantees for the
$k$-round walk (when $k=1$ and when $k=\infty$) as well as the efficiency
guarantees for the common-interest utility below.

######  Proposition 1.

Let the set $\mathcal{W}$ comprise of all submodular welfare rules $w$ that
have curvature of at most $\mathrm{C}\in[0,1]$. The optimal efficiency
guarantees are

$\displaystyle\mathrm{Eff}^{*}(\mathcal{W};1)$ $\displaystyle=1-\mathrm{C}/2,$
(11) $\displaystyle\mathrm{Eff}^{*}(\mathcal{W};\infty)$
$\displaystyle=1-\mathrm{C}/e.$ (12)

and the guarantees associated with the common interest are

$\mathrm{Eff}(\mathcal{W},\Gamma_{\mathrm{id}};1)=\mathrm{Eff}(\mathcal{W},\Gamma_{\mathrm{id}};\infty)=\left(1+\mathrm{C}\right)^{-1}.$
(13)

######  Remark.

We remark that Eq. (11) and the $k=1$ characterization in Eq. (13) come
directly from prior work in [13, Theorem 3]. The results in Eq. (12) and the
$k=\infty$ characterization in Eq. (13) come from non-trivially extending the
price of anarchy results found in [31, Theorem 1]. Details on this extension
is found in the Appendix.

We remark that the optimal efficiency guarantees after one round are
relatively close to the optimal asymptotic guarantees444Furthermore, when
utilizing the common interest utility design, the efficiency guarantees for
$k=1$ and $k=\infty$ are identical.. However, while small, there is still a
gap between the optimal efficiency guarantees for $k=1$ and $k=\infty$. We
expect this efficiency gap to decay as we run the $k$-round walk for more
rounds. However, we show surprisingly that further rounds do not increase the
relative efficiency guarantees. Specifically, running the $k$-round walk _can
not_ improve the resulting efficiency guarantee for any given $k$ over the
guarantee of the one-round walk. This is made formal in the upper bound
characterization stated in the next theorem.

######  Theorem 1.

Let the set $\mathcal{W}$ comprise of all submodular welfare rules $w$ that
have curvature of at most $\mathrm{C}\in[0,1]$. Then the efficiency guarantees
of the $k$-round walk, for any $k\geq 1$, is upper bounded by the expressions

$\displaystyle\mathrm{Eff}^{*}(\mathcal{W};k)$
$\displaystyle\leq\mathrm{Eff}^{*}(\mathcal{W};1)=1-\mathrm{C}/2,$ (14)
$\displaystyle\mathrm{Eff}(\mathcal{W},\Gamma_{\mathrm{id}};k)$
$\displaystyle=\mathrm{Eff}(\mathcal{W},\Gamma_{\mathrm{id}};1)=(1+\mathrm{C})^{-1},$
(15)

respectively for the the optimal utility design and the common interest
utility.

######  Remark.

We remark that the results in Theorem 1 are not endemic to the $k$-round walk
algorithm. Allowing for variable turn order or only allowing strict best
responses does not affect the resulting upper bounds. This is discussed in
more detail in the Appendix in Section .4.

Notably, for any curvature $\mathrm{C}\in[0,1]$, the upper bound in Eq. (14)
exactly matches the characterization in Eq. (11) and likewise for the upper
bound in Eq. (15) and the characterization in Eq. (13). Therefore, in regards
to the efficiency guarantees, running the $k$-round walk algorithm for more
than one round does not lead to gains in performance. We verify this result in
the illustrative example described in Section 4.

In Proposition 1, we describe the optimal performance guarantees for $k=1$ and
$k=\infty$. Accompanying these results are characterizations of the utility
designs that achieve said guarantees. As these utility designs are not
equivalent, this prompts the natural question: Does optimizing the efficiency
guarantees for $k=1$ have down-stream effects on the efficiency for
$k=\infty$, and vice versa? This question is precisely addressed in the next
theorem. Explicitly, we identify the reciprocal guarantees for both the
utility design that optimizes the transient guarantees for $k=1$ and the
utility design that optimizes the asymptotic guarantees for $k=\infty$.

######  Theorem 2.

Let the set $\mathcal{W}$ comprise of all submodular welfare rules $w$ that
have curvature of at most $\mathrm{C}\in[0,1]$. Consider $\Gamma^{*}_{\infty}$
to be the utility design that achieves the optimal
$\mathrm{Eff}^{*}(\mathcal{W};\infty)$ and $\Gamma^{*}_{1}$ to be the utility
design that achieves the optimal $\mathrm{Eff}^{*}(\mathcal{W};1)$. Then we
have that

$\displaystyle\mathrm{Eff}(\mathcal{W},\Gamma_{1}^{*};\infty)$
$\displaystyle=\mathrm{Eff}^{*}(\mathcal{W};1)=1-\mathrm{C}/2$ (16)
$\displaystyle\mathrm{Eff}(\mathcal{W},\Gamma^{*}_{\infty};1)$
$\displaystyle\leq
1+\frac{\left(\mathrm{C}-3\right)\mathrm{C}}{\left(2-\mathrm{C}\right)e+\mathrm{C}}$
(17)

with
$\mathrm{Eff}(\mathcal{W},\Gamma^{*}_{\infty};1)<\mathrm{Eff}^{*}(\mathcal{W};1)$
holding strictly for $\mathrm{C}>0$ and
$\mathrm{Eff}(\mathcal{W},\Gamma^{*}_{\infty};1)=0$ for curvature
$\mathrm{C}=1$.

We first observe that there are no gains in the asymptotic guarantees of the
utility design $\Gamma_{1}^{*}$ over the respective optimal guarantees for
$k=1$. Again, we see that there are diminishing returns of running the
$k$-round algorithm for more than one round. Additionally, the transient
guarantees of $\Gamma^{*}_{\infty}$ are strictly less than
$\mathrm{Eff}^{*}(\mathcal{W};1)$ as expected. However, if the curvature
$\mathrm{C}=1$ is maximal, we note that transient guarantees of
$\Gamma^{*}_{\infty}$ unexpectedly degrade to $0$. Interestingly, optimizing
for asymptotic performance does not necessarily translate to good transient
performance in our setting. Moreover, it may even result in highly undesirable
behavior in the transient in certain settings.

To clarify this stark trade-off between the transient and asymptotic
guarantees, we restrict attention to the class of _set covering games_ [26]
(see Example 1.A) and characterize the exact Pareto optimal frontier. Set
covering games are natural generalizations of covering problems [26], and are
characterized by the following welfare rule (with curvature $\mathrm{C}=1$).

$w_{\mathrm{sc}}(j)=\left\\{\begin{array}[]{lr}1,&\text{for }j\geq 1\\\
0,&\text{for }j=0\\\ \end{array}\right\\}.$ (18)

With this, we arrive at the following Pareto frontier characterization,
depicted in Figure 3. Note that the end points of the trade-off curve matches
the ones dictated in Theorem 2 for curvature $\mathrm{C}=1$ exactly.

######  Theorem 3.

Let $\mathcal{W}=\\{w_{\mathrm{sc}}\\}$, where $w_{\mathrm{sc}}$, defined in
Eq. (18), is the set covering welfare rule and
$\Gamma(w_{\mathrm{sc}})=\tilde{w}$ is the corresponding distribution rule. If
the efficiency of the limit point of the $k$-round walk is
$\mathrm{Eff}(w_{\mathrm{sc}},\tilde{w};\infty)=Q\in[\frac{1}{2},1-\frac{1}{e}]$
555We will sometimes use abuse of notation $\mathrm{Eff}(w_{r},\tilde{w};k)$
to mean $\mathrm{Eff}(\mathcal{W}=\\{w_{r}\\},\Gamma;k)$ with
$\Gamma(w_{r})=\tilde{w}$ for a specific $w_{r}$ and $\tilde{w}_{r}$., the
maximum efficiency $\max_{\tilde{w}}\mathrm{Eff}(w_{\mathrm{sc}},\tilde{w};1)$
achievable after $k=1$ rounds is

$\left[\sum^{\infty}_{j=0}\max\left\\{j!(1-\frac{1-Q}{Q}\sum^{j}_{\tau=1}{\frac{1}{\tau!}}),0\right\\}+1\right]^{-1}.$
(19)

Figure 3: We depict the Pareto-optimal frontier of the one-round efficiency
$\mathrm{Eff}(w_{\mathrm{sc}},\tilde{w};1)$ versus the asymptotic efficiency
guarantees $\mathrm{Eff}(w_{\mathrm{sc}},\tilde{w};\infty)$ that are possible
with regards to the class of set-covering games. We note that the severe drop
off in transient efficiency that results from optimizing the asymptotic
efficiency.

Notably in Figure 3, we see a stark drop-off in transient efficiency when the
asymptotic efficiency is close to the optimal guarantee of $1-\frac{1}{e}$.
This extreme trade-off should prompt a more careful interpretation of
asymptotic results, especially in the setting of resource allocation games.

##  4 Illustrative Example

To illustrate the results of the paper, we examine the average performance
over $5$ rounds of the $k$-round algorithm of three utility designs: the
common interest utility design, the utility design that optimizes the
efficiency for $k=1$, and the utility design that optimizes the efficiency for
$k=\infty$. The average performance is measured across $100$ random instances
of _weapon-target assignment problems_ (see Example 1) with $20$ agents with a
defense rate of $p_{d}=.5$. In each simulated instance, we set the number of
targets that the agents can possibly defend to $30$. The values $v_{r}$ for
each target $r$ are uniformly selected from the unit interval $[0,1]$ and
subsequently normalized by dividing by $\sum_{r\in\mathcal{R}}v_{r}$. Each
agent has $2$ actions available, in addition to the empty allocation
$a^{\varnothing}$. Each action $a$ is a consecutive selection of $2$ resources
chosen uniformly randomly from the resource set $\mathcal{R}$.

The resulting system welfare across $5$ rounds for each utility design is
highlighted in Figure 4, where the distributions of the system welfare across
the randomized instances are depicted with a box and whisker plot. Note that
the optimal allocation may also not achieve a $100\%$ detection rate. In
Figure 4, we see that worst instance of the optimal one-round performs better
than the greedy and asymptotically optimal utility designs when $k=1$. This is
supported in the worst-case analysis presented in this paper. Additionally, we
note that the resulting efficiency plateaus quickly, with almost no
differences in efficiency after two rounds of best response - confirming that
successive rounds give diminishing returns in system performance.
Interestingly, on average, the differences in performance across utility
designs is much more subtle.

Figure 4: We plot the average rate of defense in a randomly generated set of
weapon-target assignment problems with respect to three utility designs: the
one-round optimal, the common interest, and the asymptotically optimal utility
design. We see that in the short term, the one-round optimal design performs
better in the worst case than the greedy and the asymptotically optimal
utility designs.

##  5 Conclusion

This work focuses on characterizing the performance along a $k$-round walk
algorithm in submodular resource allocation problems. Using the language of
game theory, this work shifts the emphasis from studying the system-level
performance of the limit points of the $k$-round walk to the transient states
along each round of the algorithm. We can characterize the gap between the
performance after one round and in the limit of the $k$-round walk algorithm.
We show that non-intuitively, this gap persists for any fixed finite number of
rounds $k$. Furthermore, we characterize the trade-offs when trying to
optimize the utility functions to maximize the performance of the one-round
and the limit points. Surprisingly, when optimizing for the asymptotic
performance, the performance of the one-round walk may be arbitrarily bad. We
additionally characterize the exact Pareto-frontier for these trade-offs in a
sub-class of submodular resource allocation games. Future work may comprise of
extending the results to other game models or consider average-case efficiency
analysis.

## References

  * [1] R. Konda, R. Chandan, D. Grimsman, and J. R. Marden, “Balancing asymptotic and transient efficiency guarantees in set covering games,” in 2022 American Control Conference, IEEE, 2022.
  * [2] S.-J. Chung, A. A. Paranjape, P. Dames, S. Shen, and V. Kumar, “A survey on aerial swarm robotics,” IEEE Transactions on Robotics, vol. 34, no. 4, pp. 837–855, 2018.
  * [3] R. H. Guttman, A. G. Moukas, and P. Maes, “Agent-mediated electronic commerce: A survey,” The Knowledge Engineering Review, vol. 13, no. 2, pp. 147–159, 1998.
  * [4] X. Wang, N. Xiao, T. Wongpiromsarn, L. Xie, E. Frazzoli, and D. Rus, “Distributed consensus in noncooperative congestion games: An application to road pricing,” in 2013 10th IEEE International Conference on Control and Automation (ICCA), pp. 1668–1673, IEEE, 2013.
  * [5] Y. Wang, X. Lin, and M. Pedram, “A stackelberg game-based optimization framework of the smart grid with distributed pv power generations and data centers,” IEEE Transactions on Energy Conversion, vol. 29, no. 4, pp. 978–987, 2014.
  * [6] H. P. Young, “The evolution of conventions,” Econometrica: Journal of the Econometric Society, pp. 57–84, 1993.
  * [7] T. Roughgarden, “Intrinsic robustness of the price of anarchy,” in Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 513–522, 2009.
  * [8] A. Vetta, “Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions,” in The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 416–425, IEEE, 2002.
  * [9] E. Koutsoupias and C. Papadimitriou, “Worst-case equilibria,” in Annual Symposium on Theoretical Aspects of Computer Science, pp. 404–413, Springer, 1999.
  * [10] D. Paccagnan, R. Chandan, and J. R. Marden, “Utility design for distributed resource allocation—part i: Characterizing and optimizing the exact price of anarchy,” IEEE Transactions on Automatic Control, vol. 65, no. 11, pp. 4616–4631, 2019.
  * [11] A. Fabrikant, C. Papadimitriou, and K. Talwar, “The complexity of pure nash equilibria,” in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 604–612, 2004.
  * [12] J. R. Marden and A. Wierman, “Distributed welfare games,” Operations Research, vol. 61, no. 1, pp. 155–168, 2013.
  * [13] R. Konda, R. Chandan, D. Grimsman, and J. R. Marden, “Optimal utility design of greedy algorithms in resource allocation games,” IEEE Transactions on Automatic Control, 2024.
  * [14] M. Goemans, V. Mirrokni, and A. Vetta, “Sink equilibria and convergence,” in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 142–151, IEEE, 2005.
  * [15] O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, “Flows and decompositions of games: Harmonic and potential games,” Mathematics of Operations Research, vol. 36, no. 3, pp. 474–503, 2011.
  * [16] C. Papadimitriou and G. Piliouras, “Game dynamics as the meaning of a game,” ACM SIGecom Exchanges, vol. 16, no. 2, pp. 53–63, 2019.
  * [17] G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos, “Convergence and approximation in potential games,” in Annual Symposium on Theoretical Aspects of Computer Science, pp. 349–360, Springer, 2006.
  * [18] V. Bilò, A. Fanelli, M. Flammini, and L. Moscardelli, “Performances of one-round walks in linear congestion games,” in International Symposium on Algorithmic Game Theory, pp. 311–322, Springer, 2009.
  * [19] A. Fanelli, M. Flammini, and L. Moscardelli, “The speed of convergence in congestion games under best-response dynamics,” in International Colloquium on Automata, Languages, and Programming, pp. 796–807, Springer, 2008\.
  * [20] V. Bilo, “A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games,” Theory of Computing Systems, vol. 62, no. 5, pp. 1288–1317, 2018.
  * [21] V. S. Mirrokni and A. Vetta, “Convergence issues in competitive games,” in Approximation, randomization, and combinatorial optimization. algorithms and techniques, pp. 183–194, Springer, 2004.
  * [22] S. Suri, C. D. Tóth, and Y. Zhou, “Selfish load balancing and atomic congestion games,” Algorithmica, vol. 47, no. 1, pp. 79–96, 2007.
  * [23] I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli, “Tight bounds for selfish and greedy load balancing,” in International Colloquium on Automata, Languages, and Programming, pp. 311–322, Springer, 2006.
  * [24] A. Krause and D. Golovin, “Submodular function maximization.,” Tractability, vol. 3, pp. 71–104, 2014.
  * [25] A. S. Manne, “A target-assignment problem,” Operations research, vol. 6, no. 3, pp. 346–351, 1958.
  * [26] M. Gairing, “Covering games: Approximation through non-cooperation,” in International Workshop on Internet and Network Economics, pp. 184–195, Springer, 2009.
  * [27] J. R. Marden and M. Effros, “The price of selfishness in network coding,” IEEE Transactions on Information Theory, vol. 58, no. 4, pp. 2349–2361, 2012.
  * [28] L. S. Shapley et al., “A value for n-person games,” Princeton University Press Princeton, 1953.
  * [29] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—i,” Mathematical programming, vol. 14, no. 1, pp. 265–294, 1978.
  * [30] M. Conforti and G. Cornuéjols, “Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem,” Discrete applied mathematics, vol. 7, no. 3, pp. 251–274, 1984.
  * [31] R. Chandan, D. Paccagnan, and J. R. Marden, “Tractable mechanisms for computing near-optimal utility functions,” arXiv preprint arXiv:2102.04542, 2021.
  * [32] D. Paccagnan and J. R. Marden, “Utility design for distributed resource allocation–part ii: Applications to submodular, covering, and supermodular problems,” IEEE Transactions on Automatic Control, 2021.

We provide technical details for the proofs of the main results, as well as
supporting discussion and lemmas, in the appendix. An overview of the provided
proofs are as follows.

  * (A)

We first introduce alternative formulations of the utility functions in Eq.
(8) to incorporate locality.

  * (B)

The connection between $\infty$-round walks and Nash equilibrium are
established in Lemma 1, which allows for established results in price of
anarchy to be used for asymptotic characterization.

  * (C)

We provide a proof of Proposition 1 that is based on previous work and results
in price of anarchy.

  * (D)

A proof of Theorem 1 is given, where game constructions provide the efficiency
bounds for $k\geq 1$ rounds.

  * (E)

A proof of Theorem 2 is provided, where trade-offs are established for
asymptotic and transient efficiency guarantees.

  * (F)

We provide a proof of Theorem 3, characterizing the exact Pareto-optimal
frontier of the trade-offs for set covering welfare rules.

_Notation._ Given a set $\mathcal{S}$, $|\mathcal{S}|$ represents its
cardinality. We use the denotation $w(0)=u(0)=0$. We also assume without loss
of generality in the appendix that $w_{r}(1)=1$ for any resource $r$
666Consider any game $\mathrm{G}\in\mathcal{G}_{\mathcal{W},\mathcal{U}}$. For
any resource $r\in\mathcal{R}$ with a welfare rule $w_{r}$, we can define
another game $\mathrm{G}^{\prime}\in\mathcal{G}_{\mathcal{W},\mathcal{U}}$
with instead $|w_{r}(1)|$ copies of resource $r$ with a welfare rule
$w_{r}^{\prime}(j)=w_{r}(j)/w_{r}(1)$. If $|w_{r}(1)|$ is not integer, we can
scale the number of resources uniformly and round to get arbitrarily close.
Thus we can assume without loss of generality that $w_{r}(1)=1$.. We define
the bent welfare rule for some $b\geq 1$ and curvature $\mathrm{C}\in[0,1]$ as

$w^{b,\mathrm{C}}(j)=(1-\mathrm{C})j+\mathrm{C}\cdot\min\\{j,b\\}.$ (20)

###  .1 Equivalence of Marginal Contribution Utilities

We outline a key equivalence in order to reformulate the utility functions in
Eq. (8) to only depend on the agents’ decisions locally. Given a utility
function $\mathrm{U}_{i}$, we can define a new utility structure as
$\mathrm{U}_{i}^{\mathrm{mc}}(a_{i},a_{-i})\doteq\mathrm{U}_{i}(a)-\mathrm{U}_{i}(a^{\varnothing}_{i},a_{-i})$,
sometimes referred to as the _marginal contribution utility_[12]. Following
Eq. (8), this corresponds to the following expression.

$\mathrm{U}_{i}^{\mathrm{mc}}(a_{i},a_{-i})=\sum_{r\in a_{i}}u_{r}(|a|_{r}),$
(21)

where $u_{r}(j)\equiv\tilde{w}_{r}(j)-\tilde{w}_{r}(j-1)$. From the
assumptions on $\tilde{w}_{r}$, we have that $u_{r}$ is non-negative and non-
increasing and that $u_{r}(1)=\tilde{w}_{r}(1)$. We observe that now
$\mathrm{U}_{i}^{\mathrm{mc}}$ only depends on the resource utilization on the
resources selected by agent $i$ while also satisfying the following preference
equivalence.

######  Fact 1.

For a given joint action $\alpha\in\mathcal{A}$, the best response according
to the marginal contribution utility

$\arg\max_{a_{i}\in\mathcal{A}_{i}}\mathrm{U}_{i}^{\mathrm{mc}}(a_{i},\alpha_{-i})=\arg\max_{a_{i}\in\mathcal{A}_{i}}\mathrm{U}_{i}(a_{i},\alpha_{-i})$
(22)

is the same with respect to the original utility.

An immediate consequence is that the best response process is invariant to
using the marginal contribution utility. Thus, we instead use
$\mathrm{U}_{i}^{\mathrm{mc}}$ in Eq. (21) throughout the appendix to define
the utility structure. Specifically we will refer to $u_{r}$ as _utility
rules_ and $\mathcal{U}:\mathcal{W}\to\mathbb{R}^{\mathbb{N}}_{\geq 0}$ with
$\mathcal{U}(w_{r})=u_{r}$ as the utility design rather than using $\tilde{w}$
and $\Gamma$.

###  .2 Price of Anarchy and $\infty$-round walks

Note that resource allocation games are isomorphic to _potential games_ , and,
as such, the limit points from any best response process must necessarily be
in the set of Nash equilibrium $\mathrm{NE}\subseteq\mathcal{A}$ of the game.
Thus the limit points $\lim_{k\to\infty}a^{k}$ of the $k$-round walk are Nash
equilibrium as well. We consider $a^{\mathrm{ne}}\in\mathrm{NE}$ to be a Nash
equilibrium if any unilateral deviations are not preferable by any agent, or

$a^{\mathrm{ne}}_{i}\in\arg\max_{a_{i}\in\mathcal{A}_{i}}\mathrm{U}_{i}(a_{i},a^{\mathrm{ne}}_{-i})\
\text{ for all }i\in\mathcal{I}.$ (23)

Measuring the quality of Nash equilibrium is done through the classical metric
of _price of anarchy_ as follows.

$\mathrm{PoA}(G)=\frac{\min_{a\in\mathrm{NE}}{\mathrm{W}(a)}}{\max_{a\in\mathcal{A}}{\mathrm{W}(a)}}.$
(24)

We similarly define
$\mathrm{PoA}(\mathcal{W},\Gamma)=\inf_{\mathrm{G}\in\mathcal{G}_{\mathcal{W},\mathcal{U}}}\mathrm{PoA}(\mathrm{G})$
mirroring Eq. (9). The price of anarchy is a well understood metric, with a
host of results on its characterization, complexity, and design [7]. As
solutions of the $\infty$-round walk must also be Nash equilibrium, we have
that $\lim_{k\to\infty}a^{k}\subseteq\mathrm{NE}$. However, this inclusion may
be strict, as not every Nash equilibrium may be reachable from the $k$-round
walk considered in Algorithm 1. But in the next theorem, we show equivalence
of price of anarchy and the efficiency of the $\infty$-round walk. Thus in the
subsequent sections, we can use previous results in the literature on price of
anarchy to quantify the efficiency of the $\infty$-round walk.

######  Lemma 1.

Let $\mathcal{W}$ be a set of welfare rules. The efficiency of the
$\infty$-round walk is equivalent to the price of anarchy

$\mathrm{Eff}(\mathcal{W},\Gamma;\infty)=\mathrm{PoA}(\mathcal{W},\Gamma),$
(25)

if the utility rules $u_{\ell}=\mathcal{U}(w_{\ell})$ for $1\leq\ell\leq m$
are non-increasing, and
$\mathrm{Eff}(\mathcal{W},\Gamma;\infty)\geq\mathrm{PoA}(\mathcal{W},\Gamma)$
otherwise.

###### Proof.

For ease of notation, we remove the subscript of $u^{\mathrm{mc}}_{\ell}$ as
$u_{\ell}$. Since $\lim_{k\to\infty}a^{k}\subseteq\mathrm{NE}$, by definition,
the efficiency guarantee of
$\mathrm{Eff}(\mathcal{W},\Gamma;\infty)\geq\mathrm{PoA}(\mathcal{W},\Gamma)$
must be higher than the guarantee for the total set of Nash equilibrium.

Now we show the
$\mathrm{Eff}(\mathcal{W},\Gamma;\infty)\leq\mathrm{PoA}(\mathcal{W},\Gamma)$
by a game construction $\mathrm{G}$, in which a Nash equilibrium with the
efficiency arbitrarily close to $\mathrm{PoA}(\mathcal{W},\mathcal{U})$ can
result from a one-round walk. Let $\varepsilon_{1}>0$ and
$\mathrm{PoA}^{n}(\mathcal{W},\mathcal{U})$ refer to the price of anarchy for
the set of games in $\mathcal{G}_{\mathcal{W},\mathcal{U}}$ that have only $n$
number of agents. Note that $\mathrm{PoA}^{n}(\mathcal{W},\mathcal{U})$ is
non-increasing in $n$ and lower bounded by $0$. Therefore
$\mathrm{PoA}^{n}(\mathcal{W},\mathcal{U})$ is a convergent sequence in $n$
and for any $\varepsilon_{1}$, there exists an $N_{1}\in\mathbb{N}$ such that
$\mathrm{PoA}^{N_{1}}(\mathcal{W},\mathcal{U})-\mathrm{PoA}(\mathcal{W},\mathcal{U})\leq\varepsilon_{1}$.

Generalizing [10, Theorem 2] to a set of welfare rules provides a
characterization of the price of anarchy for $N_{1}$ agents as
$\mathrm{PoA}^{N_{1}}(\mathcal{W},\mathcal{U})=Q^{-1}$ with

$\displaystyle
Q=\max_{\theta(a,x,b,\ell)}\sum_{\begin{subarray}{c}1\leq\ell\leq m,\\\
a,x,b\end{subarray}}w_{\ell}(b+x)\theta(a,x,b,\ell)$ (26) s.t.
$\displaystyle\sum_{\begin{subarray}{c}1\leq\ell\leq m,\\\
a,x,b\end{subarray}}[au_{\ell}(a+x)-bu_{\ell}(a+x+1)]\theta(a,x,b,\ell)\geq 0$
$\displaystyle\sum_{\begin{subarray}{c}1\leq\ell\leq m,\\\
a,x,b\end{subarray}}w_{\ell}(a+x)\theta(a,x,b,\ell)=1$
$\displaystyle\theta(a,x,b,\ell)\geq 0,$

where $a,x,b\in\mathbb{N}$ with $1\leq a+x+b\leq N_{1}$. We refer to
$\Theta(a,x,b,\ell)$ to denote the corresponding optimal variables for
$\theta(a,x,b,\ell)$ of the linear program. We construct a matching game
$\mathrm{G}$ as follows. Let $N_{2}>N_{1}$ be the number of agents in the game
and $D=N_{2}+a+x-1$. For each $a$, $x$, $b,\ell$ pair and $1\leq k\leq D$, we
construct a set of resources $\mathcal{R}_{a,x,b,\ell}^{k}$ with
$|\mathcal{R}_{a,x,b,\ell}^{k}|=\Theta(a,x,b,\ell)/D$ 777While
$\Theta(a,x,b,\ell)/D$ might not be an integer, we can scale
$|\mathcal{R}_{a,x,b,\ell}^{k}|$ uniformly and round to arrive at a game
construction with the arbitrarily close efficiency guarantees.. Each agent $i$
has three actions in its action set
$\mathcal{A}_{i}=\\{a^{\varnothing}_{i},a^{\mathrm{ne}}_{i},a^{\mathrm{opt}}_{i}\\}$.
Each agent $i$ selects $\\{\mathcal{R}_{a,x,b,\ell}^{k}\\}_{i\leq k\leq
a+x+i-1}$ in $a^{\mathrm{ne}}_{i}$ for each pair $a,b,x$, $\ell$. If
$a+b+x\leq i\leq N_{2}$, agent $i$ selects
$\\{\mathcal{R}_{a,x,b,\ell}^{k}\\}_{i-b\leq k\leq x+i-1}$ in
$a^{\mathrm{opt}}_{i}$ for each pair $a,b,x$. Otherwise for $1\leq i\leq
a+b+x-1$, $a^{\mathrm{opt}}_{i}=a^{\varnothing}_{i}$ and agent $i$ doesn’t
select any resources in $a^{\mathrm{opt}}_{i}$. This is shown in Figure 5 for
one $a$, $x$, $b,\ell$. pair

Figure 5: In this figure, rows represent players and columns represent
resources. Red circles represent selections in $a^{\mathrm{ne}}$ and blue
circles represent selections in $a^{\mathrm{opt}}$.

We first confirm that the action $a^{\mathrm{ne}}$ is indeed a Nash
equilibrium. Showing this for the first $a+x+b-1$ agents is trivial, since no
resources are selected in $a^{\mathrm{opt}}_{i}$. For the rest of the agents,
the utility difference of a unilateral deviation to $a^{\mathrm{opt}}_{i}$
from $a^{\mathrm{ne}}_{i}$ is

$\displaystyle\mathrm{U}_{i}(a^{\mathrm{ne}})-\mathrm{U}_{i}(a^{\mathrm{opt}}_{i},a^{\mathrm{ne}}_{-i})$
$\displaystyle\geq\sum_{r\in
a^{\mathrm{ne}}_{i}}u_{r}(|a^{\mathrm{ne}}|_{r})-\sum_{r\in
a^{\mathrm{opt}}_{i}}u_{r}(|(a^{\mathrm{opt}}_{i},a^{\mathrm{ne}}_{-i})|_{r})$
$\displaystyle\geq\sum_{a,x,b,\ell}[(a+x)u_{\ell}(a+x)-$ $\displaystyle\quad\
xu_{\ell}(a+x)-bu_{\ell}(a+x+1)]\cdot|\mathcal{R}_{a,x,b,\ell}^{k}|$
$\displaystyle\geq\frac{1}{D}\sum_{a,x,b,\ell}[au_{\ell}(a+x)-bu_{\ell}(a+x+1)]\Theta(a,x,b,\ell)$
$\displaystyle\geq 0.$

The first inequality comes from the definitions of the utility function. The
second inequality comes from counting the resources that are selected in the
either $a^{\mathrm{ne}}_{i}$ or $a^{\mathrm{opt}}_{i}$ by the agent in each
set of resources in $\mathcal{R}_{a,x,b,\ell}^{k}$. The third inequality comes
from simplifying. The fourth inequality comes from the fact that since
$\Theta(a,x,b,\ell)$ has to satisfy the inequality constraint in Eq. (26) to
be feasible. Similarly, in a one-round walk, the best response for the first
$a+x+b-1$ agents is $a^{\mathrm{ne}}_{i}$. The best response for the other
agents during the one-round walk is also $a^{\mathrm{ne}}_{i}$, since

$\displaystyle\mathrm{U}_{i}(a^{\mathrm{ne}}_{j<i},a^{\mathrm{ne}}_{i},a^{\varnothing}_{j>i})-\mathrm{U}_{i}(a^{\mathrm{ne}}_{j<i},a^{\mathrm{opt}}_{i},a^{\varnothing}_{j>i})$
$\displaystyle=\sum_{a,x,b,\ell}[\sum_{j=1}^{a+x}u_{\ell}(i)-xu_{\ell}(a+x)-bu_{\ell}(a+x+1)]|\mathcal{R}_{a,x,b,\ell}^{k}|$
$\displaystyle\geq\frac{1}{D}\sum_{a,x,b,\ell}[au_{\ell}(a+x)-bu_{\ell}(a+x+1)]\Theta(a,x,b,\ell)$
$\displaystyle\geq 0.$

We use similar arguments as before, where the second inequality comes from the
fact that $u_{\ell}$ is non-increasing. Therefore, the Nash equilibrium
$a^{\mathrm{ne}}$ is reached from an empty configuration in one-round.
Additionally, since $a^{\mathrm{ne}}$ is a Nash equilibrium, the resulting
action state after any $k$ rounds can also be itself $a^{\mathrm{ne}}$.
Therefore in this game,
$\mathrm{Eff}(\mathrm{G};\infty)\leq\mathrm{PoA}(\mathrm{G})$. Now we
calculate the efficiency of the Nash equilibrium $\mathrm{W}(a^{\mathrm{ne}})$
with respect to $\mathrm{W}(a^{\mathrm{opt}})$. We have that

$\displaystyle\mathrm{W}(a^{\mathrm{ne}})=$
$\displaystyle\sum_{a,x,b,\ell}w_{\ell}(a+x)\cdot\Theta(a,x,b,\ell)\frac{N_{2}-2(a+x-1)}{N_{2}}$
$\displaystyle+2\sum_{\begin{subarray}{c}1\leq\ell\leq m\\\ 1\leq i\leq
a+x-1\end{subarray}}w_{\ell}(i)\frac{\Theta(a,x,b,\ell)}{N_{2}}=1+\mathrm{O}(\frac{1}{N_{2}}),$

where, since $\Theta(a,x,b,\ell)$ is feasible, then it satisfies the equality
constraint that $\sum_{a,x,b,\ell}w_{\ell}(a+x)\Theta(a,x,b,\ell)=1$.
$\mathrm{O}(\frac{1}{N_{2}})$ reflects that the rest of the terms are on order
of $1/N_{2}$. Similarly,

$\displaystyle\mathrm{W}(a^{\mathrm{opt}})=\sum_{a,x,b,\ell}w_{\ell}(b+x)\cdot\Theta(a,x,b,\ell)\frac{N_{2}-3(b+x-1)}{N_{2}}$
$\displaystyle+2\sum_{\begin{subarray}{c}1\leq\ell\leq m\\\ 1\leq i\leq
b+x-1\end{subarray}}w_{\ell}(i)\frac{\Theta(a,x,b,\ell)}{N_{2}}=Q+\mathrm{O}(\frac{1}{N_{2}}),$

where, since $\Theta(a,x,b,\ell)$ is optimal, then
$\sum_{a,x,b,\ell}w_{\ell}(b+x)\Theta(a,x,b,\ell)=Q=\mathrm{PoA}^{N_{1}}(\mathcal{W},\mathcal{U})^{-1}$.
For any $\varepsilon_{2}$, we can choose $N_{2}$, such that
$\mathrm{O}(\frac{1}{N_{2}})\leq\varepsilon_{2}$, so
$\mathrm{PoA}(\mathrm{G})\leq\mathrm{PoA}^{N_{1}}(\mathcal{W},\mathcal{U})^{-1}+\varepsilon_{2}$.
To put everything together, we have that

$\displaystyle\mathrm{Eff}(\mathcal{W},\mathcal{U};\infty)\leq\mathrm{Eff}(\mathrm{G};\infty)=\mathrm{PoA}(\mathrm{G})$
$\displaystyle\leq\mathrm{PoA}^{N_{1}}(\mathcal{W},\mathcal{U})^{-1}+\varepsilon_{2}\leq\mathrm{PoA}(\mathcal{W},\mathcal{U})+\varepsilon_{1}+\varepsilon_{2},$

and since $\varepsilon_{1}$ and $\varepsilon_{2}$ are arbitrary, we have the
result. ∎

######  Remark.

A simple corollary from the above proof also shows that
$\mathrm{Eff}(\mathcal{W},\mathcal{U};k)\leq\mathrm{PoA}(\mathcal{W},\mathcal{U})$
for any $k\geq 1$ as well. Thus the efficiency guarantees of $k$-round walks
are upper bounded by the price of anarchy.

###  .3 Proof of Proposition 1

The equalities $\mathrm{Eff}^{*}(\mathcal{W};1)=1-\mathrm{C}/2$ in Eq. (11)
and $\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};1)=1/(1+\mathrm{C})$
in Eq. (13) comes from the results in [13, Theorem $3$]. The equality
$\mathrm{Eff}^{*}(\mathcal{W};\infty)=1-\mathrm{C}/e$ in Eq. (12) comes from
the fact that
$\mathrm{Eff}^{*}(\mathcal{W};\infty)=\sup_{\mathcal{U}}\mathrm{PoA}(\mathcal{W},\mathcal{U})$
by Lemma 1 for the set of non-increasing utility rules and that
$\sup_{\mathcal{U}}\mathrm{PoA}(\mathcal{W},\mathcal{U})=1-\mathrm{C}/e$ comes
from [31, Theorem $1$].

Now we show
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};\infty)=\left(1+\mathrm{C}\right)^{-1}$.
Since any best response with a common interest utility must increase the
welfare $\mathrm{W}$, the limiting efficiency
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};\infty)\geq\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};1)=1/(1+\mathrm{C})$
is greater than the efficiency of the one-round walk. Since we consider
welfare rules $w_{r}$ that are submodular, then the utility rules
$u^{\mathrm{mc}}_{r}$ are non-increasing, and we can apply Lemma 1 to have
that
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};\infty)=\mathrm{PoA}(\mathcal{W},\mathcal{U}_{\mathrm{CI}})$.
From applying [32, Corollary 1] with the bent welfare rule $w^{b,\mathrm{C}}$
in Eq. (20) gives

$\displaystyle\mathrm{PoA}(\mathcal{W},\mathcal{U}_{\mathrm{CI}})^{-1}\geq\mathrm{PoA}(w^{b,\mathrm{C}},\mathcal{U}_{\mathrm{CI}})^{-1}=$
$\displaystyle 1+\max_{j\geq
1}\left\\{\frac{j}{w^{b,\mathrm{C}}(j)}\left[2w^{b,\mathrm{C}}(j)-w^{b,\mathrm{C}}(j-1)-w^{b,\mathrm{C}}(j+1)\right]\right\\}$

Simplifying the inequality for $b=1$ gives
$\mathrm{PoA}(\mathcal{W},\mathcal{U}_{\mathrm{CI}})\leq\left(1+\mathrm{C}\right)^{-1}$.
Since $\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};\infty)$ is both
upper bounded and lower bounded by $\left(1+\mathrm{C}\right)^{-1}$, we have
the result.

###  .4 Proof of Theorem 1

In this section, we first provide upper bounds on the efficiency metric
$\mathrm{Eff}^{*}(\mathcal{W};k)$. To do this, we construct a game
$\mathrm{G}$ such that for any utility design $\mathcal{U}$, rounds $k\geq 1$,
and curvature $\mathrm{C}$, we have that
$\mathrm{Eff}(\mathcal{W},\mathcal{U};k)\leq\mathrm{Eff}(\mathrm{G};k)\leq
1-\mathrm{C}/2$. Let $\mathrm{C}$ be the curvature and consider the bent
welfare rule $w^{b,\mathrm{C}}$ with $b=1$ as in Eq. (20) with
$w^{b,\mathrm{C}}(2)=2-\mathrm{C}$. Additionally, let
$u=\mathcal{U}(w^{b,\mathrm{C}})$ be the corresponding utility rules for a
given utility design. A two-agent game $\mathrm{G}$ is constructed as follows.
Let the resource set be
$\mathcal{R}=\mathcal{R}_{1}\cup\mathcal{R}_{2}\cup\mathcal{R}_{3}$, where
$\mathcal{R}_{j}$ is a set of resources such that the ratio of resources
satisfies $|\mathcal{R}_{1}|=|\mathcal{R}_{2}|=u(2)\cdot|\mathcal{R}_{3}|$. If
$u(2)$ is not a whole number, we can scale up $|\mathcal{R}_{j}|$ uniformly
and round $u(2)\cdot|\mathcal{R}_{3}|$ to get arbitrarily close to the given
ratio. Let $x=|\mathcal{R}_{1}|$. The action sets for the game construction
the agents will be determined by $u$ according to the following three cases:
(a) $0\leq u(2)\leq(1-\mathrm{C})$, (b) $(1-\mathrm{C})\leq u(2)\leq 1$, and
(c) $u(2)\geq 1$.

For case (a), Agent $1$’s actions are
$\mathcal{A}_{1}=\\{a^{\varnothing}_{1},a_{1}^{1}=\mathcal{R}_{1},a_{1}^{2}=\mathcal{R}_{2}\\}$.
Agent $2$’s actions are
$\mathcal{A}_{2}=\\{a^{\varnothing}_{2},a_{2}^{1}=\mathcal{R}_{3},a_{2}^{2}=\mathcal{R}_{1}\\}$.
The optimal allocation is $a^{\mathrm{opt}}=\\{a_{1}^{2},a_{2}^{2}\\}$
resulting in a welfare of $2x$. An allocation that can occur after a one round
walk is $a^{\mathrm{br}}=\\{a_{1}^{1},a_{2}^{1}\\}$ resulting in a welfare of
$(1+u(2))x$. Therefore,
$\mathrm{Eff}(\mathrm{G};1)\leq\frac{(1+u(2))x}{2x}\leq
1-\frac{\mathrm{C}}{2}$ by assumption of $u\leq 1-\mathrm{C}$. Additionally,
observe that $a^{\mathrm{br}}$ is a Nash equilibrium and therefore is still
the resulting allocation after any number of additional rounds $k\geq 1$.
Therefore
$\mathrm{Eff}(\mathcal{W},\mathcal{U};k)\leq\mathrm{Eff}(\mathrm{G};k)\leq
1-\frac{\mathrm{C}}{2}$ for this case of utility design.

For case (b), Agent $1$’s actions are
$\mathcal{A}_{1}=\\{a^{\varnothing}_{1},a_{1}^{1}=\mathcal{R}_{1},a_{1}^{2}=\mathcal{R}_{2}\\}$.
Agent $2$’s actions are
$\mathcal{A}_{2}=\\{a^{\varnothing}_{2},a_{2}^{1}=\mathcal{R}_{3},a_{2}^{2}=\mathcal{R}_{1}\\}$.
The optimal allocation is $a^{\mathrm{opt}}=\\{a_{1}^{2},a_{2}^{2}\\}$
resulting in a welfare of $2x$. An allocation that can occur after a one-round
walk is $a^{\mathrm{br}}=\\{a_{1}^{1},a_{2}^{2}\\}$ resulting in a welfare of
$w^{b,\mathrm{C}}(2)\cdot x$. Therefore,
$\mathrm{Eff}(\mathrm{G};1)\leq\frac{w^{b,\mathrm{C}}(2)\cdot
x}{2x}=1-\frac{\mathrm{C}}{2}$. For $k\geq 2$, there is a best response path
that leads to the end state $a^{\mathrm{br}}$. This is achieved by reaching
$a^{\prime}=\\{a_{1}^{1},a_{2}^{1}\\}$ in the first round. As $a^{\prime}$ is
a Nash action, the best response process can remains at $a^{\prime}$ for $k-1$
rounds and in the last round, switch to $a^{\mathrm{br}}$. Therefore
$\mathrm{Eff}(\mathcal{W},\mathcal{U};k)\leq\mathrm{Eff}(\mathrm{G};k)\leq
1-\frac{\mathrm{C}}{2}$ for this case.

For case (c), Agent $1$’s actions are
$\mathcal{A}_{1}=\\{a^{\varnothing}_{1},a_{1}^{1}=\mathcal{R}_{1},a_{1}^{2}=\mathcal{R}_{2}\\}$.
Agent $2$’s actions are
$\mathcal{A}_{2}=\\{a^{\varnothing}_{2},a_{2}^{1}=\mathcal{R}_{1},a_{2}^{2}=\mathcal{R}_{3}\\}$.
The optimal allocation is $a^{\mathrm{opt}}=\\{a_{1}^{2},a_{2}^{2}\\}$
resulting in a welfare of $(1+u(2))x$. An allocation that can occur after a
one round walk is $a^{\mathrm{br}}=\\{a_{1}^{1},a_{2}^{1}\\}$ resulting in a
welfare of $w^{b,\mathrm{C}}(2)\cdot x$. Therefore,
$\mathrm{Eff}(\mathrm{G};1)=\frac{w^{b,\mathrm{C}}(2)\cdot x}{(1+u(2))x}\leq
1-\frac{\mathrm{C}}{2}$ by assumption of $u(2)>1$. Additionally, observe that
$a^{\mathrm{br}}$ is a Nash equilibrium and therefore is still the resulting
allocation after any number of additional rounds. Therefore
$\mathrm{Eff}(\mathcal{W},\mathcal{U};k)\leq\mathrm{Eff}(\mathrm{G};k)\leq
1-\frac{\mathrm{C}}{2}$ for this case.

Since $u=\mathcal{U}(w^{b,\mathrm{C}})$ was chosen arbitrarily, we have that
the upper bound holds for any utility design and we have shown that
$\mathrm{Eff}^{*}(\mathcal{W};k)\leq 1-\mathrm{C}/2$. Furthermore, based on
our game construction, the efficiency bounds hold even when we relax the class
of best response dynamics that we consider. Since the game construction
comprises of only two agents, allowing agents to best respond multiple times
during a round or best respond out of order of round-robin does not improve
the efficiency guarantees that result from the given game $\mathrm{G}$.

Figure 6: The worst case game construction achieving the $k$-round walk
guarantee dictated in Equation (14). P1 and P2 represent the two agents and
$|x|$ and $|x\cdot u(2)|$ represent the size of the resources. The black lines
represent the selections in the different joint actions by the two agents.

####  .4.1 Common Interest Utility

First, we note that since any best response improves the welfare under the
common interest utility, we must have that
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};k)\geq\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};1)=(1+\mathrm{C})^{-1}$.
Now we show that the upper bound
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};k)\leq(1+\mathrm{C})^{-1}$
to complete the equality in Eq. (15). As before, a game $\mathrm{G}$ is
constructed such that under the common interest design
$\mathcal{U}_{\mathrm{CI}}$, $k\geq 1$, and curvature $\mathrm{C}$, we have
that
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{CI}};k)\leq\mathrm{Eff}(\mathrm{G};k)\leq(1+\mathrm{C})^{-1}$.
Let $\mathrm{G}$ have $n$ players with a resource set
$\mathcal{R}=\mathcal{R}^{\mathrm{opt}}\cup\mathcal{R}^{\mathrm{both}}\cup\\{r^{n}\\}$
with $|\mathcal{R}^{\mathrm{opt}}|=n$ and $|\mathcal{R}^{\mathrm{both}}|=n-1$.
Each agent $i$ has three actions in its action set
$\mathcal{A}_{i}=\\{a^{\varnothing}_{i},a^{\mathrm{br}}_{i},a^{\mathrm{opt}}_{i}\\}$.
The resources are selected by the agents in the following manner: each
resource $r_{j}^{\mathrm{opt}}\in\mathcal{R}^{\mathrm{opt}}$ is selected by
agent $j$ in action $a^{\mathrm{opt}}_{j}\ni r_{j}^{\mathrm{opt}}$ for all
$1\leq j\leq n$; each resource
$r_{j}^{\mathrm{both}}\in\mathcal{R}^{\mathrm{both}}$ is selected by agent
$j+1$ in action $a^{\mathrm{opt}}_{j+1}\ni r_{j}^{\mathrm{both}}$ and by agent
$j$ in action $a^{\mathrm{br}}_{j}\ni r_{j}^{\mathrm{both}}$ for all $1\leq
j\leq n-1$; agent $n$ selects the resource $r^{n}$ in action
$a^{\mathrm{br}}_{n}$. See Figure 7 for a visual representation of this game.

Given a curvature $\mathrm{C}$, consider two bent welfare rules
$w_{1},w_{2}\in\mathcal{W}$ with curvature $\mathrm{C}$ such that
$w_{1}=w^{b,\mathrm{C}}$ with $b=1$ and $w_{2}=\mathrm{C}\cdot w_{1}$. For any
$r\in\mathcal{R}^{\mathrm{both}}\cup\\{r^{n}\\}$, let the corresponding
welfare rule be $w_{r}=w_{1}$ and for any $r\in\mathcal{R}^{\mathrm{opt}}$,
let the corresponding welfare rule be $w_{r}=w_{2}$. Under this game
construction it can be seen that under $a^{\mathrm{br}}$, each resource
$r\in\mathcal{R}^{\mathrm{both}}\cup\\{r^{n}\\}$ is selected by exactly one
agent, resulting in a welfare of $\mathrm{W}(a^{\mathrm{br}})=n$; also, under
$a^{\mathrm{opt}}$, each resource
$r\in\mathcal{R}^{\mathrm{both}}\cup\mathcal{R}^{\mathrm{opt}}$ is selected by
exactly one agent, resulting in a welfare of
$\mathrm{W}(a^{\mathrm{opt}})=(n-1)(1+\mathrm{C})+\mathrm{C}$. Assuming that
$a^{\mathrm{br}}$ is the joint action that results after $k$ rounds, we have
that $\mathrm{Eff}(\mathrm{G},k)\leq\frac{n}{(n-1)(1+\mathrm{C})+\mathrm{C}}$.
Limiting the number of agents $n\to\infty$ to infinity gives the result. To
verify that $a^{\mathrm{br}}$ can result after $k$ rounds, observe that for
agent $1$ selecting $a^{\mathrm{br}}_{1}$ over $a^{\mathrm{opt}}_{1}$ results
in a higher system welfare. After that, agents $2$ through $n$ are indifferent
between $a^{\mathrm{br}}_{j}$ and $a^{\mathrm{opt}}_{j}$ given that the
previous $i<j$ players have selected $a^{\mathrm{br}}_{i}$. Therefore,
$a^{\mathrm{br}}$ is the resulting allocation after one round. Additionally,
$a^{\mathrm{br}}$ is a Nash equilibrium, so after any number of rounds $k$,
the joint action $a^{\mathrm{br}}$ is still the result of a $k$-round walk.

Figure 7: The worst case game construction achieving the $k$-round walk
guarantee dictated in Equation (15). In this figure, rows represent players
and columns represent resources. Red circles represent selections in
$a^{\mathrm{br}}$ and blue circles represent selections in $a^{\mathrm{opt}}$.

###  .5 Proof of Theorem 2

We show the trade-offs in Theorem 2 that result from considering utility
designs that maximize the one-round walk efficiency versus the $\infty$-round
walk. We first show the equality in Eq. (16). From Lemma 1, we have

$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{1}^{*};\infty)=\mathrm{PoA}(\mathcal{W},\mathcal{U}_{1}^{*})\geq\mathrm{Eff}(\mathcal{W},\mathcal{U}_{1}^{*};1)=1-\mathrm{C}/2,$

since $\mathcal{U}_{1}^{*}$ is a non-increasing utility design, which is shown
in [13, Appendix Section B]. We now show
$\mathrm{PoA}(\mathcal{W},\mathcal{U}_{1}^{*})\leq 1-\mathrm{C}/2$. Consider
the bent rule $w^{b,\mathrm{C}}$ in Eq. (20) with $b=1$ and a utility rule
$u_{1}$ with $u_{1}(1)=1$ and $u_{1}(2)=(2-2\mathrm{C})/(2-\mathrm{C})$. In
[13, Appendix Section C.2], it was shown that $u_{1}$ is the utility rule that
maximizes the one-round efficiency for $\mathcal{W}=\\{w^{b,\mathrm{C}}\\}$.
It can be easily verified that $u_{1}$ satisfies the assumptions of [32,
Theorem 2] and we can derive the price of anarchy as

$\mathrm{PoA}(w^{b,\mathrm{C}},u_{1})^{-1}={\scriptstyle\max_{1\leq l\leq
j}\left\\{\frac{w^{b,\mathrm{C}}(l)+ju_{1}(j)-lu_{1}(j+1)}{w^{b,\mathrm{C}}(j)}\right\\}.}$

Under $j=1$ and $l=1$, we have that $\mathrm{PoA}(w^{b,\mathrm{C}},u_{1})\leq
1-\mathrm{C}/2$. Using the fact that
$\mathrm{PoA}(\mathcal{W},\mathcal{U}_{1}^{*})\leq\mathrm{PoA}(w^{b,\mathrm{C}},u_{1})$,
we have the upper bound as well.

We show that $\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\infty};1)\leq
1+\frac{(\mathrm{C}-3)\mathrm{C}}{(2-\mathrm{C})e+\mathrm{C}}$ in Lemma 2 and
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\infty};1)=0$ for $\mathrm{C}=1$ in
Lemma 3. These lemmas are stated below.

######  Lemma 2.

Let the set $\mathcal{W}$ comprise of all submodular welfare rules $w$ that
have curvature of at most $\mathrm{C}\in[0,1]$. Consider
$\mathcal{U}^{*}_{\infty}$ to be the utility design that achieves the optimal
$\mathrm{Eff}^{*}(\mathcal{W};\infty)$. Then we have that

$\mathrm{Eff}(\mathcal{W},\mathcal{U}^{*}_{\infty};1)\leq
1+\frac{\left(\mathrm{C}-3\right)\mathrm{C}}{\left(2-\mathrm{C}\right)e+\mathrm{C}}.$
(27)

###### Proof.

From results in [31, Lemma 1 iii], the utility design that optimizes the price
of anarchy
$\mathcal{U}_{\mathrm{poa}}\doteq\arg\max_{\mathcal{U}}\mathrm{PoA}(\mathcal{W},\mathcal{U})$
have non-increasing utility rules. Since these utility rules are non-
increasing, under Lemma $1$, the resulting asymptotic efficiency
$\mathrm{Eff}(\mathcal{W},\mathcal{U}_{\mathrm{poa}},\infty)=\mathrm{PoA}(\mathcal{W},\mathcal{U}_{\mathrm{poa}})$
and thus $\mathcal{U}_{\mathrm{poa}}\equiv\mathcal{U}^{*}_{\infty}$ is the
utility design that maximizes the asymptotic efficiency.

To construct the upper bound in Eq. (27), we characterize the one-round
efficiency of the asymptotically optimal utility design against the bent
welfare rule $w^{b,\mathrm{C}}$ for $b=1$. We have that
$\mathrm{Eff}(\mathcal{W},\mathcal{U}^{*}_{\infty};1)\leq\mathrm{Eff}(w^{1,\mathrm{C}},u^{\infty};1)$,
where $u^{\infty}\equiv\mathcal{U}^{*}_{\infty}(w^{1,\mathrm{C}})$. We can use
the linear program given in [13, Corollary 1] to characterize the one-round
efficiency. Under only the bent welfare rule, the constraint for a given $z$,
$y$ simplifies to

$\displaystyle\beta\cdot
w^{1,\mathrm{C}}(y)\geq\sum_{i=1}^{y}u^{\infty}(i)-z\min_{1\leq i\leq
y+1}u^{\infty}(i)+w^{1,\mathrm{C}}(z).$

According to [31, Lemma 1], the asymptotically optimal utility rule
$u^{\infty}$ for the bent welfare rule is given by the following recursive
equation

$\displaystyle u^{\infty}(1)$ $\displaystyle=1,$ $\displaystyle
u^{\infty}(j+1)$ $\displaystyle=\max\\{ju^{\infty}(j)-\rho
w^{1,\mathrm{C}}(j)+1,1-\mathrm{C}\\},$

with $\rho=(1-\mathrm{C}/e)^{-1}$. Now we characterize the binding constraints
for $z$. Since $u^{\infty}(j)\leq 1$ for all $j$ and $u^{\infty}(j)\geq
w^{1,\mathrm{C}}(j)-w^{1,\mathrm{C}}(j-1)$ for $j\geq 2$, the binding
constraint is when $z=1$. Coupled with the fact that $u^{\infty}$ is non-
increasing, we can simplify the one-round characterization as

$\displaystyle\mathrm{Eff}(w^{1,\mathrm{C}},u^{\infty};1)^{-1}$
$\displaystyle=\max_{y\geq
1}\left\\{\frac{1+\sum_{i=1}^{y}u^{\infty}(i)-u^{\infty}(y+1)}{w^{1,\mathrm{C}}(y)}\right\\}$
$\displaystyle\geq\frac{(2-\mathrm{C})e+\mathrm{C}}{(2-\mathrm{C})(e-\mathrm{C})},$

where the second inequality comes from only considering $y=2$ and solving for
$u^{\infty}(j)$ explicitly for $j=2$ and $j=3$. Taking the reciprocal on both
sides and simplifying gives the expression in Eq. (27). ∎

######  Lemma 3.

Let the set $\mathcal{W}$ comprise of all submodular welfare rules $w$ that
have curvature of at most $\mathrm{C}=1$. Consider $\mathcal{U}^{*}_{\infty}$
to be the utility design that achieves the optimal
$\mathrm{Eff}^{*}(\mathcal{W};\infty)$. Then
$\mathrm{Eff}(\mathcal{W},\mathcal{U}^{*}_{\infty};1)=0$.

###### Proof.

By definition, $\mathrm{Eff}(\mathcal{W},\mathcal{U}^{*}_{\infty};1)\geq 0$
must be greater than zero. For the upper bound, we construct a game
$\mathrm{G}\in\mathcal{G}_{\mathcal{W},\mathcal{U}^{*}_{\infty}}$ such that
one-round walk efficiency is $\mathrm{Eff}(\mathrm{G};1)=0$. Consider a game
$\mathrm{G}$ with $n$ players as follows. We partition the resource set as
$\mathcal{R}=\bigcup_{1\leq j\leq n+1}\mathcal{R}_{j}$. Every resource
$r\in\mathcal{R}$ is endowed the local welfare rule $w_{r}=w^{b,\mathrm{C}}$
as the bent welfare rule with curvature of $\mathrm{C}=1$ for some fixed
$b\geq 1$, as defined in Eq. The corresponding utility rule is
$u^{\infty}=\mathcal{U}^{*}_{\infty}(w^{b,\mathrm{C}})$ is the following
recursive expression from [31, Lemma 1]888The recursive expression found in
[31] is for the utility rule that maximizes the price of anarchy. Since this
utility rule is non-increasing, we can apply Lemma 1 to translate the results
to $\infty$-round walks.,

$\displaystyle u^{\infty}(1)$ $\displaystyle=1$ $\displaystyle
u^{\infty}(j+1)$
$\displaystyle=\frac{1}{b}[ju^{\infty}(j)-\rho^{b}\min\\{j,b\\}]+1,$

with $\rho^{b}=(1-\frac{b^{b}e^{-b}}{b!})^{-1}$. The number of resources in
each set is $|\mathcal{R}_{1}|=v$ and $|\mathcal{R}_{j+1}|\sim v\cdot
u^{\infty}(j)$ for $1\leq j\leq n$ and for some $v\geq 0$. If $u^{\infty}(j)$
is not a whole number, we can scale $v$ up and round to get arbitrarily close
to the correct ratio of resources. Agent $i$ selects
$\mathcal{R}_{1}=a^{\mathrm{br}}_{i}$ and
$\mathcal{R}_{i+1}=a^{\mathrm{opt}}_{i}$ in each of its actions. It can be
verified that $a^{\mathrm{br}}$ is a joint action that can result after a one
round walk. Therefore, the efficiency is upper bounded by

$\mathrm{Eff}(\mathrm{G};1)\leq\frac{\mathrm{W}(a^{\mathrm{br}})}{\mathrm{W}(a^{\mathrm{opt}})}=\frac{vb}{v\sum_{1\leq
i\leq n}u^{\infty}(i)}.$

Now we show that as we increase $n$, the series $\sum_{1\leq i\leq
n}u^{\infty}(i)$ diverges, and the efficiency can get arbitrarily bad as the
number of agents increase. To construct the closed form expression of
$u^{\infty}(j)$, we construct the following LTV state space system with
$u^{\infty}(j):=x(t)$

$\displaystyle x(t+1)$ $\displaystyle=A(t)x(t)+s(t)\quad\quad
A(t)=\frac{t}{b}$ $\displaystyle s(t)$
$\displaystyle=1-\frac{\rho^{b}}{b}\min(t,b)$

Solving for the solution $x(t)$ using the state transition matrix with the
initial condition $x(1)=1$ results in the following expression

$\displaystyle x(t)$
$\displaystyle=\prod_{\tau=1}^{t}\frac{\tau}{b}+\sum_{T=1}^{t-1}\big{[}\big{(}1-\frac{\rho^{b}}{b}\min(t,b)\big{)}\prod_{\tau=T+1}^{t-1}\frac{\tau}{b}\big{]}$
$\displaystyle=\frac{t!}{b^{t}}\bigg{(}1+\sum_{T=1}^{t}\frac{b^{T}}{T!}\big{(}1-\frac{\rho^{b}}{b}\min(t,b)\big{)}\bigg{)}$

If $t\geq b$, then

$\displaystyle x(t)$
$\displaystyle=\frac{t!}{b^{t}}\bigg{(}1-(e^{b}-1)(\rho-1)+\sum_{T=t+1}^{\infty}\frac{b^{T}}{T!}\big{(}\rho^{b}-1\big{)}+$
$\displaystyle\sum_{T=1}^{b}\frac{b^{T}}{T!}\frac{\rho^{b}(b-T)}{b}\bigg{)}$
$\displaystyle=\frac{t!}{b^{t}}\sum_{T=t+1}^{\infty}\frac{b^{T}}{T!}\big{(}\rho^{b}-1\big{)}$
$\displaystyle\geq(\rho^{b}-1)\frac{b}{t+1}$
$\displaystyle\sim\mathrm{O}(\frac{1}{t})$

The first equality results from splitting the summation and the second
equality will be shown later. Since $x(t)$ is on the order of $\frac{1}{t}$,
the series $\sum_{i=1}^{N}u^{\infty}(i)$ diverges and the claim is shown. Now
we verify the equality

$\displaystyle\sum_{T=1}^{b}\frac{b^{T}}{T!}\frac{\rho^{b}(b-T)}{b}$
$\displaystyle=(e^{b}-1)(\rho^{b}-1)-1$
$\displaystyle\sum_{T=1}^{b}\frac{b^{T}(b-T)}{bT!}$
$\displaystyle=\frac{1}{\rho^{b}}\big{(}e^{b}\rho^{b}-e^{b}-\rho^{b}\big{)}$
$\displaystyle\sum_{T=1}^{b}\frac{b^{T}}{T!}-\sum_{T=1}^{b}\frac{b^{T-1}}{(T-1)!}$
$\displaystyle=\big{(}e^{b}-1-e^{b}(1-\frac{b^{b}e^{-b}}{b!})\big{)}$
$\displaystyle\frac{b^{b}}{b!}-1$ $\displaystyle=\frac{b^{b}}{b!}-1$

The last equality results from recognizing the terms on the left hand side as
a telescoping sum. ∎

###  .6 Proof of Theorem 3

To characterize the Pareto optimal frontier in Eq. (19), we first derive the
closed form solution for the one-round walk efficiency
$\mathrm{Eff}(w_{\mathrm{sc}},u;1)$ specifically for the set covering welfare
rule $w_{\mathrm{sc}}$.

######  Lemma 4.

Let $\mathcal{W}=\\{w_{\mathrm{sc}}\\}$, where $w_{\mathrm{sc}}$ is the set
covering welfare rule defined in Eq. (18), and
$\mathcal{U}(w_{\mathrm{sc}})=u$ be the corresponding utility rule. Then the
one-round walk efficiency guarantee is

$\mathrm{Eff}(w_{\mathrm{sc}},u;1)=\left[\sum_{i\in\mathbb{N}}{u(i)}-\min_{i\in\mathbb{N}}{u(i)}+1\right]^{-1}.$
(28)

###### Proof.

Examine the linear program in [13, Corollary 1] with substituting the set
covering welfare defined in Eq. (18). Under the substitution, the constraint
for a given $z$, $y$ simplifies to

$\beta\geq\sum_{i=1}^{y}u(i)-z\min_{1\leq i\leq y+1}u(i)+\min(1,z).$

We have applied the fact $w_{\mathrm{sc}}(j)=\min(1,j)=1$ when $j\geq 1$.
Observe that the binding constraint occurs when we limit $y\to\infty$ and set
$z=1$ (and not $z=0$ since $u(1)=1$, the term $1-\min_{j}u(j)\geq 0$). Under
the binding constraint, $\mathrm{Eff}(w_{\mathrm{sc}},u;1)=\beta^{-1}$, where
$\beta^{-1}$ matches the given expression in Eq. (28). ∎

Figure 8: The worst case game construction achieving the one-round walk
guarantee dictated by Lemma 4. The agents are represented by circles, each
oval represents the number of resources with the set covering welfare, and the
black lines represent the agent action selections. In this game, all the
agents can either stack on the first resource set or spread out.

To describe the trade-off, we now provide an explicit expression of Pareto
optimal utility rules, i.e., the utility rules $u$ that satisfy either
$\mathrm{Eff}(w_{\mathrm{sc}},u;1)\geq\mathrm{Eff}(w_{\mathrm{sc}},u^{\prime};1)$
or
$\mathrm{Eff}(w_{\mathrm{sc}},u;\infty)\geq\mathrm{Eff}(w_{\mathrm{sc}},u^{\prime};\infty)$
for all $u^{\prime}\neq u$.

######  Lemma 5.

For a given $\mathcal{X}\geq 0$, a utility rule $u^{\mathcal{X}}$ that
satisfies $\mathrm{Eff}(w_{\mathrm{sc}},u;\infty)\geq 1/(1+\mathcal{X})$ while
maximizing $\mathrm{Eff}(w_{\mathrm{sc}},u;1)$ is defined as in the following
recursive formula:

$\displaystyle u^{\mathcal{X}}(1)$ $\displaystyle=1$ (29) $\displaystyle
u^{\mathcal{X}}(j+1)$
$\displaystyle=\max\\{ju^{\mathcal{X}}(j)-\mathcal{X},0\\}.$

###### Proof.

We only consider utility rules that are non-increasing in this paper. Under
this assumption, from Lemma 1, we have that
$\mathrm{Eff}(w_{\mathrm{sc}},u;\infty)=\mathrm{PoA}(w_{\mathrm{sc}},u)$.
According to Corollary $2$ in [10], the price of anarchy for $n$ agents can be
written as

$\frac{1}{\mathrm{PoA}^{n}(w_{\mathrm{sc}},u)}=1+\\\ \max_{1\leq j\leq
n-1}\\{ju(j)-u(j+1),(n-1)u(n)\\}.$

We define the following constant for each possible utility rule.

$\mathcal{X}_{u}=\max_{1\leq j\leq n-1}\\{ju(j)-u(j+1),(n-1)u(n)\\}.$ (30)

For $u$ to be Pareto optimal, we claim that $ju(j)-u(j+1)=\mathcal{X}_{u}$
must hold for all $j$. Consider any other $u^{\prime}$ with
$\mathcal{X}_{u}=\mathcal{X}_{u^{\prime}}$. It follows that
$\mathrm{PoA}^{n}(w_{\mathrm{sc}},u)=\mathrm{PoA}^{n}(w_{\mathrm{sc}},u^{\prime})=1/(1+\mathcal{X}_{u})$.
By induction, we show that $u(j)\leq u^{\prime}(j)$ for all $j$. The base case
is satisfied, as $1=u(1)\leq u^{\prime}(1)=1$. Under the assumption $u(j)\leq
u^{\prime}(j)$, we also have that

$ju(j)-\mathcal{X}_{u}=u(j+1)\leq
u^{\prime}(j+1)=ju^{\prime}(j)-\mathcal{X}^{j}_{u},$ (31)

where
$\mathcal{X}^{j}_{u^{\prime}}=ju^{\prime}(j)-u^{\prime}(j+1)\leq\mathcal{X}_{u^{\prime}}$
by definition in Eq. (30), and so $u(j)\leq u^{\prime}(j)$ for all $j$.
Therefore the summation
$\sum_{i\in\mathbb{N}}{u(i)}-\min_{i\in\mathbb{N}}{u(i)}$ in Eq. (28) is
diminished when $u(i)\leq u^{\prime}(i)$ for all $i$ and
$\mathrm{Eff}(w_{\mathrm{sc}},u;1)\geq\mathrm{Eff}(w_{\mathrm{sc}},u^{\prime};1)$,
proving our claim. As $u$ must satisfy $u(j)\geq 0$ for all $j$ to be a valid
utility rule, $u(j+1)$ is set to be $\max\\{ju(j)-\mathcal{X},0\\}$. Then we
get the recursive definition for the maximal $u^{\mathcal{X}}$ in Eq. (29)
when we limit $n\to\infty$. Finally, we note that for infinite $n$,
$\mathcal{X}<\frac{1}{e-1}$ is not achievable, as shown in [26]. ∎

With the two previous lemmas, we can move to proving Theorem 3. We first
characterize a closed form expression of the maximal utility rule
$u^{\mathcal{X}}$, which is given in Lemma 5. We fix $\mathcal{X}$ so that
$\mathrm{Eff}(w_{\mathrm{sc}},u^{\mathcal{X}};\infty)=\frac{1}{\mathcal{X}+1}$
= $Q$. To calculate the expression for $u^{\mathcal{X}}$ for a given
$\mathcal{X}$, a corresponding time varying, discrete time system to Eq. (29)
is constructed as follows.

$\displaystyle x(t+1)$ $\displaystyle=tx(t)-\mathcal{X},$ $\displaystyle y(t)$
$\displaystyle=\max\\{x(t),0\\},$ $\displaystyle x(1)$ $\displaystyle=1,$

where $y(t)\equiv u^{\mathcal{X}}(j)$ corresponds to the utility rule. Solving
for the explicit solution for $y(t)$ using the state-transition matrix gives

$\displaystyle y(1)$ $\displaystyle=1$ $\displaystyle y(t)$
$\displaystyle=\max\Big{[}\prod_{\ell=1}^{t-1}\ell-\mathcal{X}\big{(}\sum_{\tau=1}^{t-2}\prod_{\ell=\tau+1}^{t-1}\ell\big{)}-\mathcal{X},0\Big{]}\
\ t>1.$

Simplifying the expression and substituting for $u^{\mathcal{X}}(j)$ gives

$u^{\mathcal{X}}(j)=\max\Big{[}(j-1)!(1-\mathcal{X}\sum_{\tau=1}^{j-1}\frac{1}{\tau!}\big{)},0\Big{]}\
\ \ j\geq 1.$

Substituting the expression for the maximal $u^{\mathcal{X}}$ into Eq. (28)
gives the one round efficiency. Notice that for
$\mathcal{X}\geq\frac{1}{e-1}$, $\lim_{j\to\infty}u^{\mathcal{X}}(j)=0$, and
therefore $\min_{j}{u^{\mathcal{X}}(j)}=0$. Shifting the variables
$j^{\prime}=j+1$, we get the statement in Eq. (19).

[]Rohit Konda received a B.S in Biomedical Engineering in 2018 and an M.S in
Electrical and Computer Engineering in 2019 from Georgia Tech. He is currently
a Ph.D Candidate in the Department of Electrical and Computer Engineering at
the University of California, Santa Barbara. His research interests include
distributed optimization and game-theoretic applications in multi-agent
systems.

[]Rahul Chandan received his B.A.Sc. degree in Engineering Science, and
Electrical and Computer Engineering from the University of Toronto, Toronto,
ON, Canada, in June 2017. He received his Ph.D. degree in 2022, under the
supervision of Jason R. Marden with the Electrical and Computer Engineering
Department, University of California, Santa Barbara, Santa Barbara, CA, USA.
His research interests include the application of game theoretic and control
methods to the analysis and design of multi-agent systems.

[]David Grimsman received the B.S. degree in electrical and computer
engineering from Brigham Young University, Provo, UT, USA, in 2006 as a
Heritage Scholar, with a focus on signals and systems. He received the M.S.
degree in computer science from Brigham Young University in 2016. He received
the Ph.D. degree in 2021, under the supervision of Jason R. Marden and Joao P.
Hespanha, with the Electrical and Computer Engineering Department, University
of California, Santa Barbara, Santa Barbara, CA, USA. He is currently an
Assistant Professor with the Department of Computer Science in Brigham Young
University.

He worked with BrainStorm, Inc. for several years as a Trainer and IT Manager.
His research interests include multiagent systems, game theory, distributed
optimization, network science, linear systems theory, and security of
cyberphysical systems.

[]Jason R. Marden received the B.S. degree in 2001 and the Ph.D. degree in
2007 under the supervision of Jeff S. Shamma from the University of
California, Los Angeles (UCLA), Los Angeles, CA, USA, both in mechanical
engineering. After graduating from UCLA, he served as a Junior Fellow with the
Social and Information Sciences Laboratory, California Institute of Technology
until 2010 when he joined the University of Colorado. He is currently a Full
Professor with the Department of Electrical and Computer Engineering,
University of California, Santa Barbara, CA, USA. His research interests focus
on game theoretic methods for the control of distributed multi-agent systems.

Dr. Marden is a recipient of the NSF Career Award in 2014, he was awarded the
Outstanding Graduating Ph.D. degree, the ONR Young Investigator Award in 2015,
the AFOSR Young Investigator Award in 2012, the American Automatic Control
Council Donald P. Eckman Award in 2012, and the SIAG/CST Best SICON Paper
Prize in 2015.


# AGN sub-populations important for black hole mass growth: a rule of thumb

Johannes Buchner Max Planck Institute for Extraterrestrial Physics,
Giessenbachstrasse, 85741 Garching, Germany

###### Abstract

For building the super-massive black hole population within a Hubble time,
only sub-populations with more than $10^{52}\mathrm{erg/s}/\overline{L}$
objects on the sky are relevant, where $\overline{L}$ is the sample-averaged
bolometric luminosity.

##  1 Building mass

To build a super-massive black hole with $M_{\bullet}=10^{8}\,M_{\odot}$
within the age of the Universe $\Delta t$ requires an average accretion
luminosity of $\overline{L}_{\mathrm{bol}}=5\times 10^{43}\,\mathrm{erg/s}$,
assuming the usual luminosity efficiency conversions
($L_{\mathrm{bol}}=\frac{\epsilon}{1-\epsilon}\dot{M}c{{}^{2}}$,
$\epsilon=10\%$). This is slightly above the common threshold for what is
considered an active galactic nucleus (AGN),
$L_{\mathrm{X}}>10^{42}\,\mathrm{erg/s}$, with the bolometric conversion
$L_{\mathrm{X}}(2-10\mathrm{keV})\approx L_{\mathrm{bol}}/10$ (e.g., Marconi
et al., 2004). Smaller black holes $M_{\bullet}=10^{4}M_{\odot}$ can be
assembled with $\overline{L}_{\mathrm{bol}}=5\times 10^{39}\,\mathrm{erg/s}$.

In considering the average luminosity, it is not necessary to assume a
constant luminosity over $\Delta t$. Indeed, the accretion rate may be
fluctuating over many orders of magnitude over long time-scales (e.g. Sartori
et al., 2019), and most galaxies are not AGN. This means that if the black
hole is active only in brief phases, the observed luminosities need to be
higher to reach the same average luminosity.

##  2 Building mass density

In the local Universe, the mass density locked into black holes is estimated
to be $\rho_{\bullet}\approx 5\times 10^{5}\,M_{\odot}/\mathrm{Mpc}^{3}$
(e.g., Marconi et al., 2004). Which sub-populations of AGN contribute
substantially ($>10\%$) to black hole growth history? Ten per cent
($50,000\,M_{\odot}/\mathrm{Mpc}^{3}$) corresponds to an average luminosity
density over the age of the Universe $\Delta t$ of:

$10\%\times\rho_{\bullet}/\Delta
t\times\left(\frac{\epsilon}{1-\epsilon}c{{}^{2}}\right)=\overline{L\times\phi}=2\times
10^{40}\,\mathrm{erg/s/Mpc}^{3}$ (1)

For a substantial contribution (eq. 1), sources need to be luminous but also
_numerous_. They need to be numerous to enable a high on-time (duty cycle) of
the accretion process, ortherwise the luminosity averaged over cosmic time is
small. The expected number of AGN on the entire sky can be estimated by
$N=V_{\mathrm{c}}\times\overline{\phi}$. We use the comoving volume
$V_{\mathrm{c}}=2\times 10^{12}\,\mathrm{Mpc}^{3}$ out to $z=4$, as the number
density of AGN strongly declines above $z=3$ (e.g., Georgakakis et al., 2015).
This gives the rule of thumb that samples that contribute more than 10 percent
of black hole growth need to have at least
$10^{52}\,\mathrm{erg/s}/\overline{L}$ sources in the Universe.

##  3 Examples

Lets first consider the _most extreme AGN_. For hot dust-obscured galaxies
(DOGs, Tsai et al., 2015), $\overline{L}=10^{48}\mathrm{erg/s}$. Therefore,
$\overline{\phi}=10^{-8}\mathrm{Mpc}^{-3}$, which means on the entire sky, at
least $N=V_{c}\times\overline{\phi}=10^{4}$ objects need to be seen for this
population to be significant. However, only a few hundred objects were found,
indicating that hot DOGs are not an important black hole mass growth phase.
This can be either because hot DOGs are created too rarely, or because the
phase is too brief.

Figure 1: Top panel: Black hole accretion history inferred from X-ray
luminosity functions, including Compton-thick growth. Bottom panel:
accumulated mass density over cosmic time. The gray error bars are local
densities estimates are from Marconi et al. (2004) and Shankar et al. (2004).
Most black hole growth occurs after the first and before the last 2 Gyrs.

Considering a more moderate luminosity, $\overline{L}=10^{46}\mathrm{erg/s}$,
such as for merger-induced red quasars (e.g., Urrutia et al., 2008), then
$\overline{\phi}=10^{-6}\mathrm{Mpc}^{-3}$, which means on the entire sky, at
least $N=10^{6}$ objects, or 24 objects per square degree, are required.
However, only a few hundred objects have been found, suggesting that _major
merger phases_ are too rare to contribute substantially to black hole growth.

Finally, let us consider the redshift interval where substantial growth
occurs. Figure 1 plots the accretion history inferred from the X-ray
luminosity function of Buchner et al. (2015, slope-constant machine-learned
space density model), and includes unobscured, mildly obscured and the most
heavily obscured AGN population. The top panel illustrates that in the _local
Universe_ , the current accretion rate density is an order of magnitude lower
than at its peak at cosmic noon, where it was $6\times
10^{41}\mathrm{erg/s/Mpc}^{3}/\mathrm{Gyr}$ . For this reason, the growth
accumulated (bottom panel) in the last 2 Gyrs (since $z<0.3$) is small and
amounts to less than 5 per cent. The growth in the first Gyr is also
negligible.

##  4 Closing words

While extreme and rare sub-populations may not contribute substantially to
black hole growth, they are laboratories that expose extreme physical
processes most clearly. However, when super-massive black hole mass assembly
is considered, sub-populations with more than
$10^{52}\mathrm{erg/s}/\overline{L}$ objects on the sky, and
$\overline{L}>5\times 10^{39}\mathrm{erg/s}$ are required.

## Acknowledgements

I thank Isabelle Gauger and Qingling Ni for helpful feedback on the
manuscript. This work was inspired by discussions in the “What drives the
Growth of Black Holes? A decade of reflection” workshop 2022.

## References

  * Buchner et al. (2015) Buchner, J., Georgakakis, A., Nandra, K., et al. 2015, ApJ, 802, 89
  * Georgakakis et al. (2015) Georgakakis, A., Aird, J., Buchner, J., et al. 2015, MNRAS, 453, 1946
  * Marconi et al. (2004) Marconi, A., Risaliti, G., Gilli, R., et al. 2004, MNRAS, 351, 169
  * Sartori et al. (2019) Sartori, L. F., Trakhtenbrot, B., Schawinski, K., et al. 2019, ApJ, 883, 139
  * Shankar et al. (2004) Shankar, F., Salucci, P., Granato, G. L., De Zotti, G., & Danese, L. 2004, MNRAS, 354, 1020
  * Tsai et al. (2015) Tsai, C.-W., Eisenhardt, P. R. M., Wu, J., et al. 2015, ApJ, 805, 90
  * Urrutia et al. (2008) Urrutia, T., Lacy, M., & Becker, R. H. 2008, ApJ, 674, 80