1 Introduction

The proportional allocation mechanism, introduced by Kelly [12], is fundamental in the network optimization literature. According to this mechanism, a divisible resource — such as bandwidth of a communication link — is allocated to users as follows. Each user submits a bid to the mechanism; this corresponds to the user’s willingness-to-pay for sharing the resource. The mechanism allocates to each user a fraction of the resource that is equal to the ratio of her bid over the total amount of bids. It also receives a payment from each user that is equal to her bid. This naturally defines a proportional allocation game among the users who act as players; each player has a (typically concave, non-negative, and non-decreasing) valuation function for the resource share she receives and aims to maximize her utility, i.e., her value for the resource share minus her payment to the mechanism. As it is typically the case in games, the social welfare (i.e., the total value of the players for the resource share they receive) at equilibria is, in general, suboptimal.

We aim to quantify this inefficiency of equilibria by bounding the price of anarchy [13] of proportional allocation games. Besides the well-known work of Johari and Tsitsiklis [10] who considered pure Nash equilibria in the full information setting, there has been surprisingly little focus on price of anarchy bounds over more general equilibrium concepts. The only exception we are aware of is the recent work of Syrgkanis and Tardos [23] who studied proportional allocation as part of a broader class of mechanisms. Motivated by their work, we present new bounds on the price of anarchy of proportional allocation under general equilibrium concepts, such as coarse-correlated equilibria in the full information setting and Bayes-Nash equilibria in the incomplete information setting. In particular, we prove that the social welfare at equilibrium is at least 1/2 of the optimal social welfare. The bound holds for coarse-correlated and pure Bayes-Nash equilibria in the full information and Bayesian setting, respectively, and improves the bound of 26.8 % of [23]. The proof is conceptually simple and is obtained by bounding the utility of every player at equilibrium by the utility this player would have by deviating to a particular deterministic bid.

We also consider the scenario where players have budget constraints representing their ability-to-pay. Here, each player has a budget and is never allowed to bid above it. We assess the quality of equilibria in this case in terms of an effective welfare benchmark — proposed in previous work but further refined here — that takes budgets into account. We show that the effective welfare at equilibrium is at least a constant fraction of the optimal one. To the best of our knowledge, this is the first constant price of anarchy bound (in particular, between 36 and 50 %) with respect to this benchmark. Again, our proofs follow by considering a single deterministic deviation for each player, defined in a slightly different way compared to the deviation we consider in our bound on the social welfare.

Related Work

The proportional allocation mechanism and its variations have received significant attention in the network optimization literature. Proportional allocation games have been considered in [8, 14, 15] where the existence and uniqueness conditions for pure Nash equilibria are proved. Variations of the mechanism with different definitions for the allocation rule or the payments have been considered in [16–18, 21] (see also the discussion in [9]).

Johari and Tsitsiklis [10] were the first who assessed the quality of proportional allocations in terms of the social welfare. They focus on pure Nash equilibria and proved a lower bound of 3/4 on their price of anarchy. Their analysis is based on the important observation that a pure Nash equilibrium in a proportional allocation game is also a pure Nash equilibrium in a game where each player has a linear valuation function with slope equal to the derivative of the original valuation function at the share value they get at equilibrium. The optimal social welfare in the new game is not smaller than the original one and this allows them to consider the significantly simpler case of linear valuations in their analysis. Then, the price of anarchy bound is obtained by solving a linear program. An alternative proof to the result of [10] without using this argument is presented in [19] (see also [9]).

Unfortunately, this transformation does not apply to more general equilibrium concepts since the resource share each player receives is, in general, a random variable. This is a rather common difficulty that manifests itself in the analysis of games, as we depart from pure Nash equilibria and full information. In particular, Bayes-Nash equilibria have such an extremely rich structure that, typically, the price of anarchy analysis assesses their quality by rather ignoring this structure. Instead, it resorts to bounding the utility of each player by appropriately selected deviations which reveal a relation between the social welfare at equilibrium and the optimal social welfare. This approach has been used in a series of papers that mostly focus on auctions (e.g., see [1, 2, 4, 7, 11, 20, 23]) and is actually the approach we follow in the current paper as well.

Syrgkanis and Tardos [23] present a general analysis framework for the broad class of smooth mechanisms. Among other results, they show a price of anarchy lower bound of 26.8 % over coarse-correlated and mixed Bayes-Nash equilibria of proportional allocation games. In their analysis, they bound the utility of each player by the utility she would have by deviating to an appropriately defined randomized bid (an approach that has also been used in different contexts in [2, 11, 22, 24]) with a probability distribution that depends only on the optimal allocation and the valuation function of the player. In contrast, the deviating bid we consider depends on the bid strategies at equilibrium (this is in the same spirit as the recent analysis of Feldman et al. [7]) and, more interestingly, it is deterministic. In particular, it is defined as the product of the (expected) resource share a bidder receives in the optimal allocation and the expectation of bids of the other players at equilibrium.

Budget constraints are well-motivated in auction settings. In a slightly different context than ours, the effective welfare benchmark is considered by Dobzinski and Paes Leme, who call it liquid welfare in [6]. In proportional allocation, Syrgkanis and Tardos [23] prove that the social welfare at equilibrium is a constant fraction (specifically, equal to \(2-\sqrt {3}\approx 26.8~\%\)) of the optimal effective welfare. Note that our guarantee is considerably stronger as we compare directly the effective welfare at equilibrium with its optimal value.

Roadmap

The rest of the paper is structured as follows. We begin with preliminary definitions in Section 2. Our price of anarchy bounds in terms of the social welfare are proved in Section 3. There, we also argue that in order to improve our analysis, radically new ideas are required. The budget-constrained setting is studied in Section 4. We remark that we have not mentioned mixed Bayes-Nash equilibria in the above presentation of our results. Actually, we have observed that such equilibria coincide with pure Bayes-Nash ones even in the budget-constrained setting. We discuss related issues as well as additional open problems in Section 5.

2 Preliminaries

Each player (henceforth called bidder) i in a proportional allocation game has a concaveFootnote 1 non-decreasing valuation function \(v_{i}:[0,1]\rightarrow \mathbb {R}^{+}\). A strategy for bidder i is simply a non-negative bid. Given a bid vector b = (b 1, b 2, ...,b n ), with one bid per bidder, the proportional allocation mechanism allocates to each bidder a fraction of the resource that is proportional to the bid submitted by her. Denoting by d i the resource share that is allocated to bidder i, it is \(d_{i}=\frac {b_{i}}{{\sum }_{j}{b_{j}}}\). We often use the notation B −i to denote the sum of bids of all bidders besides i (hence, \(d_{i}=\frac {b_{i}}{b_{i}+B_{-i}}\)). The utility of bidder i from an allocation is simply the difference of her value for the fraction of the resource she gets minus her bid, i.e., u i (b) = v i (d i )−b i .

A bid vector b is a pure Nash equilibrium if the utility of all bidders is maximized, given the bid strategies of the other bidders. So, in a pure Nash equilibrium, no bidder has any incentive to deviate to another strategy. Denoting by \((b^{\prime }_{i},\mathbf {b}_{-i})\) the bid vector that is obtained from b when bidder i unilaterally deviates to bid strategy \(b^{\prime }_{i}\), we can express this condition as \(u_{i}(\mathbf {b}) \geq u_{i}(b^{\prime }_{i},\mathbf {b}_{-i})\).

The social welfare of an allocation d is the total value of bidders for the resource shares they receive, i.e., \(\text {SW}(d) = {\sum }_{i}{v_{i}(d_{i})}\). We denote by SW∗ the maximum value of the social welfare over all possible allocations. The price of anarchy over pure Nash equilibria is defined as the minimum value of the social welfare among all pure Nash equilibria divided by the optimal social welfare.

The bid strategy of a bidder i can be randomized. In this case, b i is a random variable and the bidder aims to maximize her expected utility \(\mathbb {E}[{u_{i}(\mathbf {b})]}\). The bid strategies of different bidders can be independent or correlated. A vector of independent randomized bid strategies is called a mixed Nash equilibrium if it simultaneously maximizes the expected utility of each bidder, given the bid strategies of the other bidders. More generally, coarse-correlated equilibria are solution concepts that capture correlated bid strategies. A vector of (possibly correlated) bid strategies is called a coarse-correlated equilibrium if no bidder has any incentive to unilaterally deviate to any deterministic bid strategy in order to improve her expected utility (again, given the strategies of the other bidders). The notion of the price of anarchy naturally extends to these solution concepts as well. For example, the price of anarchy over coarse-correlated equilibria is defined as the minimum value of the expected social welfare among all coarse-correlated equilibria divided by the optimal social welfare.

The above setting is known as the full (or complete) information setting. We consider the incomplete information (or Bayesian) setting as well; in this case, the valuation function v i of each bidder i is drawn randomly (and independently from the other bidders) from a probability distribution F i over concave, non-decreasing, and non-negative functions in [0,1]. Again, bidder i aims to maximize her expected utility for each possible valuation function v i drawn from F i . In the incomplete information setting, each bidder i bases her decision on her exact valuation v i and on the probability distributions according to which other bidders draw their valuations (and their corresponding bid strategies); these distributions are common knowledge.

So, the bid strategy of bidder i is a (possibly random) bid function b i (v i ). A vector with one such strategy per bidder (with independence between bid strategies of different bidders) is called a mixed Bayes-Nash equilibrium if no bidder has any incentive to deviate to some other bid for any valuation function drawn from F i . In pure Bayes-Nash equilibria, bidders use deterministic bid functions. The price of anarchy over Bayes-Nash equilibria is defined as the minimum value of the expected social welfare among all Bayes-Nash equilibria divided by the expectation of the optimal social welfare. With some abuse in notation, we also use SW∗ to denote the expectation of the optimal social welfare in the Bayesian setting.

We also extend the above model by adding budget constraints to the bidders. In this setting, each bidder i has a non-negative budget c i and she is never allowed to bid above her budget. This restriction can result to equilibria that have extremely low social welfare compared to the optimal one (whose definition does not take budgets into account). Following [23] and [6], we use the effective welfare benchmark in order to assess the quality of equilibria with budget-constrained bidders. The effective welfare of a (deterministic) allocation d = (d 1, d 2, ...,d n ) is defined as \(\text {EW}(d) = {\sum }_{i}{\min \{v_{i}(d_{i}),c_{i}\}}\). Note that the definition is similar to the definition of the social welfare; the important difference is that the value of each bidder is capped by her budget. We extend this definition to random allocations d as \(\text {EW}(d) = {\sum }_{i}{\min \{\mathbb {E}[{v_{i}(d_{i})}],c_{i}\}}\). We denote by EW∗ the maximum value of the effective welfare over all allocations. The price of anarchy with respect to the effective welfare benchmark (over equilibria in a given class) is the minimum value of the effective welfare (among all allocations induced by equilibria in the class) divided by the optimal effective welfare.

In the Bayesian setting, both the budget c i of bidder i and her valuation v i are drawn randomly according to the probability distribution F i . We refine the effective welfare benchmark in this case as

$$\text{EW}(d) = \underset{i}{\sum}~{\mathbb{E}_{(\mathbf{v}_{i},\mathbf{c}_{i})\sim \mathbf{F}_{i}}\left[\min\{\mathbb{E}_{(\mathbf{v}_{-i},\mathbf{c}_{-i})\sim \mathbf{F}_{-i}}\left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\}\right]},$$

where the inner expectation is taken over the valuation-budget value pairs of the other bidders once the pair for bidder i has been fixed (and over the corresponding bid strategies).

3 Bounding the Social Welfare of Equilibria

In this section, we prove the price of anarchy bounds with respect to the social welfare. We consider both coarse-correlated equilibria in the full information setting as well as pure Bayes-Nash equilibria in the Bayesian setting. Our proofs use the following lemma which bounds the utility of a bidder at a deterministic deviation. We also use this lemma later in Section 4 where we study budget-constrained bidders.

Lemma 3.1

Consider a bidder with a concave and non-decreasing valuation function \(v:[0,1]\rightarrow \mathbb {R}^{+}\) and let Γ be the random variable denoting the sum of bids of the other bidders. Then, for every z ∈ [0, 1] and for every μ > 0, the expected utility the bidder would have by deviating to the deterministic bid \(\mu z \mathbb {E}\left [{\Gamma }\right ]\) is at least \(\frac {3\mu -1}{4\mu }v(z)-\mu z \mathbb {E}{\Gamma }\).

Proof

It suffices to show that the expected value of the bidder when she deviates to the deterministic bid \(y=\mu z \mathbb {E}\left [ {\Gamma } \right ]\) is at least \(\frac {3\mu -1}{4\mu }v(z)\). Define the event \(T:=\left \lbrace {\Gamma } \geq y \left (\frac {1}{z}-1 \right ) \right \rbrace \). When T is false, we have \(\frac {y}{y+{\Gamma }} > z\) and, since v is non-decreasing, we clearly have that

$$\begin{array}{@{}rcl@{}} v\left( \frac{y}{y+{\Gamma}}\right)& \geq & v(z). \end{array} $$

Otherwise, when T is true, \(\frac {y}{y+{\Gamma }}\in [0,z]\). Since v is concave and non-negative, its value in [0,z] is lower-bounded by the line connecting points (0, 0) and (z, v(z)). Hence,

$$\begin{array}{@{}rcl@{}} v\left( \frac{y}{y+{\Gamma}}\right)& \geq & \frac{y}{y+{\Gamma}}\cdot \frac{v(z)}{z}. \end{array} $$

So, we can bound the expected value of the bidder when she deviates to the deterministic bid y using the two observations above and linearity of expectation.

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ v \left( \frac{y}{y+{\Gamma}} \right) \right] &=& \mathbb{E}\left[ v \left( \frac{y}{y+{\Gamma}} \right) \mathbb{1} \overline{T} \right] + \mathbb{E}\left[ v \left( \frac{y}{y+{\Gamma}} \right) \mathbb{1} T \right]\\ &\geq & \mathbb{E}\left[ v(z)\mathbb{1}\overline{T} \right]+\mathbb{E}\left[ \frac{y}{y+{\Gamma}}\cdot \frac{v(z)}{z}\mathbb{1}T \right]\\ &=& v(z) (1-\Pr[T])+\frac{v(z)}{z} \mathbb{E}\left[ \frac{y}{y+{\Gamma}}\mathbb{1}T \right]. \end{array} $$
(1)

Here, we have used the notation \(X\mathbb {1}T\) to denote the random variable that is equal to X if T is true and is zero otherwise.

We will now work with the rightmost term of the above right-hand side expression. Since the function \(\frac {y}{y+{\Gamma }}\) is convex with respect to Γ, we can apply Jensen’s inequality to obtain that

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ \frac{y}{y+{\Gamma}}\mathbb{1}T \right] &=& \mathbb{E}\left[ \frac{y}{y+{\Gamma}}|T \right]\cdot \Pr[T] \geq \frac{y\Pr[T]}{y+\mathbb{E}\left[ {\Gamma}|T \right]} \end{array} $$

and, since \(\mathbb {E}\left [ X|T \right ] \leq \frac {\mathbb {E}\left [ X \right ]}{\Pr [T]}\) for every random variable X ≥ 0, we have

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ \frac{y}{y+{\Gamma}}\mathbb{1}T \right] &\geq & \frac{y\Pr[T]^{2}}{y\Pr[T]+\mathbb{E}\left[ {\Gamma} \right]} \geq \frac{y\Pr[T]^{2}}{y+\mathbb{E}\left[ {\Gamma} \right]}. \end{array} $$

The second inequality follows trivially since Pr[T]≤1. Substituting y and using the fact that z ≤ 1, we get

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ \frac{y}{y+{\Gamma}}\mathbb{1}T \right] &\geq & \frac{\mu z \Pr[T]^{2}}{1+ \mu z}\geq \frac{\mu z}{\mu+1}\Pr[T]^{2}. \end{array} $$
(2)

Now, using (1), (2), and the fact that \(1-\alpha +\frac {\mu }{\mu +1}\alpha ^{2} \geq \frac {3\mu -1}{4\mu }\) for every α, we obtain that

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ v \left( \frac{y}{y+{\Gamma}} \right) \right] &\geq & v(z) \left( 1-\Pr[T]+\frac{\mu}{\mu+1}\Pr[T]^{2}\right) \geq \frac{3\mu-1}{4\mu}v(z), \end{array} $$

as desired. □

We are ready to prove our price of anarchy bounds. We begin with the case of coarse-correlated equilibria in the full information setting which is much simpler.

Theorem 3.2

The price of anarchy of proportional allocation games over coarse-correlated equilibria is at least 1/2.

Proof

Consider a full information proportional allocation game with n bidders in which bidder i has valuation function v i and denote by x i the resource fraction bidder i gets in the optimal allocation. Let b be a coarse-correlated equilibrium that induces a random allocation d = (d 1, ...,d n ) and let \(B={\sum }_{i}{b_{i}}\) be the random variable denoting the sum of bids of all bidders, with B −i being the sum of bids of all bidders besides bidder i. Since b is a coarse-correlated equilibrium, bidder i has no incentive to deviate to any deterministic bid (including the deviating bid \(x_{i} \mathbb {E}\left [B_{-i}\right ]\)). By applying Lemma 3.1 for bidder i with z = x i , μ = 1 and Γ = B −i , we obtain that

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b}) \right] &\geq & \mathbb{E}\left[ u_{i}(x_{i} \mathbb{E}\left[ B_{-i} \right], \mathbf{b}_{-i}) \right]\geq \frac{1}{2}v_{i}(x_{i}) - x_{i} \mathbb{E}\left[B_{-i}\right]. \end{array} $$

Summing over all bidders and using the facts that \({\sum }_{i}{x_{i}}=1\) and B −i ≤ B for every bidder i, we have

$$\begin{array}{@{}rcl@{}} \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b}) \right]} & \geq & \frac{1}{2}\underset{i}{\sum}~{v_{i}(x_{i})} - \underset{i}{\sum}~{x_{i} \mathbb{E}\left[ B_{-i} \right]}\\ &\geq & \frac{1}{2}\underset{i}{\sum}~{v_{i}(x_{i})} - \underset{i}{\sum}~{x_{i} \mathbb{E}\left[ B \right]}\\ &=& \frac{1}{2}\text{SW}^{*} - \mathbb{E}\left[ B \right]. \end{array} $$
(3)

The theorem follows by this inequality since the social welfare equals the sum of bidders’ utilities plus their bids, i.e., \(\mathbb {E}\left [\text {SW}(d)\right ] = {\sum }_{i}{\mathbb {E}\left [u_{i}(\mathbf {b})\right ]}+ \mathbb {E}\left [B\right ]\). □

The last step of the proof above begins with inequality (3). Essentially, this inequality has the form

$$\begin{array}{@{}rcl@{}} \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b}) \right]} & \geq & \lambda \text{SW}^{*} - \mu\underset{i}{\sum}~{x_{i} \mathbb{E}\left[ B_{-i} \right]}. \end{array} $$

The price of anarchy bound of [23] follows after first proving an inequality of this type and then concluding to a price of anarchy bound of \(\frac {\lambda }{\max \{1,\mu \}}\). The smoothness arguments of [23] lead to a version of this inequality with \(\lambda =2-\sqrt {3}\) and μ = 1. Here, we have been able to improve the parameters to λ = 1/2 and μ = 1. The next lemma demonstrates that these parameters cannot be improved further.

Lemma 3.3

For every 𝜖 > 0, there exists a proportional allocation game such that for every λ, μ satisfying

$$\begin{array}{@{}rcl@{}} \underset{i}{\sum}~{u_{i}(\mathbf{b})} \geq \lambda \text{SW}^{*} - \mu \underset{i}{\sum}~{ x_{i} B_{-i}} \end{array} $$
(4)

where x i is the resource fraction of bidder i in the optimal allocation and B −i is the sum of bids of all bidders besides bidder i at a (pure Nash) equilibrium, it holds that \(\frac {\lambda }{\max \{1,\mu \}}\leq \frac {1}{2}+\epsilon \).

Proof

Consider the proportional allocation game with n ≥ 2 bidders in which bidder 1 has valuation v 1(x) = x and bidder i has valuation \(v_{i}(x)=\frac {n-1}{2n-3} x\) for i ≥ 2. We can show that the bids in the (unique) pure Nash equilibrium are b 1 = 1/4 and \(b_{i}=\frac {1}{4(n-1)}\) for i ≥ 2. Indeed, assuming that this is true for all bidders besides i, it can be verified that the strategy y that maximizes the utility \(u_{i}(y,\mathbf {b}_{-i}) = v_{i}\left (\frac {y}{y+B_{-i}}\right )-y\) for bidder i satisfies y = b i . I.e., bidder 1 gets half of the resource and the remaining bidders share the remaining resource equally. Hence, u 1(b) = v 1(1/2)−1/4=1/4 and \({\sum }_{i\not =1}{u_{i}(\mathbf {b})} = (n-1)\left (v_{i}\left (\frac {1}{2(n-1)}\right )-\frac {1}{4(n-1)}\right ) = \frac {1}{4(2n-3)}\).

In the optimal allocation, the whole resource is allocated to bidder 1, i.e., SW∗ = 1, x 1 = 1 and x i = 0 for i ≥ 2. Hence, inequality (4) becomes

$$\begin{array}{@{}rcl@{}} \frac{1}{4}+\frac{1}{4(2n-3)} &\geq & \lambda - \frac{\mu}{4} \end{array} $$

and implies that \(\lambda \leq \max \{1,\mu \}\left (\frac {1}{2}+\frac {1}{4(2n-3)}\right )\). The lemma follows by setting n sufficiently large. □

The proof for Bayes-Nash equilibria follows the same general approach with that of Theorem 3.2.

Theorem 3.4

The price of anarchy of proportional allocation games over pure Bayes-Nash equilibria is at least 1/2.

Proof

Consider an incomplete information proportional allocation game in which the valuation function v i of bidder i is drawn from the probability distribution F i , independently for each bidder. Let x i be the random variable denoting the resource fraction bidder i gets in the optimal allocation. Let b be a pure Bayes-Nash equilibrium and B be the random variable denoting the sum of bids of all bidders; again, B −i denotes the sum of bids of all bidders besides bidder i. Since b is a pure Bayes-Nash equilibrium, bidder i has no incentive to deviate to any deterministic bid (including the deviating bid \(\mathbb {E}\left [x_{i}| v_{i}\right ] \mathbb {E}\left [B_{-i}|v_{i}\right ]\)) when the valuation drawn from probability distribution F i is v i . So, in all conditional expectations below, we simply write v i to denote the event that the valuation v i drawn from F i is v i . By applying Lemma 3.1 for bidder i with \(z=\mathbb {E}\left [x_{i}|v_{i}\right ]\), μ = 1 and Γ = B −i , we obtain that

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})|v_{i} \right] &\geq & \mathbb{E}\left[ u_{i}(\mathbb{E}\left[ x_{i}|v_{i} \right] \mathbb{E}\left[ B_{-i}|v_{i} \right], \mathbf{b}_{-i})|v_{i} \right]\\ &\geq& \frac{1}{2}v_{i}(\mathbb{E}\left[ x_{i}|v_{i} \right]) - \mathbb{E}\left[ x_{i}|v_{i} \right] \mathbb{E}\left[ B_{-i}|v_{i} \right]\\ &\geq & \frac{1}{2}\mathbb{E}\left[ v_{i}(x_{i})|v_{i} \right] - \mathbb{E}\left[ x_{i}|v_{i} \right]\mathbb{E}\left[ B \right]. \end{array} $$

The second inequality follows by Jensen’s inequality since the valuation function v i is concave and due to the fact that in a pure Bayes-Nash equilibrium, the bid of a bidder different than i does not depend on the exact valuation of bidder i and, hence, \(\mathbb {E}\left [B_{-i}|v_{i}\right ]=\mathbb {E}\left [B_{-i}\right ]\leq \mathbb {E}\left [B\right ]\). Considering all possible valuations for bidder i that are drawn from probability distribution F i , we have that her unconditional expected utility is

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b}) \right] & \geq & \frac{1}{2}\mathbb{E}\left[ \mathbf{v}_{i}(x_{i}) \right] - \mathbb{E}\left[ x_{i} \right] \mathbb{E}\left[ B \right]. \end{array} $$

Summing over all bidders and using the fact that \({\sum }_{i}{x_{i}}=1\), we have

$$\begin{array}{@{}rcl@{}} \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b}) \right]} & \geq & \frac{1}{2}\underset{i}{\sum}~{\mathbb{E}\left[ \mathbf{v}_{i}(x_{i}) \right]} - \underset{i}{\sum}~{ \mathbb{E}\left[ x_{i} \right] \mathbb{E}\left[ B \right]} = \frac{1}{2}\text{SW}^{*} - \mathbb{E}\left[B\right]. \end{array} $$

The theorem follows from this inequality since, again, the social welfare equals the sum of expected bidders’ utilities plus the total amount of bids. □

4 Budget-Constrained Bidders

In this section, we consider budget-constrained bidders and prove a lower bound of approximately 36 % and an upper bound of 50 % on the price of anarchy in terms of the effective welfare benchmark (Theorem 4.1 for coarce-correlated equilibria and Theorem 4.2 for Bayes-Nash equilibria). Furthermore, we present an upper bound (Theorem 4.3) which applies even to pure Nash equilibria.

Before proceeding to the presentation of our bounds for budget-constrained bidders, we remark that minor modifications of the proofs in the previous section can show that the social welfare over equilibria with budget-constrained bidders is at least 1/2 of the optimal effective welfare, improving a corresponding bound of 26.8 % from [23]. The necessary modifications are as follows. First, we need to define the deviating bids in terms of the resource shares in the allocation that maximizes the effective welfare. Then, there is a subtle case where Lemma 3.1 cannot be used, namely when the deviating bid for a bidder exceeds her budget. Fortunately, the inequality provided by Lemma 3.1 follows trivially in this case (actually, we use this argument in the proof below). By repeating the analysis in the proofs of Theorems 3.2 and 3.4, we can conclude that the social welfare at equilibrium is at least 1/2 of the social welfare of the allocation that maximizes the effective welfare. The bound then follows by observing that the effective welfare of this allocation is upper-bounded by its social welfare.

We are now ready to prove our main results for budget-constrained bidders. Again, we begin with the case of coarce-correlated equilibria in the full information setting which is simpler.

Theorem 4.1

The price of anarchy of proportional allocation games with budget-constrained bidders over coarse-correlated equilibria is at least 0.3596.

Proof

Let μ ∈ (1/3,1] be a parameter whose exact value will be defined later. Consider a full information proportional allocation game with n bidders in which bidder i has valuation function v i and budget c i and denote by x i the resource fraction bidder i gets in the allocation that maximizes the effective welfare. Let b be a coarse-correlated equilibrium inducing an allocation d = (d 1, ...,d n ) and let \(B={\sum }_{i}{b_{i}}\) be the random variable denoting the sum of bids of all bidders, with B −i being the sum of bids of all bidders besides bidder i. Let A be the set of bidders with \(\mathbb {E}\left [v_{i}(d_{i})\right ] \leq c_{i}\). Clearly, for every bidder not belonging to set A, it holds that

$$\begin{array}{@{}rcl@{}} \min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\} &\geq &\min\{v_{i}(x_{i}),c_{i}\}. \end{array} $$

Summing over all bidders not belonging to A (and multiplying by 1 − μ), we obtain that

$$\begin{array}{@{}rcl@{}} (1-\mu) \underset{i\not\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\}} &\geq & (1-\mu) \underset{i\not\in A}{\sum}~{\min\{v_{i}(x_{i}),c_{i}\}}. \end{array} $$
(5)

For every bidder i ∈ A, we distinguish between two cases. If \(\mu x_{i}\mathbb {E}\left [ B_{-i} \right ] > c_{i}\), then clearly

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b}) \right] &\geq & 0\\ &> &c_{i} - \mu x_{i}\mathbb{E}\left[ B_{-i} \right]\\ &\geq & \frac{3\mu-1}{4\mu}\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\} - \mu x_{i}\mathbb{E}\left[ B_{-i} \right]. \end{array} $$

In order to prove the same inequality when \(\mu x_{i}\mathbb {E}\left [ B_{-i} \right ] \leq c_{i}\), we bound the utility of bidder i by the utility she would have when deviating to bid \(\mu x_{i}\mathbb {E}\left [B_{-i}\right ]\) (which is within i’s budget c i ). Using Lemma 3.1, we have again

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b}) \right] &\geq & \frac{3\mu-1}{4\mu}\mathbb{E}\left[ v_{i}(x_{i}) \right] - \mu x_{i}\mathbb{E}\left[ B_{-i} \right]. \end{array} $$

Summing this last inequality over all bidders of A, we obtain

$$\begin{array}{@{}rcl@{}} \underset{i\in A}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b}) \right]} &\geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\}} - \underset{i\in A}{\sum}~{\mu x_{i}\mathbb{E}\left[B_{-i}\right]}\\ & \geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\}} - \mu \mathbb{E}\left[ B \right]\underset{i\in A}{\sum}~{x_{i}}\\ & \geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\}} - \mu \mathbb{E}\left[ B \right]. \end{array} $$

Using the equality \(B={\sum }_{i}{b_{i}}\) and linearity of expectation, this inequality implies that

$$\begin{array}{@{}rcl@{}} \underset{i\in A}{\sum}~{\left( \mathbb{E}\left[ u_{i}(\mathbf{b}) \right]+\mu \mathbb{E}\left[ b_{i} \right]\right)} +\mu \underset{i\not\in A}{\sum}~{\mathbb{E}\left[ b_{i} \right]} & \geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[v_{i}(x_{i})\right],c_{i}\}}. \end{array} $$

Since \(\mathbb {E}\left [ u_{i}(\mathbf {b}) \right ]+\mu \mathbb {E}\left [ b_{i} \right ] \leq \min \{\mathbb {E}\left [ v_{i}(d_{i}) \right ],c_{i}\}\) for every bidder in A (recall that μ ≤ 1 and v i (d i ) = u i (b) + b i ) and \(\mathbb {E}\left [b_{i}\right ]\leq \min \{\mathbb {E}\left [v_{i}(d_{i})\right ],c_{i}\}\) for every bidder not belonging to A, the above inequality yields

$$\begin{array}{@{}rcl@{}} \underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\}} +\mu \underset{i\not\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\}}& \geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[v_{i}(x_{i})\right],c_{i}\}} \end{array} $$
(6)

By summing (5) and (6), we obtain

$$\begin{array}{@{}rcl@{}} \text{EW}(d) &=& \underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\}} +\underset{i\not\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(d_{i}) \right],c_{i}\}}\\ & \geq & \frac{3\mu-1}{4\mu}\underset{i\in A}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\}}+(1-\mu) \underset{i\not\in A}{\sum}~{\min\{\mathbb{E}\left[v_{i}(x_{i})\right],c_{i}\}}\\ &\geq & \min\left\{\frac{3\mu-1}{4\mu},1-\mu\right\}\underset{i}{\sum}~{\min\{\mathbb{E}\left[ v_{i}(x_{i}) \right],c_{i}\}}\\ &=& \min\left\{\frac{3\mu-1}{4\mu},1-\mu\right\} \text{EW}^{*}. \end{array} $$

Hence, the price of anarchy with respect to the effective welfare benchmark is bounded by the quantity \(\min \left \{\frac {3\mu -1}{4\mu },1-\mu \right \}\) which is maximized to \(\frac {7-\sqrt {17}}{8}\approx 0.3596\) for \(\mu =\frac {1+\sqrt {17}}{8}\). □

The proof for Bayes-Nash equilibria in the incomplete information setting is a bit more complicated. Again, as we did in the proof of Theorem 4.1, we will show that

$$\text{EW}(d) \geq \min\left\{\frac{3\mu-1}{4\mu},1-\mu\right\} \text{EW}^{*}. $$

Recall that in the incomplete information setting, both the valuation v i and the budget c i of bidder i are drawn randomly according to a probability distribution F i , and the effective welfare is defined as

$$\text{EW}(d) = \underset{i}{\sum}~{\mathbb{E}_{(\mathbf{v}_{i},\mathbf{c}_{i})\sim \mathbf{F}_{i}}\left[ \min \{\mathbb{E}_{(\mathbf{v}_{-i},\mathbf{c}_{-i})\sim \mathbf{F}_{-i}}\left[\mathbf{v}_{i}(d_{i})\right], \mathbf{c}_{i}\}\right]}. $$

In order to simplify notation in the proof of Theorem 4.2, we will not explicitly use the subscripts in the expectations.

Theorem 4.2

The price of anarchy of proportional allocation games with budget-constrained bidders over Bayes-Nash equilibria is at least 0.3596.

Proof

Let μ ∈ (1/3, 1] be a parameter whose exact value will be defined later. Consider an incomplete information proportional allocation game with n bidders in which the valuation function v i and the budget c i of bidder i are drawn from the probability distribution F i , independently for each bidder. Let x i be the random variable denoting the resource fraction bidder i gets in the allocation that maximizes the effective welfare. Let b be a pure Bayes-Nash equilibrium that induces a random allocation d = (d 1, ...,d n ) and B be the random variable denoting the sum of bids of all bidders; again, B −i denotes the sum of bids of all bidders besides bidder i. We denote by A i the set that contains all pairs of a valuation function and a corresponding budget value (v i , c i ) that are drawn from the probability distribution F i and satisfy \(\mathbb {E}\left [\mathbf {v}_{i}(d_{i})|v_{i}\right ] \leq c_{i}\). Consider a bidder i with valuation-budget pair (v i , c i )∉A i . By the definition of A i , we have

$$\begin{array}{@{}rcl@{}} \min\{\mathbb{E}\left[ \mathbf{v}_{i}(d_{i})|(v_{i},c_{i}) \right],c_{i}\} &\geq & \min\{\mathbb{E}\left[ \mathbf{v}_{i}(x_{i})|(v_{i},c_{i}) \right],c_{i}\}. \end{array} $$

By considering all valuation-budget pairs not belonging to A i , we obtain

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ \min\{\mathbb{E}\left[ \mathbf{v}_{i}(d_{i}) \right],\mathbf{c}_{i}\} \mathbb{1}(\mathbf{v}_{i}, \mathbf{c}_{i})\not\in A_{i} \right] &\geq & \mathbb{E}\left[\min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right], \mathbf{c}_{i}\}\mathbb{1}{(\mathbf{v}_{i}, \mathbf{c}_{i})\not\in A_{i}}\right], \end{array} $$

and summing over all bidders, we have

$$\begin{array}{@{}rcl@{}} \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\} \mathbb{1} (\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i} \right]} &\geq & \underset{i}{\sum}~{\mathbb{E}\left[ \min \{\mathbb{E} \left[\mathbf{v}_{i}(x_{i})\right],\mathbf{c}_{i}\}\mathbb{1}{(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i}} \right]}. \end{array} $$
(7)

Now consider a valuation-budget pair (v i , c i )∈A i for bidder i that is drawn from F i . If \(\mu \mathbb {E}\left [x_{i}|(v_{i},c_{i})\right ]\mathbb {E}\left [B_{-i}|(v_{i},c_{i})\right ]\leq c_{i}\), we can bound the expected utility \(\mathbb {E}\left [u_{i}(\mathbf {b})|(v_{i},c_{i})\right ]\) by considering the deviation of bidder i to bid \(\mu \mathbb {E}\left [x_{i}|(v_{i},c_{i})\right ]\mathbb {E}\left [B_{-i}|(v_{i},c_{i})\right ]\) (which is within bidder i’s budget c i ). By Lemma 3.1, we have

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})|(v_{i},c_{i}) \right] &\geq & \frac{3\mu-1}{4\mu} v_{i}(\mathbb{E}\left[ x_{i}| (v_{i},c_{i}) \right]) - \mu \mathbb{E}\left[ x_{i}|v_{i} \right]\mathbb{E}\left[ B_{-i}|(v_{i},c_{i}) \right]\\ &\geq & \frac{3\mu-1}{4\mu} \mathbb{E}\left[ v_{i}(x_{i})|(v_{i},c_{i}) \right] - \mu \mathbb{E}\left[ x_{i}|(v_{i}, c_{i}) \right]\mathbb{E}\left[ B \right]\\ &\geq & \frac{3\mu-1}{4\mu} \min\{\mathbb{E}\left[ v_{i}(x_{i})|(v_{i},c_{i}) \right],c_{i}\} - \mu \mathbb{E}\left[ x_{i}|(v_{i},c_{i}) \right]\mathbb{E}\left[ B \right]. \end{array} $$

The second inequality follows by Jensen’s inequality and by the fact \(\mathbb {E}\left [ B_{-i}|(v_{i},c_{i}) \right ]= \mathbb {E}\left [ B_{-i} \right ]\). Otherwise, if \(\mu \mathbb {E}\left [x_{i}|(v_{i},c_{i})\right ]\mathbb {E} \left [B_{-i}| (v_{i},c_{i})\right ]> c_{i}\), the same inequality follows easily since

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})|(v_{i},c_{i}) \right] &\geq & 0\\ & > & c_{i} - \mu \mathbb{E}\left[ x_{i}|(v_{i},c_{i}) \right]\mathbb{E}\left[ B_{-i}|(v_{i},c_{i}) \right]\\ &\geq & \frac{3\mu-1}{4\mu} \min\{\mathbb{E}\left[ v_{i}(x_{i})|(v_{i},c_{i}) \right],c_{i}\} - \mu \mathbb{E}\left[ x_{i}|(v_{i},c_{i}) \right]\mathbb{E}\left[ B \right]. \end{array} $$

Hence, when (v i , c i )∈A i , we have

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})|(v_{i},c_{i}) \right] + \mu \mathbb{E}\left[ x_{i}|(v_{i},c_{i}) \right]\mathbb{E} \left[ B \right] &\geq & \frac{3\mu-1}{4\mu} \min\{\mathbb{E}\left[v_{i}(x_{i})|(v_{i},c_{i})\right],c_{i}\}. \end{array} $$

By considering all valuation-budget values belonging to A i , we have

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\!\in\! A_{i} \right] \,+\, \mu \mathbb{E}\left[ x_{i}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\!\in\! A_{i} \right]\mathbb{E}\left[ B \right] \!\!&\geq&\!\!\! \frac{3\mu\!\,-\,\!1}{4\mu} \mathbb{E}\left[\min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right],\mathbf{c}_{i}\}\mathbb{1}{(\mathbf{v}_{i}, \mathbf{c}_{i})\!\in\! A_{i}}\right]. \end{array} $$

Using the obvious fact that \(\mathbb {E}\left [ x_{i} \right ]\geq \mathbb {E}\left [ x_{i}\mathbb {1}(\mathbf {v}_{i}, \mathbf {c}_{i})\in A_{i} \right ]\) and the above inequality, we obtain that

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(\mathbf{b})\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right] + \mu \mathbb{E}\left[ x_{i} \right]\mathbb{E}\left[ B \right] \!\!&\geq&\!\!\mathbb{E}\left[ u_{i}(\mathbf{b})\mathbb{1}(\mathbf{v}_{i}, \mathbf{c}_{i})\in A_{i} \right]\\ &&+ \mu \mathbb{E}\left[ x_{i}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]\mathbb{E}\left[ B \right]\\ \!\!&\geq&\!\! \frac{3\mu-1}{4\mu} \mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right],c_{i}\} \mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\!\in\! A_{i} \right]. \end{array} $$
(8)

Now, we have

$$\begin{array}{@{}rcl@{}} && \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\} \mathbb{1} (\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]}+\mu \underset{i}{\sum}~{\mathbb{E}\left[\min\{\mathbb{E} \left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\}\mathbb{1}{(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i}} \right]}\\ &\geq & \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b})+b_{i}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]} + \mu\underset{i}{\sum}~{\mathbb{E}\left[b_{i}\mathbb{1}{(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i}}\right]}\\ &\geq & \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b})+\mu b_{i}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]} + \mu\underset{i}{\sum}~{\mathbb{E}\left[b_{i}\mathbb{1}{(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i}}\right]}\\ &=& \underset{i}{\sum}~{\mathbb{E}\left[ u_{i}(\mathbf{b})\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]} + \mu \mathbb{E}\left[ B \right]\\ &=& \underset{i}{\sum}~{\left( \mathbb{E}\left[ u_{i}(\mathbf{b})\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]+\mu \mathbb{E}\left[ x_{i} \right]\mathbb{E}\left[ B \right]\right)}\\ &\geq & \frac{3\mu-1}{4\mu} \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right], \mathbf{c}_{i}\}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]}. \end{array} $$
(9)

The first inequality follows since the quantity \(\min \{\mathbb {E}\left [ \mathbf {v}_{i}(d_{i}) \right ],\mathbf {c}_{i}\}\) equals \(\mathbb {E}\left [ \mathbf {v}_{i}(d_{i}) \right ]\) when (v i , c i )∈A i and c i otherwise; in the latter case, the budget is clearly not smaller than the bid of bidder i. The second inequality follows since μ ≤ 1, the two equalities are obvious, and the last inequality follows by (8). Now, using (7) and (9), we have

$$\begin{array}{@{}rcl@{}} \text{EW}(d) &=& \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[ \mathbf{v}_{i}(d_{i}) \right],\mathbf{c}_{i}\} \right]}\\ & = & \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\} \mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]}\\ &&+\mu \underset{i}{\sum}~{\mathbb{E}\left[\min\{\mathbb{E} \left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\} \mathbb{1}{(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i}}\right]}\\ & & +(1-\mu) \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(d_{i})\right],\mathbf{c}_{i}\} \mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i} \right]}\\ &\geq & \frac{3\mu-1}{4\mu} \underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right], \mathbf{c}_{i}\}\mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\in A_{i} \right]}\\ & & +(1-\mu)\underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E}\left[\mathbf{v}_{i}(x_{i})\right],\mathbf{c}_{i}\} \mathbb{1}(\mathbf{v}_{i},\mathbf{c}_{i})\not\in A_{i} \right]}\\ &\geq& \min\left\{\frac{3\mu-1}{4\mu},1-\mu\right\}\underset{i}{\sum}~{\mathbb{E}\left[ \min\{\mathbb{E} \left[\mathbf{v}_{i}(x_{i})\right],\mathbf{c}_{i}\} \right]}\\ &=& \min\left\{\frac{3\mu-1}{4\mu},1-\mu\right\} \text{EW}^{*}. \end{array} $$

Hence, the price of anarchy with respect to the effective welfare benchmark is bounded by the quantity \(\min \left \{\frac {3\mu -1}{4\mu },1-\mu \right \}\) which is maximized to \(\frac {7-\sqrt {17}}{8}\approx 0.3596\) for \(\mu =\frac {1+\sqrt {17}}{8}\). □

We conclude this section by presenting our upper bound on the price of anarchy; note that it holds even for pure Nash equilibria.

Theorem 4.3

For every 𝜖>0, there exists a proportional allocation game among budget-constrained bidders with price of anarchy at most 1/2 + 𝜖 over pure Nash equilibria, with respect to the effective welfare benchmark.

Proof

Let α ∈ (0, 1). Consider a proportional allocation game with two bidders. Bidder 1 has valuation v 1(x) = x and budget \(c_{1}=\frac {\alpha }{(1+\alpha )^{2}}\). Bidder 2 has valuation v 2(x) = α x and infinite budget. The state in which bidder 1 bids \(\frac {\alpha }{(1+\alpha )^{2}}\) (i.e., her budget) and bidder 2 bids \(\frac {\alpha ^{2}}{(1+\alpha )^{2}}\) is a pure Nash equilibrium, since the derivatives \(\frac {b_{2}}{(b_{1}+b_{2})^{2}}-1\) and \(\frac {\alpha b_{1}}{(b_{1}+b_{2})^{2}}-1\) of the utilities of the bidders (as functions of their strategies) are equal to zero. Observe that \(v_{1}\left (\frac {1}{1+\alpha }\right )\) significantly exceeds her budget for every value of α. Hence, \(\text {EW}(\mathbf {b}) = \frac {\alpha }{(1+\alpha )^{2}}+\frac {\alpha ^{2}}{1+\alpha } = \frac {\alpha +\alpha ^{2}+\alpha ^{3}}{(1+\alpha )^{2}}\). The optimal effective welfare is bounded by the welfare at the state when bidder 1 bids her budget \(\frac {\alpha }{(1+\alpha )^{2}}\) and bidder 2 bids \(1-\frac {\alpha }{(1+\alpha )^{2}}\) so that bidder 1 gets value equal to her budget. Hence, the optimal effective welfare is \(\text {EW}^{*} = \frac {2\alpha +\alpha ^{2}+\alpha ^{3}}{(1+\alpha )^{2}}\). Clearly, the ratio EW(b)/EW∗ approaches 1/2 from above as α approaches 0 and the theorem follows by selecting α to be sufficiently small. □

5 Discussion and Open Problems

Our work leaves the obvious open problem of computing the tight bound on the price of anarchy over coarse-correlated and Bayes-Nash equilibria. In the full information model, proving bounds specifically for correlated equilibria (a well-known equilibrium class that lies between mixed Nash and coarse-correlated equilibria) is interesting as well. So far, the only upper bound that is known is the counter-example of 3/4 from [10] for pure Nash equilibria. Is 3/4 the tight bound for all equilibrium concepts considered in the current paper? Actually, we have not been able to identify any coarse-correlated equilibrium in the full information model that is non-pure. Do such equilibria really exist? Interestingly, we show in Lemma 5.1 that mixed Nash equilibria coincide with pure ones. More generally, this statement applies to mixed Bayes-Nash equilibria in the budget-constrained setting. Does it extend to coarse-correlated ones? We believe that this is an interesting open problem.

Lemma 5.1

The set of mixed Bayes-Nash equilibria in any proportional allocation game (possibly with budget-constrained bidders) coincides with that of pure Bayes-Nash equilibria.

Proof

Assume that there exists an incomplete information proportional allocation game (possibly with budget-constrained bidders) that has a mixed Bayes-Nash equilibrium b in which bidder i bids two different values y 1 and y 2 (with y 1<y 2) with non-zero probability when her valuation function is v i ; both values are within the budget of bidder i (if any). We will show that this is not possible.

By the mixed Bayes-Nash equilibrium condition, both y 1 and y 2 should yield the same maximum expected utility U to bidder i, i.e.,

$$\begin{array}{@{}rcl@{}} U = \mathbb{E}\left[ u_{i}(y_{1},\mathbf{b}_{-i})|v_{i} \right] = \mathbb{E}\left[ u_{i}(y_{2},\mathbf{b}_{-i})|v_{i} \right]. \end{array} $$

Let B −i be the random variable denoting the sum of bids of all bidders besides bidder i and let \(f(y)=\mathbb {E}\left [ v_{i} \left (\frac {y}{y+B_{-i}} \right ) \right ]\) be the expected value of bidder i when unilaterally deviating to bid y. Clearly, f is non-decreasing. It is also concave in [y 1, y 2] since it is defined as the linear combination of concave functions: for every value of B −i , \(v_{i} \left (\frac {y}{y+B_{-i}} \right )\) is a concave function with respect to y, and the expectation over B −i is simply a linear combination over such functions. Clearly, \(\mathbb {E}\left [u_{i}(y,\mathbf {b}_{-i})\right ]=f(y)-y\).

We furthermore claim that f is strictly increasing in [y 1, y 2]. If this was not the case, then due to the concavity of f there should exist y ′ ∈ [y 1, y 2) such that f(y ′) = f(y 2) and, hence, bidder i could deviate to bid y ′ (which is clearly within her budget, if any) for an improved expected utility of \(\mathbb {E}\left [ u_{i}(y^{\prime },\mathbf {b}_{-i})|v_{i} \right ]=f(y^{\prime })-y^{\prime }> f(y_{2})- y_{2}=U\). This would contradict the mixed Bayes-Nash equilibrium condition.

The fact that f is strictly increasing clearly implies that Pr[B −i > 0] > 0. But then, for every positive value of B −i , \(v_{i} \left (\frac {y}{y+B_{-i}} \right )\) is a strictly concave function of y and, subsequently, f is also strictly concave as a linear combination of concave functions including strictly concave ones. Hence, there exists λ ∈ [0, 1] such that f(λ y 1+(1−λ)y 2)>λ f(y 1)+(1−λ)f(y 2) and bidder i has a profitable deviation to bid y ′ = λ y 1 + (1 − λ)y 2 (which is again within her budget, if any) since

$$\begin{array}{@{}rcl@{}} \mathbb{E}\left[ u_{i}(y^{\prime},\mathbf{b}_{-i}) \right] & = & f(y^{\prime})-y^{\prime} \\ & > & \lambda f(y_{1}) + (1-\lambda)f(y_{2}) -\lambda y_{1} - (1-\lambda)y_{2} \\ & = & \lambda(f(y_{1})-y_{1})+(1-\lambda)(f(y_{2})-y_{2}) \\ & = & U. \end{array} $$

We conclude that the support of any mixed Bayes-Nash equilibrium cannot contain two different bid values for bidder i when her valuation is v i and, subsequently (by extending the same argument to all possible valuations of bidder i and to all bidders), it must be a pure Bayes-Nash equilibrium. □

We remark that if the valuation functions are differentiable (we do not make any such assumption in the above proof), a much simpler proof of theorem 5.1 follows by observing that the utility of bidder i, when seen as a function of bidder i’s strategy, has strictly decreasing derivative. Then, the utility is maximized either by a bid equal to the budget of the bidder (if any) or at the unique bid that nullifies its derivative.

In the Bayesian setting, we have not considered more general equilibrium concepts such as coarse-correlated Bayesian equilibria. A vector of possibly correlated bid functions is called a coarse-correlated Bayesian equilibrium if no bidder i has any incentive to unilaterally deviate to any deterministic bid strategy in order to improve her expected utility (again, given the strategies of the other bidders), for any valuation she draws from her probability distribution F i . Coarse-correlated Bayesian equilibria are more general than mixed Bayes-Nash equilibria since the bid functions of different bidders are not restricted to being independent [2]. The main reason for which we have not considered coarse-correlated Bayesian equilibria is that our analysis requires that the expectation of the sum of bids of the other bidders is the same for any possible valuation bidder i can draw from her distribution; this property is not satisfied by more general equilibrium concepts. What is the price of anarchy in this case? Interestingly, the answer cannot be 3/4 as our next counter-example indicates.

Lemma 5.2

There exists a proportional allocation game that has price of anarchy at most 0.7154 over coarse-correlated Bayesian equilibria.

Sketch of Proof

Our counter-example has two bidders. Bidder 1 has valuation function x with probability p 1 and 𝜖 1 x with probability 1 − p 1. Bidder 2 has valuation function α x with probability p 2 and 𝜖 2 x with probability 1 − p 2. We require 1 ≥ α and, furthermore, α is significantly larger than 𝜖 1 which in turn is significantly larger than 𝜖 2 (multiplicatively).

We construct a coarse-correlated Bayesian equilibrium of the following form: When the valuations of the bidders are x and α x, the bid strategies are γ and δ respectively. These values are significant and yield constant resource fractions to both bidders. In all other cases where at least one of the bidders has an almost zero valuation, the bids are extremely close to zero. However, the bidder that has significantly higher valuation than the other submits a significantly higher bid (but still very close to zero) and gets almost 100 % of the resource. In the following, we round negligibly small bids or valuations to 0 and treat an allocation of almost 100 % of the resource to some bidder as exactly 100 %. This rounding does not affect the final result that we can obtain but significantly more detailed (and tedious) calculations are needed for a formal proof. So, we will assume that when the valuations are x or 𝜖 1 x for bidder 1 and 𝜖 2 x for bidder 2, the bid strategies are (almost) 0 but the bid of bidder 1 is significantly higher so that she gets (almost) 100 % of the resource. Similarly, when the valuations are 𝜖 1 x and α x, the bid strategies are (almost) 0 but the bid of bidder 2 is significantly higher so that she gets almost 100 % of the resource.

Notice that the expected utility of bidder 1 when her valuation is x is (approximately) \(p_{2}\frac {\gamma }{\gamma + \delta }+1-p_{2}-p_{2} \gamma \) and becomes (approximately) \(p_{2}\frac {y}{y+\delta }+1-p_{2}-y\) when deviating to a deterministic bid y. We require that the first quantity is higher than the second one so that no such deviation exists, i.e., \(p_{2}\frac {\gamma }{\gamma +\delta }-p_{2} \gamma \geq p_{2}\frac {y}{y+\delta }-y\) for every y ≥ 0. Similarly, we require that \(p_{1}\frac {\alpha \delta }{\gamma +\delta }-p_{1} \delta \geq p_{1}\frac {\alpha y}{\gamma +y}-y\). Note that the right-hand side of the above constraints are maximized to \((\sqrt {p_{2}}- \sqrt {\delta })^{2}\) and \((\sqrt {\alpha p_{1}}-\sqrt {\gamma })^{2}\), respectively. It remains to compute the exact bid values that satisfy these constraints and minimize the price of anarchy. This is done in the following non-linear mathematical program

$$\begin{array}{@{}rcl@{}} \text{minimize} & & \frac{p_{1}p_{2}\left( \frac{\gamma}{\gamma+\delta}+\alpha\frac{\delta}{\gamma+ \delta}\right)+ p_{1}(1-p_{2})+\alpha(1-p_{1})p_{2}}{p_{1}+\alpha (1-p_{1})p_{2}}\\ \text{subject to:} & & p_{2} \frac{\gamma}{\gamma+\delta}-p_{2} \gamma \geq (\sqrt{p_{2}}-\sqrt{\delta})^{2}\\ & & \alpha p_{1}\frac{\delta}{\gamma+\delta}-p_{1} \delta \geq (\sqrt{\alpha p_{1}}-\sqrt{\gamma})^{2}\\ & & \gamma, \delta \geq 0, 0\leq \alpha \leq 1, 0\leq p_{1}, p_{2} \leq 1 \end{array} $$

which has been solved using Matlab to give an upper bound of 0.7154 for α = 0.2913, γ = 0.1071, δ = 0.1510, p 1 = 0.6682, and p 2 = 0.7616. □

Also, recall that we have assumed that bidders have independent valuations. This is a typical assumption in the Bayes-Nash price of anarchy literature [1, 4, 7, 11, 20, 22, 23] with [2] being the only exception we are aware of. Unfortunately, our proof of the pure Bayes-Nash price of anarchy bound does not carry over to the case of correlated valuations either (for the same reason mentioned above). Still, we have not been able to find any counter-example with non-constant price of anarchy in this setting. Again, what is the price of anarchy in this case? These questions are interesting in the budget-constrained setting as well.

Another important issue in the budget-constrained setting is related to our refinement of the effective welfare benchmark for random allocations. Even though our definition naturally extends the one for deterministic allocations, an even more natural definition of the effective welfare for a random allocation d would be \(\text {EW}(d) = {\sum }_{i}{\mathbb {E}\left [\min \{v_{i}(d_{i}),c_{i}\}\right ]}\) (as opposed to the definition \(\text {EW}(d) = {\sum }_{i}{\min \{\mathbb {E}\left [v_{i}(d_{i})\right ],c_{i}\}}\) that we have adopted); this extends to the Bayesian setting accordingly. Unfortunately, the main obstacle that did not allow us to use this more natural definition is that our techniques cannot establish a relation between the utility of a bidder i and the quantity \(\mathbb {E}\left [\min \{v_{i}(d_{i}),c_{i}\}\right ]\); this is necessary in order to bound the price of anarchy and this has been our approach in the proofs of Theorems 4.1 and 4.2 for the substantially different quantity \(\min \{\mathbb {E}\left [v_{i}(d_{i})\right ],c_{i}\}\). Interestingly, we have not found any upper bound on the price of anarchy over coarse-correlated or Bayes-Nash equilibria under these alternative definitions for the effective welfare. Is the price of anarchy still bounded by a constant? This question deserves further investigation.