On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

Abstract

We study the efficiency of the proportional allocation mechanism, that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4 / 3 bound for pure equilibria [12]. Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.

G. Christodoulou—This author was supported by EPSRC grants P/M008118/1 and EP/K01000X/1.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Allocating network resources, like bandwidth, among agents is a canonical problem in the network optimization literature. A traditional model for this problem was proposed by Kelly [14], where allocating these infinitely divisible resources is treated as a market with prices. More precisely, agents in the system submit bids on resources to express their willingness to pay. After soliciting the bids, the system manager prices each resource with an amount equal to the sum of bids on it. Then the agents buy portions of resources proportional to their bids by paying the corresponding prices. This mechanism is known as the proportional allocation mechanism or Kelly mechanism in the literature.

The proportional allocation mechanism is widely used in network pricing and has been implemented for allocating computing resources in several distributed systems [5]. In practice, each agent has different interests for different subsets and fractions of the resources. This can be expressed via a valuation function of the resource allocation vector, that is typically private knowledge to each agent. Thus, agents may bid strategically to maximize their own utilities, i.e., the difference between their valuations and payments. Johari and Tsitsiklis [12] observed that this strategic bidding in the proportional allocation mechanism leads to inefficient allocations, that do not maximize social welfare. On the other hand, they showed that this efficiency loss is bounded when agents’ valuations are concave. More specifically, they proved that the proportional allocation game admits a unique pure equilibrium with Price of Anarchy (PoA) [15] at most 4/3.

An essential assumption used by Johari and Tsitsiklis is that agents have complete information of each other’s valuations. However, in many realistic scenarios, the agents are only partially informed. A standard way to model incomplete information is by using the Bayesian framework, where the agents’ valuations are drawn independently from some publicly known distribution, that in a sense, represents the agents’ beliefs. A natural question is whether the efficiency loss is still bounded in the Bayesian setting. We give a negative answer to this question by showing that the PoA over Bayesian equilibria is at least $\sqrt{m}/2$ where m is the number of resources. This result complements the current study by Caragiannis and Voudouris [2], where the PoA of single-resource proportional allocation games is shown to be at most 2 in the Bayesian setting.

Non-concave valuation functions were studied by Syrgkanis and Tardos [20] for both complete and incomplete information games. They showed that, when agents’ valuations are lattice-submodular, the PoA for coarse correlated and Bayesian Nash equilibria is at most 3.73, by applying their general smoothness framework. In this paper, we study subadditive valuations [8] that is a superclass of lattice submodular functions. We prove that the PoA over Bayesian Nash equilibria is at most 2. Moreover, we show optimality of the proportional allocation mechanism, by showing that this bound is tight and cannot be improved by any simple mechanism, as defined in the recent framework of Roughgarden [19].

Next, we switch to the setting where agents are constrained by budgets, that represent the maximum payment they can afford. We prove that the PoA of the proportional allocation mechanism is at most $1+\phi \approx 2.618$, where $\phi$ is the golden ratio. The previously best known bound was 2.78 and for a single resource due to [2]. Finally, we consider the polyhedral environment that was previously studied by Nguyen and Tardos in [16], where they proved that pure equilibria are at least $75\,\%$ efficient with concave valuations. We prove that the PoA is exactly 2 for agents with subadditive valuations.

Related Work. The efficiency of the proportional allocation mechanism has been extensively studied in the literature of network resource allocation. Besides the work mentioned above, Johari and Tsitsiklis [13] studied a more general class of scale-free mechanisms and proved that the proportional allocation mechanism achieves the best PoA in this class. Zhang [21] and Feldman et al. [10] studied the efficiency and fairness of the proportional allocation mechanism, when agents aim at maximizing non quasi-linear utilities subject to budget constraints. Correa, Schulz and Stier-Moses [6] showed a relationship in the efficiency loss between proportional allocation mechanism and non-atomic selfish routing for not necessarily concave valuation functions.

There is a line of research studying the PoA of simple auctions for selling indivisible goods (see [1, 3, 11, 20]). Recently, Feldman et al. [9] showed tighter upper bounds for simultaneous first and second price auctions when the agents have subadditive valuations. Christodoulou et al. [4] showed matching lower bounds for simultaneous first price auctions, and Roughgarden [19] proved general lower bounds for the PoA of all simple auctions, by using the corresponding computational or communication lower bounds of the underlying allocation problem.

2 Preliminaries

There are n agents who compete for m divisible resources with unit supply. Every agent $i\in [n]$ has a valuation function $v_i: [0,1]^m \rightarrow \mathbb R_+$, where [n] denotes the set $\{1,2,\dots ,n\}$. The valuations are normalized as $v_i(\mathbf {0})=0$, and monotonically non-decreasing, that is, for every $\mathbf {x},\mathbf {x}' \in [0,1]^m$, where $\mathbf {x}=(x_j)_j, \mathbf {x}'=(x'_j)_j$ and $\forall j\in [m] \; x_j\le x'_j$, we have $v_i(\mathbf {x})\le v_i(\mathbf {x}')$. Let $\mathbf {x}+\mathbf {y}$ be the componentwise sum of two vectors $\mathbf {x}$ and $\mathbf {y}$.

Definition 1

A function $v: [0,1]^m\rightarrow \mathbb {R}_{\ge 0}$ is subadditive if, for all $\mathbf {x},\mathbf {y}\in [0,1]^m$, such that $\mathbf {x}+\mathbf {y}\in [0,1]^m$, it is $v(\mathbf {x}+ \mathbf {y})\le v(\mathbf {x})+v(\mathbf {y})$.

Remark

Lattice submodular functions used in [20] are subadditive. In the case of a single variable (single resource), any concave function is subadditive; more precisely, concave functions are equivalent to lattice submodular functions in this case. However, concave functions of many variables may not be subadditive [18].

In the Bayesian setting, the valuation of each agent i is drawn from a set of possible valuations $V_i$, according to some known probability distribution $D_i$. We assume that $D_i$’s are independent, but not necessarily identical over the agents.

A mechanism can be represented by a tuple $(\mathbf {x},\mathbf {q})$, where $\mathbf {x}$ specifies the allocation of resources and $\mathbf {q}$ specifies the agents’ payments. In the mechanism, every agent i submits a non-negative bid $b_{ij}$ for each resource j. The proportional allocation mechanism determines the allocation $x_i=(x_{ij})_j$ and payment $q_i$, for each agent i, as follows: $x_{ij}=\frac{b_{ij}}{\sum _{k\in [n]}b_{kj}}$, $q_i=\sum _{j\in [m]}b_{ij}.$ When all agents bid 0, the allocation can be defined arbitrarily, but consistently.

Nash Equilibrium. We denote by $\mathbf {b}=(b_1,\ldots ,b_n)$ the strategy profile of all agents, where $b_i=(b_{i1},\ldots ,b_{im})$ denotes the pure bids of agent i for the m resources. By $\mathbf {b}_{-i}=(b_1,\ldots ,b_{i-1},b_{i+1},\ldots ,b_n)$ we denote the strategies of all agents except for i. Any mixed, correlated, coarse correlated or Bayesian strategy $B_i$ of agent i is a probability distribution over $b_i$. For any strategy profile $\mathbf {b}$, $\mathbf {x}(\mathbf {b})$ denotes the allocation and $\mathbf {q}(\mathbf {b})$ the payments under the strategy profile $\mathbf {b}$. The utility $u_i$ of agent i is defined as the difference between her valuation for the received allocation and her payment: $u_i(\mathbf {x}(\mathbf {b}),\mathbf {q}(\mathbf {b}))=u_i(\mathbf {b})=v_i(x_i(\mathbf {b}))-q_i(\mathbf {b})$.

Definition 2

A bidding profile $\mathbf {B}$ forms the following equilibrium if for every agent i and all bids $b'_i$:

Pure Nash equilibrium: $\mathbf {B}=\mathbf {b}$, $u_i(\mathbf {b})\ge u_i(b'_i, \mathbf {b}_{-i})$.

Mixed Nash equilibrium: $\mathbf {B}=\times _i B_i$, $\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(\mathbf {b})]\ge \mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(b'_i,\mathbf {b}_{-i})]$.

Correlated equilibrium: $\mathbf {B}=\left( B_i\right) _i$, $\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(\mathbf {b})|b_i]\ge \mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(b'_i,\mathbf {b}_{-i})|b_i]$.

Coarse correlated equilibrium: $\mathbf {B}=\left( B_i\right) _i$, $\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(\mathbf {b})]\ge \mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(b'_i,\mathbf {b}_{-i})]$.

Bayesian Nash equilibrium: $\mathbf {B}(\mathbf {v})=\times _iB_i(v_i)$, $\mathbb {E}_{\mathbf {v}_{-i},\mathbf {b}}[u_i(\mathbf {b})]\ge \mathbb {E}_{\mathbf {v}_{-i},\mathbf {b}} [u_i(b'_i,\mathbf {b}_{-i})]$.

The first four classes of equilibria are in increasing order of inclusion. Moreover, any mixed Nash equilibrium is also a Bayesian Nash equilibrium.

Price of Anarchy (PoA). Our global objective is to maximize the sum of the agents’ valuations for their received allocations, i.e., to maximize the social welfare $\mathrm {SW}(\mathbf {x})=\sum _{i\in [n]} v_i(x_i).$ Given the valuations, $\mathbf {v}$, of all agents, there exists an optimal allocation $\mathbf {o}^{\mathbf {v}}=\mathbf {o}=(o_1,\ldots ,o_n)$, such that $\mathrm {SW}(\mathbf {o})=\max _{\mathbf {x}} \mathrm {SW}(\mathbf {x})$. By $o_i = (o_{i1}, \ldots , o_{im})$ we denote the optimal allocation to agent i. For simplicity, we use $\mathrm {SW}(\mathbf {b})$ and $v_i(\mathbf {b})$ instead of $\mathrm {SW}(\mathbf {x}(\mathbf {b}))$ and $v_i(x_i(\mathbf {b}))$, whenever the allocation rule $\mathbf {x}$ is clear from the context. We also use shorter notation for expectations, e.g. we use $\mathbb {E}_{\mathbf {v}}$ instead of $\mathbb {E}_{\mathbf {v}\sim \mathbf {D}}$, $\mathbb {E}[u_i(\mathbf {b})]$ instead of $\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(\mathbf {b})]$ and $u(\mathbf {B})$ for $\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u(\mathbf {b})]$ whenever $\mathbf {D}$ and $\mathbf {B}$ are clear from the context.

Definition 3

Let $\mathcal {I}([n],[m],\mathbf {v})$ be the set of all instances, i.e., $\mathcal {I}([n],[m],\mathbf {v})$ includes the instances for every set of agents and resources and any possible valuations that the agents might have for the resources. We define the pure, mixed, correlated, coarse correlated and Bayesian Price of Anarchy, PoA, as

$${\text {PoA}} = \max _{I \in \mathcal {I}} \max _{\mathbf {B}\in \mathcal {E}(I)} \frac{\mathbb {E}_{\begin{array}{c} \mathbf {v} \end{array}}[\mathrm {SW}(\mathbf {o})]}{\mathbb {E}_{\begin{array}{c} \mathbf {v}, \mathbf {b}\sim \mathbf {B} \end{array}}[\mathrm {SW}(\mathbf {b})]},$$

where ${}\mathcal {E}(I)$ is the set of pure Nash, mixed Nash, correlated, coarse correlated or Bayesian Nash equilibria for the specific instance $I \in \mathcal {I}$, respectively¹.

Budget Constraints. We also consider the setting where agents are budget-constrained. That is, the payment of each agent i cannot be higher than $c_i$, where $c_i$ is a non-negative value denoting agent i’s budget. Following [2, 20], we use Effective Welfare as the benchmark: $\mathrm {EW}(\mathbf {x}) = \sum _i \min \{v_i(x_i),c_i\}$. In addition, for any randomized allocation $\mathbf {x}$, the expected effective welfare is defined as: $\mathbb {E}_{\mathbf {x}}[\mathrm {EW}(\mathbf {x})] = \sum _i \min \{\mathbb {E}_{\mathbf {x}}[v_i(x_i)],c_i\}.$

3 Concave Valuations

In this section, we show that for concave valuations on multiple resources, Bayesian equilibria can be arbitrarily inefficient. More precisely, we prove that the Bayesian PoA is $\varOmega (\sqrt{m})$ in contrast to the constant bound for pure equilibria [12]. Therefore, there is a big gap between complete and incomplete information settings. We state our main theorem in this section as follows.

Theorem 4

When valuations are concave, the PoA of the proportional allocation mechanism for Bayesian equilibria is at least $\frac{\sqrt{m}}{2}$.

Proof

We consider an instance with m resources and 2 agents with the following concave valuations. $v_1(\mathbf {x})=\min _j\{x_j\}$ and $v_2(\mathbf {x})$ is drawn from a distribution $D_2$, such that some resource $j\in [m]$ is chosen uniformly at random and then $v_2(\mathbf {x})=x_j/\sqrt{m}$. Let $\delta =1/(\sqrt{m}+1)^2$. We claim that $\mathbf {b}(\mathbf {v}) = (b_1,b_2(v_2))$ is a pure Bayesian Nash equilibrium, where $\forall j\in [m]$, $b_{1j}=\sqrt{\delta / m} - \delta$ and, if $j\in [m]$ is the resource chosen by $D_2$, $b_{2j}(v_2)=\delta$ and for all $j'\ne j$ $b_{2j'}=0$.

Under this bidding profile, agent 1 bids the same value for all resources, and agent 2 only bids positive value for a single resource associated with her valuation. Suppose that agent 2 has positive valuation for resource j, i.e., $v_2(\mathbf {x})=x_j/\sqrt{m}$. Then the rest $m-1$ resources are allocated to agent 1 and agents are competing for resource j. Bidder 2 has no reason to bid positively for any other resource. If she bids any value $b'_{2j}$ for resource j, her utility would be $u_2(\mathbf {b}_1,b'_{2j}) = \frac{1}{\sqrt{m}}\frac{b'_{2j}}{b_{1j}+b'_{2j}} - b'_{2j}$, which is maximized for $b'_{2j} = \sqrt{\frac{b_{1j}}{\sqrt{m}}}-b_{1j}$. For $b_{1j}=\sqrt{\delta / m} - \delta$, the utility of agent 2 is maximized for $b'_{2j} = 1/(\sqrt{m}+1)^2=\delta$ by simple calculations.

Since $v_1(\mathbf {x})$ equals the minimum of $\mathbf {x}$’s components, agent 1’s valuation is completely determined by the allocation of resource j. So the expected utility of agent 1 under $\mathbf {b}$ is $\mathbb {E}_{v_2}[u_1(\mathbf {b})] = \frac{\sqrt{\delta / m} - \delta }{\sqrt{\delta / m} - \delta +\delta }-m(\sqrt{\delta / m} - \delta )= (1-\sqrt{m\delta })^2 = \frac{1}{\left( \sqrt{m}+1\right) ^2}=\delta$. Suppose now that agent 1 deviates to $b'_1 = (b'_{11}, \ldots , b'_{1m})$.

$$\begin{aligned} \mathbb {E}_{v_2}[u_1(b'_1,b_2)]&= \frac{1}{m} \sum _j \frac{b'_{1j}}{b'_{1j}+\delta } - \sum _j b'_{1j} = \frac{1}{m} \sum _j \left( \frac{b'_{1j}}{b'_{1j}+\delta } - m \cdot b'_{1j}\right) \\&\le \frac{1}{m} \sum _j \left( \frac{\sqrt{\delta /m} - \delta }{\sqrt{\delta /m}} - m \cdot (\sqrt{\delta /m} - \delta )\right) \\&= \frac{1}{m} \sum _j \left( 1-2 \sqrt{m\cdot \delta } + m\cdot \delta \right) = \frac{1}{m} \sum _j \left( 1 - \sqrt{m\cdot \delta } \right) ^2\\&= \frac{1}{m} \sum _j \left( \frac{1}{\sqrt{m}+1} \right) ^2 =\delta = \mathbb {E}_{v_2}[u_1(\mathbf {b})]. \end{aligned}$$

The inequality comes from the fact that $\frac{b'_{1j}}{b'_{1j}+\delta } - m \cdot b'_{1j}$ is maximized for $b'_{1j} = \sqrt{\delta /m} - \delta$. So we conclude that $\mathbf {b}$ is a Bayesian equilibrium.

Finally we compute the PoA. The expected social welfare under $\mathbf {b}$ is $\mathbb {E}_{v_2}[\mathrm {SW}(\mathbf {b})]= \frac{\sqrt{\delta / m} - \delta }{\sqrt{\delta / m} - \delta +\delta } + \frac{1}{\sqrt{m}}\frac{\delta }{\sqrt{\delta / m} - \delta +\delta } = 1-\sqrt{m\delta }+\sqrt{\delta } = \frac{2}{\sqrt{m}+1} < \frac{2}{\sqrt{m}}.$ But the optimal social welfare is 1 by allocating to agent 1 all resources. So, PoA $\ge \frac{\sqrt{m}}{2}.$    ${\square }$

4 Subadditive Valuations

In this section, we focus on agents with subadditive valuations. We first show that the proportional allocation mechanism is at least $50\,\%$ efficient for coarse correlated equilibria and Bayesian Nash equilibria, i.e., $\mathrm {PoA} \le 2$. Then we show that this bound is tight and cannot be improved by any simple mechanism.

Upper Bound. A common approach to prove PoA bounds is to find a deviation with proper utility bounds and then use the definition of Nash equilibrium to bound agents’ utilities at equilibrium. The bidding strategy described in the following lemma is for this purpose.

Lemma 5

Let $\mathbf {v}$ be any subadditive valuation profile and $\mathbf {B}$ be some randomized bidding profile. For any agent i, there exists a randomized bidding strategy $a_i(\mathbf {v},\mathbf {B}_{-i})$ such that: $\sum _iu_i(a_i(\mathbf {v},\mathbf {B}_{-i}), \mathbf {B}_{-i})\ge \frac{1}{2} \sum _iv_i(o_i^{\mathbf {v}})-\sum _i\sum _j\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[b_{ij}].$

Proof

Let $p_{ij}$ be the sum of the bids of all agents except i on resource j, i.e., $p_{ij}=\sum _{k\ne i}b_{kj}$. Note that $p_{ij}$ is a random variable that depends on $\mathbf {b}_{-i}\sim \mathbf {B}_{-i}$. Let $P_i$ be the propability distribution of $p_i=(p_{ij})_j$. Inspired by [9], we consider the bidding strategy $a_i(\mathbf {v},\mathbf {B}_{-i}) = (o_{ij}^{\mathbf {v}}\cdot b'_{ij})_j$, where $b'_i\sim P_i$. Then, $u_i(a_i(\mathbf {v},\mathbf {B}_{-i}), \mathbf {B}_{-i})$ is

$$\begin{aligned}&\mathbb {E}_{b'_i\sim P_i}\mathbb {E}_{p_i\sim P_i}\left[ v_i\left( \left( \frac{o^{\mathbf {v}}_{ij}b'_{ij}}{o^{\mathbf {v}}_{ij}b'_{ij}+p_{ij}}\right) _j\right) -o^{\mathbf {v}}_i\cdot b'_i\right] \\ \ge&\frac{1}{2} \cdot \mathbb {E}_{p_i\sim P_i}\mathbb {E}_{b'_i\sim P_i}\left[ v_i\left( \left( \frac{o^{\mathbf {v}}_{ij}b'_{ij}}{o^{\mathbf {v}}_{ij}b'_{ij}+p_{ij}}+\frac{o^{\mathbf {v}}_{ij}p_{ij}}{o^{\mathbf {v}}_{ij}p_{ij}+b'_{ij}}\right) _j\right) \right] -\mathbb {E}_{p_i\sim P_i}[o^{\mathbf {v}}_i\cdot p_i]\\ \ge&\frac{1}{2} \cdot \mathbb {E}_{p_i\sim P_i}\mathbb {E}_{b'_i\sim P_i}\left[ v_i\left( \left( \frac{o^{\mathbf {v}}_{ij}(b'_{ij}+p_{ij})}{b'_{ij}+p_{ij}}\right) _j\right) \right] -\mathbb {E}_{p_i\sim P_i}[o^{\mathbf {v}}_i\cdot p_i]\\ =&\frac{1}{2} \cdot v_i(o^{\mathbf {v}}_i)-\sum _j \sum _{k\ne i}\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[o^{\mathbf {v}}_{ij}\cdot b_{kj}] \end{aligned}$$

The first inequality follows by swapping $p_{ij}$ and $b'_{ij}$ and using the subadditivity of $v_i$. The second inequality comes from the fact that $o^{\mathbf {v}}_{ij}\le 1$. The lemma follows by summing up over all agents and the fact that $\sum _{i\in [n]}o_{ij}^{\mathbf {v}}= 1$.   ${\square }$

Theorem 6

The coarse correlated PoA of the proportional allocation mechanism with subadditive agents is at most 2.

Proof

Let $\mathbf {B}$ be any coarse correlated equilibrium (note that $\mathbf {v}$ is fixed). By Lemma 5 and the definition of the coarse correlated equilibrium, we have

$$ \sum _iu_i(\mathbf {B})\ge \sum _iu_i(a_i(\mathbf {v},\mathbf {B}_{-i}), \mathbf {B}_{-i})\ge \frac{1}{2} \sum _iv_i(o_i)-\sum _i\sum _{j}\mathbb {E}[b_{ij}]$$

By rearranging terms, $\mathrm {SW}(\mathbf {B})=\sum _iu_i(\mathbf {B})+\sum _i\sum _{j}\mathbb {E}[b_{ij}]\ge \frac{1}{2} \cdot \mathrm {SW}(\mathbf {o})$.   $\square$

Theorem 7

The Bayesian PoA of the proportional allocation mechanism with subadditive agents is at most 2.

Proof

Let $\mathbf {B}$ be any Bayesian Nash Equilibrium and let $v_{i}\sim D_{i}$ be the valuation of each agent i drawn independently from $D_i$. We denote by $\mathbf {C}=(C_1,C_2,\ldots ,C_n)$ the bidding distribution in $\mathbf {B}$ which includes the randomness of both the bidding strategy $\mathbf {b}$ and of the valuations $\mathbf {v}$. The utility of agent i with valuation $v_i$ can be expressed by $u_i(\mathbf {B}_i(v_i), \mathbf {C}_{-i})$. It should be noted that $\mathbf {C}_{-i}$ does not depend on some particular $\mathbf {v}_{-i}$, but merely on $\mathbf {D}_{-i}$ and $\mathbf {B}_{-i}$. For any agent i and any subadditive valuation $v_i\in V_i$, consider the deviation $a_i(v_i;\mathbf {w}_{-i},\mathbf {C}_{-i})$ as defined in Lemma 5, where $\mathbf {w}_{-i}\sim \mathbf {D}_{-i}$. By the definition of the Bayesian Nash equilibrium, we obtain

$$\mathbb {E}_{\mathbf {v}_{-i}}[u^{v_i}_i(\mathbf {B}_i(v_i),\mathbf {B}_{-i}(\mathbf {v}_{-i}))]= u^{v_i}_i(\mathbf {B}_i(v_i),\mathbf {C}_{-i}) \ge \mathbb {E}_{\mathbf {w}_{-i}}[u^{v_i}_i(a_i(v_i;\mathbf {w}_{-i},\mathbf {C}_{-i}), \mathbf {C}_{-i})].$$

By taking expectation over $v_i$ and summing up over all agents,

$$\begin{aligned}&\sum _i \mathbb {E}_{\mathbf {v}}[u_i(\mathbf {B}(\mathbf {v}))] \ge \sum _i\mathbb {E}_{v_i,\mathbf {w}_{-i}}[u^{v_i}_i(a_i(v_i;\mathbf {w}_{-i},\mathbf {C}_{-i}),\mathbf {C}_{-i})]\\ =&\mathbb {E}_{\mathbf {v}}\left[ \sum _iu_i^{v_i}(a_i(\mathbf {v},\mathbf {C}_{-i}), \mathbf {C}_{-i})\right] \ge \frac{1}{2}\cdot \sum _i\mathbb {E}_{\mathbf {v}}[v_i(o_i^{\mathbf {v}})]-\sum _i\sum _j\mathbb {E}[b_{ij}] \end{aligned}$$

So, $\mathbb {E}_{\mathbf {v}}[\mathrm {SW}(\mathbf {B}(\mathbf {v}))]= \sum _i\mathbb {E}_{\mathbf {v}}[u_i(\mathbf {B}(\mathbf {v}))]+ \sum _i\sum _j\mathbb {E}[b_{ij}]\ge \frac{1}{2} \cdot \mathbb {E}_{\mathbf {v}}[\mathrm {SW}(\mathbf {o}^{\mathbf {v}})].$    ${\square }$

Lower Bound. Now, we show a lower bound that applies to all simple mechanisms, where the bidding space has size (at most) sub-doubly-exponential in m. More specifically, we apply the general framework of Roughgarden [19], for showing lower bounds on the price of anarchy for all simple mechanisms, via communication complexity reductions with respect to the underlying optimization problem. In our setting, the problem is to maximize the social welfare by allocating divisible resources to agents with subadditive valuations. We proceed by proving a communication lower bound for this problem in the following lemma.

Lemma 8

For any constant $\varepsilon >0$, any $(2-\varepsilon )$-approximation (non-deterministic) algorithm for maximizing social welfare in resource allocation problem with subadditive valuations, requires an exponential amount of communication.

Proof

We prove this lemma by reducing the communication lower bound for combinatorial auctions with general valuations (Theorem 3 of [17]) to our setting (see also [7] for a reduction to combinatorial auctions with subadditive agents).

Nisan [17] used an instance with n players and m items, with $n < m^{1/2-\varepsilon }$. Each player i is associated with a set $T_i$, with $|T_i| = t$ for some $t>0$. At every instance of this problem, the players’ valuations are determined by sets $I_i$ of bundles, where $I_i \subseteq T_i$ for every i. Given $I_i$, player i’s valuation on some subset S of items is $v_i(S)=1$, if there exists some $R\in I_i$ such that $R\subseteq S$, otherwise $v_i(S)=0$. In [17], it was shown that distinguishing between instances with optimal social welfare of n and 1, requires t bits of communication. By choosing t exponential in m, their theorem follows.

We prove the lemma by associating any valuation v of the above combinatorial auction problem, to some appropriate subadditive valuation $v'$ for our setting. For any player i and any fractional allocation $\mathbf {x}= (x_1,\ldots , x_m)$, let $A_{x_i} = \{j|x_{ij} > \frac{1}{2}\}$. We define $v'_i(x_i)=v_i(A_{x_i})+1$ if $x_i\ne \mathbf {0}$ and $v'_i(x_i)=0$ otherwise. It is easy to verify that $v'_i$ is subadditive. Notice that $v'_i(x) =2$ only if there exists $R\in I_i$ such that player i is allocated a fraction higher than 1 / 2 for every resource in R. The value 1 / 2 is chosen such that no two players are assigned more than that fraction from the same resource. This corresponds to the constraint of an allocation in the combinatorial auction where no item is allocated to two players.

Therefore, in the divisible goods allocation problem, distinguishing between instances where the optimal social welfare is 2n and $n+1$ is equivalent to distinguishing between instances where the optimal social welfare is n and 1 in the corresponding combinatorial auction and hence requires exponential, in m, number of communication bits.   $\square$

The PoA lower bound follows the general reduction described in [19].

Theorem 9

The PoA of $\epsilon$-mixed Nash equilibria² of every simple mechanism, when agents have subadditive valuations, is at least 2.

Remark

This result only holds for $\epsilon$-mixed Nash equilibria. Considering exact Nash equilibria, we show a lower bound for all scale-free mechanisms including the proportional allocation mechanism in the full version.

5 Budget Constraints

In this section, we switch to scenarios where agents have budget constraints. We use as a benchmark the effective welfare similarly to [2, 20]. We compare the effective welfare of the allocation at equilibrium with the optimal effective welfare. We prove an upper bound of $\phi + 1\approx 2.618$ for coarse correlated equilibria, where $\phi = \frac{\sqrt{5}+1}{2}$ is the golden ratio. This improves the previously known 2.78 upper bound in [2] for a single resource and concave valuations.

To prove this upper bound, we use the fact that in the equilibrium there is no profitable unilateral deviation, and, in particular, the utility of agent i obtained by any pure deviating bid $a_i$ should be bounded by her budget $c_i$, i.e., $\sum _{j \in [m]} a_{ij} \le c_i$. We define $v^{c}$ to be the valuation v suppressed by the budget c, i.e., $v^{c}(x) = \min \{v(x),c\}$. Note that $v^c$ is also subadditive since v is subadditive. For a fixed pair $(\mathbf {v},\mathbf {c})$, let $\mathbf {o}= (o_1,\ldots ,o_n)$ be the allocation that maximizes the effective welfare. For a fixed agent i and a vector of bids $\mathbf {b}_{-i}$, we define the vector $p_i$ as $p_i = \sum _{k\ne i}b_k$. We first show the existence of a proper deviation.

Lemma 10

For any subadditive agent i, and any randomized bidding profile $\mathbf {B}$, there exists a randomized bid $a_i(\mathbf {B}_{-i})$, such that for any $\lambda \ge 1$, it is

$$u_i(a_i(\mathbf {B}_{-i}), \mathbf {B}_{-i})\ge \frac{ v_i^{c_i}\left( o_i \right) }{\lambda +1} - \frac{\sum _{j\in [m]}\sum _{k\in [n]}o_{ij}\mathbb {E}[b_{kj}]}{\lambda }.$$

Moreover, if $\hat{a}_i$ is any pure strategy in the support of $a_i(\mathbf {B}_{-i})$, then $\sum _j \hat{a}_{ij} \le c_i$.

Proof

In order to find $a_i(B_{-i})$, we define the truncated bid vector $\tilde{\mathbf {b}}_{-i}$ as follows. For any set $S\subseteq [m]$ of resources, we denote by $\mathbf {1}_S$ the indicator vector w.r.t. S, such that $x_j = 1$ for $j \in S$ and $x_j = 0$ otherwise. For any vector $p_i$ and any $\lambda >0$, let $T:=T(\lambda ,p_i)$ be a maximal subset of resources such that, $v_i^{c_i}(\mathbf {1}_T) < \frac{1}{\lambda } \sum _{j \in T} o_{ij}p_{ij}$. For every $k\ne i$, if $j \in T$, then $\tilde{b}_{kj} = 0$, otherwise $\tilde{b}_{kj} = b_{kj}$. Similarly, $\tilde{p}_i = \sum _{k\ne i}\tilde{b}_k$. Moreover, if $\mathbf {b}_{-i} \sim \mathbf {B}_{-i}$, then $p_i$ is an induced random variable with distribution denoted by $P_i$. We further define distributions $\tilde{\mathbf {B}}_{-i}$ and $\tilde{P}_i$, as $\tilde{\mathbf {B}}_{-i} = \{\tilde{\mathbf {b}}_{-i}|\mathbf {b}_{-i} \sim \mathbf {B}_{-i}\}$ and $\tilde{P}_i = \{\tilde{p}_i|p_i\sim P_i\}$.

Now consider the following bidding strategy $a_i(\mathbf {B}_{-i})$: sampling $b'_i\sim \tilde{P}_i$ and bidding $a_{ij}=\frac{1}{\lambda } o_{ij} b'_{ij}$ for each resource j. We first show $\sum _{j\in [m]}a_{ij}\le c_i$. It is sufficient to show that $v_i^{c_i}(\mathbf {1}_{[m] \setminus T}) \ge \sum _{j\notin T} a_{ij}$ since $c_i\ge v_i^{c_i}(\mathbf {1}_{[m] \setminus T})$. For the sake of contradiction suppose $v_i^{c_i}(\mathbf {1}_{[m] \setminus T}) < \sum _{j \notin T} a_{ij}$. Then, by the definition of T and $\tilde{p}_i$, $v_i^{c_i}(\mathbf {1}_{[m]}) \le v_i^{c_i}(\mathbf {1}_{T}) + v_i^{c_i}(\mathbf {1}_{[m] \setminus T}) < \sum _{j\in T} a_{ij}+\sum _{j \notin T} a_{ij}=\frac{1}{\lambda } \sum _{j \in [m]} o_{ij}p_{ij}$,which contradicts the maximality of T.

Next we show for any bid $b_i$ and $\lambda >0$,

$$\begin{aligned} v_i^{c_i}(x_i(b_i, \mathbf {B}_{-i})) + \frac{1}{\lambda } \sum _{j \in [m]}o_{ij} \mathbb {E}_{p_i \sim P_i}[p_{ij}] \ge v_i^{c_i}(x_i(b_i, \tilde{\mathbf {B}}_{-i})) + \frac{1}{\lambda } \sum _{j \in [m]}o_{ij}\mathbb {E}_{\tilde{p}_i \sim \tilde{P}_i}[\tilde{p}_{ij}] \end{aligned}$$

(1)

Observe that $x_i(b_i,\tilde{\mathbf {b}}_{-i}) \le x_i(b_i,\mathbf {b}_{-i}) + \mathbf {1}_T$. Therefore, and by the definitions of T and $\tilde{p}_i$, $v_i^{c_i}(x_i(b_i,\tilde{\mathbf {b}}_{-i})) \le v_i^{c_i}(x_i(b_i,\mathbf {b}_{-i})) + v_i^{c_i}(\mathbf {1}_T)\le v_i^{c_i}(x_i(b_i,\mathbf {b}_{-i})) +\frac{1}{\lambda } \sum _{j \in T} o_{ij}p_{ij} = v_i^{c_i}(x_i(b_i,\mathbf {b}_{-i})) +\frac{1}{\lambda } \sum _{j \in [m]} o_{ij}p_{ij} - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij}\tilde{p}_{ij}$. The claim follows by rearranging terms and taking the expectation of $\mathbf {b}_{-i}$, $\tilde{\mathbf {b}}_{-i}$, $p_i$ and $\tilde{p}_i$ over $\mathbf {B}_{-i}$, $\tilde{\mathbf {B}}_{-i}$, $P_i$ and $\tilde{P}_i$, respectively.

$$\begin{aligned} \mathbb {E}_{b'_i \sim \tilde{P_i}}&\left[ u_i\left( \frac{1}{\lambda } o_i b'_i,\mathbf {B}_{-i}\right) \right] = \mathbb {E}_{b'_i \sim \tilde{P_i}}\left[ v_i\left( \frac{1}{\lambda } o_i b'_i,\mathbf {B}_{-i}\right) \right] - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij} \mathbb {E}_{b'_i \sim \tilde{P_i}}\left[ b'_{ij}\right] \\\ge & {} \mathbb {E}_{b'_i \sim \tilde{P_i}}\left[ v_i^{c_i}\left( \frac{1}{\lambda } o_i b'_i,\mathbf {B}_{-i}\right) \right] - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij} \mathbb {E}_{\tilde{p}_i \sim \tilde{P_i}}\left[ \tilde{p}_{ij}\right] \quad \mathrm {(by~definition~of}~ {v_i^{c_i}})\\\ge & {} \mathbb {E}_{b'_i \sim \tilde{P_i}}\left[ v_i^{c_i}\left( \frac{1}{\lambda } o_i b'_i,\tilde{\mathbf {B}}_{-i}\right) \right] - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij} \mathbb {E}_{p_i \sim P_i}\left[ p_{ij}\right] \quad \text {(by Inequality (1))}\\\ge & {} \frac{1}{2}\mathbb {E}_{b'_i \sim \tilde{P_i}}\mathbb {E}_{\tilde{p}_i \sim \tilde{P_i}} \left[ v^{c_i}_i\left( \frac{ o_i b'_i}{ o_i b'_i + \lambda \tilde{p}_i}+\frac{o_i \tilde{p}_i}{ o_i \tilde{p}_i + \lambda b'_i}\right) \right] - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij} \sum _{k\ne i} B_{kj}\\&\text{(by } \text{ swapping } b'_i \text{ with } \tilde{p}_i \text{ and } \text{ the } \text{ subadditivity } \text{ of } v_i^{c_i}(\cdot )\text{) }\\\ge & {} \frac{1}{2}\mathbb {E}_{b'_i \sim \tilde{P_i}}\mathbb {E}_{\tilde{p}_i \sim \tilde{P_i}} \left[ v^{c_i}_i\left( o_i \left( \frac{ b'_i}{b'_i + \lambda \tilde{p}_i}+\frac{\tilde{p}_i}{\tilde{p}_i + \lambda b'_i}\right) \right) \right] - \frac{1}{\lambda } \sum _{j \in [m]}\sum _{k\in [n]}o_{ij}\mathbb {E}[b_{kj}]\\\ge & {} \frac{1}{2}v^{c_i}_i\left( \frac{2o_i}{\lambda +1} \right) - \frac{1}{\lambda } \sum _{j \in [m]} o_{ij} \sum _{k} B_{kj} \quad \text{(by } \text{ monotonicity } \text{ of } v^{c_i}_i\text{) }\\\ge & {} \frac{1}{\lambda +1} v^{c_i}_i(o_i)-\frac{1}{\lambda }\sum _{j\in [m]}o_{ij}\sum _{k} B_{kj} \;\left( \text{ subadditivity } \text{ of } v^{c_i}_i\text{; } \frac{2}{\lambda +1} \le 1\right) \end{aligned}$$

For the second inequality, notice that the second term doesn’t depend on $b'_i$, so we apply Lemma 11 for every $b'_i$. For the forth and fifth inequalities, $o_i \le 1$ and $\frac{ b'_i}{ b'_i + \lambda \tilde{p}_i}+\frac{ \tilde{p}_i}{\tilde{p}_i + \lambda b'_i} \ge \frac{2}{\lambda +1}$ for every $b'_i$, $\tilde{p}_i$ and $\lambda \ge 1$.   $\square$

We are ready to show the PoA bound by using the above lemma.

Theorem 11

The coarse correlated PoA for the proportional allocation mechanism when agents have budgets and subadditive valuations, is at most $\phi + 1 \approx 2.618$.

Proof

Suppose $\mathbf {B}$ is a coarse correlated equilibrium. Let A be the set of agents such that for every $i \in A$, $v_i(\mathbf {B}) \le c_i$. For simplicity, we use $v^{c_i}_i(\mathbf {B})$ to denote $\min \{\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[v_i(x_i(\mathbf {b}))],c_i\}$. Then for all $i \notin A$, $v^{c_i}_i(\mathbf {B})=c_i\ge v^{c_i}_i(o_i)$ and $v^{c_i}_i(\mathbf {B})=c_i\ge \sum _{j \in [m]}\mathbb {E}[b_{ij}]$. The latter inequality comes from that agents do not bid higher than their budgets. Let $\lambda =\phi$. So $1-1/\lambda =1/(1+\lambda )$. By taking the linear combination and summing up over all agents not in A, we get

$$\begin{aligned} \sum _{i \notin A}v^{c_i}_i(\mathbf {B})\ge \frac{1}{\lambda +1}\sum _{i \notin A}v^{c_i}_i(o_i) + \frac{1}{\lambda } \sum _{i \notin A}\sum _{j \in [m]}\mathbb {E}[b_{ij}] \end{aligned}$$

(2)

For every $i \in A$, we consider the deviating bidding strategy $a_i(\mathbf {B}_{-i})$ that is described in Lemma 10, then

$$\begin{aligned} v^{c_i}_i(\mathbf {B})= & {} v_i(x_i(\mathbf {B})) = u_i(x_i(\mathbf {B})) + \sum _{j \in [m]}\mathbb {E}[b_{ij}] \ge u_i(a_i(\mathbf {B}_{-i}), \mathbf {B}_{-i}) + \frac{1}{\lambda }\sum _{j \in [m]}\mathbb {E}[b_{ij}]\\\ge & {} \frac{1}{\lambda +1} v_i^{c_i}(o_i)-\frac{1}{\lambda }\sum _{j\in [m]}\sum _{k\in [n]}o_{ij}\mathbb {E}[b_{kj}]+\frac{1}{\lambda } \sum _{j \in [m]}\mathbb {E}[b_{ij}] \end{aligned}$$

By summing up over all $i \in A$ and by combining with inequality (2) we get

$$\begin{aligned}&\sum _{i\in [n]}\min \{v_i(x_i(\mathbf {B})),c_i\}\\\ge & {} \frac{1}{\lambda +1} \sum _{i\in [n]}v^{c_i}_i(o_i)+\frac{1}{\lambda } \sum _{i\in [n]}\sum _{j \in [m]}\mathbb {E}[b_{ij}]- \frac{1}{\lambda } \sum _{i \in A}\sum _{j \in [m]} \sum _{k\in [n]}o_{ij}\mathbb {E}[b_{kj}]\\\ge & {} \frac{1}{\lambda +1} \sum _{i\in [n]}v^{c_i}_i(o_i) \qquad \qquad \left( \text {since }\sum _{i\in A} o_{ij} \le 1\right) \end{aligned}$$

Therefore, the PoA with respect to the effective welfare is at most $\phi + 1$.   $\square$

By applying Jensen’s inequality for concave functions, our upper bound also holds for the Bayesian case with single-resource and concave functions.

Theorem 12

The Bayesian PoA of single-resource proportional allocation games is at most $\phi + 1 \approx 2.618$, when agents have budgets and concave valuations.

Remark

Syrgkanis and Tardos [20], compared the social welfare in the equilibrium with the effective welfare in the optimum allocation. Caragiannis and Voudouris [2] also give an upper bound of 2 for this ratio in the single resource case. We can obtain the same upper bound by replacing $\lambda$ with 1 in the proofs.

6 Polyhedral Environment

In this section, we study the efficiency of the proportional allocation mechanism in the polyhedral environment, that was previously studied by Nguyen and Tardos [16]. We show a tight price of anarchy bound of 2 for agents with subadditive valuations. Recall that, in this setting, the allocation to each agent i is now represented by a single parameter $x_i$, and not by a vector $(x_{i1},\ldots , x_{im})$. In addition, any feasible allocation vector $\mathbf {x}=(x_1,\dots ,x_n)$ should satisfy a polyhedral constraint $A\cdot \mathbf {x}\le \mathbf {1}$, where A is a non-negative $m\times n$ matrix and each row of A corresponds to a different resource, and $\mathbf {1}$ is a vector with all ones. Each agent aims to maximize her utility $u_i=v_i(x_i)-q_i$, where $v_i$ is a subadditive function representing the agent’s valuation. The proportional allocation mechanism determines the following allocation and payments for each agent:

$$x_i(\mathbf {b})=\min _{j:a_{ij}>0}\left\{ \frac{b_{ij}}{a_{ij}\sum _{k\in [n]}b_{kj}}\right\} ;\quad \quad q_i(\mathbf {b})=\sum _{j\in [m]}b_{ij},$$

where $a_{ij}$ is the (i, j)-th entry of matrix A. It is easy to verify that the above allocation satisfies the polyhedral constraints.

Theorem 13

If agents have subadditive valuations, the pure PoA of the proportional allocation mechanism in the polyhedral environment is exactly 2.

Proof

We first show that the PoA is at most 2. Let $\mathbf {o}=\{o_1,\dots ,o_n\}$ be the optimal allocation, $\mathbf {b}$ be a pure Nash Equilibrium, and let $p_{ij}=\sum _{k\ne i}b_{ij}$. For each agent i, consider the deviating bid $b'_i$ such that $b'_{ij}=o_ia_{ij}p_{ij}$ for all resources j. Since $\mathbf {b}$ is a Nash Equilibrium,

$$\begin{aligned} u_i(\mathbf {b})\ge & {} u_i(b'_i, b_{-i})=v_i\left( \min _{j:a_{ij}>0} \left\{ \frac{o_ia_{ij}p_{ij}}{a_{ij}\left( p_{ij}+o_ia_{ij}p_{ij}\right) }\right\} \right) -\sum _{j\in [m]}o_ia_{ij}p_{ij}\\\ge & {} v_i\left( \min _{j:a_{ij}>0}\left\{ \frac{o_i}{1+o_ia_{ij}}\right\} \right) -\sum _{j\in [m]}o_ia_{ij}p_{ij} \ge \frac{1}{2} v_i(o_i)-\sum _{j\in [m]}o_ia_{ij}p_{ij} \end{aligned}$$

The second inequality is true since $A\cdot \mathbf {x}\le \mathbf {1}$, for every allocation $\mathbf {x}$, and therefore $o_ia_{ij} < 1$. The last inequality holds due to subadditivity of $v_i$. By summing up over all agents, we get $\sum _iu_i(\mathbf {b})\ge \frac{1}{2} \sum _iv_i(o_i) -\sum _{j\in [m]}\sum _{i\in [n]}o_ia_{ij}p_{ij} \ge \frac{1}{2} \sum _iv_i(o_i) -\sum _{j\in [m]}\sum _{k\in [n]}b_{kj}$. The last inequality holds due to the fact that $p_{ij}\le \sum _{k\in [n]}b_{kj}$ and $\sum _{i\in [n]}o_ia_{ij}\le 1$. PoA $\le 2$ follows by rearranging the terms.

For the lower bound, consider a game with only two agents and a single resource where the polyhedral constraint is given by $x_1+x_2\le 1$. The valuation of the first agent is $v_1(x)=1+\epsilon \cdot x$, for some $\epsilon <1$ if $x<1$ and $v_1(x)=2$ if $x=1$. The valuation of the second agent is $\epsilon \cdot x$. One can verify that these two functions are subadditive and the optimal social welfare is 2. Consider the bidding strategies $b_1=b_2=\frac{\epsilon }{4}$. The utility of agent 1, when she bids x and agent 2 bids $\frac{\epsilon }{4}$, is given by $1+\epsilon \cdot \frac{x}{x+\epsilon /4}-x$ which is maximized for $x=\frac{\epsilon }{4}$. The utility of agent 2, when she bids x and agent 1 bids $\frac{\epsilon }{4}$, is $\epsilon \cdot \frac{x}{x+\epsilon /4}-x$ which is also maximized when $x=\frac{\epsilon }{4}$. So $(b_1,b_2)$ is a pure Nash Equilibrium with social welfare $1+\epsilon$. Therefore, the PoA converges to 2 when $\epsilon$ goes to 0.   $\square$