Balancing Asymptotic and Transient Efficiency Guarantees
in Set Covering Games

To prove the statements outlined in items $\rm{(a)}$ and $\rm{(b)}$ of the theorem statement, we show, more generally, that for any $f$ and any $k$, the following series of inequalities is true:

The fact that $\mathrm{PoB}(f_{MC},n,1)=1/2$ is a result of Lemma 1 (stated later in the paper) for $n\geq 2$ and the definition of $f_{MC}$. For proving $\mathrm{PoB}(f_{MC},n,k)=\frac{1}{2}$, we first show that

Let $a,a^{\prime}\in\mathcal{A}$ be joint actions such that $a^{\prime}$ is a best response to $a$ for agent $i$. If the MC rule is used as in Equation (13), then

Then, after any $m\geq 1$ best response rounds, $\mathrm{W}(\mathrm{end}(m))\geq\mathrm{W}(\mathrm{end}(1))$, and therefore the claim is shown. For the other direction as well as the inequality $\frac{1}{2}\geq\mathrm{PoB}(f,n,k)$, we construct a game construction (also shown in Figure 1) such that for any utility rule $f$, $\mathrm{PoB}(\mathrm{G}^{f},k)\leq\frac{1}{2}$. The game $\mathrm{G}^{f}$ is constructed as follows with $2$ agents. Let the resource set be $\mathcal{R}=\{r_{1},r_{2},r_{3},r_{4}\}$ with $v_{r_{1}}=1$, $v_{r_{2}}=1$, $v_{r_{3}}=f(2)$, and $v_{r_{4}}=0$. For agent $1$, let $\mathcal{A}_{1}=\{a^{\varnothing}_{1},a^{1}_{1},a^{2}_{1}\}$ with $a^{1}_{1}=\{r_{1}\}$ and $a^{2}_{1}=\{r_{2}\}$. For agent $2$, let $\mathcal{A}_{2}=\{a^{\varnothing}_{2},a^{1}_{2},a^{2}_{2}\}$ with $a^{1}_{2}=\{r_{3}\}$ and $a^{2}_{2}=\{r_{1}\}$. It can be seen in this game, if $f(2)\leq 1$, the optimal joint action is $(a^{2}_{1},a^{2}_{2})$ resulting in a welfare of $2$, and if $f(2)>1$, the optimal joint action is $(a^{2}_{1},a^{1}_{2})$ resulting in a welfare of $1+f(2)\geq 2$. Additionally, starting from $(a^{\varnothing}_{1},a^{\varnothing}_{2})$, note the best response path $((a^{\varnothing}_{1},a^{\varnothing}_{2}),(a^{1}_{1},a^{\varnothing}_{2})(a^{1}_{1},a^{1}_{2}),\dots,(a^{1}_{1},a^{1}_{2}),(a^{1}_{1},a^{1}_{2}),(a^{1}_{1},a^{2}_{2}))$ exists, ending in the action $(a^{1}_{1},a^{2}_{2})$ with a welfare $1$. Since $(a^{1}_{1},a^{1}_{2})$ is a Nash equilibrium, both agents stay playing their first action $a^{1}$ for $k-1$ rounds and agent $2$ only switches to $a^{2}_{2}$ in the $k$-round. Therefore $\mathrm{PoB}(\mathrm{G}^{f},k)\leq\frac{1}{2}$ for this game. This game construction $\mathrm{G}^{f}$ can be extended to $n>2$ by fixing the actions of agents $i\geq 2$ to be $\mathcal{A}_{i}=\{a^{\varnothing}_{i},a^{1}_{i}\}$, where the only nonempty action available to them is $a^{1}_{i}=\{r_{4}\}$ that selects the $0$ value resource.

Since $\mathrm{G}^{f}$ may not be the worst case game, $\mathrm{PoB}(f,n,k)\leq\mathrm{PoB}(\mathrm{G}^{f},k)\leq\frac{1}{2}$ and the final claim is shown. ∎

To characterize $\mathrm{PoB}(f,n,1)$, we first formulate it as an optimization program, where we search over all possible set covering games with a fixed $f$ and $n$ for the worst $1$-round outcome. We give a proof sketch of the correctness of the proposed optimization program in (22). Without loss of generality, we can only consider games where each agent $i$ has $2$ actions $a^{\mathrm{opt}}_{i}$ and $a^{\mathrm{br}}_{i}$, in which $a^{\mathrm{opt}}$ is the action that optimizes the welfare $\mathrm{W}$ and $a^{\mathrm{br}}$ is the action that results from a $1$-round best response. Informally, the optimization program involves searching for a set covering game that maximizes $\mathrm{W}(a^{\mathrm{opt}})$ with the constraints $\mathrm{W}(a^{\mathrm{br}})=1$ and that $a^{\mathrm{br}}$ is indeed the state that is achieved after a $1$-round best response. Since the welfare $\mathrm{W}(a)$ as well as $\mathrm{U}_{i}(a)$ can be described fully by $v_{r}$ and $f$, each game is parametrized through the resource values $v_{r}$ from a common resource set $\mathcal{R}^{*}$. Let

denote the set of agents that select the resource $r$ in $a^{\mathrm{br}}$. We define $\mathbf{a}_{\mathrm{opt}}(r)$ similarly. Additionally, we can define $\mathbf{a}_{\mathrm{br}}^{<i}(r)=\{1\leq j<i:r\in a^{\mathrm{br}}_{j}\}$ to denote the set of agents $\{1,\dots,i-1\}$ that select the resource $r$ in in $a^{\mathrm{br}}_{i}$. The common resource set $\mathcal{R}^{*}$ is comprised of all the resources $r$ that have unique signature from $\mathbf{a}_{\mathrm{br}}(r)$ and $\mathbf{a}_{\mathrm{opt}}(r)$. Taking the dual of the program in the previous outline results in the following program.

Now we reduce the constraints of this program to give a closed form expression of $\mathrm{PoB}(f,n,k)$. We first examine the constraints in (23) associated with $r\in\mathcal{R}^{*}$ with $\mathbf{a}_{\mathrm{br}}(r)=\varnothing$. Simplifying the corresponding constraints gives

for any subset of agents $P\subset\mathcal{I}$. Only considering $P=\{j\}$ gives the set of binding constraints $\lambda_{j}\geq 1/f(1)$ for any agent $j$.

Now we consider the converse constraints in (23) where $\mathbf{a}_{\mathrm{br}}(r)\neq\varnothing$. For this set of constraints, the binding constraint is postulated to be

corresponding to the resource $\bar{r}$ with $\mathbf{a}_{\mathrm{br}}(\bar{r})=\mathcal{I}$ and $\mathbf{a}_{\mathrm{opt}}(\bar{r})=\{\arg\min_{j}f(j)\}$. Under this assumption, the optimal dual variables $\lambda_{j}$ are $\lambda_{j}=1/f(1)\ \forall j$. This follows from the constraint in (24) and the fact that decreasing any $\lambda_{j}$ results in a lower binding constraint in (25).

Now we can verify that the constraint in (25) with $\mathbf{a}_{\mathrm{br}}(\bar{r})=\mathcal{I}$ and $\mathbf{a}_{\mathrm{opt}}(\bar{r})=\{\arg\min_{j}f(j)\}$ is indeed the binding constraint under the dual variables $\lambda_{j}=1/f(1)$. The resulting dual program assuming $\mathbf{a}_{\mathrm{br}}(r)\neq\varnothing$ is

Since any valid utility rule has $f(j)\geq 0$ for any $j$, the terms in (27) is maximized if $\mathbf{1}_{\mathbf{a}_{\mathrm{br}}(r)}(j)=1$ for all $j$ which implies that $\mathbf{a}_{\mathrm{br}}(r)=\mathcal{I}$. Also note that $|\mathbf{a}_{\mathrm{opt}}(r)|\leq 1$, as

is less binding if $|\mathbf{a}_{\mathrm{opt}}(r)|>1$. Since $\mathbf{a}_{\mathrm{br}}(r)=\mathcal{I}$ for the binding constraint, if $|\mathbf{a}_{\mathrm{opt}}(r)|=1$, the terms in (28) reduces to $1-f(j)/f(1)$ for some $j$. Similarly, if $|\mathbf{a}_{\mathrm{opt}}(r)|=0$, the terms in (28) reduces to $0$. Note that $1-f(1)/f(1)\geq 0$, and so $1-\min_{j}\{f(j)\}/f(1)\geq 0$ as well. Thus $|\mathbf{a}_{\mathrm{opt}}(r)|=1$ is binding. Taking any $\mathbf{a}_{\mathrm{opt}}(\bar{r})\in\arg\min_{j}f(j)$ attains the maximum value for $1-\min_{j}\{f(j)\}/f(1)$, and so we have shown the claim that the binding constraint for $\mu$ is in equation (25). Taking the binding constraint with equality gives

giving the expression for $\mathrm{PoB}$ as stated. ∎

According to a modified version of Theorem $2$ in [26], the price of anarchy ($\mathrm{PoA}$) can be written as

We first show that if $f$ is Pareto optimal, then it must also be non-increasing. Otherwise, we show that another $f$ exists that achieves at least the same $\mathrm{PoB}$, but a higher $\mathrm{PoA}$, contradicting our assumption that $f$ is Pareto optimal. Assume, by contradiction, that there exists $f$ that is Pareto optimal and decreasing, i.e., there exists a $j^{\prime}\geq 1$, in which $f(j^{\prime})<f(j^{\prime}+1)$. Notice that switching the value $f(j^{\prime})$ with $f(j^{\prime}+1)$ results in an unchanged $\mathrm{PoB}$ according to (20) in Lemma 1 if $j^{\prime}>1$. We show that $f^{\prime}$ with the values switched has a higher $\mathrm{PoA}$ than $f$.

For any $1\leq j^{\prime}\leq n-1$, the expressions from (IV) that include $f(j^{\prime})$ or $f(j^{\prime}+1)$ are

After switching, the relevant expressions for $f^{\prime}$ are

Since $f(j^{\prime})<f(j^{\prime}+1)$, switching the values results in a strictly looser set of constraints, and the value of the binding constraint in (IV) for $f^{\prime}$ is at most the value of the binding constraint for $f$. Therefore $\mathrm{PoA}(f)\leq\mathrm{PoA}(f^{\prime})$. Note that if $j^{\prime}=1$, then $\mathrm{PoB}(f^{\prime})>\mathrm{PoB}(f)$ as well. This contradicts our assumption that $f$ is Pareto optimal.

Now we restrict our focus to non-increasing $f$ with $f(1)=1$. Observe that for any $f$, the transformation $f^{\prime}(j)=f(j)/C$, $C>0$, doesn’t change the price of best response and price of anarchy. Thus, we can take $f(1)=1$ without loss of generality. Given a $f$ that satisfies the above constraints, the price of anarchy is

as detailed in Corollary $2$ in [26]. Let

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

where $\mathcal{X}^{j}_{f}=jf(j)-f(j+1)\leq\mathcal{X}_{f}$ by definition in (33), and so $f(j)\leq f^{\prime}(j)$ for all $j$. Therefore the summation $\sum_{j=1}^{n}{f(j)}-\min_{j}{f(j)}$ in (20) is diminished and $\mathrm{PoB}(f)\geq\mathrm{PoB}(f^{\prime})$, proving our claim. As $f$ must satisfy $f(j)\geq 0$ for all $j$ to be a valid utility rule, $f(j+1)$ is set to be $\max\{jf(j)-\mathcal{X},0\}$. Then we get the recursive definition for the maximal $f^{\mathcal{X}}$. Finally, we note that for infinite $n$, $\mathcal{X}\leq\frac{1}{e-1}$ is not achievable, as shown in [10]. ∎

We first characterize a closed form expression of the maximal utility rule $f^{\mathcal{X}}$, which is given in Lemma 2. We fix $\mathcal{X}$ so that $\mathrm{PoA}(f^{\mathcal{X}})=\frac{1}{\mathcal{X}+1}$ = $C$. To calculate the expression for $f^{\mathcal{X}}$ for a given $\mathcal{X}$, a corresponding time varying discrete time system to (30) is constructed as follows.

where $y[m]$ corresponds to $f^{\mathcal{X}}(j)$. Solving for the explicit expression for $y[m]$ gives

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

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

Finally, we prove that if $\mathrm{PoA}(f)=1-\frac{1}{e}$ for a given $f$, then $\mathrm{PoB}(f,1)$ must be equal to $0$. According to (19), among utility rules $f$ with $\mathrm{PoA}(f)=1-\frac{1}{e}$, the best achievable $\mathrm{PoB}(f,1)$ can be written as