## The Efficiency of Generalized Nash and Variational Equilibria

Ankur A. Kulkarni

## Abstract

Shared-constraint games are noncooperative N -player games where players are coupled through a common coupling constraint. It is known that such games admit two kinds of equilibria - generalized Nash equilibria (GNE) and variational equilibria (VE) - with two different economic interpretations. We consider such games in the context of resource allocation, where players move simultaneously to decide portions of the resource they can consume under a coupling constraint that the sum of the portions they demand be no more than the capacity of the resource. We clarify the worst case and best case efficiency of these kinds of equilibria over all games in a class. We find that the worst case efficiency of both solution concepts in zero and the best case efficiency is unity. Moreover, we characterize the subclass of games where all VE are efficient and show that even in this subclass but the worst case efficiency of GNE is zero. We finally discuss means by which zero worst case efficiency can be remedied.

## I. INTRODUCTION

Generalized Nash games with shared constraints are noncooperative N -player games in which the strategies available to each player are constrained by the requirement that the N -tuple of player-strategies belong to a common set. This work considers shared-constraint games which arise from the competition for a finite resource, such as bandwidth or energy. The shared constraint is the common requirement that the portions of the resource allocated to all players must total to not exceed the available quantity of the resource. We investigate and clarify the efficiency of the equilibria of these games with respect to a socially desirable outcome.

Our game may be thought of as a resource allocation game , though this term has acquired a somewhat more specific meaning [7] that does not commonly allude to our setting. The traditional resource allocation game has players that compete in a noncooperative fashion to access the resource, but their competition is mediated by a mechanism . A mechanism accepts bids from players and allocates the resource to the players in exchange for a payment, thereby also maintaining feasibility of the allocation. Since players may be price anticipating, the choice of a player's bid is strategically coupled to the bids of other players, leading to a game in which the strategy of each player is its bid, its constraint is the space of its bids and its objective is to maximize its utility less the payment charged by the mechanism. In contrast, our game is played in the space of resource portions, the players are cognizant of the finiteness of the resource and their objective is to maximize their utility.

In a resource-allocation game, each player desires to maximize its utility. But from the system-perspective, the goal is to allocate resources in a manner that a prescribed societal objective, characterized by the optimization of a welfare function , is met. A natural and commonly employed societal objective is the optimzation of aggregate utility or sum of utilities of all players, i.e. the maximization of social welfare, though other objectives could be chosen based on the setting. When utilities are measured in monetary terms and arbitrary money transfers are permitted across agents, aggregate utility maximization also equivalent to

Systems and Control Engineering, Indian Institute of Technology Bombay, Mumbai, India 400076. The author can be contacted at kulkarni.ankur@iitb.ac.in , or +91-9167889384 (phone) or +91-2225720057 (fax)

the classical concept of Pareto efficiency 1 [6] or economic efficiency . We say that an allocation is efficient if it implements the aggregate utility and we call the efficiency of an allocation, the ratio of the aggregate utility for this allocation to that of an efficient allocation.

The allocation corresponding to the Nash equilibrium of the game is, in general, only feasible for the social planner's problem of maximizing aggregate utility. Thus these allocations are, in general, not efficient. The question of resource allocation is therefore one with dual, and possibly conflicting objectives of efficiency and competition. The usual approach to this dilemma gives primacy to competition while attempting to control the loss in efficiency. Specifically, when allocating resources through a mechanism, the effort is to design a mechanism that provides a guarantee of low efficiency loss at its Nash equilibrium. This is the central pursuit of the field of mechanism design [21], though the societal objective to be met differs according to situation.

Our game represents a departure from this approach. Though we also have the dual objectives of competition and efficiency, our game is relevant if one makes the assumption that the option of a mechanism does not exist. In our setting, players move simultaneously, in a noncooperative manner and compete for portions of the resource. A shared-constraint game naturally fits such an interaction. The goal behind our work is not to suggest this game as an alternative to mechanism driven approaches to resource allocation, but instead to analyze the specific setting where it is relevant and to study the efficiency of equilibria that result from it. The subtlety though is that shared-constraint games admit two kinds of solution concepts, generalized Nash equilibrium (GNE) and the variational equilibrium (VE), with two different economic interpretations (see [10] and [11]). In [10], a theory was presented to argue that the VEcan be considered a refinement of the GNEfor a large class of games. In the light of this, our goal is also to do a comparative study of these classes of equilibria with respect to the metric of efficiency. Though our work is not intended as an alternative to other mechanism-based approaches, it contributes to identifying settings where the VEs of this shared-constraint game have higher efficiency than the equilibria induced by mechanisms.

We discuss the efficiency of these equilibria separately. In particular, we are concerned with the best case efficiency and the worst case efficiency of the GNE and the VE. Ours is, to the best of our knowledge, the only work on the efficiency of equilibria in general shared-constraint games, though the social welfare of the equilibria of these games has been considered in the setting of congestion control [1]. A detailed comparison with other work is encompassed in Section III.

We consider two kinds of utility functions. In the first kind, the utility derived by any player is a function only of the allocation it receives. In the second, and more general setting, utilities are dependent on allocations received by other players. The first setting has an interesting interpretation in terms of the competitive equilibrium. We also see that the VE is efficient in this setting, whereas the GNE can be arbitrarily inefficient. In the more general setting we are concerned with the best case efficiency and worst case efficiency over a class of utility functions. We characterize settings under which full efficiency is obtained and identify that the solution concept of the VE achieves this unit efficiency. We also show that a departure from this setting can lead to arbitrarily low efficiency. Specifically, if one considers the GNE as a solution concept, for settings where the VE is efficient, one can get arbitrarily low efficiency. And a departure from the 'efficient' setting of the VE can lead to arbitrarily low efficiency for the VE.

We then suggest some ways in which this arbitrarily low efficiency may be remedied. One of the causes of low efficiency is the possibility of wide variation in the marginal utilities of players. A more restricted class of utility functions gives a more favorable worst case efficiency. We consider a setting, inspired by [1], with a slightly different social choice function. This setting is a game where players incur costs that, from the system point of view, are not additive. Thus the social choice function is not merely the sum of the objectives of all players. We characterize utility functions for which the VE is efficient under this notion of

1 A Pareto efficient allocation is an allocation, by deviations from which the value derived by any player cannot be strictly increased without simultaneously resulting in strictly lower value for another player.

efficiency. Finally we consider the imposition of a reserve price on players. The reserve price has the effect of eliminating players with low interest in the resource. The GNE of the resulting game is more indicative of the system optimal solution. We find that under certain conditions, efficiency as high as unity is obtainable by the imposition of an appropriate reserve price.

In Section II we introduce the model and our assumptions. In Section III we clarify the relationship of our approach with the competitive equilibrium and other approaches that use mechanisms. Following that we give a general bound on the efficiency by showing that In Section V we characterize the class of games where the VE is efficient and show that the GNE can be arbitrarily inefficient in this class. Section VI some ways to lower bound the efficiency loss and some other models are considered. We conclude with some final considerations in Section VII.

## II. PRELIMINARIES

In this section we describe the setting for our resource allocation game and our notions of efficiency. We mention some mathematical characterizations that will be used in later sections.

Let N = { 1 2 , , . . . , N } be a set of players. For each i ∈ N , let x i ∈ R be player i 's strategy and ϕ i : R N → R be his utility function. By x we denote the tuple ( x , x 1 2 , . . . , x N ) , x -i denotes the tuple ( x , . . . , x 1 i -1 , x i +1 , . . . , x N ) and ( y , x i -i ) the tuple ( x , . . . , x 1 i -1 , y i , x i +1 , . . . , x N ) . Let Φ denote the tuple ( ϕ , . . . , ϕ 1 N ) . The shared constraint in our game is the requirement that the tuple x be constrained to lie in a set C ⊆ R N , where C is a positive real number

A tuple x ∈ C is termed an allocation and the number C represents the capacity of the resource. We consider an model with a single resource, whereby x i is the portion of the resource demanded by player i . In the generalized Nash game with shared constraint C , player i is assumed to solve the parameterized optimization problem,

$$\begin{array} { l } \text{unt in our game is the requirement that} \\ \\ \mathbb { C } = \left \{ x \geq 0 \ \Big | \ \sum _ { j \in \mathcal { N } } x _ { j } \leq C \right \}, \\ \\ \vdots \\ \end{array}$$

$$\begin{matrix} \frac { A _ { i } ( x ^ { - i } ) & \max _ { x _ { i } } & \varphi _ { i } ( x _ { i } ; x ^ { - i } ) \\ \text{subject to } \sum _ { j \in \mathcal { N } } x _ { j } \leq C, \\ x _ { i } \geq 0. \end{matrix}$$

In other words, each player decides a portion of the resource so as to maximize his utility, but he does so while being cognizant of the fact that portion he has access to is that which when added to the portions of other players, does not exceed C . Throughout this paper we abbreviate the aggregate utility function by

$$\text{rougout} & u s \text{ paper we aoprevue aue aggregate unity function by} \\ & \Theta & \stackrel { \triangle } { = } \sum _ { j \in \mathcal { N } } \varphi _ { j }, & ( 1 )$$

and make the following assumption.

Assumption 2.1: We assume that for each i ∈ N , the utility function ϕ i ( x ) is a concave, continuously differentiable and strictly increasing function in x i . Furthermore, the utility obtained from the allocation x = 0 , i.e. ϕ i (0) , is nonnegative for all i . Finally, the aggregate utility Θ is a concave function such that for each allocation x , ∇ Θ( ) x is component-wise nonnegative.

Following are the motivations behind these assumptions. It is common to assume that utility is an increasing function of the portion, and that marginal utility is nonincreasing. This leads one to an assumption that of each ϕ i is increasing and strictly concave in x i . The other assumptions, in particular the concavity of Θ and nonnegativity of ∇ Θ may not hold in all cases. The nonnegativity of ∇ Θ and the concavity of Θ says

/negationslash

We recall the solution concepts of the generalized Nash equilibrium (GNE) and variational equilibrium (VE) from [10], [5], [4]. For this game, these concepts reduce to the following.

that utility functions of players are such that for the social planner, withholding portions of the resource so as to not exhaust the capacity C , is not optimal. We note that these assumptions are compatible wth the usual case where for all i , ϕ i ( x ) = U i ( x i ) for all x and that they are met by quasi-linear utility functions: ϕ i ( x ) = U i ( x i ) -∑ j = i d x i j j commonly used in economics [17].

Definition 2.1 (Generalized Nash equilibrium (GNE)): A tuple x is a generalized Nash equilibrium if there exists a tuple Λ = ( λ , . . . , λ 1 N ) ∈ R N such that x and Λ satisfy the KKT conditions of the optimization problems (A 1 ) , . . . , ( A N ):

$$0 & \leq x _ { i } \perp - \nabla _ { i } \varphi _ { i } ( x ) + \lambda _ { i } \geq 0 \\ 0 & \leq \lambda _ { i } \perp C - \mathbf 1 ^ { T } x \geq 0, \quad \ \forall \ i \in \mathcal { N }.$$

The set of all GNEs of this game with objective functions Φ is denoted by GNE(Φ) .

Here 1 denotes a vector in R N with each coordinate unity. The GNE that corresponds to equal Lagrange multipliers, i.e. Λ = λ 1 for some λ is the VE.

Definition 2.2 (Variational equilibrium (VE)): A tuple x is a variational equilibrium if there exists λ ∈ R such that x satisfies the KKT conditions of all the optimization problems (A 1 ) , . . . , ( A N ) with λ as the Lagrange multiplier. i.e.

$$0 & \leq x _ { i } \perp - \nabla _ { i } \varphi _ { i } ( x ) + \lambda \geq 0 \\ 0 & \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0, \quad \forall \ i \in$$

$$0 \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0, \quad \forall \ i \in \mathcal { N }.$$

The set of all VEs of this game with objective functions Φ is denoted as VE(Φ) .

As a consequence of the compactness of C , any game with utility functions satisfying Assumption 2.1, the set of VEs (and hence the set of GNEs) is nonempty. The proof of this fact can be found, e.g., in Rosen [25].

It was argued in [10] that the VE may be considered a refinement of the GNE. The main argument rests on the observation that the Lagrange multipliers λ , . . . , λ 1 N in the definition of the GNE can be interpreted as prices charged by an administrator for consumption of the resource. As such any specific GNE can be realized by the choice of these multipliers. A GNE that is not a VE corresponds to the imposition of nonuniform prices across players by the administrator, whereas the VE corresponds to uniform prices. However, nonuniform prices necessarily require the administrator to be able to distinguish between the players. If players are anonymous, only uniform prices are feasible and as such the only GNE that can be meaningful is the VE.

The goal of this work is to study the efficiency of these solution concepts. As mentioned in the introduction, our notion of efficiency is the maximization of aggregate utility.

Definition 2.3: A point x is said to be efficient if it solves the following optimization problem

$$\boxed { \underset { x } { \max } \quad \Theta ( x ) } \quad \underset { \substack { \sum _ { j \in \mathcal { N } } } { x _ { j } \leq C, \\ x _ { j } \geq 0, \quad \forall \ j \in \mathcal { N }. } } } \, \boxed { \underset { \substack { \Theta / \cap \lambda } } { \Theta / \cap \lambda } } }$$

The efficiency of a point x is defined as the ratio Θ( ) x Θ( x ∗ ) , where x ∗ is a solution of (SYS).

By Assumption 2.1, (SYS) is a convex optimization problem. It follows that x is efficient if there exists λ ∈ R such that

$$0 & \leq x \perp - \nabla \Theta ( x ) + \lambda 1 \geq 0 \\ 0 & \leq \lambda \perp C - \sum _ { j \in \mathcal { N } } x _ { j } \geq 0$$

An alternative characterization of the GNEs and VEs is through the use of quasi-variational inequalities and variational inequalities respectively. To define these objects, let F : R N → R N be the following function and K be the set-valued map

$$\text{respectively. To define these objects, \, \stackrel { \sim } { \, \text{let } \, F \, \colon \, \mathbb { R } ^ { N } \to \mathbb { R } ^ { j } } \\ F ( x ) = - \begin{pmatrix} \nabla _ { 1 } \varphi _ { 1 } ( x ) \\ \vdots \\ \nabla _ { N } \varphi _ { N } ( x ) \end{pmatrix}, \quad \forall \ x \in \mathbb { R } ^ { N }, \\ \text{ap} \\ \cdot \quad. \quad \nu \nu - i \cdot \quad \nu \quad \nu \quad \nu - \mu \mu + i \quad \nu \quad \nu - i \cdot \quad \nu \nu$$

A allocation x is a GNE if and only if x solves the quasi-variational inequality QVI ( K,F ) below.

$$& \text{and $K$ be the set-valued map} \\ & K ( x ) \coloneqq \prod _ { i \in \mathcal { N } } K _ { i } ( x ^ { - i } ) \ \text{ where } \ K _ { i } ( x ^ { - i } ) \coloneqq \{ y _ { i } \in \mathbb { R } ^ { m _ { i } } \ | \ ( y _ { i }, x ^ { - i } ) \in \mathbb { C } \}, \ \ \forall i \in \mathcal { N }, \forall \ x \in \mathbb { R } ^ { N }. \\ & A \text{ allocation $x$ is a GNE if and only if $x$ solves the quasi-variational inequality QVI(K,F) below.}$$

$$\left | \quad & \quad \text{Find } x \in K ( x ) \quad \text{such that } \quad F ( x ) ^ { T } ( y - x ) \geq 0 \quad \forall \ y \in K ( x ). & & ( Q \text{VI} ( K, F ) ) \ \right |$$

Likewise, x is a VE if and only if it solves the variational inequality VI ( C , F ) .

$$\left | \quad & \quad \text{Find } x \in \mathbb { C } \quad \text{such that } \quad F ( x ) ^ { T } ( y - x ) \geq 0 \quad \forall \ y \in \mathbb { C }. & \quad ( \text{VI} ( \mathbb { C }, F ) ) \ \right |$$

Since under Assumption 2.1 (SYS) is a convex optimization problem, efficient allocations are characterized by the solutions of the VI( C , -∇ Θ) ,

$$\left | \quad \text{ Find } x \in \mathbb { C } \quad \text{such that } \quad - \nabla \Theta ( x ) ^ { T } ( y - x ) \geq 0 \quad \forall \ y \in \mathbb { C }. \quad \text{(VI(\mathbb{C},-\nabla \Theta)) } \ \right |$$

The efficiency of an allocation depends on utility functions considered. In order to provide guarantees of efficiency of an allocation one needs to consider classes of utility functions and examine the worst (or best) case of efficiency over all of them. Therefore to provide efficiency guarantees for a solution concept , one needs to examine the worst (or best) case of efficiency over allocations generated by the said solution concept for each utility function in the class. For this purpose denote by F the class of utility functions that satisfy Assumption 2.1:

$$\mathcal { F } = \{ \Phi \ | \ \varphi _ { 1 }, \dots, \varphi _ { N } \text{ satisfy Assumption 2.1} \}.$$

Let L be the subclass of F comprising of linear objective functions:

$$\mathcal { L } = \{ \Phi \ | \ \varphi _ { 1 }, \dots, \varphi _ { N } \text{ are linear and satisfy Assumption 2.1} \}.$$

Following are our notions of best case and worst case efficiency for the GNE and VE respectively.

Definition 2.4: The best case efficiency of the GNE and the VE are defined as

$$\bar { \rho } = \sup _ { x \in \text{GNE} ( \Phi ), \, \Phi \in \mathcal { F } } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) },$$

$$\text{and} \quad \bar { \vartheta } = \sup _ { x \in \text{VE} ( \Phi ), \Phi \in \mathcal { F } } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) },$$

respectively.

Definition 2.5: The worst case efficiency of the GNE and the VE are defined as

$$\underline { \rho } = \inf _ { x \in \text{GNE} ( \Phi ), \Phi \in \mathcal { F } } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) },$$

$$\text{and} \quad \underline { \vartheta } = \inf _ { x \in \text{VE} ( \Phi ), \Phi \in \mathcal { F } } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) },$$

$$& \frac { \Theta ( x ) } { \tt n { \tt x } _ { z \in \mathbb { C } } \, \Theta ( z ) }, \\ & \frac { \Theta ( x ) } { \tt x _ { z \in \mathbb { C } } \, \Theta ( z ) },$$

respectively.

By Assumption 2.1, Θ(0) ≥ 0 and ∇ Θ ≥ 0 . This ensures that Θ is nonnegative on C and thereby the solution of (SYS) is positive and finite, whereby the efficiencies defined above are all finite and nonnegative. In other words, ¯ ρ, ρ, ϑ, ϑ ¯ ∈ [0 , 1] , and that ¯ ρ ≥ ρ and ¯ ϑ ≥ ϑ . Furthermore, since every VE is a GNE, we readily get

$$\bar { \rho } \geq \bar { \vartheta }, \quad \text{and} \quad \underline { \rho } \leq \underline { \vartheta }.$$

## III. RELATION TO PAST WORK

The appropriate allocation of resources is perhaps the fundamental concern that led to the inquiries that we today recognize as being part of the field of economics. Adam Smith's classic, The Wealth of Nations [29], first published back in 1776, contains perhaps the first scholarly attempt at understanding and explaining how societies allocate resources. Smith's observations, which say that competition and efficiency go hand in hand, are the foundations of general equilibrium theory and the welfare theorems [17], [32]: every competitive equilibrium maximizes social welfare and under certain conditions, every social welfare maximizing allocation is achievable as a competitive equilibrium.

These theorems rely on the assumption of perfect competition which states that players do not strategically anticipate the impact of their actions on the actions of other players [16]. Things changed in the mid-1940's with the invention of game theory [31]. Game theory provided a formal paradigm for studying the more general and, in some cases, somewhat more realistic setting where players were allowed to be strategic and price anticipating . In game-theoretic parlance, social welfare maximization was seen as the outcome of a cooperative game. By considering the Nash equilibrium as the outcome of the noncooperative counterpart, it was easily seen that the welfare theorems need not hold, i.e. cooperative and noncooperative games yield patently different equilibria. The classic game of Prisoner's Dilemma [17] is a telling example of this fact. The noncooperative interaction yields both prisoners significantly more years in prison than a decision they could have achieved had they cooperated. In fact a theorem of Dubey [2] rigorously establishes that Nash equilibria are generically (for an open dense subset of the space of utility functions) inefficient in the Pareto sense 2 .

Efficiency has also been a question in mechanism design. Though Nash equilibria can be inefficient, in the context of mechanism design, these Nash equilibria correspond to the game in the space of bids induced by the mechanism. In this setting, more encouraging results are seen. The Vickrey auction [30], is an success story of this approach, for it is known to be efficient 3 and has other attractive properties. The last two decades in particular has seen a dramatic surge in the interest in such questions, especially in the computer science and electrical engineering community. Most of this interest find its origins in the seminal work of Kelly et al. [8] in which congestion or rate control in a communication network, such as the internet, was modelled as a resource allocation problem. Kelly et al. introduced a model in which each player submitted a 'bid' and received an allocation proportional to its bid and showed that the competitive equilibrium of this mechanism was efficient. Since then Johari [6], Roughgarden [26], [27], Papadimitriou [24] and many others have worked on bounding the efficiency loss in resource allocation or related games. Indeed, Papadimitriou has called the worst case efficiency as the price of anarchy . The volume of work in this area is too large to be cited here to any degree of completeness. We instead refer the reader to the above references and to the book by Nisan et al. [22] for more.

2 See also Maskin [18] which gives sufficient conditions for a social choice rule to implementable by a game and the Pigou example [22]

3 The Vickrey auction pertains to the auctioning of a single indivisible good. Efficiency in this context means that the good is allocated to the bidder who values it most.

Our work is distinct from all the other work on resource allocation. But thanks to this long and rich history of resource allocation, it does bear similarities to some of the past approaches. We highlight the distinctions here and the relation other approaches is explained in the following sections. The first distinction between our approach and any of the past approaches is the use of a shared-constraint game. Though shared-constraint game formulation appeals naturally to resource allocation, to the best of our knowledge there is no work directly shared-constraint games as a vehicle for the abstract question of resource allocation. There is however work in the specific context of congestion in networks [1]. Secondly, our work does not attempt to provide an alternative to mechanisms, but instead considers the setting where the option of a mechanism is not available. In our setting, players wish to split a pie N -ways without communication with each other and without the intervention of an administrator while simultaneously moving to get pieces of it. This is perhaps an example of a somewhat extreme anarchy in resource allocation. Finally, the shared-constraint game admits to kinds of equilibria (GNE and VE) and with different consequences on efficiency. We want to know how they perform in the context of efficiency. This question has not been studied before.

The varied nature of the equilibria of the shared-constraint game has the potential to yield extremely high efficiency as well as extremely low efficiency and therein lies the possibility for similarities with other approaches. With utility functions of the 'perfectly competitive' kind, i.e. the utility obtained by a player is a function only of the allocation received by it, the VE is seen to be identical to the competitive equilibrium. We elaborate on this comparison in Section III-A. In Section III-B, we compare our approach for this same model with a typical mechanism-based approach.

## A. Relation to the competitive equilibrium

Consider a setting with one seller and N buyers and a single resource with capacity C . Buyers are similar to what we have called players in this work; they are characterized by utility functions ϕ i ( x ) = U i ( x i ) for all x and i ∈ N , which we assume satisfy Assumption 2.1. Imagine that each buyer sees a unit price p for the resource. Taking this price for granted, the buyer decides a quantity to buy so as to maximize his net payoff which is his utility less the payment he makes. Thus buyer i is faced with the following optimization problem.

```
\begin{matrix} B _ { i } & \max _ { x _ { i } } & U _ { i } ( x _ { i } ) - p x _ { i } \\ & \text{subject to } & x _ { i } \geq 0. \end{matrix}
```

The seller, on the other hand, seeks to maximize revenue. The sellers decision variables are the quantity sold to each buyer and he is constrained by the capacity of the resource. The seller also takes this price for granted in making his decision and is therefore faced with the following optimization problem.

```
\begin{cases} \underset { x } { \max } \quad p ( 1 ^ { T } x ) \\ \text{subject to } \begin{smallmatrix} 1 ^ { T } x \leq C, \\ x \geq 0. \end{smallmatrix} \end{cases}
```

Now imagine a societal objective of maximizing the aggregate utility of all buyers , which corresponds to the 4 following problem.

```
\text{unowing production}. \begin{matrix} \text{unowing production} \\ \text{SOC} & \max _ { x } & \sum _ { i \in \mathcal { N } } U _ { i } ( x _ { i } ) \\ \text{subject to} & \frac { 1 ^ { T } x \leq C, } { x \geq 0. } \end{matrix}
```

4 This is also the aggregate surplus of buyers and sellers. See [6] for more on this.

The setting described above is called the perfectly competitive setting. Notice that buyers and sellers simultaneously the quantities x , . . . , x 1 N . The 'price' is assumed to be exogenously given 5 and in addition there is a societal objective maximizing social welfare with the same decision variables. The first welfare theorem states that there exists a price p such that all the above optimzation problems are consistently solved. i.e. there exists a price p and an allocation x so that x i ∈ SOL(B ) i , for all i ∈ N , x ∈ SOL(S) and x ∈ SOL(SOC) . The evidence for this lies in the fact that the KKT conditions of the problem (SOC) which say that x solves R

(SOC) if there exists a λ ∈ such that

$$0 & \leq x _ { i } \perp - \nabla _ { i } U _ { i } ( x _ { i } ) + \lambda \geq 0, \\ 0 & \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0, \quad \forall \ i \in \mathcal { N },$$

are identical to the KKT conditions of (B 1 ) , . . . , (B N ) and (S) taken together with p = λ . This x is called the competitive equilibrium 6 , and the first welfare theorem states that the competitive equilibrium is efficient.

Now consider a shared constraint game with these buyers as players. Player i solves the problem

$$\begin{cases} A _ { i } ( x ^ { - i } ) & \max _ { x _ { i } } & U _ { i } ( x _ { i } ) \\ & \text{subject to} \quad \begin{matrix} 1 ^ { T } x \leq C, \\ x _ { i } \geq 0. \end{matrix} \end{cases}$$

Consider the solution concept of the VE. The allocation x is a VE for this game if and only if there exists λ such that

$$0 & \leq x _ { i } \perp - \nabla U _ { i } ( x _ { i } ) + \lambda \geq 0, \\ 0 & \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0, \quad \forall \ i \in \mathcal { N }.$$

Herein lies the connection between the competitive equilibrium and our model. For utility functions of the kind considered in perfectly competitive settings, the solution concept of the VE provides an allocation identical to that of a competitive equilibrium and is thereby efficient. Thus one may say that at a VE, players demand resources as if they were sold by a seller with a fixed price.

## B. Relation to mechanism design

Resource allocation through a shared-constraint game is different from that through the use of mechanisms. To clarify this difference we compare our approach with the approach of Johari [6], [7], which may be taken to be a canonical mechanism-based approach to resource allocation.

Example III.1. Johari considers the utility functions from the perfectly competitive setting ϕ i ( x ) = U i ( x i ) for all x . Every player submits a bid , or willingness to pay to a system administrator. Let the bids of the players be w , . . . , w 1 N where each w i ∈ [0 , ∞ ) . The system administrator aggregates these bids and allocates a portion of the resource according to an allocation rule. For e.g., Johari uses the proportional allocation rule wherein player i gets a portion x i

He is charged a payment w i . The price for a unit of the resource is ∑ j ∈N w /C j . When players are price taking they choose their bids taking p = ∑ j ∈N w /C j as constant and receive a quantity x i = w /p i . It is easy to show that this is allocation of the competitive equilibrium [9].

$$x _ { i } = \frac { w _ { i } } { \sum _ { j \in \mathcal { N } } w _ { j } } C. \\ \text{or a unit of the resource} \cdot \dots \, u _ { i } / C \text{ as constant} \, a$$

5 Akin to Adam Smith's Invisible Hand

6 Oftentimes the tuple x, p is called the competitive equilibrium

When players are price-anticipating, i.e. they strategically anticipate the influence of their bids and their opponent's bids on the price, their interaction can be modelled as a game.

$$\underset { \substack { J _ { i } ( w ^ { - i } ) \max \, \sum _ { w _ { i } } U _ { i } \left ( \frac { w _ { i } } { \sum _ { j \in \mathcal { N } } w _ { j } } C \right ) - w _ { i } } { \text{subject to } } } }$$

Let w ∗ = ( w , . . . , w ∗ 1 ∗ N ) be the (unique) Nash equilibrium of this game and let x ∗ = w ∗ C ∑ j ∈N w ∗ j . The worst case efficiency of the proportional allocation mechanism is the ratio

$$\rho = \inf _ { \Phi \in \mathcal { F } } \frac { \Theta ( x ^ { * } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

It was shown in [6] that this ratio is 3 4 / .

Observe that the use of a mechanism effectively alters the game. The strategies of the players are now their bids, the feasibility of the allocation, which in a competitive equilibrium is determined by the seller is now in the hands of the administrator who aggregates these bids. Furthermore, the efficiency claimed holds only for the particular mechanism used.

In comparison, we directly consider the generalized Nash game over the space of allocations. As shown in Section III-A, the VE for a game with these objective functions has (worst case) efficiency one. /square

## IV. WORST CASE EFFICIENCY

In this section we derive the worst case efficiencies of the solution concepts of the GNE and the VE over the class of utility functions F .

In the case of the GNE as well as the VE, we show that the worst case efficiency is achieved for the class of linear objective functions L . The worst case efficiency is then calculated constructively. This part of the analysis that uses estimation with linear objective functions follows lines similar to those in [7]. In particular, we require the following lemma, which is similar to the one used in [7].

Lemma 4.1: Suppose Assumption 2.1 holds. Let Φ ∈ F and let x ∗ a solution of (SYS). For every x ∈ C , we have

$$\frac { \Theta ( x ) } { \Theta ( x ^ { * } ) } \geq \frac { \nabla \Theta ( x ) ^ { T } x } { \nabla \Theta ( x ) ^ { T } x ^ { \ell } },$$

where x /lscript solves the problem (SYS) linearized at x , (SYS /lscript ( x ) ):

$$\begin{matrix} \text{SYS} ^ { \ell } ( x ) & \max _ { z } & \nabla \Theta ( x ) ^ { T } z \\ & \text{subject to } & z \in \mathbb { C }. \end{matrix}$$

The proof is in the Appendix.

## A. Worst case efficiency of the VE

Suppose we allow Φ to be any function in F , i.e., ϕ , . . . , ϕ 1 N are utility functions satisfying Assumption 2.1. In this section we ask the following question: what is the worst possible efficiency that the GNE and the VE can yield when Φ varies over the class F ? In other words, what are the ratios ϑ and ρ ? We prove that the worst case efficiency of the VE over is in fact zero, i.e. ϑ = 0 . It follows that ρ = 0 .

Our argument proceeds by characterizing ϑ . Theorem 4.3 shows that the worst case efficiency of the VE over F in fact the same as the worst case efficiency over L . To prove this, let us set up some notation. For arbitrary ¯ x ∈ C and Φ ∈ F , define the linearized functions ϕ , i ¯ x i ∈ N and Θ ¯ x as

$$\mathcal { F } \text{ in fact the same as the worst case efficiency over $\mathcal{L}$. To prove this, let us set up some notatio} \\ \text{ry } \bar { x } \in \mathbb { C } \text{ and } \Phi \in \mathcal { F }, \text{ define the linearized functions } \widetilde { \varphi } _ { i } ^ { \widetilde { x } }, i \in \mathcal { N } \text{ and } \widetilde { \Theta } ^ { \bar { x } } ( x ) = \nabla \Theta ( \bar { x } ) ^ { T } x = \sum _ { j \in \mathcal { N } } \widetilde { \varphi } _ { j } ^ { \bar { x } } ( x ).$$

Clearly the utility functions ˜ Φ ¯ x := ( ˜ ϕ , . . . , ϕ ¯ x 1 ¯ x N ) lie in the class L . Let ˜ F ¯ x denote the mapping

Observe that

$$( \widetilde { \varphi } _ { 1 } ^ { \widetilde { x } }, \dots, \widetilde { \varphi } _ { N } ^ { \widetilde { x } } ) \, \text{lie in the class $\mathcal{L}$. Let } \, \hat { I } \\ \widetilde { F } ^ { \widetilde { x } } ( x ) = - \, \begin{pmatrix} \nabla _ { 1 } \widetilde { \varphi } _ { 1 } ^ { \widetilde { x } } ( x ) \\ \vdots \\ \nabla _ { N } \widetilde { \varphi } _ { N } ^ { \widetilde { x } } ( x ) \end{pmatrix}. \\ \Big / \, \nabla _ { 1 } \varphi _ { 1 } ( \bar { x } ) \, \Big.$$

This also shows that every VE of a game with Φ ∈ F is a VE of some game with linear objectives.

$$F ^ { x } ( x ) = - \left \lfloor \underset { N \varphi _ { N } ( \bar { x } ) } { \vdots } \right \rfloor. \\ \widetilde { F } ^ { \bar { x } } ( x ) = - \left ( \underset { N \varphi _ { N } ( \bar { x } ) } { \nabla _ { 1 } \varphi _ { 1 } ( \bar { x } ) } \right \rfloor = F ( \bar { x } ) \quad \forall x. \\ \text{VE of a game with $\Phi \in \mathcal{F}$ is a VE of some game wit}$$

Lemma 4.2: Let Φ ∈ F . Then

Proof : Since ¯ x is a VE for objective functions Φ ,

$$\Lambda \quad \ V E ( \Phi ) & \subseteq \bigcup _ { x \in V E ( \Phi ) } V E ( \widetilde { \Phi } ^ { x } ). \\ \text{ve functions } \Phi,$$

$$F ( \bar { x } ) ^ { T } ( y - \bar { x } ) \geq 0 \quad \forall \ y \in \mathbb { C } \implies \widetilde { F } ^ { \bar { x } } ( \bar { x } ) ^ { T } ( y - \bar { x } ) \geq 0 \quad \forall \ y \in \mathbb { C }. \\ \text{rm implies } \bar { x } \in V E ( \widetilde { \Phi } ^ { \bar { x } } ).$$

Following the central result of this section. We show that for the worst case efficiency of the VE over the class F , ϑ , it suffices to look at the class of linear objective functions, L . The proof is in the appendix. Theorem 4.3: Suppose Assumption 2.1 holds. Then

This in turn implies ¯ x ∈ VE(Φ ) ˜ ¯ x .

$$\underline { \vartheta } = \inf _ { \bar { x } \in \mathbb { V E } ( \Phi ), \, \Phi \in \mathcal { F } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } = \inf _ { \bar { x } \in \mathbb { V E } ( \Phi ), \, \Phi \in \mathcal { L } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

The above result does not provide us the value of ϑ but only a characterization of it. We now show that ϑ = 0 through an example.

Example IV.2. Consider a game with objective functions ϕ i ( x ) = d T i x , where d i = ( d , . . . , d 1 i N i ) ∈ R N such that ∇ Θ = ∑ d i ≥ 0 . Furthermore, assume that d i i &gt; 0 for all i ∈ N . It is easy to see this collection of utility functions Φ satisfies Assumption 2.1.

Let c i = d i i and c := ( c 1 , . . . , c N ) T = F x ( ) , for each x . The set of VEs of this game, VE( ) c is the set of x for which there exists λ such that

$$0 & \leq x \perp - c + \lambda 1 \geq 0 \\ 0 & \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0$$

Since c &gt; 0 , observe that any λ satisfying these equilibrium conditions must be strictly positive and that 1 T x = C must hold for any VE x .

We construct values for d , . . . , d 1 N so that there exists a VE whose worst case efficiency is arbitrarily close to zero. Let ε ∈ (0 1) , and let

/negationslash

It follows that c = ( ε, . . . , ε, 2 ) ε and d = ∑ i ∈N d i = ( ε + 1 , ε, . . . , ε, 2 ) ε . It is easy to check that x ∗ := (0 , . . . , 0 , C ) is a VE (the equilibrium conditions are satisfied for λ = 2 ε ). Since ε + 1 &gt; 2 /epsilon1 , the optimal

$$\text{et } \varepsilon \in ( 0, 1 ) \text{ and let } \\ d _ { i } ^ { j } \coloneqq \begin{cases} 0, & \forall \ j \neq i, \\ \varepsilon, & j = i. \end{cases} \forall i \in \mathcal { N } \{ N \}, \quad d _ { N } ^ { j } \coloneqq \begin{cases} 1 & j = 1, \\ 0 & \forall \ j \not \in \{ N, 1 \}, \\ 2 \varepsilon & j = N. \end{cases} \\ \text{s that } c = ( \varepsilon, \dots, \varepsilon, 2 \varepsilon ) \text{ and } d = \sum _ { i \in \mathcal { N } } d _ { i } = ( \varepsilon + 1, \varepsilon, \dots, \varepsilon, 2 \varepsilon ). \text{ It is easy to check it} \\, C ) \text{ is a VE (the equilibrium conditions are satisfied for } \lambda = 2 \varepsilon ). \text{ Since } \varepsilon + 1 > 2 \epsilon, \text{th}$$

value of (SYS) is C ε ( +1) . The worst case efficiency of the VE is bounded above by the efficiency of x ∗ . Therefore,

$$\underline { \vartheta } \leq \frac { c ^ { T } x ^ { * } } { \max _ { z \in \mathbb { C } } d ^ { T } z } = \frac { 2 C \varepsilon } { C ( \varepsilon + 1 ) } = \frac { 2 \varepsilon } { \varepsilon + 1 }.$$

Letting ε decrease to zero reveals that the worst case efficiency ϑ = 0 , implying that the VE can be arbitrarily inefficient. Letting ε approach one shows that efficiencies arbitrarily close to unity are also achievable in the class F . /square

Summarizing the above example we have the following result for the worst case efficiency of the VE.

Theorem 4.4: The worst case efficiency of the VE (and the GNE) over the class F is zero. This bound is tight in the sense that for any ε ∈ (0 1] , , there exists a game with objective functions Φ in F such that a VE (and hence a GNE) of this game has efficiency ε .

Proof : We only need to prove the tightness. That efficiency of ε for any ε ∈ (0 1) , are achieved is demonstrated in the example above. Section III-A showed that in the setting of perfect competition, the VE coincides with the competitive equilibrium and is therefore efficient. Thus efficiency ε = 1 is also achievable.

## V. BEST CASE EFFICIENCY

In this section we present the best case analysis of the efficiency of the GNE and the VE. Although Section III-A demonstrates that the best case efficiency of the VE and the GNE is unity, we go a step further in this section and characterize the class of games for which every VE is efficient. i.e., in this case, the best and the worst case efficiency of the VE is unity. This class is large and it includes in it the perfectly competitive setting. Then, restricting ourselves to this class we determine the worst case efficiency of the GNE over this class. We find that while the VE is efficient for every game in this class, the GNE can be arbitrarily inefficient.

For the VE to be efficient, it has to be optimal for the problem (SYS). To find a sufficient condition for the VE to solve (SYS), let us first answer a related question: is there an optimization problem that the VE solves? By this we seek another optimization problem whose optimality conditions are the same as the equilibrium conditions of the VE, whereby solving the two is equivalent. Fortunately the answer to this is rather simple. The VE is the solution of VI( C , F ). If there exists a concave differentiable function f : R N → R such that

$$- \, \nabla f ( x ) = F ( x ) \quad \forall \ x \in \mathbb { R } ^ { N },$$

then VI( C , F ) is equivalent to the VI( C , -∇ f ) which, by the convexity of C is equivalent to the optimization problem

One way of interpreting (4) is that it asks for F to be integrable and for -f to be its integrand. It is well known that such a function f exists if and only if the Jacobian ∇ F x ( ) is symmetric [23].

Now, suppose such a function does exist. Then since -∇ f ( x ) = F x ( ) holds for all x , we must have for each i

$$\nabla _ { i } \left [ f ( x ) - \varphi _ { i } ( x ) \right ] & = 0 \\ \text{i.e.,} \quad f ( x ) - \varphi _ { i } ( x ) & = \eta _ { i } ( x ^ { - i } ),$$

for some η i which is a function of x -i and for all i ∈ N . Using this, one may now ask the original question. For what objective functions Φ is f ( x ) = Θ( x ) = ∑ j ∈N ϕ j ( x ) ? The following theorem provides us such a characterization.

$$\intertext { e u n c o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o n s o } & \varphi _ { i } ( x ) = \frac { \sum _ { j = 1 } ^ { N } \eta _ { j } ( x ^ { - j } ) } { N - 1 } - \eta _ { i } ( x ^ { - i } ), & & ( 6 )$$

Theorem 5.1: Suppose Assumption 2.1 holds. The identity -∇ Θ = F holds if and only if there exist continuously differentiable functions η i of x -i for each i ∈ N , such that the utility functions are given by for every i ∈ N . Proof : ' = ⇒ ' Let -∇ Θ = F . In particular, we have, for each i ∈ N , and for all x , ∇ i Θ( ) = x ∇ i ϕ i ( x . ) Recall from Assumption 2.1 that Θ is concave. Therefore (5) gives that for each i ∈ N ,

$$\Theta ( x ) - \varphi _ { i } ( x ) = \eta _ { i } ( x ^ { - i } ),$$

for some η i which is a function of x -i . Since ϕ i and Θ are continuously differentiable, it follows that η i is continuously differentiable. Summing (7) over i and using that Θ = ∑ ϕ i , gives

Now substituting for Θ from (8) in (7) gives the result desired in (6).

$$\text{ming,\/\/\/overview\/} \, \forall \, \imath \, \underset { \mu } { \nu } \, \text{and} \, \underset { \mu } { \nu } \, - \, \nearrow \, \varphi _ { i }, \text{gives} \\ \Theta ( x ) = \frac { \sum _ { i = 1 } ^ { N } \eta _ { i } ( x ^ { - i } ) } { N - 1 }. \\ \} ) \, \text{in} \, ( 7 ) \, \text{gives the result desired in} \, ( 6 ).$$

' ⇐ = ' Suppose (6) holds for some continuously differentiable functions η , . . . , η 1 N . Summing (6) over i gives (8). Then for each i ∈ N ,

$$\i i \in \mathcal { N } \,, \\ \nabla _ { i } \varphi _ { i } ( x ) = \nabla _ { i } \left ( \frac { \sum _ { j = 1 } ^ { N } \eta _ { j } ( x ^ { - j } ) } { N - 1 } \right ) = \nabla _ { i } \Theta ( x ). \\ \nu$$

In other words, -∇ Θ = F .

Theorem 5.1 shows that for a class of objective functions, the worst and best case efficiency of the VE is unity.

Theorem 5.2: Suppose Assumption 2.1 holds. Then the best case efficiencies of the VE and GNE are unity. i.e. ¯ = ¯ = 1 ρ ϑ .

Remarkably, the class given by (6) does not depend on C . i.e. if ϕ , . . . , ϕ 1 N are of the form given by (6), then the VI( V, F ) is equivalent to VI ( V, -∇ Θ) for any closed convex set V . Note also that from (5),

/negationslash

In general the right hand side may not independent of x i , and the above equation may not hold. Thus, not every game has VEs equivalent to optimization problems.

$$\text{valent to $v_{1}(v,-v\chi)$ for any closea convex set $v$. note} \\ \eta _ { i } ( x ^ { - i } ) = \sum _ { j \in \mathcal { N } } \varphi _ { j } ( x ) - \varphi _ { i } ( x ) = \sum _ { j \neq i } \varphi _ { j } ( x ). \\ \text{side max not independent of $x$}. \text{ and the above equation}$$

We now revisit the relationship of the VE with the competitive equilibrium in the light of this result.

Example V.3. In Section III-A, we considered a perfectly competitive setting and then we considered a shared-constraint game analogous to it. The game considered therein was with ϕ i ( x ) = U i ( x i ) for all i . For this game, we indeed have the functions η i given by

/negationslash

$$\eta _ { i } ( x ^ { - i } ) = \sum _ { j \neq i } U _ { j } ( x _ { j } ),$$

which is independent of x i .

$$& \text{given by} \\ & _ { h _ { i } } ( x ^ { - i } ) = \sum _ { j \neq i } U _ { j } ( x _ { j } ), & & \text{$\Box$}$$

Notice that the statement ' -∇ Θ = F ' characterized by Theorem 5.1 is somewhat stronger than the statement 'every VE is efficient'. ' -∇ Θ = F ' provides the equivalence between the VIs characterizing the VE and

solutions of (SYS). This equivalence implies the equality of the solution sets of the said VIs, though it is not necessary to conclude the equality of these sets. Following is an example of a game where objectives do not satisfy (6), every VE is efficient.

Example V.4. Consider ϕ i ( x ) = x g i ( 1 T x ) whereby Θ( ) x = 1 T xg ( 1 T x ) and assume that g ( 1 T x ) + x g i ′ ( 1 T x ) &gt; 0 and ∇ Θ( ) = x 1 ( g ( 1 T x ) + ( 1 T x g ) ′ ( 1 T x )) ≥ 0 for all x . It is easy to check that this set of functions does not satisfy (6). But, as we show below, every VE of this game is efficient.

Let us first consider the system problem (SYS). Since ∇ Θ ≥ 0 , the maximum in (SYS) is attained at 1 T x = C , whereby the optimal value of (SYS) is Cg C ( ) . Now consider the shared-constraint game formed from these utilities. Thus x is a VE of this game if and only if

$$0 & \leq x \perp - g ( \mathbf 1 ^ { T } x ) \mathbf 1 - x g ^ { \prime } ( \mathbf 1 ^ { T } x ) + \lambda \mathbf 1 \geq 0 \\ 0 & \leq \lambda \perp C - \mathbf 1 ^ { T } x \geq 0,$$

for some λ ∈ R . Since g ( 1 T x ) 1 + xg ′ ( 1 T x ) &gt; 0 , λ = 0 does not satisfy these equations. Consequently, for each VE x , the equality 1 T x = C must hold. So for any VE x , Θ( ) = x 1 T xg ( 1 T x ) = Cg C ( ) , which is the optimal value of (SYS). /square

Also note that the requirement ' -∇ Θ = F ' is, strictly speaking, not the same as ' VI( C , F ) ≡ VI( C , -∇ Θ) ', because the solution set of a VI is invariant under multiplication of the function by a positive constant. Specifically, if - ∇ c Θ = F , where c &gt; 0 is a real number, then VI ( C , F ) is equivalent to VI ( C , F ) . Therefore if F = -∇ f and f = Θ c , we get using (5),

$$c \Theta ( x ) = \varphi _ { i } ( x ) + \eta _ { i } ( x ^ { - i } ).$$

Arguing as in Theorem 5.1, we get

$$\text{img as in neorem } \mathfrak { I }, \, \text{we get} \\ \Theta ( x ) & = \frac { \sum _ { j \in \mathcal { N } } \eta _ { j } ( x ^ { - j } ) } { c N - 1 } \quad \text{and} \quad \varphi _ { i } ( x ) = \frac { \sum _ { j \in \mathcal { N } } \eta _ { j } ( x ^ { - j } ) } { c N - 1 } - \eta _ { i } ( x ^ { - i } ) \quad \forall \ x. \\ \text{nall we note that } \mathfrak { S } \, \text{has also anneared nrevious} \, \text{in literature in a different context. Slade in } \mathbb { R }$$

Finally, we note that (5) has also appeared previously in literature in a different context. Slade in [28] has derived (5) as a means of giving sufficient conditions for the stationarity conditions of an unconstrained Nash equilibrium to be equivalent to an optimization problem.

We will invoke this class of games in the following section. For reference, denote

$$\mathcal { F } ^ { \prime } & = \{ \Phi \ | \ \Phi \in \mathcal { F } \ \text{and} \ \exists \ \text{functions} \ \eta _ { i } \ \text{of} \ x ^ { - i }, i \in \mathcal { N }, \ \text{so that} \ \varphi _ { 1 }, \dots, \varphi _ { N } \ \text{are given by} \ ( 6 ) \} \\ \mathcal { L } ^ { \prime } & = \{ \Phi \ | \ \Phi \in \mathcal { L } \ \text{and} \ \exists \ \text{functions} \ \eta _ { i } \ \text{of} \ x ^ { - i }, i \in \mathcal { N }, \ \text{so that} \ \varphi _ { 1 }, \dots, \varphi _ { N } \ \text{are given by} \ ( 6 ) \}.$$

Denote the efficiencies of the GNE over the class F ′ by

$$\bar { \rho } ^ { \prime } \coloneqq \sup _ { x \in \mathbb { G N E } ( \Phi ), \, \Phi \in \mathcal { F } ^ { \prime } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \ \text{ and } \ \underline { \rho } ^ { \prime } \coloneqq \inf _ { x \in \mathbb { G N E } ( \Phi ), \, \Phi \in \mathcal { F } ^ { \prime } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \quad \text{ (10)}$$

Clearly, ¯ = 1 ρ ′ and ρ ′ ≥ ρ . The best and worst case efficiencies of the VE,

$$\bar { \vartheta } ^ { \prime } \coloneqq \sup _ { x \in V E ( \Phi ), \, \Phi \in \mathcal { F } ^ { \prime } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \, \Theta ( z ) } \ \text{ and } \ \underline { \vartheta } ^ { \prime } \coloneqq \inf _ { x \in V E ( \Phi ), \, \Phi \in \mathcal { F } ^ { \prime } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \, \Theta ( z ) }$$

are both unity.

In the following section the worst case efficiency of the GNE to the class of functions F ′ is addressed. i.e. we calculate ratio ρ ′ . We find that this ratio is in fact zero, indicating that the GNE can be arbitrarily inefficient even while the VE is efficient.

## A. Worst case efficiency of the GNE when the VE is efficient

Recall the linearized objective functions from Section IV-A ˜ Φ ¯ x where ¯ x ∈ C is the point of linearization. We first show that a result similar to Theorem 4.3 holds, thanks to which ρ ′ is the worst case efficiency of GNE over the class L ′ .

Theorem 5.3: Suppose Assumption 2.1 holds. Then the ratio ρ ′ defined in (10) is given by

$$\underline { \rho } ^ { \prime } = \inf _ { x \in \text{GNE} ( \Phi ), \, \Phi \in \mathcal { L } ^ { \prime } } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

Once again we obtain that the linear case is where the worst case of efficiency is achieved. We now show through an example that this efficiency ρ ′ is indeed zero.

Example V.5. Consider a game with objective functions ϕ i ( x ) = d T i x for each i ∈ N , where d i = ( d , . . . , d 1 i N i ) ∈ R N such that d := ∇ Θ = ∑ d i ≥ 0 and d i i &gt; 0 for all i ∈ N . It is easy to see this collection of objective function Φ satisfies Assumption 2.1. Let c i = d i i and

Furthermore we assume

$$\mathrm e \, \text{function } \Phi \, \text{ satisfies } \text{Assumption } 2. 1. \, \text{Let } c _ { i } = d _ { i } ^ { i } \text{ and } \\ c \coloneqq \begin{pmatrix} c _ { 1 } \\ \vdots \\ c _ { N } \end{pmatrix} = \begin{pmatrix} \nabla _ { 1 } \varphi _ { 1 } ( x ) \\ \vdots \\ \nabla _ { N } \varphi _ { N } ( x ) \end{pmatrix} = F ( x ), \quad \forall \, x. \\ \mathrm e \, \text{ne} \, \quad \nabla \Theta = \nabla \, d _ { i } = c _ { i }.$$

/negationslash

$$\nabla \Theta = \sum d _ { i } = c, \\ _ { r } \text{ denote the set of GNE}$$

that is ∑ j = i d j i = 0 for all i. Let GNE( ) c denote the set of GNEs of this game. Recall that x is a GNE if and only if there exists Λ = ( λ , . . . , λ 1 N ) T such that

$$0 & \leq x \perp - c + \Lambda \geq 0, \\ 0 & \leq \Lambda \perp \mathbf 1 ( C - \mathbf 1 ^ { T } x ) \geq 0.$$

Observe that any Λ satisfying these equilibrium conditions must be strictly positive in all components because c is assumed to be so. This implies that 1 T x = C must hold for any GNE x . In fact, 1 T x = C along with x ≥ 0 is also sufficient for x to be a GNE; the equilibrium conditions are then satisfied by Λ = c . So we get

$$\text{GNE} ( c ) = \{ x \ | \ \mathbf 1 ^ { T } x = C, \ x \geq 0 \}.$$

Now let 1 &gt; ε &gt; 0 and take c = c ∗ := (1 , ε, ε, . . . , ε ) . The point x ∗ := (0 , . . . , 0 , C ) is a GNE for this c . The worst case efficiency of the GNE no greater than the efficiency of the GNE x ∗ for the game with c = c ∗ . Therefore,

$$\underline { \rho } ^ { \prime } \leq \frac { c _ { * } ^ { T } x ^ { * } } { \max _ { z \in \mathbb { C } } c _ { * } ^ { T } z } = \frac { C \varepsilon } { C } = \varepsilon. \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
. \quad. \quad. \quad.$$

Evidently, since ε may take any value in (0 1) , , the worst case efficiency ρ ′ = 0 . In other words, the GNE can be arbitrarily inefficient. /square

Combining the above example with the best case efficiency of the GNE (i.e. ε = 1 ), we get our final result. Theorem 5.4: Suppose Assumption 2.1 holds. The worst case efficiencies of the GNE over the class F and over class F ′ are both zero. This bound is tight, in the sense that for every ε ∈ (0 1] , there is a game satisfying Assumption 2.1 for which every VE is efficient but has a GNE that has efficiency ε .

This is a particularly surprising result for it clearly shows the disparity between the VE and GNE. Example V.5 also indicates the cause for loss of efficiency in the GNE. Games like these often admit a manifold of GNEs. In Example V.5, the set { x | x ≥ 0 , 1 T x = C } is this manifold. When the utility functions are linear, it is always possible to find a GNE that allocates zero quantity the player with the highest contribution to Θ (i.e. the player i with the largest ∇ i ϕ i ). One may also conclude that this, somewhat pathological property of the GNE, makes it unattractive as a solution concept for shared-constraint resource allocation games.

## VI. REMEDYING ZERO WORST CASE EFFICIENCY

In this section we discuss some ways by which the possibility of arbitrarily low efficiency in the case of the GNE and the VE can be remedied.

## A. Utility functions with bounded gradients

Looking back at Example V.5 we see that the limiting efficiency of zero is achieved as the gradient of Θ approaches the zero-vector. In the case of linear utilities, this corresponds to the possibility of constant zero utility. This is perhaps a pathological situation that does not occur in realistic settings. This observation also suggests a way for salvaging nonzero efficiency. Consider the following class of functions for 0 &lt; α &lt; β &lt; ∞ ,

$$\mathcal { F } ^ { [ \alpha, \beta ] } = \{ \Phi \ | \ \Phi \in \mathcal { F } \ \text{and} \ \beta 1 \geq \nabla \Theta ( x ) \geq \alpha 1 \quad \forall \ x \in \mathbb { C } \}.$$

Utility functions Φ belonging to this class have the gradients of their sum bounded above and below. Let Φ ∈ F . Recall Lemma 4.1, which showed that for any x ∈ C , the ratio Θ( ) x Θ( x ∗ ) , where x ∗ ∈ SOL(SYS) is was bounded below by the ratio ∇ Θ( ) x T x ∇ Θ( ) x T x /lscript where x /lscript solves (SYS /lscript ( x ) ). Now if Φ ∈ F [ α,β ] , then for any x ∈ C ,

$$\frac { \Theta ( x ) } { \Theta ( x ^ { * } ) } \geq \frac { \alpha { \mathbf 1 } ^ { T } x } { \beta { \mathbf 1 } ^ { T } x ^ { \ell } }.$$

Furthermore since Assumption 2.1 ensures that F x ( ) &gt; 0 whereby, for any GNE x , 1 T x = C . Likewise, for the problem (SYS /lscript ( x ) ) optimality of x /lscript implies 1 T x /lscript = C This immediately gives us that

$$\inf _ { x \in \text{GNE} ( \Phi ) } \frac { \Theta ( x ) } { \Theta ( x ^ { * } ) } \geq \frac { \alpha } { \beta }.$$

Since this holds for all Φ ∈ F [ α,β ] , the worst case efficiency of the GNE over this class is α β . It follows that the worst case efficiency of the VE over the class F [ α,β ] is greater than or equal to α β .

Example VI.6. Consider the following class of exponential utility functions.

$$\varphi _ { i } ( x ) = 1 - \exp ( - d _ { i } ^ { T } x ), \ \forall \ i \in \mathcal { N },$$

where for each i , the vector of coefficients d i = ( d , . . . , d 1 i N i ) is chosen from a compact set D ⊆ R N + and with d i i &gt; 0 . It follows that these utility functions satisfy Assumption 2.1. It is easy to see that the following bounds hold.

where α is given by

$$\intertext { g i v e n h v } \intertext { \alpha \sum d _ { i } \leq \nabla \Theta ( x ) } = \sum _ { i \in \mathcal { N } } d _ { i } \exp ( - d _ { i } ^ { T } x ) \leq \sum d _ { i }, \quad \forall \ x \in \mathbb { C }, \\ \intertext { g i v e n h v }$$

$$\alpha = \min _ { ( d, z ) \in D \times \mathbb { C } } \exp ( - d ^ { T } z ).$$

α is positive because D is compact. Thus this set of utility functions lie in F [ α, 1] . It follows that Θ( ) x Θ( x ∗ ) ≥ α, and that the worst case efficiency of the GNE for this class of games is at least α . /square

## B. Other notions of efficiency

The notion of what constitutes efficient allocations varies with the setting in question and need not always correspond to the allocation that maximizes the sum of the objective functions of players. This is particularly true when what players are maximizing are not merely their utilities but some modifications thereof. The system-level goal though, from the point of view of social welfare, remains the maximization of aggregate utility. As mentioned in Section III-B, mechanism design employs such a paradigm. The optimization problems that players solve are not of 'utility maximization' but instead of ' payoff maximization ', though the efficiency is benchmarked on the aggregate utility. And under this interpretation, greater efficiency may be obtained.

In this section, we study a particular kind of model that uses the above philosophy and provide a general principle for the VE to be efficient in this new sense. This model is adapted from and is a somewhat simplified version of the model in [1]. We first explain the model from [1]. Similar models are used in [12], [13], [19].

Example VI.7. The game consists of N players that attempt to access bandwidth over a general network with a set of links L . The subset of links used by player i are L i and the utility received by player i is U i ( x i ) for flow x i that it obtains. If x is the vector of typical flows of all players, the flows permitted by the network are those in the set { x | x ≥ 0 , A x ≤ C } where A is a | L | × N matrix whose element A [ /lscript, i ] is 1 if player i uses link /lscript and C is the | L | -vector of capacities the links. The network is however subject to delay, the cost of which is seen by a player for every link it uses. Specifically, each player faces a cost which is the sum of the costs on the links that it uses,

$$c ^ { i } ( x ) = \sum _ { \ell \in L _ { i } } c _ { \ell } ( \sum _ { j \colon \ell \in L _ { j } } x _ { j } ), \\ \intertext { \ell \text{ when that total flow on it is $4$} } \,.$$

where c /lscript ( ) t is the cost of using link /lscript when the total flow on it is t. Each player is thus faced with the following optimization problem.

$$\begin{cases} \text{AB} _ { i } ( x ^ { - i } ) & \max _ { x _ { i } } & \varphi _ { i } ( x ) \coloneqq U _ { i } ( x _ { i } ) - c ^ { i } ( x ) \\ \text{subject to } \quad \text{$\text{A}_{x} \leq C$,} \\ x _ { i } \geq 0. \end{cases}$$

The game formed from these problems is clearly a shared-constraint game, more general than the game we have considered. Our game can be thought of a special case of this game with one link, i.e. | L | = 1 .

The system-level problem defined 7 in [1] however is not to maximize the sum of the objectives ∑ ϕ i , but instead to maximize the aggregate utility less the total delay over the network. Specifically, an efficient allocation in this case is the solution of following problem.

$$\underset { x \geq 0. } { \overset { \text{SYS-AB} \max } { \max } } \sum _ { i \in \mathcal { N } } U _ { i } ( x _ { i } ) - \sum _ { \ell \in L } c _ { \ell } ( \sum _ { j \cdot \ell \in L _ { j } } x _ { j } ) \\ \text{subject to } \underset { x \geq 0. } { \text{A} } x \leq C,$$

Notice that while the delay on a particular link /lscript appears in the optimization problem of possibly multiple players, it is accounted for only once in (SYS-AB). The motivation for this is that, while each player that experiences the delay on /lscript suffers a cost c /lscript due to it, the system goal is to merely minimize total delay over all links (not players), in addition to maximizing aggregate utility. In particular, in (SYS-AB) the delay on link /lscript is not scaled by the number of players using it. Under the assumption that c /lscript approaches infinity as the link /lscript gets congested, it is proved in [1] that the GNE of this game is efficient. The GNE and the VE coincide in this case because they are in the interior of the feasible region [10]. /square

7 The constraint ' A x ≤ C ' is not used in the system problem in [1]. This constraint is irrelevant in their case since the costs approach infinity as this constraint becomes active.

We derive a general principle within our setting for a result such as that in [1] to hold. We stick to the solution concept of the VE and show that for utility functions taken from the class F ′ , the VE of the shared-constraint game is optimal for the system problem analogous to the one above.

Consider the game where player i derives utility U i ( x ) from an allocation x but he suffers a cost τ ( x ) , which we assume is a convex function of x . Player i 's objective then is to solve

$$\boxed { A _ { i } ( x ^ { - i } ) \max _ { x _ { i } } \ U _ { i } ( x ) - \tau ( x ) } _ { \text{subject to } } \sum _ { j \in \mathcal { N } } x _ { j } \leq C, \\ x \geq 0.$$

(SYS) problem is changed to the following.

$$\begin{array} { l l } \cos \text{$p$} \text{plowish is change} \colon \, \overbrace { \underset { x } { S Y S } } & \max _ { x } \quad \sum _ { j \in \mathcal { N } } U _ { j } ( x ) - \tau ( x ) \\ \text{subject to} \quad \sum _ { j \in \mathcal { N } } x _ { j } \leq C, \\ x \geq 0. \end{array}$$

Let U be the tuple ( U , . . . , U 1 N ) and let F be as before,

We now ask the question: for what utility functions U does the VE of the shared-constraint game formed from (A 1 ) , . . . , ( A N ) solve (SYS)? Similar to the argument in Section V, suppose there exists a concave continuously differentiable function f such that -∇ f = F . It follows that there exist for each i continuously differentiable functions η i of x -i such that

$$& \text{and let $F$ be as before}, \\ & \text{$F=-\binom{n}{n}U_{1}-\nabla_{1}\tau}{\vdots\nabla_{N}U_{N}-\nabla_{N}\tau}$}. \\ & \text{ utility functions $U$ does the VE of} \\ & \text{Similar to the argument in Action}.$$

$$f ( x ) = U _ { i } ( x ) - \tau ( x ) + \eta _ { i } ( x ^ { - i } ) \quad \forall \ x.$$

For the VE to solve (SYS), we need that f = Θ , where Θ now is

$$\coloneqq \varnothing, \, \text{where $\varpi$ now is} \\ \Theta = \sum _ { j \in \mathcal { N } } U _ { j } - \tau. \\ \text{mntion $2 1$ Substitution}$$

Θ is a concave function if U satisfies Assumption 2.1. Substituting f = Θ above gives

$$\cup \text{sauishes Assumption 2.1. } \text{$\chi$} \text{sauosity $J = \chi$} \text{adov} \\ \sum _ { j \in \mathcal { N } } U _ { j } ( x ) = U _ { i } ( x ) + \eta ( x ^ { - i } ), \quad \forall \ x, \\ \text{is the same as $7\wedge$ but for functions $UT$ instead of $d$}$$

for all i . The above equation is the same as (7), but for functions U instead of Φ . It follows that for each i , U i must be of the form given by (6), and in particular must belong to class F ′ . This is summarized in the following result.

Theorem 6.1: Suppose U satisfies Assumption 2.1 and consider the game formed from (A ) 1 , . . . , (A N ) described above. The identity -∇ Θ = F holds if and only if U belongs to the class F ′ . It is easy to see that the game of Example VI.7 follows as a special of this theorem.

## C. Reserve price

So far we have assumed that there is no administrative intervention in the allocation of the resources. A consequence of this is the possibility that, at equilibrium, 'non-serious' players with low marginal utility get large portions of the resource. An apt instance of this situation is the game in Example V.5, where at equilibrium, the player with the highest marginal utility amongst all players gets no portion of the resource

while the player with lowest marginal utility gets all of it. The system problem, on the other hand, allocates all the resource to player with highest marginal utility. Since the lowest marginal utility could be arbitrarily small, the worst case efficiency is zero.

One way to mitigate this problem is to screen players so that, at equilibrium, only those players play the game who are 'sufficiently serious' about wanting the resource. We show here that this can be done with some, though minimal administrative intervention and that under certain assumptions, efficiency as high as unity is achievable. Underlying this approach, is the concept of a reserve price .

The idea of a reserve price or reservation price can be traced to Myerson's seminal work on optimal auction design for a single indivisible object in a Bayesian setting [20]. In this setting, a reserve price is set by the auctioneer or seller and revealed to all players with the rider that only those bids will be considered in the auction that are at least large as the reserve price. As a consequence, players whose valuations do not exceed the reserve price are eliminated from the auction. The seller risks keeping the object to himself in the event that the all players bid below this price but he also has a chance for higher revenue . 8

In the context of allocation of divisible resources that we are concerned with, the reserve price is typically implemented through the pricing formula or mechanism employed, as has been done, e.g., by Maheswaran and Bas ¸ar [15], [14]. In our setting of a shared-constraint game we do not have a pricing formula or a direct handle on the price. We impose the price through a cost or a toll. The administrator fixes a value π so that each player i that receives quantity x i is charged a cost πx i . This cost may be monetary and collected by an administrator or it may be a cost induced by a physical inconvenience such as delay which does not require imposition by an administrator. We do not concern ourselves with the manner of imposition of this cost, but only note that even in the case where an administrator imposes it, it can be imposed with minimal intervention. As a result of the reserve price, player i now solves the following optimization problem.

$$\begin{matrix} \frac { A _ { i } ( x ^ { - i } ) & \max _ { x _ { i } } & \varphi _ { i } ( x ) - \pi x _ { i } \\ \text{subject to } \sum _ { j \in \mathcal { N } } x _ { j } \leq C, \\ x _ { i } \geq 0. \end{matrix}$$

We benchmark efficiency with respect to the original system problem.

$$\begin{array} { c c c } \text{we evenmark efficiency with respect to use original system problem.} \\ \underset { x } { \sqrt { \text{SYS} } } \underset { x } { \max } \quad \sum _ { j \in \mathcal { N } } \varphi _ { j } ( x ) \\ \text{subject to } \underset { y \in \mathcal { N } } { \sum _ { j \in \mathcal { N } } x _ { j } } \leq C, \\ x \geq 0. \end{array}$$

/negationslash

/negationslash

If the reserve price is larger than the marginal utility of a player ˆ i , i.e. π &gt; c ˆ i , then it is optimal for ˆ i to ask for zero quantity. For the other players, the shared constraint is now the set

Consider utility functions Φ ∈ F ′ . The argument in Section V-A shows, it suffices to consider utility functions Φ ∈ L ′ to evaluate the worst case efficiency, so we restrict ourselves to linear utility functions. In particular, consider for each i , ϕ i ( x ) = d T i x for all x and d i i &gt; 0 . Notice that for any i , coefficients d j i , with j = i do not affect optimal choice of player i and the resulting equilibrium. For simplicity, we consider 'perfectly competitive' utility functions, i.e., d j i = 0 for j = i.

/negationslash

8 See [3], [22] for an analysis of the revenue-optimal reserve price in auctions.

$$\text{her players, the shared constraint is now the } \\ \left \{ x ^ { - \hat { i } } \, \Big | \, x ^ { - \hat { i } } \geq 0, \sum _ { j \neq \hat { i } } x _ { j } \leq C \right \}. \\ \text{

revenue-optimal reserve price in auctions.}$$

Effectively, player ˆ i is eliminated and we are left with a game similar to the original game, but amongst players N\ ˆ i . The imposition of a reserve price filters players with 'low interest' in the resource and retains only those players who gain utility at least π from a unit of the resource.

There is, of course, a possibility of overdoing this elimination by eliminating all players in the competition. Indeed, for a given c , one can always find a price π = π , ∗ where π ∗ &gt; max i c i so that for each player, it is optimal to demand zero, and no resource is allocated. i.e. the allocation (0 , . . . , 0) is the (unique) equilibrium. This is akin to the nonzero probability in the Bayesian single object auction, that the seller has to keep the item for itself with zero revenue. In that setting, one can counter possibility by arguing that the expected profit of the seller is positive for a certain price [22]. To rule out this possibility in our setting, we are compelled to assume that there is at least one player who is not eliminated. With this assumption, the imposition of a reserve price leads to improvement in efficiency. Indeed arbitrarily high efficiencies are achievable. We show this below.

Consider the GNE as a solution concept and assume that Φ ∈ L ′ is given by linear functions as above. In particular, let c be such that c 1 = max i c i = 1 and let the reserve price π be a number in (0 1) , . Let x be a GNE of this game. i.e., suppose there exists Λ = ( λ , . . . , λ 1 N ) such that

$$0 & \leq x \perp - c + \pi \mathbf 1 + \Lambda \geq 0 \\ 0 & \leq \Lambda \perp C - \mathbf 1 ^ { T } x \geq 0$$

Since π &lt; 1 = c 1 , at equilibrium, the Lagrange multiplier λ 1 for player 1 , has to be positive. The complementarity between λ 1 and ' C -1 T x ' now ensures that 1 T x = C holds for the GNE x . Therefore at least one component of x is positive. If x is a VE, i.e. a GNE with λ 1 = λ j for all j , those players i with c i = c 1 receive positive quantity, whereas the rest receive zero. If x is a GNE, denote by I the set of players with marginal utility at least π , i.e.,

$$\mathcal { I } = \{ i \in \mathcal { N } \ | c _ { i } \geq \pi \}, \quad \text{and let } \ c _ { \mathcal { I } } = ( c _ { i } ) _ { i \in \mathcal { I } }, \ \ x _ { \mathcal { I } } = ( x _ { i } ) _ { i \in \mathcal { I } },$$

then x I c , which is the tuple of x j so that c j &lt; π , is the tuple of |I c | zeroes. Consequently, ∑ j ∈I x j = C . Therefore for this game and a GNE x ,

$$\text{his game and a ONE } x, \\ \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } = \frac { c ^ { T } x } { \max _ { z \in \mathbb { C } } c ^ { T } z } = \frac { c ^ { T } _ { \mathcal { I } } x _ { \mathcal { I } } } { C } \geq \frac { \pi \sum _ { j \in \mathcal { I } } x _ { j } } { C } = \pi. \\ \text{ev of the ONE is at least } \pi \text{Wharac away } \mathbb { V } \text{ } \text{$\vec{v}$ is off} \text{siant}.$$

i.e. the efficiency of the GNE is at least π . Whereas every VE x is efficient:

$$\frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } = \frac { c ^ { T } x } { \max _ { z \in \mathbb { C } } c ^ { T } z } = \frac { c _ { 1 } \mathbf 1 ^ { T } x } { C } = 1.$$

This is true for for all c &gt; 0 such that max i c i = 1 when the reserve price π &lt; 1 . More generally, for any c &gt; 0 and a reserve price π , we have

$$\text{ve price $\pi$, we have} \\ \inf _ { x \in \text{GNE} ( c ) } \frac { \Theta ( x ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \quad \begin{cases} \geq \frac { \pi } { \max _ { i } c _ { i } } & \pi < \max _ { i } c _ { i }, \\ = 0 & \pi \geq \max _ { i } c _ { i }. \end{cases}$$

/negationslash

/negationslash

When max i c i = c 1 = 1 and π ∈ (0 1) , , note that π is a lower bound and the actual efficiency may in fact be greater than π . For e.g., consider a game where max j =1 c j &lt; 1 and 1 &gt; π &gt; max j =1 c j . For this game, all players other than player 1 are 'eliminated', i.e. they receive zero quantity at equilibrium. Therefore the efficiency of the GNE in this case is unity.

## VII. CONCLUSIONS

This work considered resource allocation through a shared-constraint game from the point of view of economic efficiency. This game is relevant in the setting where an auctioneer is not available for operationalizing a mechanism. We clarified the relationship of this game with other modes of allocating resources. Sharedconstraint games admit two kinds of equilibria, namely, the GNE and the VE. We considered a class of concave objective functions and found that the worst case efficiency over this class of both, the GNE and the VE, is zero. However we show that there is subclass for which the VE is always efficient but the GNE can be arbitrarily inefficient. This further corroborates the thesis put forth in [10] that the VE should be considered a refinement of the GNE. We then discussed remedies by which the worst case efficiency may be bounded away from zero. Specifically, we showed that utility functions with bounded gradients, alternative notions of efficiency and the imposition of a reserve price can mitigate the loss of efficiency.

## APPENDIX

## A. Proof of Lemma 4.1

Proof : Since Θ is concave, the following inequality holds:

$$\Theta ( \bar { x } ) \leq \Theta ( x ) + \n$$

Now consider the ratio Θ( ) x Θ( x ∗ ) . Adding and subtracting ∇ Θ( ) x T x in the numerator and using (11) with ¯ = x x ∗ , it follows that this ratio satisfies

$$\frac { \Theta ( x ) } { \Theta ( x ^ { * } ) }$$

By definition of x /lscript , ∇ Θ( ) x T x /lscript ≥ ∇ Θ( ) x T x , ∗ and since both these terms are positive, using this inequality in (12) gives

$$\frac { \Theta ( x ) } { \Theta ( x ^ { * } ) }$$

Now, from (11), taking ¯ = 0 x , we get

$$\Theta ( x ) - \nabla \Theta ( x ) ^ { T } x$$

which is nonnegative, by Assumption 2.1. Furthermore Assumption 2.1 also provides that ∇ Θ( ) x is nonnegative whereby ∇ Θ( ) x T x and ∇ Θ( ) x T x /lscript are both nonnegative. So therefore, dropping the nonnegative term ' Θ( ) x -∇ Θ( ) x T x ' from the numerator and denominator of (13) and recalling that ∇ Θ( ) x T x /lscript ≥ ∇ Θ( ) x T x , we obtain,

Θ( )

x

∇

Θ( )

x

T

x

Θ(

x

∗

)

∇

Θ( )

x

T

x

/lscript

≥

,

which is the desired result.

## B. Proof of Theorem 4.3

Proof : Lemma 4.1 shows that for Φ ∈ F and ¯ x ∈ VE(Φ) ,

$$\begin{array} {$$

So for any Φ ∈ F ,

Since this holds for any Φ ∈ F , we must have

$$\text{So for any } \Phi \in \mathcal { F }, \quad \inf _ { \tilde { x } \in V E ( \Phi ) } \frac { \Theta ( \tilde { x } ) } { \max _ { z \in C } \tilde { C } \Theta ( z ) } \geq \inf _ { \tilde { x } \in V E ( \Phi ) } \frac { \widetilde { \Theta } ^ { \tilde { x } } ( \tilde { x } ) } { \max _ { z \in C } \tilde { C } \Theta ^ { \tilde { x } } ( z ) } \\ \geq \inf _ { \tilde { x } \in V E ( \tilde { \Phi } ^ { \ast } ), z \in V E ( \Phi ) } \frac { \widetilde { \Theta } ^ { \tilde { x } } ( \tilde { x } ) } { \max _ { z \in C } \tilde { C } \Theta ^ { \tilde { x } } ( z ) }, \quad \text{by Lemma } 4. 2, \\ = \inf _ { \tilde { x } \in V E ( \tilde { \Phi } ^ { \ast } ), z \in V E ( \Phi ) } \frac { \sum _ { i \in \mathcal { N } } \widetilde { \varphi } ^ { \tilde { x } } _ { i } ( \tilde { x } ) } { \max _ { z \in C } \tilde { C } \sum _ { i \in \mathcal { N } } \widetilde { \varphi } ^ { \tilde { x } } _ { i } ( z ) }, \\ \geq \min _ { \tilde { x } \in V E ( \Phi ), \Phi \in \mathcal { L } } \frac { \Theta ( \tilde { x } ) } { \max _ { z \in C } \tilde { C } \Theta ( z ) }, \quad \text{since } \{ \tilde { \Phi } ^ { \tilde { x } } \colon x \in V E ( \Phi ) \} \subseteq \mathcal { L }. \\ \text{Since this holds for any } \Phi \in \mathcal { F }, \, \text{we must have } \quad \inf _ { \tilde { x } \in V E ( \partial ) \ \partial \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \ \tilde { \omega } \$$

$$\inf _ { \bar { x } \in \mathbb { V E } ( \Phi ), \, \Phi \in \mathcal { F } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \geq \inf _ { \bar { x } \in \mathbb { V E } ( \Phi ), \, \Phi \in \mathcal { L } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

But since L ⊆ F , we must also have

$$\inf _ { \bar { x } \in \mathbb { V } ( \Phi ), \, \Phi \in \mathcal { F } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \leq \inf _ { \bar { x } \in \mathbb { V } ( \Phi ), \, \Phi \in \mathcal { L } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

The result follows.

## C. Proof of Theorem 5.3

Proof : The proof is similar to that of Theorem 4.3, so we will only sketch it. By repeating the arguments in Lemma 4.2, one can conclude that for any Φ ∈ F ′ ,

$$\text{lude that for any } \Phi \in \mathcal { J } ^ { \prime }, \\ \text{GNE} ( \Phi ) & \subseteq \bigcup _ { x \in \text{GNE} ( \Phi ) } \text{GNE} ( \widetilde { \Phi } ^ { x } ), \\ \text{ands for the linearized version of } \Phi, as is Section IV-A. By Lemma 4.1, for any$$

$$& \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \geq \frac { \widetilde { \Theta } ^ { \bar { x } } ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \widetilde { \Theta } ^ { \bar { x } } ( z ) }. \\ & \text{class} \, \mathcal { F } ^ { \prime }. \, \text{i.e. if } \, F ( x ) = - \nabla \Theta ( x ) \text{ for all } x. \, \text{tl}$$

where the notation ˜ Φ x stands for the linearized version of Φ , as is Section IV-A. By Lemma 4.1, for any Φ ∈ F ′ and ¯ x ∈ GNE(Φ) ,

˜ We see that, if Φ belongs to the class F ′ , i.e. if F x ( ) = -∇ Θ( ) x for all x , then the linearization ˜ Φ ¯ x belongs to L ′ . i.e. we have ˜ F ¯ x ( x ) = -∇ ˜ Θ ( ¯ x x ) for all x . Similar to the proof of Theorem 4.3, using (15), we get that for each Φ ∈ F ,

$$\inf _ { \bar { x } \in \text{GNE} ( \Phi ) } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) } \geq \inf _ { \bar { x } \in \text{GNE} ( \Phi ), \Phi \in \mathcal { L } ^ { \prime } } \frac { \Theta ( \bar { x } ) } { \max _ { z \in \mathbb { C } } \Theta ( z ) }.$$

Then using that L ⊆ F ′ completes the proof.

$$\cdot$$

## REFERENCES

- [1] T. Alpcan and T. Bas ¸ar. A game-theoretic framework for congestion control in general topology networks. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002 , volume 2, pages 1218-1224, 2002.
- [2] P. Dubey. Inefficiency of Nash equilibria. Mathematics of Operations Research , 11(1):1-8, February 1986.
- [3] R. Engelbrecht-Wiggans. On optimal reservation prices in auctions. Management Science , 33(6):763-770, June 1987.
- [4] F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. 4OR: A Quarterly Journal of Operations Research , 5(3):173-210, 2007.
- [5] F. Facchinei and J.-S. Pang. Nash equilibria: The Variational Approach. In Convex Optimization in Signal Processing and Communication , chapter 12, pages 443-495. Cambridge University Press, Cambridge, 2009.
- [6] R. Johari. Efficiency loss in market mechanisms for resource allocation . PhD thesis, Massachusetts Institute of Technology, 2004.
- [7] R. Johari and J. N. Tsitsiklis. Efficiency loss in a newtork resource allocation game. Mathematics of Operations Research , 29(3):407-435, 2004.
- [8] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability. The Journal of the Operational Research Society , 49(3):237-252, March 1998.
- [9] F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications , 8(1):33-37, 1997.
- [10] A. A. Kulkarni and U. V. Shanbhag. On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica , 48(1):45-55, 2012.
- [11] A. A. Kulkarni and U. V. Shanbhag. Revisiting generalized Nash games and variational inequalities. Journal of Optimization Theory and Applications , 154(1):1-12, 2012.
- [12] S. Kunniyur and R. Srikant. End-to-end congestion control schemes: Utility functions, random losses and ECN marks. Networking, IEEE/ACM Transactions on , 11(5):689-702, oct. 2003.
- [13] R. La and V. Anantharam. Charge-sensitive TCP and rate control in the internet. In Proceedings of IEEE INFOCOM. , volume 3, pages 1166-1175, mar 2000.
- [14] R. T. Maheswaran and T. Bas ¸ar. Efficient signal proportional allocation (ESPA) mechanisms: decentralized social welfare maximization for divisible resources. IEEE Journal on Selected Areas in Communications , 24(5):1000-1009, 2006.
- [15] R. T. Maheswaran and T. Bas ¸ar. Nash equilibrium and decentralized negotiation in auctioning divisible resources. Group Decision and Negotiation , 12(5):361-395, 2003.
- [16] A. Mas-Colell. Noncooperative approaches to the theory of perfect competition: Presentation. Journal of Economic Theory , 22(2):121-135, April 1980.
- [17] A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory . Oxford University Press, USA, June 1995.
- [18] E. Maskin. Nash equilibrium and welfare optimality. The Review of Economic Studies , 66(1):23-38, January 1999.
- [19] J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking , 8(5):556-567, 2000.
- [20] R. B. Myerson. Optimal auction design. Mathematics of Operations Research , 6(1):58-73, February 1981.
- [21] Y. Narahari, D. Garg, R. Narayanam, and H. Prakash. Game Theoretic Problems in Network Economics and Mechanism Design Solutions . Springer, London, 1 edition, 2009.
- [22] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory . Cambridge University Press, Cambridge, September 2007.
- [23] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables . Academic Press, New York, January 1987.
- [24] C. Papadimitriou. Algorithms, games, and the internet. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing , pages 749-753, Hersonissos, Greece, 2001. ACM.
- [25] J. B. Rosen. Existence and uniqueness of equilibrium points for concave N -person games. Econometrica , 33(3):520-534, July 1965.
- [26] T. Roughgarden. Selfish Routing . PhD thesis, Cornell University, 2002.
- [27] T. Roughgarden and E. Tardos. ´ Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior , 47(2):389-403, 2004.
- [28] M. E. Slade. What does an oligopoly maximize? The Journal of Industrial Economics , 42(1):45-61, 1994.
- [29] A. Smith. An Inquiry into the Nature and Causes of the Wealth of Nations . BiblioBazaar. Originally published in 1776, August 2008.
- [30] W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance , 16(1):8-37, March 1961.
- [31] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior . Princeton University Press, Princeton, 1944.
- [32] L. Walras. ´ l´ments d' ´ conomie Politique Pure: Ou, Th´ eorie de la richesse sociale E e E . originally published in 1874, 1952.
Ankur A. Kulkarni
The Efficiency of Generalized Nash and Variational Equilibria
Shared-constraint games are noncooperative $N$-player games where players are
coupled through a common coupling constraint. It is known that such games admit
two kinds of equilibria -- generalized Nash equilibria (GNE) and variational
equilibria (VE) -- with two different economic interpretations. We consider
such games in the context of resource allocation, where players move
simultaneously to decide portions of the resource they can consume under a
coupling constraint that the sum of the portions they demand be no more than
the capacity of the resource. We clarify the worst case and best case
efficiency of these kinds of equilibria over all games in a class. We find that
the worst case efficiency of both solution concepts in zero and the best case
efficiency is unity. Moreover, we characterize the subclass of games where all
VE are efficient and show that even in this subclass but the worst case
efficiency of GNE is zero. We finally discuss means by which zero worst case
efficiency can be remedied.