Non-Price Equilibria in Markets of Discrete Goods

Introduction

The basic question that Economics deals with is how to “best” allocate scarce resources. The basic answer is that trade can improve everyone’s welfare, and will lead to a market equilibrium: a vector of resource prices that “clear the market” and lead to an efficient allocation. Indeed, Arrow and Debreu and much further work shows that such market equilibria exist in general settings.

Or do they…? An underlying assumption for the existence of price-equilibria is always some notion of “convexity”. While some may feel comfortable with the restriction to “convex economies”, markets of discrete items – arguably the main object of study in computerized markets and auctions – are only rarely “convex” and indeed in most cases do not have any price-based equilibria. What can we predict to happen in such markets? Will these outcomes be efficient in any sense? In this paper we approach this questions by viewing the market as a game, and studying its Nash-equilibria.

2 Our Model

To focus on the basic issue of lack of price-based equilibria, our model does not address informational issues, assumes a single seller, and does not assume any budget constraints.

Our seller is selling $m$ heterogeneous indivisible items to $n$ buyers who are competing for them. Each buyer $i$ has a valuation function $v_{i}$ specifying his value for each subset of the items. I.e. for a subset $S$ of the items $v_{i}(S)$ specifies the value for that buyer if he gets exactly this subset of the items, expressed in some currency unit (i.e., the buyers are quasi-linear). We will assume free disposal, i.e., that the $v_{i}$’s are monotonically non-decreasing, but nothing beyond that.

The usual notion of price-based equilibrium in this model is called a Walrasian equilibrium: a set of item prices $p_{1}\ldots p_{m}$ and a partition $S_{1}\ldots S_{n}$ of the $m$ items among the $n$ buyers such that each buyer gets his “demand” under these prices, i.e., $S_{i}\in argmax_{S}(v_{i}(S)-\sum_{j\in S}p_{j})$. When such equilibria exist they maximize social welfare, $\sum_{i}v_{i}(S_{i})$, but unfortunately it is known that they only rarely exist – exactly when the associated integer program has no integrality gap (see for a survey).

We will consider this market situation as a game where each playerWe use interchangeably the terms: player, bidder and buyer, and all three have the same meaning. $i$ announces $m$ offers $b_{i1},\ldots b_{im}$, with the interpretation that $b_{ij}$ is player $i$’s bid of item $j$. After the offers are made, $m$ independent first price auctions are being made. That is the utility of each bidder $i$ is given by $u_{i}(b)=v_{i}(S_{i})-\sum_{j\in S_{i}}b_{ij}$ where $S_{1}\ldots S_{n}$ are a partition of the $m$ items with the property that each item went to a highest bidder on it. Some care is needed in the case of ties – two (or more) bidders $i\neq i^{\prime}$ that place the highest bid $b_{ij}=b_{i^{\prime}j}$ for some item $j$. In this case a tie breaking rule is needed to complete the specification of the allocation and thus of the game. Importantly, we view this as a game with complete information, so each player knows the (combinatorial) valuation function of each other player.

3 Pure Nash Equilibrium

Our first observation is that the pure equilibria of this game capture exactly the Walrasian equilibria of the market. This justifies our point of view that when we later allow mixed-Nash equilibria as well, we are in fact strictly generalizing the notion of price-equilibria.

Theorem: Fix a profile of valuations. Walrasian equilibria of the associated market are in 1-1 correspondence with pure Nash equilibria of the associated game. This holds in the exact sense for some tie-breaking rule, and holds in the sense of limits of $\epsilon$-Nash equilibria for all ties-breaking rules.

A profile of strategies (bids) in the game is called a “limit of $\epsilon$-Nash equilibria” if for every $\epsilon>0$ there exists a sequence of $\epsilon$-Nash equilibria that approach it.

Let us demonstrate this theorem with a trivial example: a single item on sale and two bidders who have values of 1 and 2 respectively for it. A Walrasian equilibrium can fix the item’s price $p$ anywhere between 1 and 2, at which point only the second bidder desires it and the market clears. In the associated game (with any tie breaking rule), a bid $p$ for the first player and bid $p+\epsilon$ for the second player will be an $\epsilon$-Nash-equilibrium. In the special case that the tie breaking rule gives priority to the second bidder, an exact pure-Nash equilibrium will have both bidders bidding $p$ on the item.

This theorem is somewhat counter intuitive as strategic (non-price-taking) buyers in markets may improve their utility by strategically “reducing demand”. Yet, in our setting strategic buyers still reach the basic non-strategic price-equilibrium.

As an immediate corollary of the fact that a Walrasian equilibrium optimizes social welfare (“The first welfare theorem”), we get the same optimality in our game setting:

Corollary – A “First Welfare Theorem” For every profile of valuations and every tie-breaking rule, every pure Nash equilibrium of the game (including a limit of $\epsilon$-equilibria) optimizes social welfare. In other words, the price of anarchy of pure Nash equilibria is trivial.

4 Mixed Nash Equilibria

As mentioned above, since Walrasian equilibria only rarely exists, so do only rarely exist pure Nash equilibria in our games. So it is quite natural to consider also the standard generalization, Mixed-Nash equilibria of our market games. The issue of existence of such mixed Nash equilibria is not trivial in our setting as buyers have a continuum of strategies and discontinuous utilities so Nash’s theorem does not apply. Nevertheless, there has been a significant amount of economic work on these types of settings and a theorem of Simon and Zame provides at least a partial general positive answer:

Corollary (to a theorem of ): For every profile of valuations, there exists some (mixed) tie-breaking rule such that the game has a mixed-Nash equilibrium.

It seems that, like in the case of pure equilibria, an $\epsilon$-Nash equilibrium should exist for all tie breaking rules, but we have not been able to establish this.

Once existence is established, we turn our attention towards analyzing what these mixed equilibria look like. We start with the two basic examples that are well known not to have a price equilibria:

Example – Complements and Substitutes Bidders: In this example there are two items and two bidders. The first bidder (“OR bidder”) views the two items as perfect substitutes and has value of $v_{or}$ for either one of them (but is not interested in getting both). The second bidder (“AND bidder”) views them as complements and values the bundle of both of them at $v_{and}$ (but is not interested in either of them separately). It is not difficult to see that when $v_{and}<2v_{or}$ no pure equilibrium exists, however we find specific distributions $F$ and $G$ for the bids of the players that are in mixed-Nash equilibrium.

Example – Triangle: In this example there are three items and three players. Each of the players is interested in a specific pair of items, and has value 1 for that pair, and 0 for any single item, or any other pair. A pure Nash equilibrium does not exist, but we show that the following is a mixed-Nash equilibrium: each player picks a bid $x$ uniformly at random in the range $[0,1/2]$ and bids this number on each of the items. Interestingly the expected utility of each player is zero. We generalize the analysis to the case of single minded players, each desiring a set of size $k$, each item is desired by $d$ players, and no two players’ sets intersect in at most a single item.

We generalize our analysis to more general examples of these veins. In particular, these provide examples where the mixed-Nash equilibrium is not optimal in terms of maximizing social welfare and in fact is far from being so.

Corollary – A “First Non-Welfare Theorem”: There are profiles of valuations where a mixed-Nash equilibrium does not maximize social welfare. There are examples where pure equilibria (that maximize social welfare) exist and yet a mixed Nash equilibrium achieves only $O(1\sqrt{m})$ fraction of social welfare (i.e., “price of anarchy” is $\Omega(\sqrt{m})$). There exist examples where all mixed-Nash equilibria achieve at most $O(\sqrt{(\log m)/m})$ fraction of social welfare (i.e., “price of stability” is $\Omega(\sqrt{m/(\log m)})$).

At this point it is quite natural to ask how much efficiency can be lost, in general, as well for interesting subclasses of valuations, which we answer as follows.

Theorem – An “Approximate First Welfare Theorem”: For every profile of valuations, every tie-breaking rule, and every mixed-Nash equilibrium of the game we have that the expected social welfare obtained at the equilibrium is at least $1/\alpha$ (the “price of anarchy”) times the optimal social welfare, where

$\alpha\leq 2\beta$ if all valuations $\beta$-fractionally subadditive. (The case $\beta=1$ correponds to fractionally subadditive valuations, also known as XOS valuations. They include the set of sub-modular valuations.)

$\alpha=O(\log m)$ if all valuations are sub-additive.

These bounds apply also to correlated-Nash equilibria and even to coarse-correlated equilibria.

A related PoA result is that of which derive PoA for $\beta$-fractionally sub-additive bidders in a second price simultaneous auction under the assumption of “conservative bidding.” In this work we use the first price (rather than the second price) and do not make any assumption regarding the bidding.

Finally we extend these results also to a Bayesian setting where players have only partial information on the valuations of the other players. We show that for any prior distribution on the valuations and in every Bayesian Nash equilibrium, where each player bids only based on his own valuation (and the knowledge of the prior), the average social welfare is lower by at most $\alpha=O(mn)$ than the optimal social welfare achieved with full shared knowledge and cooperation of the players. For a prior which is a product distribution over valuations which are $\beta$-fractionally sub-additive we show that $\alpha=4\beta$, which implies a bound of $4$ for sub-modular valuations and a bound of $O(\log m)$for sub-additive valuations. Our proof methodology for this setting is similar to that of .

5 Open Problems and Future Work

We consider our work as a first step in the systematic study of notions of equilibrium in markets where price equilibria do not exist. Our own work focused on the mixed-Nash equilibrium, its existence and form, and its welfare properties. It is certainly natural to consider other properties of such equilibria such as their revenue or invariants over the set of equilibria. One may also naturally study other notions of equilibrium such as those corresponding outcomes of natural dynamics (e.g. coarse correlated equilibria which are the outcome of regret minimization dynamics). It is also natural to consider richer models of markets (e.g. two-sided ones, non-quasi-linear ones, or ones with partial information).

Even within the modest scope of this paper, there are several remaining open questions: the existence of mixed-Nash equilibrium under any tie-breaking rule; the characterization of all equilibria for the simple games we studied; and closing the various gaps in our price of anarchy and price of stability results.

Model

We have a set $M$ of $m$ heterogeneous indivisible items for sale to a set $N$ of $n$ bidders. Each bidder $i$ has a valuation function $v_{i}$ where for a set of items $S\subseteq M$, $v_{i}(S)$ is his value for receiving the set $S$ of items. We will not make any assumptions on the $v_{i}$’s except that they are monotone non decreasing (free disposal) and that $v_{i}(\emptyset)=0$. We assume that the utility of the bidders is quasi-linear, namely, if bidder $i$ gets subset $S_{i}$ and pays $p_{i}$ then $u_{i}(S_{i},p_{i})=v_{i}(S_{i})-p_{i}$.

We will consider this market situation as a game where the items are sold in simultaneous first price auctions. Each bidder $i\in N$ places a bid $b_{ij}$ on each each item $j\in M$, and the highest bidder on each item gets the item and pays his bid on the item. We view this as a game with complete information. The utility of each bidder $i$ is given by $u_{i}(b)=v_{i}(S_{i})-\sum_{j\in S_{i}}b_{ij}$ where $S_{1}...S_{n}$ are a partition of the $m$ items with the property that each item went to the bidder that gave the highest bid for it.

Some care is required in cases of ties, i.e., if for some bidders $i\neq i^{\prime}$ and an item $j\in M$ we have that $b_{ij}=b_{i^{\prime}j}$ are both highest bids for item $j$. In these cases the previous definition does not completely specify the allocation, and to complete the definition of the game we must specify a tie breaking rule that chooses among the valid allocations. (I.e. specifies the allocation $S_{1},\ldots,S_{n}$ as a function of the bids.) In general we allow any tie breaking rule, a rule that may depend arbitrarily on all the bids. Even more, we allow randomized (mixed) tie breaking rules in which some distribution over deterministic tie breaking rules is chosen. We will call any game of this family (i.e.,with any tie breaking rule) a “first price simultaneous auction game” (for a given profile of valuations).

Pure Nash Equilibrium

The usual analysis of this scenario considers a market situation and a price-based equilibrium:

A partition of the items $S_{1}...S_{n}$ and a non-negative vector of prices $p_{1}...p_{m}$ are called a Walrasian equilibrium if for every $i$ we have that $S_{i}\in argmax_{S}(v_{i}(S)-\sum_{j\in S}p_{i})$.

We consider bidders participating in a simultaneous first price auction game, with some tie breaking rule.

Our first observation is that pure equilibria of a first price simultaneous auction game correspond to Walrasian equilibiria of the market. In particular the price of anarchy of pure equilibria is 1.

A profile of valuation functions $v_{1}...v_{n}$ admits a Walrasian equilibrium with given prices and allocation if and only if the first price simultaneous auction game for these valuations has a pure Nash equilibrium for some tie breaking rule with these winning prices and allocation.

Every pure Nash equilibrium of a first price simultaneous auction game achieves optimal social welfare.

Proof: Let $S_{1},\ldots,S_{n}$ and $p_{1},\ldots,p_{m}$ be a Walrasian equilibrium. Consider the bids where $b_{ij}=p_{j}$ for all $j$ and let the game break ties according to $S_{1}...S_{n}$. Why are these bids a pure equilibrium of this game? Since we are in a Walrasian equilibrium, each player gets a best set for him under the prices $p_{j}$. In the game, given the bids of the other players, he can never win any item for strictly less than $p_{j}$, whatever his bid, and he does wins the items in $S_{i}$ for price $p_{j}$ exactly, so his current bid is a best response to the othersThe reader may dislike the fact that the bids of loosing players seem artificially high and indeed may be in weakly dominated strategies. This however is unavoidable since, as we will see in the next section, counter-intuitively sometimes there are no pure equilibria in un-dominated strategies. What can be said is that minimal Walrasian equilibria correspond to pure equilibria of the game with strategies that are limits of un-dominated strategies..

Now fix a pure Nash equilibrium of the game with a given tie breaking rule. Let $S_{1},\ldots,S_{n}$ the allocation specified by the tie breaking rule, and let $p_{j}=\max_{i}b_{ij}$ for all $j$. We claim that this is a Walrasian equilibrium. Suppose by way of contradiction that some player $i$ strictly prefers another bundle $T$ under these prices. This contradicts the original bid of $i$ was a best reply since the deviation bidding $b_{ij}=p_{j}+\epsilon$ for $j\in T$ and $b_{ij}=0$ for $j\not\in T$ would give player $i$ the utility from $T$ (minus some $\epsilon$’s) which would be more than he currently gets from $S_{i}$ – a contradiction.

The allocation obtained by the game, is itself the allocation in a Walrasian equilibrium, and thus by the First Welfare Theorem is a social-welfare maximizing allocation.

Two short-comings of this proposition are obvious: first is the delicate dependence on tie-breaking: we get a Nash equilibrium only for some, carefully chosen, tie breaking rule. In the next section we will show that this is un-avoidable using the usual definitions, but that it is not a “real” problem: specifically we show that for any tie-breaking rule we get arbitrarily close to an equilibrium.

The second short-coming is more serious: it is well known that Walrasian equilibria exist only for restricted classes of valuation profilesWhen all valuations are “substitutes”.. In the general case, there is no pure equilibrium and thus the result on the price of anarchy is void. In particular, the result does not extend to mixed Nash equilibria and in fact it is not even clear whether such mixed equilibria exist at all since Nash’s theorem does not apply due to the non-compactness of the space of mixed strategies. This will be the subject of the the following sections.

This subsection shows that the quantification to some tie-breaking rule in the previous theorem is unavoidable. Nevertheless we argue that it is really just a technical issue since we can show that for every tie breaking rule there is a limit of $\epsilon$-equilibria.

Consider the full information game describing a first price auction of a single item between Alice, who has a value of 1 for the item, and Bob who values it at 2, where the bids, $x$ for Alice and $y$ for Bob, are allowed to be, say, in the range $$. The full information game specifying this auction is defined by$u_{A}(x,y)=0$for$x$and$u_{A}(x,y)=1-x$for$x>y$, and$u_{B}(x,y)=2-y$for$x$and$u_{B}(x,y)=0$for$x>y$. Now comes our main point: how would we define what happens in case of ties? It turns out that formally this “detail” determines whether a pure Nash equilibrium exists.

Let us first consider the case where ties are broken in favor of Bob, i.e., $u_{B}(x,y)=2-y$ for $x=y$ and $u_{A}(x,y)=0$ for $x=y$. In this case one may verify that $x=1,y=1$ is a pure Nash equilibriumThe bid $x=1$ is weakly dominated for Alice. Surprisingly, however, there is no pure equilibrium in un-dominated strategies: suppose that some $y$ is at equilibrium with an un-dominated strategy $x<1$. If $yge1$ then reducing $y$ to $y=x$ would still make Bob win, but at a lower price. However, if $y<1$ too, then the loser can win by bidding just above the current winner – contradiction..

Now let us look at the case that ties are broken in favor of Alice, i.e $u_{A}(x,y)=1-x$ and $u_{B}(x,y)=0$ for $x=y$. In this case no pure Nash equilibrium exists: first no $x\neq y$ can be an equilibrium since the winner can always reduce his bid by $\epsilon$ and still win, then if $x=y>1$ then Alice would rather bid $x=0$, while if $x=y<2$ then Bob wants to deviate to $y+\epsilon$ and to win, contradiction.

This lack of pure Nash equilibrium doesn’t seem to capture the essence of this game, as in some informal sense, the ”correct” pure equilibrium is $(x=1,y=1+\epsilon)$ (as well as $(x=1-\epsilon,y=1)$), with Bob winning and paying $1+\epsilon$ ($1$). Indeed these are $\epsilon$-equilibria of the game. Alternatively, if we discretize the auction in any way allowing some minimal $\epsilon$ precision then bids close to $1$ with minimal gap would be a pure Nash equilibrium of the discrete game. We would like to formally capture this property: that $x=1$, $y=1$ is arbitrarily close to an equilibrium.

Limits of ϵitalic-ϵ\epsilon-Equilibria

We will become quite abstract at this point and consider general games with (finitely many) $n$ players whose strategy sets may be infinite. In order to discuss closeness we will assume that the pure strategy set $X_{i}$ of each player $i$ has a metric $d_{i}$ on it. In applications we simply consider the Euclidean distance.

$(x_{1}...x_{n})$ is called a limit (pure) equilibrium of a game $(u_{1}...u_{n})$ if it is the limit of $\epsilon$-equilibria of the game, for every $\epsilon>0$.

Thus in the example of the first price auction, $(1,1)$ is a limit equilibrium, since for every $\epsilon>0$, $(1,1+\epsilon)$ is an $\epsilon$-equilibrium. Note that if all the $u_{i}$’s are continuous at the point $(x_{1}...x_{n})$ then it is a limit equilibrium only if it is actually a pure Nash equilibrium. This, in particular, happens everywhere if all strategy spaces are discrete.

We are now ready to state a version of the previous proposition that is robust to the tie breaking rule:

For every first price simultaneous auction game with any tie breaking rule, a profile of valuation functions $v_{1}...v_{n}$ admits a Walrasian equilibrium with given prices and allocation if and only if the game has a limit Nash equilibrium for these valuations with these winning prices and allocation.

Every limit Nash equilibrium of a first price simultaneous auction game achieves optimal social welfare.

Proof: Let $S_{1}...S_{n}$ and $p_{1}...p_{m}$ be a Walrasian equilibrium. Consider the bids where $b_{ij}=p_{j}+\epsilon$ for all $j\in S_{i}$ and $b_{ij}=p_{j}$ for all $j\not\in S_{i}$. Why are these bids an $m\epsilon$-equilibrium of this game? Since we are in a Walrasian equilibrium, each player gets a best set for him under the prices $p_{j}$. In the game, given the bids of the other players, he can never win any item for strictly less than $p_{j}$, whatever his bid, and player $i$ does win each item $j$ in $S_{i}$ for price $p_{j}+\epsilon$, so his current bid is a best response to the others up to an additive $\epsilon$ for each item he wins.

Now fix a limit Nash equilibrium $(b_{ij})$ of the game with some tie breaking rule and let $(b^{\prime}_{ij})$ be an $\epsilon$-equilibrium of the game with $|b_{ij}-b^{\prime}_{ij}|\leq\epsilon$ for all $i,j$ and with no ties; let $S_{1}...S_{n}$ the allocation implied; and let $p_{j}=\max_{i}b_{ij}$ for all $j$. We claim that this is an $m\epsilon$-Walrasian equilibrium. Suppose by way of contradiction that for some player $i$ and some bundle $T\neq S_{i}$, $v_{i}(T)-\sum_{j\in T}p_{j}>v_{i}(S_{i})-\sum_{j\in S_{i}}p_{j}+m\epsilon$. This would contradict the original bid of $i$ being an $\epsilon$-best reply since the deviation bidding $b_{ij}=p_{j}+\epsilon$ for $j\in T$ and $b_{ij}=0$ for $j\not\in T$ would give player $i$ the utility from $T$ up to $m\epsilon$ which would be more than he currently gets from $S_{i}$ – a contradiction.

Now let $\epsilon$ approach zero and look at the sequence of price vectors $\vec{p}$ and sequence of allocations obtained as $(b^{\prime}_{ij})$ approach $(b_{ij})$. The sequence of price vectors converges to a fixed price vector (since they are a continuous function of the bids). Since there are only a finite number of different allocations, one of them appears infinitely often in the sequence. It is now easy to verify that this allocation with the limit price vector are a Walrasian equilibrium.

General Existence of Mixed Nash Equilibrium

In this section we ask whether such a game need always even have a mixed-Nash equilibrium. This is not a corollary of Nash’s theorem due to the continuum of strategies and discontinuity of the utilities, and indeed even zero-sum two-player games with $$as the set of pure strategies of each player may fail to have any mixed-Nash equilibrium or even an$\epsilon$-equilibriumA well known example is having highest bidder win, as long as his bid is strictly less than 1, in which case he looses (with ties being ties).. There is some economic literature about the existence of equilibiria in such games (starting e.g. with ), and a theorem of Simon and Zame , implies that for some (randomized) tie breaking rule, a mixed-Nash equilibrium exists. The main example of their (more general) theorem is the following (cf. page 864):

Suppose we are given strategy spaces $S_{i}$, a dense subset $S^{*}$ of $S=S_{1}\times\cdots\times S_{n}$, and a bounded continuous function $\varphi:S^{*}\rightarrow\Re^{n}$. Let $C_{\varphi}:S\rightarrow\Re^{n}$ be the correspondence whose graph is the closure of the graph of $\varphi$, and define $Q_{\varphi}(s)$ to be the convex hull of $C_{\varphi}(s)$ for each $s\in S$. We call the correspondence $Q_{\varphi}$ the convex completion of $\varphi$. These are Simon and Zame’s motivating example of “games with an endogenous sharing rule”, and their main theorem is that these have a “solution”: a pair $(q,\alpha)$, where $q$ is a “sharing rule”, a Borel measurable selection from the payoff correspondence $Q$ and $\alpha=(\alpha_{1},\ldots,\alpha_{n})$ is a profile of mixed strategies with the property that each player’s action is a best response to the actions of other players, when utilities are according to the sharing rule $q$.

Now to how this applies in our setting: $S^{*}$ will be the set of bids with no ties, i.e., where for all $j$ and all $i\neq i^{\prime}$ we have that $b_{ij}\neq b_{i^{\prime}j}$, which is clearly dense (since bids with ties have measure zero). Here $\varphi$ is simply the vector of utilities of the players from the chosen allocation which is fully determined and continuous in $S^{*}$ – when there are no ties. For $b\not\in S^{*}$, we have that $C_{\varphi}(\vec{b})$ is the set of utility vectors obtained from all possible deterministic tie-breaking rules at $\vec{b}$ (each of which may be obtained as a limit of bids with no ties), and $Q_{\varphi}$ is the set of mixtures (randomizations) over these. The solution thus provides a randomized tie-breaking rule $q$ and mixed strategies that are a mixed-Nash equilibrium for the game with this tie-breaking rule. So we get:

The first price simultaneous auction game for any profile of valuations has a mixed-Nash equilibrium for some randomized tie-breaking rule.

We suspect that the tie-breaking rule is not that significant and that mixed $\epsilon$-Nash-equilibria (or maybe even exact Nash-equilibria) actually exist for every tie-breaking rule, similarly to the case of pure equilibria in this paper, or as in the somewhat related setting of where an “invariance” in the tie-breaking rule holds.

Mixed-Nash Equilibria: Examples

In this section we study some of the simplest examples of markets in our setting that do not have a Walresian equilibrium.

We have two players an AND player and OR player. The AND player has a value of $1$ if he gets all the items in $M$, and the OR player has a value of $v$ if he gets any item in $M$. Formally, $v_{and}(M)=1$ and for $S\neq M$ we have $v_{and}(S)=0$, also, $v_{or}(T)=v$ for $T\neq\emptyset$ and $v_{or}(\emptyset)=0$.

When $v\leq 1/m$ there is a Walresian equilibrium with a price of $v$ per item. By Proposition 3.2 this implies a pure Nash Equilibrium in which both players bid $v$ on each item, and the AND player wins all the items. Therefore, the interesting case is when $v>1/m$. It is easy to verify that in this case is no Walresian equilibrium. We start with the case that $|M|=2$ and later extend it to the case of arbitrary size. Here is a mixed Nash equilibrium for two items.

The AND player bids $(y,y)$ where $0\leq y\leq 1/2$ according to cumulative distribution $F(y)=(v-1/2)/(v-y)$ (where $F(y)=Pr[bid\leq y]$). In particular, There is an atom at 0: $Pr[y=0]=1-1/(2v)$.

The OR player bids $(x,0)$ with probability 1/2 and $(0,x)$ with probability 1/2, where $0\leq x\leq 1/2$ is distributed according to cumulative distribution $G(x)=x/(1-x)$.

Note that since the OR player does not have any mass points in his distribution, the equilibrium would apply to any tie breaking rule.

We start by defining a restricted AND-OR game, where the AND player must bid the same value on both items, and show that the above strategies are a mixed Nash equilibrium for it.

Having the AND player bid using $F$ and the OR player bid using $G$ is a mixed Nash equilibrium of the restricted AND-OR game for two items.

Proof: Let us compute the expected utility of the AND player from some pure bid $(y,y)$. The AND player wins one item for sure, and wins the second item too if $y>x$, i.e., with probability $G(y)$. If he wins a single item he pays $y$, and he wins both items he pays $2y$. His expected utility is thus $G(y)(1-y)-y=0$ for any $0\leq y\leq 1/2$ (and is certainly negative for $y>1/2$). Thus any $0\leq y\leq 1/2$ is a best-response to the OR player.

Let us compute the expected utility of the OR player from the pure bid $(0,x)$ (or equivalently $(x,0)$). The OR player wins an item if $x>y$, i.e., with probability $F(x)$, in which case he pays $x$, for a total utility of $(v-x)\cdot F(x)=v-1/2$, for every $0\leq x\leq 1/2$ (and $x>1/2$ certainly gives less utility). Thus any $0\leq x\leq 1/2$ is a best-response to the AND player.

Next we generalize the proof to the unrestricted setting.

Having the AND player bid using $F$ and the OR player bid using $G$ is a mixed Nash equilibrium of the AND-OR game for two items.

Proof: We first show that if the AND player plays the mixed strategy $F$ then $G$ is a best response for the OR player. This holds since when the AND player is playing $F$, then all its bids are of the form $(y,y)$ for some $y\in[0,,1/2]$. Any bid $(x_{1},x_{2})$ of the OR player, with $x_{1}\leq x_{2}$, is dominated by $(0,x_{2})$, since the AND player is restricted to bidding $(y,y)$. Therefore, $G$ is a best response for the OR player.

We now need to show that if the OR player plays the mixed strategy $G$ then $F$ is a best response for the AND player.

Let $Q(x,y)$ be the cumulative probability of the OR player, i.e.,

for $x,y\in[0,\frac{1}{2}]$. The AND utility function, given its distribution $P$, is:

We show that for any $x,y\in[0,\frac{1}{2}]$ we have $u_{and}(x,y)=0$. This follows since,

We now extend the result to the AND-OR game with $m$ items. The AND player selects $y$ using the cumulative probability distribution $F(y)=\frac{v-\frac{1}{m}}{v-y}$ for $y\in[0,1/m]$, and bids $y$ on all the items. The OR player selects $x$ using the cumulative probability distribution $G(x)=\frac{(m-1)x}{(1-x)}$, where $x\in[0,1/m]$, and an $i$ uniformly from $M$, and bids $x$ on item $i$ and zero on all the other items.

Having the AND player bid using $F$ and the OR player with $G$ is a mixed Nash equilibrium.

Proof: Let $Q(x)$, for $x\in[0,1/m]^{m}$ be the cumulative probability distribution of the bids of the OR player. Given that the OR player bids using $G$ it follows that

for $x\in[0,\frac{1}{m}]^{m}$. Let $P$ denote the cumulative probability distribution of the bids of the AND player. Then the utility of the AND player is:

We show that for any $x\in[0,\frac{1}{m}]^{m}$ we have $u_{and}(x)=0$.

This implies that the mixed strategy of the AND player defined by $F$, is a best response to the mixed strategy of the OR player defined by $G$. We now show that the mixed strategy of the OR player defined by $G$, is a best response to the mixed strategy of the AND player defined by $F$.

Recall that $P(x)$, for $x\in[0,1/m]^{m}$ is the cumulative probability distribution of the bids of the AND player, and by the definition of the AND player it equals to

(Note that, as it should be, under $P$ the support is the set of all identical bids, i.e., $\forall i\;bid_{i}=x$. The probability under $P$ of having a vector $z\leq x$ is $\frac{v-\frac{1}{m}}{v-x}$.)

The utility function of the OR player is:

where $e(x)=\Pr_{P}[\exists i\mbox{ such that }X_{i}<x_{i}]$.

We obtain that for any $x\in[0,\frac{1}{m}]$ and $i\in[1,m]$ $u_{or}(x_{i}=x,x_{-i}=0)=v-\frac{1}{m}$ since

Furthermore, for any $x\in[0,\frac{1}{m}]^{m}$ we have $u_{or}(x)\leq u_{or}(y)$, where $y$ keeps only the maximal entry in $x$ and zeros the rest. This follows since given $P$, the probability of winning under $x$ and $y$ is identical. Clearly the payments under $y$ are at most those under $x$ (since all the bids in $x$ are at least the bids in $y$). We conclude that the OR player’s strategy is a best response to the AND player’s strategy, and this completes the proof.

2 The Triangle Game

We start with a simple case of three single minded bidders and three items, where each bidder wants a different set of two items, and has a value of one for this set.

Consider symmetric strategies in which each player bids the same for the pair of items it wants, namely each player draws their bid $x$ from the same distribution whose cumulative distribution function is $F(x)$. Assuming $F(x)$ has no atoms then the utility of each player is

If each player draws an $x$ from $F(x)=2x$, where $0\leq x\leq 1/2$, and bids $x$ on both items, then it is a mixed Nash equilibrium.

Proof: Suppose two of the players play according to $F(x)$ and consider the best response of the third player. For any value $0\leq x\leq 1/2$ if the third player bids $(x,x)$, his utility is zero. On the other hand, if it bids $y$ for one item and $z$ for the other then its utility is $F(y)F(z)\cdot 1-yF(y)-zF(z)=-2(y-z)^{2}\leq 0$. Finally, bidding any number strictly above $1/2$ is dominated by bidding $1/2$.

Consider now a generalization of this game where each player is single minded and is interested only in a particular set of $k$ items for which its utility is $1$. We also make the following assumptions.

Exactly $d$ agents are interested in each item.

For any two bidders $i\neq i^{\prime}$, we have $|S_{i}\cap S_{i^{\prime}}|\leq 1$. (This implies that if we fix a player $i$ and consider its set $S_{i}$ of $k$ items. The other $(d-1)k$ players who are also interested in these $k$ items are all different.)

Assume each player $i$ draws the same bid for all items in its set $S_{i}$ from the CDF $G(x)$. If $G(x)$ satisfies the equation

for all $x$ then the utility of a player is zero for every bid $x$.

satisfies Equation (1) for all $x$. So $G(x)=(kx)^{\frac{1}{(d-1)(k-1)}}$, $0\leq x\leq\frac{1}{k}$, forms an equilibrium for the restricted game, where in the restricted game a player has to bid the same bid on all the items in his set. The following shows that even if we do not restrict the players to bid the same then $G(x)$ is an equilibrium.

If all players draw a bid for all $k$ items that they want from $G(x)=(kx)^{\frac{1}{(d-1)(k-1)}}$, $0\leq x\leq\frac{1}{k}$, then it is a mixed Nash equilibrium.

Proof: Suppose all the players but one play according to $G(x)$ and consider the best response of the first player. Suppose its bid is $x_{j}$ for the $j$th item in $S_{i}$. Then its utility is

We claim that this utility is non-positive for every set of bids $x_{1},\ldots,x_{k}$. Indeed this follows since

by the inequality of arithmetic and geometric means:

Inefficiency of Mixed Equilibria

In this section we use our analysis of the examples given in the previous section to construct examples where there are large gaps between the efficiency obtained in a mixed-Nash equilibrium and the optimal efficiency.

We first analyze the AND-OR game with $m$ items, where $v\geq 1/m$, and hence there is no pure Nash equilibrium. We will analyze the following parameters: value of the OR player is $v=1/\sqrt{m}$ and the value of the AND player is $1$.

There is a mixed Nash equilibrium in the AND-OR game with the parameters above whose social welfare is at most $2/\sqrt{m}$. I.e. for this game we have $PoA\geq\sqrt{m}/2$.

Proof: For the PoA consider the equilibrium of Section 5.1. Assume that the value of the OR player is $v=1/\sqrt{m}$ and the value of the AND player is $1$. This implies that the optimal social welfare is $1$. The probability that the AND player bids $x=0$ is $\frac{v-1/m}{v-x}=1-1/\sqrt{m}$. Therefore with probability at least $1-1/\sqrt{m}$ the OR player wins. This implies that the social welfare is at most $2/\sqrt{m}$

We now prove the following lemma regarding the support of the AND player.

In any Nash equilibrium the AND player does not have in its support any bid vector $b_{and}$ such that $\sum_{i=1}^{m}b_{and,i}$ $>1$.

Proof: Assume that there is such a bid vector $b_{and}$. Since $\sum_{i=1}^{m}b_{and,i}>1$ the AND player can not get a positive utility, and the only way it can gain a zero utility is by losing all its non-zero bids. This implies that for any bid vector $b_{or}$ of the OR player, the OR player will win all the items. Therefore $\sum_{i=1}^{m}b_{or,i}>1$. This implies that the revenue of the auctioneer is larger than $1$ (every time). Since the expected revenue of the auctioneer is larger than $1$, and the optimal social welfare is $1$, the sum of the expected utilities of the players has to be negative. Hence one of the players has an expected negative utility. This clearly can not occur in equilibrium.

It turns out that for this example, not only there exist bad equilibria, but actually all equilibria are bad!

For any Nash equilibrium of the AND-OR game with the parameters above the social welfare is at most $3\sqrt{(\log m)/m}$. I.e. the $PoS\geq\sqrt{m/\log m}/3$.

Proof:Assume we have a Nash equilibrium in which the AND player wins with probability $\alpha$. This implies that the expected utility of the OR player $u_{or}$ is at most $(1-\alpha)v$. Also, the social welfare of the equilibrium is $(1-\alpha)v+\alpha\leq v+\alpha$.

By Lemma 6.2 the AND player never plays a bid $b$ in which the sum of the bids is larger than $1$. This implies that the AND player can have at most half of the bids which are larger than $2/m$. Therefore, if the OR player bid $2/m$ on $\log m$ random items, it will win some item with probability at least $1-1/m$. The OR player utility from such a strategy is at least $(1-1/m)v-(\log m)/m$. This implies that in equilibrium,

For $v=\sqrt{(\log m)/m}$ it implies that $\alpha\leq 2\sqrt{(\log m)/m}$. Therefore the social welfare is at most $3\sqrt{(\log m)/m}$.

Finally we study examples in which there are multiple equilibria, and show that they can be far apart from one another:

There is a set of valuations such that in the corresponding simultaneous first price auction there is an efficient (pure) Nash equilibrium, as well as an inefficient one, where the inefficiency is at least by a factor of $\sqrt{m}/2$. Equivalently, the corresponding auction has $PoS=1$ but $PoA\geq\sqrt{m}/2$.

Approximate Welfare Analysis

In this section we analyze the Price of Anarchy of the simultaneous first-price auction. We start with a simple proof of an $O(m)$ upper bound on the price of anarchy for general valuations. Then we consider $\beta$-XOS valuations (which are equivalent to $\beta$-fractionally subadditive valuations) and prove an upper bound of $2\beta$. Since subadditive valuations are $O(\log m)$ fractionally subadditive we also get an upper bound of $O(\log m)$ on the price of anarchy for subadditive valuations.

Assume that in $OPT$ player $i$ gets set $O_{i}$ and receives value $o_{i}=v_{i}(O_{i})$. Let $k_{i}$ be $|O_{i}|$. Let $e_{i}$ be the expected value player $i$ gets in an equilibrium and let $u_{i}$ be the expected utility of player $i$ in an equilibrium. Let $r_{i}$ be the expected sum of payments in equilibrium over all items in $O_{i}$ (these are not necessarily won by player $i$ in equilibrium).

Denote the total welfare, revenue, and utility in equilibrium by $SW(eq)$, $REV(eq)$, and $U(eq)$, respectively. By definitions we have: (1) $SW(eq)=\sum_{i}e_{i}$, (2) $SW(OPT)=\sum_{i}o_{i}$, (3) $REV(eq)=\sum_{i}r_{i}\leq SW(eq)$, (4) $U(eq)=\sum_{i}u_{i}=SW(eq)-REV(eq)$.

For any set of buyers the PoA is at most $4m$.

Proof: We first show that for each buyer $i$, we have $2u_{i}\geq o_{i}-4k_{i}r_{i}$.

By Markov, with probability of at least $1/2$ the total sum of prices of items in $O_{i}$ is at most $2r_{i}$. Thus if player $i$ bids $2r_{i}$ for each item in $O_{i}$ (and elsewhere) he wins all items with probability of at least $1/2$, getting expected value of at least $o_{i}/2$, and paying at most $2k_{i}r_{i}$. Since we were in equilibrium this utility must be at most $u_{i}$. Hence, $2u_{i}\geq o_{i}-4k_{i}r_{i}$.

Summing over all buyers, and bounding $\sum_{i}k_{i}\leq m$, we get that $OPT\leq 2U(eq)+4mRev(eq)\leq 4mSW(eq)$.

A function $v$ is $\beta$-XOS, if there exists an XOS function $X$ such that for any set $S$ we have $v(S)\geq X(S)\geq v(S)/\beta$, i.e., if there are numbers $\lambda_{j,l}$, $j\in M$ and $l\in L$, such that for any set $S$ we have

The equivalence of $\beta$-XOS and $\beta$ fractionally sub-additive follows the same proof as in .

Assume that the valuations of all the players are $\beta$-XOS. Then the PoA is $2\beta$.

Proof: Since $v$ is $\beta$-XOS, there is a $k\in L$ such that $\sum_{j\in O_{i}}\lambda_{j,k}\geq v_{i}(O_{i})/\beta$, and for any set $S$, we have $v(S)\geq\sum_{j\in S}\lambda_{j,k}$. Let $f_{j}$ be the expected price of item $j$. By Markov inequality, with probability of at least $1/2$ the price of item $j$ is at most $2f_{j}$. Consider the deviation where player $i$ bids $bid_{i,j}=\min\{\lambda_{j,k},2f_{j}\}$ for each item $j\in O_{i}$ (and elsewhere). Player $i$ wins each item $j$ with probability $\alpha_{j}$ and if $bid_{i,j}=2f_{j}$ then $\alpha_{j}\geq 1/2$. Let $S_{i}$ be the set of item that player $i$ wins with his deviation bids $bid_{i,j}$. (Note that $S_{i}$ is a random variable that depends on the random bids of the other players.) The expected utility of player $i$ from the deviation is,

Since player $i$ was playing an equilibrium strategy, we have that $u_{i}\geq E[v_{i}(S_{i})-\sum_{j\in S_{i}}bid_{i,j}]$. Summing over all players $i$’s, and recalling that $REV(eq)=\sum_{j\in M}f_{j}$, we get,

Bayesian Price of Anarchy

In a Bayesian setting there is a known prior distribution $Q$ over the valuations of the players. We first sample $v\sim Q$ and inform each player $i$ his valuation $v_{i}$. Following that, each player $i$ draws his bid from the distribution $D_{i}(v_{i})$, i.e., given a valuation $v_{i}$ he bids $(b_{i,1},\ldots,b_{i,m})\sim D_{i}(v_{i})$. The distributions $D(v)=(D_{1}(v_{1}),\dots,D_{n}(v_{n}))$ are a Bayesian Nash equilibrium if each $D_{i}(v_{i})$ is a best response of player $i$, given that its valuation is $v_{i}$ and the valuations are drawn from $Q$.

We start with the general case, where the distribution over valuations is arbitrary and the valuations are also arbitrary. Later we study product distributions over $\beta$-XOS valuations.

For any prior distribution $Q$ over the players valuations, the Bayesian PoA is at most $4mn+2$.

Proof: Fix a Bayesian Nash equilibrium $D=(D_{1},\dots,D_{n})$ as described above. Let $Q_{v_{i}}$ be the distribution on $v_{-i}$ obtained by conditioning $Q$ on $v_{i}$ as the value of player $i$.

Let $u_{i}(v_{i})$ be the expected utility of player $i$ when his valuation is $v_{i}$, i.e., $u_{i}(v_{i})=E_{b_{i}\sim D_{i}(v_{i})}E_{v_{-i}\sim Q_{v_{i}}}E_{b_{-i}\sim D_{-i}}[v_{i}(S_{i})-\sum_{j\in S_{i}}b_{i,j}]$, where $S_{i}$ is the set of items that player $i$ wins with the set of bids $b$. Let $u_{i}$ be the expected utility of player $i$, i.e., $E_{v_{i}\sim Q}[u_{i}(v_{i})]$.

For any valuation $v_{i}$ for player $i$, consider the following deviation. Let $Rev(v_{i})$ be the expected revenue given that the valuation of player $i$ is $v_{i}$, i.e., $Rev(v_{i})=E_{v\sim Q_{v_{i}}}[\sum_{j=1}^{m}\max_{k}b_{k,j}]$. Consider the deviation where player $i$ bids $2Rev(v_{i})$ on each item $j\in M$. By Markov inequality, he will win all the items $M$ with probability at least $1/2$. Therefore, his utility from the deviation is at least

Since this is an equilibrium, we have that

Summing over the players and taking the expectation with respect to $v$,

Clearly $\sum_{i=1}^{n}E_{v}[u_{i}(v_{i})]\leq E_{v}(SW(D))$, where $E_{v}(SW(D))$ is the expected social welfare of the Bayesian equilibrium $D$. Also, $\sum_{i=1}^{n}E_{v}[v_{i}(M)]\geq E_{v}[SW(OPT(v))]$. Finally, for every player $i$, $E_{v}[Rev(v_{i})]=Rev$, where $Rev$ is the expected revenue. Therefore,

Since $Rev\leq E_{v}[SW(D)]$, we have that,

The following theorem show that the Bayesian PoA is at most $4\beta$ when the valuations are limited to $\beta$-XOS and the distribution $Q$ over valuations is a product distribution. The proof uses the ideas presented in .

For a product distribution $Q$ over $\beta$-XOS valuations of the players, the Bayesian PoA is at most $4\beta$.

Proof: Fix a Bayesian Nash equilibrium $D=(D_{1},\dots,D_{n})$ as described above. Let $Q_{v_{i}}$ be the distribution on $v_{-i}$ obtained by conditioning $Q$ on $v_{i}$ as the value of player $i$.

Consider the following deviation of player $i$, given its valuation $v_{i}$. Player $i$ draws $w_{-i}\sim Q_{v_{i}}$, that is $w_{-i}$ are random valuations of the other players, conditioned on player $i$ having valuation $v_{i}$. Player $i$ computes the optimal allocation $OPT(v_{i},w_{-i})$, and in particular his share $OPT_{i}(v_{i},w_{-i})$ in that allocation. Player $i$ bids $2f_{j}(v_{i})$ on each item $j\in OPT_{i}(v_{i},w_{-i})$ , where $f_{j}(v_{i})$ is the expected maximum bid of the other players on item $j$ in the equilibrium $D$ conditioned on player $i$ having valuation $v_{i}$, i.e.,

By Markov inequality player $i$ wins each item $j\in OPT_{i}(v_{i},$ $w_{-i})$ with probability at least half. Since $v_{i}$ is an $\beta$-XOS valuation, its expected value is at least $v_{i}(OPT_{i}(v_{i},w_{-i}))/(2\beta)$ so the utility of player $i$ in this deviation is at least

Let $u_{i}(v_{i})$ be the expected utility of player $i$ when his valuation is $v_{i}$, i.e., $u_{i}(v_{i})=E_{b_{i}\sim D_{i}(v_{i})}E_{v_{-i}\sim Q_{v_{i}}}E_{b_{-i}\sim D_{-i}}[v_{i}(S_{i})-\sum_{j\in S_{i}}b_{i,j}]$, where $S_{i}$ is the set of items that player $i$ wins with the set of bids $b$. Let $u_{i}$ be the expected utility of player $i$, i.e., $E_{v_{i}\sim Q}[u_{i}(v_{i})]$. We get that,

Takin the expectation with respect to $v_{i}$,

where $I(X)$ is the indicator function for the event $X$. Summing over all the players

Now we use the fact that the distribution $Q$ over the valuations is a product distribution. This implies that for any valuation $v_{i}$, we have the same value $f_{j}(v_{i})$. Let $price(j)$ be the expected price of item $j\in M$, i.e., $price(j)=E_{v\sim Q}E_{b\sim D}[$ $\max_{k}b_{k,j}]$. Since $price(j)\geq f_{j}(v_{i})$ for any buyer $i$ and valuation $v_{i}$,

where the last equality follows since item $j$ is always assigned to some buyer, therefore, for any $v$, we have $\sum_{i=1}^{n}I(j\in OPT_{i}(v))=1$.

Let $sw(D)$ be the expected social welfare of the Bayesian Nash $D$. Note that $\sum_{i=1}^{n}u_{i}=sw(D)-\sum_{j\in M}price(j)$. Therefore,

This implies that the PoA of the Bayesian equilibrium $D$ is at most $4\beta$.

References