Composable and Efficient Mechanisms

Introduction

The goal of our paper is to initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms either simultaneously or sequentially. In most markets, (e.g. online markets) people participate in various mechanisms and the value of each player overall is a complex function of their outcomes. Predominantly, these mechanisms are run by different principals (e.g. different sellers on eBay or different ad-exchange platforms) and coordinating them to run a single combined mechanism is infeasible or impractical. The goal of this paper is to develop a theory of how to design mechanisms so that the efficiency guarantees for a single mechanism (when studied in isolation) carry over to the same or approximately the same guarantees for a market composed of such mechanisms. The key question considered in this paper can be summarized as follows:

What properties of local mechanisms guarantee global efficiency in a market composed of such mechanisms?

Mechanism design is a subject with a long and distinguished history aiming to design games that produce a certain desired outcome (such as revenue or social welfare maximization) in equilibrium. However, traditional mechanism design considered such mechanisms only in isolation, an assumption not so realistic in online markets, where players can cover their needs through multiple different mechanisms. Mechanism design has mostly focused on truthful mechanisms, where players participate by revealing their true preferences to the mechanism. In an environment with several auctions running simultaneously or sequentially, truthfulness of each individual auction loses its appeal, as the global mechanism is no longer truthful, even if each individual part is. The literature’s focus on truthful mechanisms is based on the revelation principle, showing that if there are better non-truthful solutions, the mechanism designer can run this alternate solution on the players’ behalf. However, the revelation principle is limited to mechanisms running in isolation: with multiple mechanisms run by different parties, there is no global coordinator to implement the solution. Requiring global coordination between mechanisms is not viable and could lead to complicated coordination problems, such as agreeing on ways to divide up the global revenue.

The online market setting introduces new desiderata for designing mechanisms. Typical mechanisms used in practice are extremely simple, and not truthful. The Internet environment allows for running millions of auctions, which necessitates the use of very simple and intuitive auction schemes. Second, we cannot assume that the designer knows all parameters of the environment at the design phase. Most mechanisms in online markets run in a dynamic environment and constantly adapting the mechanism is infeasible. Third, participants of such a dynamic and complex setting are bound to use learning strategies. Therefore, a mechanism should have good properties even under learning behavior. Last, we cannot expect the participants to know all the parameters of the game (e.g. valuations of opponents). Therefore, the mechanism should also be robust with respect to informational assumptions and should be approximately efficient, independent of the distribution of valuations.

We define the notion of a $(\lambda,\mu)$-smooth mechanism and show that smooth mechanisms possess all the aforementioned desired properties of composability and robustness under learning behavior and incomplete information. If a mechanism has the property that in any outcome, any participant can change her bid to receive her allocation of choice by paying the price paid at the current outcome, then the equilibrium outcome and prices are market clearing, implying that the outcome is socially optimal. Smooth mechanisms satisfy an approximate analog of this, requiring the property only in aggregate and only approximately (both in the value of the outcome achieved by the deviating bid and in the price paid), but not allowing the deviating bid to depend on the current actions of other players; a property crucial for the efficiency results described next. Our notion of smoothness is focused on mechanisms where players have quasilinear utilities and is related to the notion of smooth games introduced by Roughgarden .

Smooth Mechanisms and Efficiency. We show that a $(\lambda,\mu)$-smooth mechanism achieves at least a $\frac{\lambda}{\max(1,\mu)}$ fraction of the maximum possible social welfare in the full information setting. This is true in all correlated equilibria of the game and thereby no-internal-regret learning outcomes . We show that this result extends to the Bayesian setting with uncertainty about participants. This extension theorem strengthens the results of Roughgarden and Syrgkanis who showed a similar extension theorem requiring a complex smoothness condition involving multiple types which additionally couldn’t capture sequential games. Our proof uses a bluffing technique to handle the fact that we allow the deviating action to depend on the previous action of the deviating player (needed for sequential composition).

Complement-Free Valuations. We develop an hierarchy of valuations on outcomes of different mechanisms. Existing valuation hierarchies consider only valuations on sets of items. We identify analogs of complement-free valuations across mechanisms, without making any assumption about the valuations of players’ for outcomes within a mechanism. We define natural generalizations of fractionally subadditive and XOS valuations and show that these two classes are equivalent extending the result of Feige .

Composability of Smooth Mechanisms. We show that smooth mechanisms compose well in parallel: if we run any number of $(\lambda,\mu)$-smooth mechanisms simultaneously and players have fractionally subadditive valuations over outcomes of different mechanisms, then the global game is also a $(\lambda,\mu)$-smooth mechanism, and hence achieves a $\lambda/\max(1,\mu)$ fraction of the maximum social welfare in all correlated equilibria of the full information setting and in all mixed Bayes-Nash equilibria in the Bayesian setting.

We also show that smooth mechanisms compose well sequentially: if we run any number of $(\lambda,\mu)$-smooth mechanisms sequentially and a player’s value is the maximum valued allocation she got among all mechanisms then the global game is also $(\lambda,\mu+1)$-smooth and thereby achieves a $\lambda/(\mu+1)$ fraction of the optimal social welfare.

Applications. We show that many well-known auctions are smooth and can be analyzed in our framework. We list a few representative examples below, and note that our composition result applies when running any set of such auctions simultaneously or sequentially.

We show that the first price auction is $(1-1/e,1)$-smooth implying an efficiency bound of approximately $1.58$ for simultaneous first price item auctions, improving the bound of Hassidim et al and matching .

All-pay auctions, and a simple first price position auction are $(1/2,1)$-smooth, implying a bound of $2$.

The first price greedy combinatorial auction of Lucier and Borodin based on a $c$-approximation algorithm is $(1-e^{-1/c},c)$-smooth, improving the efficiency bound of from $c+O(\log(c))$ to $c+0.58$.

The bandwidth allocation game of Johari and Tsitsiklis is $(2-\sqrt{3},1)$-smooth, proving a somewhat weaker efficiency bound than , but extending the bound also to Bayesian games and learning outcomes.

No-overbidding. For some mechanisms, such as the second price auction, good performance requires that bidders do not bid above their value. For such mechanisms, we identify the notion of a weakly smooth mechanism. Roughly speaking, we will require that bidders’ declared maximum willingness to pay doesn’t exceed their valuation, and add a term to the smoothness definition using the participants maximum willingness to pay. As in the case of smooth mechanism, weakly smooth mechanisms remain weakly smooth when composed, and have high quality outcome in equilibrium (assuming no overbidding) both in the full information setting, in learning outcomes, and in the Bayesian setting.

Budget Constraints. The results discussed so far, assume that participants have quasi-linear valuations. The most common valuation that is not quasi-linear is when players have budget constraints. We extend our results to settings where participants have budget constraints. With budget constraints, maximizing welfare is not an achievable goal, as we cannot expect a low budget participant to be effective at maximizing her contribution to welfare. Instead, we consider the optimal “effective welfare” benchmark; capping the contribution of each player to the welfare by their budget. We show that all our results about efficiency for the case of simultaneous mechanisms carry over to bounds for this benchmark when players have budget constraints.

There has been a long line of research on quantifying inefficiency of equilibria starting from Koutsoupias and Papadimitriou who introduced the notion of the price of anarchy. More recently, this analysis technique has also been used to quantify the inefficiency of auction games, including games of incomplete information. A series of papers, Bikhchandani , Christodoulou et al , Bhawalkar and Roughgarden , Hassidim et al , Paes Leme et al , Syrgkanis and Tardos studied the efficiency of equilibria of non-truthful combinatorial auctions that are based on running separate item auctions (simultaneously or sequentially) for each item. Lucier and Borodin studied Bayes-Nash Equilibria of non-truthful auctions based on greedy allocation algorithms. Caragiannis et al studied the inefficiency of Bayes-Nash equilibria of the generalized second price auction. All this literature can be thought of as special cases of our framework and all the proofs can be understood as smoothness proofs giving the same or even tighter results. A recent exception is the paper by Feldman et al. giving a tighter bound for simultaneous item-auctions with subadditive bidders, than what would follow from smoothness.

Roughgarden proposed a framework, which he calls smoothness in games, and showed that a number of classical price of anarchy results (such as routing and valid utility games) can be proved using this framework. Further, he showed that such efficiency proofs carry over to efficiency of coarse correlated equilibria (no-regret learning outcomes). Nadav and Roughgarden give the broadest solution concept for which smoothness proofs apply. Schoppmann and Roughgarden extend the framework to games with continuous strategy spaces, providing tighter results. However, these papers consider only the full information setting and do not capture several of the auctions described previously. Our definition of a smooth mechanism is closely related to the notion of a smooth game. If utilities of the game were always non-negative (which is not the case here) then a $(\lambda,\mu)$-smooth mechanism can be thought of as a $(\lambda,\mu-1$)-smooth game, but with much weaker requirements, allowing us to capture all the auctions above, as well as sequential composition.

Recent papers offer extensions of the smoothness framework to incomplete information games. Lucier and Paes Leme introduced the concept of semi-smoothness (inspired by their GSP analysis), and showed that efficiency results shown via semi-smoothness extend to the incomplete information version of the game, even if the types of the players are arbitrarily correlated. However, semi-smoothness is a much more restrictive property (for instance, not satisfied by the item-bidding auctions) than just requiring that every complete information instance of the game is smooth. Recently Roughgarden (and independently Syrgkanis ) offered a more general such extension theorem. They show that one can prove bounds on the price of anarchy of an incomplete information game (assuming type distributions of players are independent) by restricting attention to induced complete information instances and proving a stronger version of the smoothness property, which calls universal smoothness. Our extension theorem is based on simply assuming that for any choice of valuations, the induced full information game is smooth according to the standard definition of smoothness. In contrast, the stronger universal smoothness property relates utilities of players with different types in a single inequality. While, many of the known examples satisfy this stronger notion of smoothness, our extension theorem is more natural, assuming only that the underlying full information game is smooth, and does not mix player types. In addition, our smoothness is an even weaker property that allows us to capture efficiency in sequential games of incomplete information in a unified framework.

A recent survey by Pai highlights settings where different sellers compete by announcing mechanisms, starting from the seminal work of McAfee and focusing on revenue maximization. Our work is in the same spirit, and aims to analyze the effect of such competition on social welfare.

Composition Framework

We will consider a setting where players participate in a set of mechanisms. We assume that players’ preferences are quasilinear in money. In this section we introduce our framework and set up the notation we need for defining mechanisms and compositions of mechanisms.

Observe that although we assume that the outcome space is in the form of a subset of a product space, this doesn’t restrict at all the space of mechanism design settings we can model, since we don’t put any restriction on the structure of the subset of the product space. Hence, our model captures a range of problems, including games where players have externalities or share a single outcome. A few of the special cases are: 1) combinatorial auctions where $\mathcal{X}_{i}$ is the power set of items and $\mathcal{X}$ is the subset of this product space such that no item is assigned to more than one player, 2) combinatorial public projects where $\mathcal{X}_{i}$ is the power set of projects and $\mathcal{X}$ is the subset of the product space such that every coordinate is the same, 3) position auctions where $\mathcal{X}_{i}$ is the set of positions and $\mathcal{X}$ is the subset of the product space where no two coordinates are assigned the same position, 4) bandwidth allocation mechanisms where $\mathcal{X}_{i}$ is the portion of the bandwidth assigned to player $i$ and $\mathcal{X}$ is the subset such that the sum of the coordinates is at most the bandwidth capacity. Using this product space formulation allows us to encode which part of the outcome the valuation of a player is affected by and it facilitates the formulation of valuation classes on outcome spaces as we will see in the next section.

We will only consider settings where each player has the option to not participate, and hence at any rational outcome gets non-negative utility in expectation over the information she doesn’t have and over the randomness of the other players and the mechanisms.

The Composition Framework. Mechanisms rarely run in isolation but rather, several mechanisms take place simultaneously and/or sequentially, and players typically have valuations that are complex functions on the outcomes of different mechanisms.

We will consider both simultaneous and sequential composition of mechanisms. In the case of simultaneous composition, a player’s strategy space is to report an action $a_{i}^{j}$ at each mechanism $j$. In the case of sequential composition a player can base the action she submits at mechanism $j$ on the history of the submitted action profiles in previous mechanisms (alternatively we could assume that bidders observe only allocations and payments in previous mechanisms; our results are robust to such information assumptions).

The simultaneous composition of mechanisms can be viewed as a global mechanism $\mathcal{M}=(\mathcal{A},X,P)$, where $\mathcal{A}_{i}=\times_{j}\mathcal{A}_{i}^{j}$, $\mathcal{X}=\times_{j}\mathcal{X}^{j}$, $X(a)=(X^{j}(a^{j}))_{j}$ and $P(a)=\sum_{j}P^{j}(a^{j})$. Sequential composition can also be viewed as a global mechanism with a more complex action space, where actions are functions of the observed history of play in earlier mechanisms. Our goal is to give properties of the individual mechanisms that guarantee efficiency of the global mechanism.

Efficiency Measure. We will measure efficiency of an action profile $a$ in terms of social welfare

which is the sum of the utilities of all players and the revenue of all the mechanisms. For any valuation profile $v\in\times_{i}\mathcal{V}_{i}$ there exists an optimal allocation $x^{*}(v)$ that maximizes $\sum_{i}v_{i}(x_{i})$ over all allocations $x\in\mathcal{X}$ and we will denote with

Hierarchy of Valuations

The class of valuations that will be important in our composability theorems is that of fractionally subadditive valuations across mechanisms, which we define as follows:

A valuation is fractionally subadditive across mechanisms if

The above is the natural extension of the class of fractionally subadditive valuations that has been defined only for valuations defined on sets (i.e. special case of $\mathcal{X}_{j}\in\{0,1\}$). In the context of set valuations it has been shown that fractionally subadditive valuations is equivalent to the class of XOS valuations. We give here the natural generalization of XOS valuations in our setting and then we show that the analogous equivalence theorem still holds, thereby extending the result of Feige . We defer the proof to the Appendix.

A valuation is fractionally subadditive over the outcomes of different mechanisms if and only if it is XOS. Similarly, it is $\beta$-fractionally subadditive if and only if it is $\beta$-XOS.

To define generalizations of submodular and subadditive valuations, we will assume that each mechanism has a player-specific empty outcome $\bot_{j}\in\mathcal{X}_{j}$, which intuitively corresponds to: ”the mechanism is not existent for player $i$”. These outcomes don’t affect the way the mechanism works (e.g. we don’t impose that these outcomes be picked by the mechanism for some strategy profile) but it just serves as a reference point for the valuations of the bidders: we assume that $v(\bot_{1},\ldots,\bot_{m})=0$. We will also use the notation $x_{S}$ to denote the outcome vector that is $x_{j}$ for all $j\in S$ and $\bot_{j}$ otherwise. We start with the generalization of subadditivity of set valuations:

A valuation is set-subadditive if and only if for any two sets $S_{1},S_{2}\subseteq[m]$ and any $x\in\mathcal{X}$:

In addition we define the notion of set-submodularity which extends submodularity of set valuations as follows: the marginal benefit from receiving an allocation $x_{j}$ at some mechanism $\mathcal{M}_{j}$ decreases as the set of mechanisms from which the agent has received a non-empty allocation becomes larger.

A valuation is set-submodular if and only if, for any $x\in\mathcal{X}$ and for any two sets $S\subseteq T\subseteq[m]$:

Last, we will make the intuitive assumption that if a player wins a non-empty allocation in more mechanisms then his valuation increases: a valuation is set-monotone if for any two sets $S\subseteq T$: $v\left(x_{S}\right)\leq v\left(x_{T}\right)$. We show that the relation between these classes of valuations mirrors the relations of the analogous classes for traditional valuations.

If a valuation is set - monotone and set-submodular then it is XOS.

If a valuation is set-monotone and set-subadditive then it is $H_{m}$-XOS, where $H_{m}$ is the $m$-th harmonic number.

If each poset $(\mathcal{X}_{j},\succeq_{j})$ forms a lattice then it is natural to consider valuations that have diminishing marginal returns over this lattice: i.e. for any $z\succeq y$ and $t\in\mathcal{X}$

If the lattice is distributive and the valuation is monotone then the above class of valuations is equivalent to the class of submodular valuations over the lattice (proof in Appendix).

Smooth Mechanisms

In this section we introduce the notion of a smooth mechanism for settings where agents have quasi-linear preferences. Our notion is similar to the smoothness of games of Roughgarden , but is tailored to the setting of mechanisms where participants have quasilinear preferences.

A mechanism $\mathcal{M}$ is $(\lambda,\mu)$-smooth if for any valuation profile $v\in\times_{i}\mathcal{V}_{i}$ and for any action profile $a$ there exists a randomized action $\mathbf{a}_{i}^{*}(v,a_{i})$ for each player $i$, s.t.:

for some $\lambda,\mu\geq 0$. We denote by $u_{i}^{v_{i}}(\mathbf{a})$ the expected utility of a player if $\mathbf{a}$ is a vector of randomized strategies.

The definition of a smooth mechanism has a very natural interpretation as guaranteeing an approximate analog of market cleaning prices. Bikhchandani showed that pure Nash equilibria of a simultaneous first price auction have market clearing prices, and this implies that the outcome is efficient. Aggregate market clearing prices are guaranteed when each participant can modify her bid to claim her optimal bundle at the price paid for this bundle in the current solution. $(1,1)$-smoothness in essence requires this property only in aggregate, but for any outcome of the mechanism, not only at equilibrium. While $(\lambda,\mu)$-smoothness requires this only approximately, both in terms of the bundle claimed, as well as the price paid for it. In addition, unlike the pure equilibrium analysis, it requires the modified bid to be ignorant of the actions of the rest of the players.

We show that smooth mechanisms have low price of anarchy and that this result extends to all correlated equilibria (and hence learning outcomes) in the complete information setting and to all Bayes-Nash equilibria in the incomplete information setting without any change in the assumption.

If a mechanism is $(\lambda,\mu)$-smooth and players have the possibility to withdraw from the mechanism then the expected social welfare at any Correlated Equilibrium of the game is at least $\frac{\lambda}{\max\{\mu,1\}}$ of the optimal social welfare.

Proof sketch. We prove the theorem for the case of a Pure Nash Equilibrium $a$. Since players have quasi-linear utilities we have: $v_{i}(X_{i}(a))=u_{i}(a)+P_{i}(a)$. Using that no player wants to deviate to $\mathbf{a}_{i}^{*}(v,a_{i})$ we get:

The result follows if $\mu\leq 1$. When $\mu>1$, to get the result, we note that $v_{i}(X_{i}(a))\geq P_{i}(a)$, as players have the possibility to withdraw from the mechanism and get 0 utility.

Our notion of smoothness of a mechanism differs from Roughgarden’s notion of smoothness of games. To think of a mechanism as a game, we will consider the mechanism also as a player, with utility $\sum_{i}P_{i}(a)$ and no strategic decision to make. Our definition of a $(\lambda,\mu)$-smooth mechanism, is closely related to the game being $(\lambda,\mu-1)$-smooth in the sense of , with two differences. We dropped the term $-(\mu-1)\sum_{i}u_{i}^{v_{i}}(a)$ on the right hand side, to make the definition more natural in the context of mechanisms. Note that this change makes the definitions incomparable, as with an arbitrary action profile $a$, the player utilities $u_{i}^{v_{i}}(a)$ can be negative. Second, we allow the deviating strategy $a_{i}^{*}(v,a_{i})$ to depend both on the valuation vector $v$ and the strategy of the deviating player $i$. This difference causes our Theorem 4.2 to only hold for correlated equilibria, and not coarse correlated equilibria. Allowing the deviating strategy to depend on $a_{i}$ makes it possible to prove a composability theorem for sequential mechanisms, where it is important to allow the deviating player to “wait for the right moment” to deviate. In games where the deviation required by smoothness does not depend on $a_{i}$, our results extend to coarse correlated equilibria. We focus on the version that allows this dependence so as to capture sequential composition. Simultaneous composition works well with either version of the definition.

Incomplete Information Setting. Next we consider the case where the valuation of each player is drawn from a distribution $F_{i}$ over his valuation space $\mathcal{V}_{i}$. These distributions are independent and are common knowledge. A mechanism $\mathcal{M}=(\mathcal{A},X,P)$ now defines a game of incomplete information. The strategy of each player is a function $s_{i}:\mathcal{V}_{i}\rightarrow\mathcal{A}_{i}$. We will use $s(v)=(s_{i}(v_{i}))_{i\in N}$ to denote the vector of actions given a valuation profile $v$ and $s_{-i}(v_{-i})=(s_{j}(v_{j}))_{j\neq i}$ to denote the vector of actions for all players except $i$.

The dominant solution concept in incomplete information games is the Bayes-Nash Equilibrium (BNE). A Bayes-Nash Equilibrium is a strategy profile (possibly randomized) such that each player maximizes his expected utility conditional on his private information.

Extension Theorem. The main result of this section is to show that if a mechanism is smooth according to definition 4.1 then it achieves a good fraction of the expected optimal social welfare at every Bayes-Nash equilibrium of the incomplete information game, irrespective of the distributions of valuations. In the appendix we extend this result to general normal form games, strengthening the result of Roughgarden and Syrgkanis where a strengthened notion of smoothness (universal smoothness) was used to establish efficiency results in the incomplete information setting. In addition, the previous definitions of smoothness in normal form games did not allow the deviating strategy to depend on the previous action of the deviating player and thereby wouldn’t allow us to capture sequential games.

Note that the deviating strategy $\mathbf{a}_{i}^{*}(v,a_{i})$ of player $i$ required by the smoothness property depends on the whole valuation profile $v$ and not only on the valuation of player $i$. As a result $\mathbf{a}_{i}^{*}(v,a_{i})$ cannot be directly used as deviation for the player in the incomplete information game, as she is not aware of the valuations $v_{-i}$. We use random sampling to handle the dependence on the values of other players, and a bluffing technique to handle the dependence on the action of the deviating player.

If a mechanism $\mathcal{M}$ is $(\lambda,\mu)$-smooth and players have the possibility to withdraw, then for any set of independent distributions $F_{i}$, every mixed Bayes-Nash Equilibrium of the game induced by $\mathcal{M}$ has expected social welfare at least $\frac{\lambda}{\max\{\mu,1\}}$ of the expected optimal social welfare.

We will prove it for the case of a pure Bayes-Nash equilibrium $s(v)$ (the generalization to mixed equilibria is straightforward). Consider the following randomized deviation for each player $i$ that depends only on the information that he has which is his own value $v_{i}$ and the equilibrium strategies $s(\cdot)$: He random samples a valuation profile $w\sim\times_{i}F_{i}$. Then he plays $\mathbf{a}_{i}^{*}((v_{i},w_{-i}),s_{i}(w_{i}))$, i.e., the player considers the equilibrium actions $s(w)$, using the randomly sampled type (including the random sample of his own type), and deviates from this action profile using the action given by the smoothness property for his true type $v_{i}$, the random sample of the types of the others $w_{-i}$, and the equilibrium action $s_{i}(w_{i})$ of his randomly sampled type $w_{i}$. Using the action $s_{i}(w_{i})$ as the base, corresponds to a bluffing technique that was introduced in in the context of sequential first price auctions, where player $i$ “pretends” that his valuation was $w_{i}$ until he deviates.

Since this is not a profitable deviation for player $i$:

Summing over players and using the smoothness property:

By quasi-linearity of utility and using the fact that players have the possibility to withdraw from the mechanism, we have the result.

Composition Theorems

Simultaneous Composition of Mechanisms. For simultaneous composability of mechanisms we require that each mechanism is $(\lambda,\mu)$-smooth, and that the valuation is fractionally subadditive over outcomes of mechanisms. To state the result more generally, recall that Theorem 3.3 implies that the valuation is also XOS.

Consider a valuation profile $v$ and an action profile $a$. Let $x^{*}$ be the optimal allocation for type profile $v$. Let $v_{ij}^{*}$ be the representative additive valuation for player $i$ for $x_{i}^{*}$ as implied by the definition of XOS valuations, i.e. $v_{i}(x_{i}^{*})=\sum_{j}v_{ij}^{*}(x_{ij}^{*})$ and for all $x_{i}\in\mathcal{X}_{i}$: $v_{i}(x_{i})\geq\sum_{j}v_{ij}^{*}(x_{i}^{j})$.

To prove the theorem we will show that there exists a deviation $\mathbf{a}_{i}^{*}=\mathbf{a}_{i}^{*}(v,a_{i})$ of the global mechanism such that:

To define such a deviation we use the fact that each mechanism $\mathcal{M}_{j}$ is $(\lambda,\mu)$-smooth. Suppose that we run mechanism $\mathcal{M}_{j}$ and each player has valuation $v_{ij}^{*}$ on $\mathcal{X}_{i}^{j}$ and let $v_{j}^{*}$ be this valuation profile. Since, by assumption those valuations fall in the valuation space $\mathcal{V}_{i}^{j}$ for which smoothness of $\mathcal{M}_{j}$ holds, for any action profile $a^{j}$ there exists a randomized action $\mathbf{a}_{ij}^{*}=\mathbf{a}_{ij}^{*}(v_{j}^{*},a_{i}^{j})$ for each player, such that the sum of the utilities of the agents when each agent unilaterally deviates to it, is at least $\lambda\sum_{i}v_{ij}^{*}(x_{ij}^{*})-\mu\sum_{i}P_{i}^{j}(a^{j})$.

For the global mechanism, we consider a randomized deviation $\mathbf{a}_{i}^{*}=\mathbf{a}_{i}^{*}(v,a_{i})$ of player $i$ that consists of independent randomized deviations $\mathbf{a}_{ij}^{*}=\mathbf{a}_{ij}^{*}(v_{j}^{*},a_{i}^{j})$ for each mechanism $j$ as described in the previous paragraph. For each action $a_{i}^{*}$ in the support of $\mathbf{a}_{i}^{*}$ we denote with $X_{i}(a_{i}^{*},a_{-i})$ the outcome vector in that action profile. By the properties of the representative additive valuation, we have that $v_{i}(X_{i}(a_{i}^{*},a_{-i}))\geq\sum_{j}v_{ij}^{*}(X_{i}^{j}(a_{ij}^{*},a_{-i}^{j}))$. Thus the expected utility of player $i$ from the deviation will be at least:

is the sum of the expected utilities where starting from strategy profile $a^{j}$ each player $i$ unilaterally deviates to a randomized bid $\mathbf{a}_{ij}^{*}=\mathbf{a}_{ij}^{*}(v_{j}^{*},a_{i}^{j})$ in mechanism $\mathcal{M}_{j}$ and when each player $i$ has valuation $v_{ij}^{*}$ for the different outcomes $x_{i}^{j}$ of mechanism $\mathcal{M}_{j}$. By smoothness of each mechanism $\mathcal{M}_{j}$:

where we used that by the definition of the representative additive valuation $v_{i}(x_{i}^{*})=\sum_{j\in[m]}v_{ij}^{*}(x_{ij}^{*})$.

In Sections 6 and 9 we will give a number of applications of this result. Note that if the classes $\mathcal{V}_{i}^{j}$ contain single-minded valuations (e.g. in the case of combinatorial auctions), then our composability theorem holds for any fractionally subadditive valuation. For classes of valuations that do not contain single-minded valuations (such as ad-auctions), we can apply the theorem using results from Section 3 on monotone and lattice-submodular valuations.

Sequential Composition of Mechanisms. In many scenarios, mechanisms might not all take place simultaneously. Sequentiality however can lead to inefficiencies as was shown by recent works on sequential auctions . Here, we show that the positive results of on unit-demand sequential first price auctions are a special case of a more general property of smooth mechanisms. For the sequential composition of $m$ mechanisms we prove that if each mechanism $\mathcal{M}_{j}$ is $(\lambda,\mu)$-smooth, then the resulting mechanism is $(\lambda,\mu+1)$-smooth (for the normal form representation of the extensive form of game) if an agents valuation is the best of her valuation over the different mechanisms: $v_{i}(x_{i})=\max_{j\in[m]}v_{i}^{j}(x_{i}^{j})$.

An interesting aspect of the sequential composition is that the strategy of a player is no longer just an action $a_{i}^{j}\in\mathcal{A}_{i}^{j}$ for each mechanism but rather a whole contingency plan of what action she will submit to mechanism $\mathcal{M}_{j}$ conditional on any observed history of play. Our result doesn’t depend on what part of the history is observed by the players, whether players just observe their own allocation, or all allocations, or also all prices, or bids. We don’t even need that all players observe the same things. However, we assume that the information structure is common knowledge.

We can combine these two theorems to prove efficiency guarantees when mechanisms are run in a sequence of rounds and at each round several mechanisms are run simultaneously.

An Application: Item Auctions

In this section we present a simple, yet rich, application of our framework to the case where each component mechanism is a single-item auction. We consider the three main single-item auctions: first-price, all-pay and second-price.

First Price Auction. The first price auction is a $(1-1/e,1)$-smooth mechanism. To see the smoothness note that under any valuation profile $v$ (note that we only need to argue about the full information setting), the highest value player with value $v_{h}$ can deviate to submitting a randomized bid $b_{h}^{\prime}$ drawn from a distribution with density function $f(x)=\frac{1}{v_{h}-x}$ and support $[0,(1-1/e)v_{h}]$, while all non-highest value players should just deviate to bidding . No matter what the rest of the players are bidding, the utility of the highest bidder from the deviation is:

Theorem 5.1 now implies that if we run $m$ simultaneous first price auctions and bidders have fractionally subadditive valuations then any Correlated Equilibrium in the full information setting and any mixed Bayes-Nash Equilibrium in the incomplete information setting has social welfare at least $(1-\frac{1}{e})$ of the optimal. A looser result of $1/4$ for this setting and only for mixed Nash and Bayes-Nash appeared in . The tighter result of $(1-\frac{1}{e})$ appeared in . Theorem 5.2 implies that if we run $m$ first price auctions sequentially and bidders have unit-demand valuations then any Correlated Equilibrium in the full information setting and any Bayes-Nash Equilibrium in the incomplete information setting has social welfare at least $\frac{1}{2}(1-\frac{1}{e})$ of the optimal. The latter result was given in a sequence of two papers .

All-Pay Auction. The all-pay auction is a $(1/2,1)$-smooth mechanism. The smoothness proof is similar to the first price auction with the only alteration that we make the highest value player submit a bid drawn uniformly at random from $[0,v_{h}]$. The utility from such a deviation is:

Therefore we get an efficiency guarantee of $1/2$ for the simultaneous composition of $m$ all-pay auctions and an efficiency guarantee of $1/4$ for the sequential composition both in the Bayesian setting and in learning outcomes. Simultaneous and sequential all-pay auctions have not been studied in the literature and could prove useful in capturing simultaneous or sequential all-pay contests, which is a natural model for several online crowd-sourcing environments.

Second-Price Auction. The second price auction is not a smooth mechanism. In fact, the second price auction is not as robust as the previous auctions. Second price auctions have arbitrary bad equilibria when players bid above their value, Goeree shows that signaling is bound to arise in a second price auction when bidders are strategising about future opportunities, and Paes Leme et al show an example with unbounded inefficiency when running second price auctions sequentially and bidders are unit-demand. The main difference of the second price auction and the previous two auctions is that it makes very loose connection between the bid a player needs to make to win and the price that was previously paid to the auctioneer. Several papers have used an assumption that players will not bid above their valuations to give good efficiency guarantees for second-price type of auctions. Next, we extend our results to mechanisms that require such no-overbidding assumptions.

Weak Smoothness

In this section we give a generalization of our framework to capture mechanisms that produce high efficiency under a no-overbidding refinement. First, we give a definition of no-overbidding that generalizes the no-overbidding assumptions used in the literature . In a single-item second-price auction the bid of a player is his maximum willingness to pay when he wins. The following defines maximum willingness to pay in the general mechanism design setting.

Given a mechanism $(\mathcal{A},X,P)$ a player’s maximum willingness-to-pay for an allocation $x_{i}$ when using strategy $a_{i}$ is defined as the maximum he could ever pay conditional on allocation $x_{i}$:

A mechanism is weakly $(\lambda,\mu_{1},\mu_{2})$-smooth for $\lambda,\mu_{1},\mu_{2}\geq 0$, if for any type profile $v\in\times_{i}\mathcal{V}_{i}$ and for any action profile $a$ there exists a randomized action $\mathbf{a}_{i}^{*}(v,a_{i})$ for each player $i$, s.t.:

A randomized strategy profile $\mathbf{a}$ satisfies the no-overbidding assumption if:

i.e., at this strategy profile no player is bidding in a way that she could potentially pay more than her value subject to her expected allocation remaining the same.

If a mechanism is weakly $(\lambda,\mu_{1},\mu_{2})$-smooth then any Correlated Equilibrium in the full information setting and any mixed Bayes-Nash Equilibrium in the Bayesian setting that satisfies the no-overbidding assumption achieves efficiency at least $\frac{\lambda}{\mu_{2}+\max\{\mu_{1},1\}}$ of the expected optimal.

In the Appendix, we show, analogously to the results in Section 5, that the simultaneous composition of weakly $(\lambda,\mu_{1},\mu_{2})$-smooth mechanisms is weakly $(\lambda,\mu_{1},\mu_{2})$-smooth and the sequential composition is weakly $(\lambda,\mu_{1}+1,\mu_{2})$-smooth.

Remark 1. In contrast to the smoothness used in our definition of smoothness allows us to prove efficiency under the weaker assumption of no-overbidding in expectation, rather than point-wise no-overbidding. The main difference is that we incorporate the willingness-to-pay inside the smoothness definition, while previous smoothness approaches would relate to value directly. The latter approach would require to use point-wise no-overbidding to relate bids to welfare in second-price auctions.

Remark 2. We use the non-overbidding assumption as an equilibrium refinement rather than as a strategy-space restriction. Several papers in the literature have used non-overbidding as a strategy space restriction (rather than as an equilibrium refinement). The two uses are equivalent in settings where the restricted strategy space always contains best-responses. Note that while overbidding is a dominated strategy in a single item auction, global no-overbidding is not dominated when running second price auctions simultaneously or sequentially. Overbidding equilibria that survive elimination of dominated strategies and that have non-constant inefficiency have been given both for the case of sequential and simultaneous second price auctions, even in the simplest scenario when bidders are unit-demand. Restricting the strategy space to non-overbidding strategies, could potentially create artificial equilibria that were not equilibria of the original game, since this restricted strategy space does not always contain best-responses (see for an example). On the other hand, the refined set of non-overbidding equilibria might be empty. Some of our results carry over to the strategy-space restriction version and a detailed exposition is deferred to the full version.

Budget Constraints

An important class of non-quasilinear preferences is when players have hard budget constraints on the payments they make. Studying the effect of budgets on efficiency has received great attention in recent algorithmic game theory literature mostly in the realm of truthful mechanism design and assuming that the budgets are common knowledge. Little is known about the effect of budgets in the case of non-truthful mechanisms. For instance, only recently Huang et al. analyzed efficiency in a two-player sequential first price auction game with budget constraints in the complete information setting.

Most of the literature has focused on producing pareto-optimal outcomes, i.e. a pair of allocation and prices such that there is no other pair that respects feasibility and budget constraints and such that all players receive strictly higher utility and the auctioneer receives strictly higher revenue.

We study an orthogonal benchmark, which we call Effective Welfare, obtained by capping a player’s value by his budget:

We compare the social welfare resulting in our mechanism to the maximum possible effective welfare. This benchmark reflects that we cannot expect players with low budgets to be effective at maximizing their own value.

We show that a lot of our results carry over to the effective welfare benchmark, by introducing a strengthening of the smoothness property of mechanisms; a strengthening that is is satisfied by almost all the applications we consider. We focus on smooth mechanisms, but all the results in this section extend to weak smoothness assuming no-overbidding.

A mechanism is conservatively $(\lambda,\mu)$-smooth if it is $(\lambda,\mu)$-smooth in the quasilinear utility setting and the actions in the support of the smoothness deviations satisfy:

If a mechanism is conservatively $(\lambda,\mu)$-smooth and its valuation space is closed under capping, then the social welfare at any correlated equilibrium and at any Bayes-Nash equilibrium is at least $\frac{\lambda}{\max\{1,\mu\}}$ of the expected maximum effective welfare.

Last we show that efficiency guarantees for budget-constraint bidders are composable under the conservative smoothness property for simultaneous composition. Unfortunately, sequential composition doesn’t carry over. In sequential mechanisms a good deviation may require that the player waits and plays according to equilibrium until his optimal mechanism arrives. While ”waiting” he might exhaust his budget.

The composability result is proved in a sequence of two lemmas: first we prove that conservative smoothness of a mechanism composes under XOS valuations and second we show that if the valuation space of each component mechanism is closed under capping then the corresponding valuation space of the composition mechanism is also closed under capping. The latter is shown by proving a structural property of XOS valuations: a valuation produced by capping an XOS valuation is also XOS and can be described by component valuations that are cappings of the component valuations of the XOS representation of the initial valuation. Using these two lemmas we can invoke Theorem 8.2 to get efficiency guarantees for budget constrained bidders in the global mechanism.

Applications

In this section we give several applications of our framework. Some are new smoothness proofs implying new bounds on efficiency, others are reinterpretations of existing literature as smoothness proofs. In each case adding budget constraints gives new results on efficiency of mechanisms, and our results show that the efficiency is preserved by composition of mechanisms. The efficiency guarantees hold for correlated equilibria in the full information setting and for mixed Bayes-Nash equilibria in the incomplete information setting. Our guarantees are with respect to the optimal effective welfare when the players have budget constraints.

Single Item Auctions. Extending the results of Section 6 we show that the first price single item auction is conservatively $\left(1-\frac{1}{e},1\right)$-smooth, the all-pay auction is conservatively $\left(\frac{1}{2},1\right)$-smooth and the second price auction is weakly and conservatively $(1,0,1)$-smooth. We also give a smoothness proof for the hybrid auction in which the winner pays a convex combination of her own bid and the second highest bid. Our framework implies that running $m$ simultaneous first price auctions and bidders have fractionally subadditive valuations and budget constraints achieves efficiency at least $1-\frac{1}{e}$ of the optimal effective welfare. All-pay auctions achieve a guarantee of $\frac{1}{2}$. Second price auctions achieve a guarantee of $\frac{1}{2}$ under the no-overbidding assumption. For sequential auctions with unit-demand bidders and no budget constraints the first price, all-pay and second price auctions give guarantees of $\frac{1}{2}(1-\frac{1}{e})$, $\frac{1}{4}$ and $\frac{1}{2}$ respectively.

Greedy Direct Auctions. Lucier and Borodin considers combinatorial auctions, whose allocation function is based on a greedy $c$-approximation algorithm. When a first price payment is used, they show that such a greedy auction has a $c+O(\log(c))$ efficiency guarantee.We improve this bound, by showing that this mechanism is conservatively $(1-e^{-1/c},c)$-smooth implying an efficiency guarantee of at least $\frac{1}{c+0.58}$. This bound extends to the simultaneous composition of such mechanisms when bidders have fractionally subadditive valuations across auctions and budget constraints. For example, when each auctions sells only a small number of items, greedy algorithms can do quite well (giving a $\sqrt{k}$-approximation for arbitrary valuations, if each auction sells at most $k$ items). Observe, that fractionally subadditive valuations across auctions allow for complements within the items of a single greedy auction, hence is more general than just assuming that players have fractionally subadditive valuations over the whole universe of items. In the appendix, we show that the above analysis is a special case of a more general class of direct auctions.

Position Auctions. We analyze position auctions for more general valuation spaces than what has been typically considered . We use the model of Abrams et al , where each player $i$ has an arbitrary valuation $v_{ij}$ for appearing at position $j$, that is monotone in the position. Most of the literature in position auctions has considered valuations of the form $v_{ij}=a_{j}\gamma_{i}v_{i}$, i.e. players have only value per click $v_{i}$ and their click-through-rate is dependent in a separable way on their quality and on the position. The more general class of valuations can capture settings where players have value both for click and for the impression itself, and settings where the click-through-rates are not separable. We show that the following very simple first price analog of the auction of is conservatively $(\frac{1}{2},1)$-smooth: solicit bids from the players, allocate positions in order of bids and charge each player his bid. The implied guarantee of $\frac{1}{2}$ holds for simultaneous composition when players have monotone fractionally subadditive valuations and budget constraints. Such valuations capture, for instance, settings where bidders have value $v_{i}$ only for the first $k$ clicks, or settings where the marginal value per-click of a player decreases with the number of clicks he gets. In addition a bound of $\frac{1}{4}$ is implied for the sequential composition when bidders value is the maximum value among all impressions he got. In contrast, consider the second price analog of this auction, and show that it always has an efficient Nash equilibrium, but do not consider the price of anarchy. We show that the second price version is conservatively weakly $(\frac{1}{2},0,1)$-smooth, implying an efficiency guarantee of $\frac{1}{4}$ for simultaneous and sequential composition of such auctions under the no-overbidding assumption. In the appendix we also consider other variations of the well-studied GFP and GSP mechanisms for the case when players have only values per click.

References

Appendix A Applications

Our work provides some new results in the context of efficiency of non-truthful mechanisms and unifies previous work. For each application we will show how smooth each mechanism is. Then we will highlight some of the implications that our framework implies. For conciseness we will not list all the implications of our framework for each mechanism, but one can apply all our general theorems for each of the applications. In our efficiency theorems for conciseness we will refer to a correlated equilibrium in the full information setting as CE and to a mixed Bayes-Nash equilibrium in the incomplete information setting as BNE. When we refer to expected welfare then this would be over the randomness of the action profiles in the complete information setting and over the randomness of the valuations, budgets and action profiles in the incomplete information setting. When we refer to settings with budget constraints our bounds are with respect to the optimal effective welfare.

In this section we revisit the three main single-item auctions discussed in Section 6 as well as the hybrid auction where the winner pays a mixture of his bid and the second highest bid and give a complete list of our results.

First Price Auction. As explained in Section 6 a first price auction is $(1-\frac{1}{e},1)$-smooth since for any valuation profile the highest value player with value $v_{\max}$ can deviate to submitting a randomized bid $b_{\max}^{\prime}$ drawn from a distribution with density function $f(x)=\frac{1}{v_{\max}-x}$ and support $[0,(1-1/e)v_{\max}]$. Here we observe that the above deviation also implies conservative smoothness.

The first price single-item auction is conservatively $(1-\frac{1}{e},1)$-smooth.

If we run $m$ simultaneous first price auctions and bidders have budgets and fractionally subadditive valuations then every CE and BNE achieves at least $\frac{e-1}{e}\approx 0.63$ of the expected optimal effective welfare.

If we run $m$ sequential first-price auctions with unit-demand bidders then every CE and BNE achieves $\frac{1}{2}\frac{e-1}{e}\approx 0.32$ of the expected optimal social welfare.

All-Pay Auction. The all-pay auction is $(1/2,1)$-smooth since the highest value player submit a bid drawn uniformly at random from $[0,v_{\max}]$ as shown in section 6. Observe again that this deviation also implies conservative smoothness. Hence:

If we run $m$ simultaneous all-pay auctions and bidders have budgets and fractionally subadditive valuations then the expected effective welfare at every CE in the complete information case and at every BNE in the incomplete information case is at least $1/2$ of the expected optimal effective welfare.

If we run $m$ sequential all-pay auctions with unit-demand bidders then every CE and BNE achieves $1/4$ of the expected optimal social welfare.

Second Price Auction. In a second-price auction the winning bidder pays the second highest bid. Here we show that the second price auction is weakly $(1,0,1)$-smooth. Observe that in a hybrid auction the willingness to pay of a winning bidder is exactly his bid. This can be easily shown since the highest value player can switch to bidding his true value in which case his utility is at least $v_{\max}-b$ where $b$ was the highest bid in the previous strategy profile and hence the willingness-to-pay of the winning bidder in the previous strategy profile.

The second price auction is weakly $(1,0,1)$-smooth.

If we run $m$ simultaneous second price auction and bidders have budgets and fractionally subadditive valuations then any CE and BNE that satisfies the weak no-overbidding assumption globally, achieves at least $1/2$ of the optimal social welfare.

If we run $m$ sequential second price auctions with unit-demand bidders then every CE and BNE that satisfies the no-overbidding assumption achieves $1/2$ of the expected optimal social welfare.

Hybrid Auction. In the $\gamma$-hybrid auction the winner pays his bid with probability $\gamma$ and the second highest bid with probability $(1-\gamma)$.

Consider a valuation profile $v$ and a bid profile $b$. Let $b_{\max}$ the highest bid and $v_{\max}$ the highest value. The non highest value bidders deviation is bidding . The highest value bidder’s deviation is bidding as follows: With probability $\gamma$ he submits a bid according to distribution with density $f(t)=\frac{1}{v_{\max}-t}$ and support $[0,(1-\frac{1}{e})v_{\max}]$. With probability $(1-\gamma)$ he submits his true value.

In the first case the utility of the bidder is at least:

In the case when he submits his true value then when $b_{\max}<v_{\max}$ he wins and gets utility

When $b_{\max}\geq v_{\max}$ he either loses or ties and in any case gets non-negative utility and thereby utility at least $(1-\gamma)(v_{\max}-b_{\max})$.

Thus overall the expected utility from the deviation is at least:

The lemma follows by just observing that the payment under bid profile $b$ is at least $\gamma b_{\max}$

If we run $m$ simultaneous $\gamma$-hybrid auctions and bidders have budgets and fractionally subadditive valuations then every CE and BNE that satisfies the no-overbidding assumption achieves $\frac{\gamma(1-\frac{1}{e})+(1-\gamma)^{2}}{1+(1-\gamma)^{2}}$ of the expected optimal social welfare.

If we run $m$ sequential $\gamma$-hybrid auctions with unit-demand bidders then every CE and BNE achieves $\frac{\gamma(1-\frac{1}{e})+(1-\gamma)^{2}}{2+(1-\gamma)^{2}}$ of the expected optimal social welfare.

A.2 Direct Auctions.

Is there a similar characterization for the more general setting? For more general settings the standard mechanism that is efficient and guarantees non-negative prices and individual rationality is the VCG mechanism. Unfortunately, the VCG mechanism doesn’t have a similar simple "threshold bid" interpretation. Despite this fact, one could still define threshold bids in the more general quasi-linear setting as follows:

To make a mechanism truthful in a single parameter setting remember that one had to strongly tie together the threshold bids of the players with their actual payments. In what follows we show that even in smooth mechanism design in order to get approximately efficient smooth mechanisms one needs to approximately tie threshold bids to the payments.

The above relation between threshold bids and payments is in the essence of the analysis of Lucier and Borodin as described in the next section.

First, we show that if a mechanism is $c$-threshold approximate then this implies a good efficiency guarantee on the Bayes-Nash Equilibria of the game that it induces.

If a direct mechanism is $c$-threshold approximate and individually rational then it is

for any $\beta\geq 0$. Moreover, it is also conservatively smooth.

Thus the utility of a player from this deviation is at least:

Now a player by using a randomized $\Theta$ that follows a distribution with density $f(\theta)=\frac{\beta}{v_{i}(x_{i}^{*}(v))-\theta}$ for $\theta\in[0,v_{i}(x_{i}^{*}(v))(1-e^{-1/\beta})]$ he will get expected utility at least:

Adding over all players and using the $c$-threshold payment approximate property we get the theorem.

If a direct mechanism is $(c_{1},c_{2})$-threshold approximate and individually rational then it is weakly and conservatively

The proof is similar to that of Theorem A.14 and is omitted.

Greedy Direct Combinatorial Auctions A very interesting instance of $c$-threshold approximate mechanisms in the literature is that of Greedy Direct Auctions introduced by Lucier and Borodin . In the terminology that we introduced in the previous section, Lucier and Borodin proved that in any direct combinatorial auction setting if the allocation is decided by a greedy $c$-approximate mechanism then coupling the mechanism with a first price payment rule we get a $c$-threshold approximate mechanism. These proofs don’t assume anything about the valuation of a player and allow for complements.

We note that not all greedy algorithms adhere to the framework defined by Lucier and Borodin . In Section A.7 we show how smoothness can capture a version of the $2$-approximation algorithm by Lehmann et al. not captured by . The greedy mechanisms studied in are as follows.

Remove both $i$ and $S$ from consideration and repeat until all items are allocated.

The ranking function is monotone in $S$ (by inclusion) and $v_{i}(S)$ and could potentially be adaptive with respect to the existing allocation. For the case of general combinatorial auctions a $\sqrt{k}$-approximate greedy such algorithm exists, where $k$ is the number of items.

Hence, for the setting of greedy first price $c$-approximate combinatorial auctions our framework implies:

Any CE or BNE of a greedy $c$-approximate first price combinatorial auction achieves at least $\frac{1-e^{-c}}{c}$ of the expected optimal social welfare. If bidders have budgets then it achieves the same fraction of the optimal effective welfare.

Lucier and Borodin give a bound of $\frac{1}{c+O(\log(c))}$ for the efficiency of such a greedy auction. More specifically the bound is $\frac{c-1-\log(c)}{c(c+1+\log(c))}$. Our bound is asymptotically same, but is strictly better. Our bound decreases as $\frac{1}{c+O(ce^{-c})}$ rather than $\frac{1}{c+O(\log(c))}$. When $c=1$ the bound coincides with the bound of $1-\frac{1}{e}$ for the first price single item auction and our bound is always larger than $\frac{1}{c+\frac{1}{e-1}}\approx\frac{1}{c+0.58}$ and thereby decreases exactly linearly with $c$.

Our composability framework gives new results for the case when several greedy combinatorial auctions are run simultaneously or sequentially.

If we run $m$ greedy $c$-approximate first price combinatorial auctions simultaneously and bidders have budgets and fractionally subadditive valuations across mechanisms, then any CE and any BNE achieves at least $\frac{1-e^{-c}}{c}$ of the expected optimal effective welfare.

If we run $m$ greedy $c$-approximate first price combinatorial auctions sequentially and bidders have unit-demand valuations across mechanisms, then any CE and any BNE achieves at least $\frac{1-e^{-c}}{c+1}$ of the expected optimal social welfare.

Recall that fractional subadditivity across mechanisms does not impose any assumption on the valuations within each greedy combinatorial auction. Hence, the valuations of the bidders could have complements within the items sold in each greedy auction, as long as they don’t have complements across items sold in different auctions.

A.3 Position Auctions

In this section we consider a generalized version of position auctions introduced by Abrams et al , which allows us to extend analysis of ad auctions to simultaneous and sequential composition as well as to the case where players have budget constraints. It also allows us to capture settings where bidders have values not only per-click but also per-impression, which is considered an interesting direction from a practical perspective since many companies on the web strive mainly for impressions rather than clicks. We also propose new simple mechanisms that are approximately efficient and robust in terms of simultaneous and sequential composition and in terms of budget constraints.

Consider a setting where the outcome space is an allocation of $n$ positions to $n$ agents. Each agent has a valuation $v_{ij}$ for being allocated position $j$ and such that the valuations of all the agents are monotone decreasing: if $j\leq j^{\prime}$ then $v_{ij}\geq v_{ij^{\prime}}$. The value $v_{ij}$ could be thought of as the value of player $i$ for appearing at position $j$. This value could consist of a per-click part and a per-impression part. For instance, if the bidder thinks that his click-through-rate at position $j$ is $a_{ij}$ and knows that his value per-click is $v_{i}^{\text{c}}$, while he also has a value $v_{ij}^{\text{im}}$ for appearing at position $j$, then his valuation for position $j$ is: $v_{ij}=a_{ij}v_{i}^{\text{c}}+v_{ij}^{\text{im}}$. We just assume that the above total value is monotone in position.

Observe that in our framework notation the allocation space $\mathcal{X}$ consists of vectors $x=(j_{1},\ldots,j_{n})$ such that $j_{i}\neq j_{i^{\prime}}$ for all $i\neq i^{\prime}$. In addition the allocation space of each player $\mathcal{X}_{i}=\{1,\ldots,n\}$ is totally ordered from his perspective (in that any outcome where he gets a higher position is greater than any outcome where he gets a lower one) and the value of a player is monotone with respect to his own ordering of allocations.

A position mechanism $M$ defines the action space of the players. We will consider here mechanisms where players submit only a single bid $b_{i}$ (interpreted differently by the different mechanisms that we consider). Given a bid profile, the allocation function of a position mechanism is to assign a position $j_{i}(b)$ to each player $i$ and the payment of each player is some function of the bid profile $P_{i}(b)$.

We show that for the class of position-monotone valuations a greedy first price pay-per-impression mechanism (Mechanism 1) is $(\frac{1}{2},1)$-smooth and its second price analog is weakly $(\frac{1}{2},0,1)$-smooth.

Mechanism 1 is conservatively $\left(\frac{1}{2},1\right)$-smooth when valuations are monotone in the position.

Consider a valuation profile $v$ and any bid profile $b$ and let $j^{*}_{i}$ be the optimal position of player $i$ under valuation profile $v$. Suppose that player $i$ deviates to bidding according to the uniform distribution $U[0,v_{ij^{*}_{i}}]$. For a given bid profile $b$, let $\pi(j)$ be the player allocated at position $j$. If the bid that the player submits is greater than $b_{\pi(j_{i}^{*})}$ then he is allocated position at least as high as $j_{i}^{*}$. By monotonicity of valuations with respect to position we get that his utility from the deviation is at least:

where $f(x)=1/v_{ij^{*}_{i}}$ is the density function. Summing over all players we get the theorem.

The fact that the above mechanism is smooth for any monotone valuation allows us to invoke Theorem 3.8 and get composability results. In addition the fact that the class of monotone valuations is closed under cappings allows us to invoke our budget constraint results.

If we run $m$ greedy first price pay-per-impression mechanisms simultaneously and bidders have monotone fractionally subadditive valuations and budget constraints then any CE and BNE achieves at least $1/2$ of the expected optimal effective welfare.

If we run $m$ greedy first price pay-per-impression mechanisms sequentially and bidders have unit-demand valuations then every CE and BNE achieves at least $1/4$ of the expected optimal welfare.

Note that in the last theorem, unit-demand valuations in our terminology, means that a players value for getting several impressions at different position mechanisms is of the form:

where the induced valuations $v_{i}^{k}(j_{i}^{k})$ are monotone in the position $j_{i}^{k}$ allocated at position mechanism $\mathcal{M}_{k}$.

Threshold-Price Mechanism 1. We also consider the variation of Mechanism 1 studied in Abrams et al. , where each player is charged the bid of the player in the position beneath him. We show that such a mechanism is conservatively and weakly $\left(\frac{1}{2},0,1\right)$-smooth, implying a bound of $1/4$ in isolation, when composed simultaneously under budget constraints and when composed sequentially.

In it was shown that in the full information setting there will always exist a Pure Nash Equilibrium of this mechanism that achieves optimal social welfare, thereby generalizing the result of Edelman et al where only valuations per-click where considered. However, no price of anarchy analysis exists for this mechanism and the Bayesian setting or solution concepts that use randomization have not been studied.

First, we clarify our no-overbidding assumption for the mechanism of . In this mechanism when a player is allocated position $j$ with a bid $b_{i}$ then his maximum willingness-to-pay is $b_{i}$, since in the strategy profile where the player in position $j+1$ bids $b_{i}$ too, he is charged $b_{i}$. Thus under Definition 7.1 of willingness-to-pay we have:

Using a proof identical to that of Lemma A.20 we can show the weak and conservative smoothness of this mechanism.

The threshold price version of Mechanism 1 where each player is charged the bid in the position beneath him is weakly and conservatively $\left(\frac{1}{2},0,1\right)$-smooth.

Our no-overbidding assumption states that in expectation no player is bidding more than his value for the expected position he gets. A randomized bid profile ${\bf b}$ satisfies the no-overbidding assumption if:

If a player participates in many position auctions his strategy is to submit a bid $b_{i}^{k}$ at each position auction $\mathcal{M}_{k}$. Let $b_{i}=(b_{i}^{k})_{k\in[m]}$ and $b^{k}=(b_{i}^{k})_{i\in[n]}$. Then the no-overbidding assumption generalizes to:

Under this no-overbidding assumption, our framework gives the following results.

If we run $m$ greedy threshold price pay-per-impression mechanisms simultaneously and bidders have monotone fractionally subadditive valuations and budget constraints then any CE and BNE that satisfies the no-overbidding assumption, achieves at least $1/4$ of the expected optimal effective welfare.

If we run $m$ greedy threshold price pay-per-impression mechanisms sequentially and bidders have unit-demand valuations then every CE and BNE that satisfies the no-overbidding assumption, achieves at least $1/4$ of the expected optimal welfare.

To draw a stronger connection with existing position auction literature we now examine the case when bidders have only valuations per-click and not per impression. We will consider two special cases of bidder valuations:

While this class of valuations neglects effects captured by the more general valuation models, special cases of this model are widely used in the literature. The latter case contains the separable model that has been long studied in the algorithmic game theory literature and has become the standard .

We say that the click through rates are separable, when $a_{ij}=\alpha_{j}\gamma_{i}$ for all $i$ and $j$, that is, the click through rate is the product of a factor depending on the slot and a factor depending on the advertiser.

We use our smoothness framework to strengthen results in the literature. We give a simple smooth mechanism for the first case, which is equivalent to the standard form of the Generalized First Price (GFP) auction when specialized to the case of separable click-through rates $a_{ij}=\alpha_{j}\gamma_{i}$, showing an $1/2$ efficiency bound on GFP and its generalization to the first case above, and an $1/4$ efficiency bound for the corresponding second price analog.

For the second case, we show that the above auction is $(1-1/e,1)$ smooth when using first price and weakly $(1-1/e,0,1)$ smooth when using second price. This result generalizes the efficiency bound of $\frac{1}{2}(1-\frac{1}{e})$ of Caragiannis et al that considered only the separable case when $a_{ij}=\alpha_{j}\gamma_{i}$.

Note, however, that this class of valuations is not closed under capping, so our results do not extend to the case with budgets. The smoothness results we provide in the remainder of the section do imply efficiency guarantees in isolation and for special cases of complement-free valuations (e.g. bidders have value only for the $k$ highest impressions they got and their value per impression is of the form for which smoothness is proved).

Mechanism 2 is $\left(\frac{1}{2},1\right)$-smooth when click-through-rates and valuations per click are monotone in the position.

By summing over all players we get the theorem.

Separable CTRs. Observe that when the click-through-rates are separable, then Mechanism 2 takes the standard form of the Generalized First Price (GFP) auction that has been studied in the literature. Specifically, the allocation function of Mechanism 2 can be concisely described as: weight each players bid by his quality factor and allocate positions in order of the weighted bid. Each player is then charged his bid, per-click: $a_{j_{i}(b)}\gamma_{i}b_{i}$. Hence, the utility of a player at some bid profile is:

The specialization of Lemma A.27 for separable click-through-rates gives a $\frac{1}{2}$ efficiency bound for the Generalized First Price auction even when the per-click valuations of the players.

The Generalized First Price Auction is $\left(\frac{1}{2},1\right)$-smooth when click-through-rates are separable and valuations per-click are dependent on the position.

Mechanism 2 is $\left(1-\frac{1}{e},1\right)$-smooth when per-click valuations are position independent even if click-through-rates are not separable.

(where $\pi(j)$ is the player at position $j$ in the current bid profile) then player $i$ is assigned a position at least as high as $j^{*}_{i}$. Thus his utility from the deviation is:

By summing over all players we get the theorem.

If the click-through-rates are separable, then this brings us to the standard model studied in the literature, where the valuation of a player $i$ from being assigned at position $j$ is: $a_{j}\gamma_{i}v_{i}$ and thereby the utility of a player at some bid profile is:

The specialization of Lemma A.29, gives a better smoothness property for the Generalized First Price Auction.

The GFP auction is $\left(1-\frac{1}{e},1\right)$-smooth when per-click valuations are position independent and click-through-rates are separable.

Under this valuation model the threshold-price version of Mechanism 2 becomes the standard Generalized Second Price (GSP) auction introduced by Edelman et al and extensively studied from the price of anarchy perspective . In this mechanism, under strategy profile $b$, each player $i$ is charged $\frac{\gamma_{\pi(j_{i}(b)+1)}b_{j_{i}(b)+1}}{\gamma_{i}}$ per-click, where $\pi(j)$ is the player that got position $j$ under bid profile $b$, and thus his utility at some bid profile is:

In this mechanism a player’s willingness-to-pay for a position $j$ is simply $a_{j}\gamma_{i}b_{i}$ since in the special case where the player beneath him was bidding $\frac{\gamma_{i}}{\gamma_{\pi(j_{i}(b)+1)}}b_{i}$, player $i$ is charged an expected total payment of $a_{j}\gamma_{i}b_{i}$. Thus from Definition 7.1 of willingness-to-pay we have that:

Our no-overbidding assumption will then become:

Under the no-overbidding assumption and using the same proof as in Lemma A.29 specialized for separable click-through-rates would give that the Generalized Second Price auction is weakly $\left(1-\frac{1}{e},0,1\right)$-smooth. This implies the efficiency result of $\frac{1}{2}\left(1-\frac{1}{e}\right)$ that was given in Caragiannis et al and the proof of Lemma A.29 is a generalization of their analysis.

The Generalized Second Price auction is weakly $\left(1-\frac{1}{e},0,1\right)$-smooth when per-click valuations are position independent and click-through-rates are separable.

In fact applying the same proof of Lemma A.29 we get a generalization of this result for non-separable click-through-rates.

The threshold-price version of Mechanism 2 is weakly $\left(1-\frac{1}{e},0,1\right)$-smooth when per-click valuations are position independent, even if the click-through-rates are not separable.

This result implies an efficiency bound of $\frac{1}{2}\left(1-\frac{1}{e}\right)$ under the same no-overbidding assumption that was used by Caragiannis et al .

A.4 Public Goods Auctions

In this section we consider a first price auction for choosing a public good and show that it is $(\frac{1-e^{-n}}{n},1)$-smooth where $n$ is the number of participants in the mechanism. This bound is proportional to the number of participants in the auction. We then give an application of a simultaneous public good auction where the number of participants at each one is small. We leave as a very important open question whether there exist smooth mechanisms for the combinatorial public project setting that imply efficiency guarantees that are independent of the number of participants.

We consider the following formal setting: there are $n$ bidders and $m$ public projects. The mechanism wants to choose a single public project to implement and each player $i$ has a value $v_{ij}$ if project $j$ is implemented.

A generalization of Mechanism 3 where multiple projects are to be chosen and bidders have combinatorial valuations on the projects, is considered by Singer et al , who give an efficiency analysis for pure, correlated and Bayes-Nash equilibria. For the special case that we describe here, their analysis implies an efficiency bound of $\frac{1}{n+1}$. The following lemma gives a slightly better result.

Mechanism 3 is $(\frac{1-e^{-n}}{n},1)$-smooth.

Consider a valuation profile $v$ and a bid profile $b$. Let $j^{*}$ be the optimal project for this valuation profile and let $j(b)$ be the project chosen under bid profile $b$. Suppose that each player $i$ deviates to bidding $f(t)=\frac{1/n}{v_{ij^{*}}-b}$ with support $[0,(1-e^{-n})v_{ij^{*}}]$ on project $j^{*}$ only. Let $B_{j}$ be the total bid of project $j$ under bid profile $b$. Then the utility of player $i$ from the deviation, even if he is the only one bidding on project $j^{*}$, is at least:

Simultaneous Local Public Good Auctions. Consider a social network setting where players bid for facilities to be placed on nodes in a social network. Each node is an agent and when a facility is placed on a node then all of the neighbors of the node can use it. There exists a set of facilities $F_{u}$ that can be placed on each node $u$ (let $F_{u}$ contain also the empty facility for the case where no facility is built). Now we assume that auctioneers run a public good auction on each node to decide which facility they are going to place. Specifically, he asks from the node and its neighbors to submit a bid for each possible facility. Then he is going to choose the facility that received the highest sum of bids and charge each player his bid for the chosen facility.

Each mechanism is $(\frac{1-e^{-d_{i}}}{d_{i}},1)$-smooth where $d_{i}$ is the degree of the node that is auctioned. Now our framework shows that if we run simultaneous such auctions and the valuation of a player is a fractionally subadditve valuation over the facilities placed on his neighboring nodes, then the overall social welfare of this game will be at most $\frac{D}{1-e^{-D}}$ where $D=\max_{i}d_{i}$. Similarly, one could imagine of a setting where facilities are not placed on nodes of the graph but rather on edges of it or on hyper-edges in a hyper-graph that tries to model groups of interested agents. In such settings our framework implies that the above simultaneous local public good mechanism has price of anarchy at most $\frac{k}{1-e^{-k}}$, where $k$ is the size of the hyper-edge.

A.5 Proportional Bandwidth Allocation Mechanism

In this section we consider the bandwidth allocation setting of Johari and Tsitsiklis . In this setting a bandwidth of $C$ is to be split among $n$ bidders. The bidders submit a bid $b_{i}$ which they have to pay no matter how much bandwidth they receive. Given the bid profile each player is allocated a bandwidth proportional to his bid:

Each player has a concave value function $v_{i}(x_{i})$ for getting a share of bandwidth $x_{i}$, with $v_{i}(0)=0$, and his utility is quasi-linear with respect to payments:

As one can easily observe the latter mechanism falls into our general definition of a mechanism with quasi-linear preferences. We will show that such a mechanism is $(2-\sqrt{3},1)$-smooth. This will imply efficiency guarantees of approximately $1/4$ for any CE and BNE as well as for simultaneous compositions and sequential composition of bandwidth allocation mechanisms. For the simultaneous setting it also implies such a bound even when players have budget constraints. Johari and Tsitsiklis give an efficiency bound of $3/4$ but their efficiency guarantee is proved only for the case of pure nash equilibria and only in the complete information setting. Hence, though our bound is slightly worse, it is a bound that extends to a plethora of relaxations and extensions.

Given a valuation profile $v$ for each player, let $x_{i}^{*}(v)$ be the bandwidth allocated to player $i$ in the optimal allocation. For simplicity we will denote it with $x_{i}^{*}$ for the remainder of the proof since we focus on a specific valuation profile.

Consider the deviation where player $i$ deviates to bidding uniformly at random $B_{i}\sim U[0,\lambda v_{i}(x_{i}^{*})]$, for some constant $\lambda$ that will be determined later on. Then his expected utility for any bid profile $b_{-i}$ is as follows:

Given the bids of the rest of the players $b_{-i}$, if player $i$ bids above $\frac{x\sum_{j\neq i}b_{j}}{C-x}$ then he is given a bandwidth share of at least $x$ for any $x$. Thus for all the $t\geq\frac{x_{i}^{*}\sum_{j\neq i}b_{j}}{\mu C-x_{i}^{*}}$ player $i$ is allocated a bandwidth of at least $x_{i}^{*}/\mu$.

Thus by monotonicity of $v_{i}$ his utility from the deviation is at least:

By concavity and the fact that $v_{i}(0)=0$ we know that $v_{i}\left(\frac{x_{i}^{*}}{\mu}\right)\geq\frac{v_{i}(x_{i}^{*})}{\mu}$ for any $\mu\geq 1$. Thus:

Since $x_{i}^{*}\leq C$ and $\sum_{j\neq i}b_{j}\leq\sum_{j}b_{j}$ we get:

By setting $\lambda=\frac{1}{\mu(\mu-1)}$ we get that the mechanism is $(\frac{1}{\mu}-\frac{\lambda}{2},1)$-smooth. By optimizing over $\mu$ we get that the best bound is implied by $\mu=\frac{1}{2}(3+\sqrt{3})$ for which we get that the mechanism is $(2-\sqrt{3},1)$-smooth.

For sequential composition we get our theorem for the case where the valuation of the bidder is the maximum among his valuations on different links: $v_{i}(x_{i})=\max_{j}v_{ij}(x_{ij})$.

If we rum $m$ sequential bandwidth allocation mechanisms and the valuations are unit-demand then any CE and any BNE achieves at least $\frac{1}{2(2-\sqrt{3})}$ of the expected optimal social welfare.

A.6 Multi-Unit Auctions with Concave Values

Consider the following setting: An auctioneer wants to sell $k$ units of a good. A bidder’s valuation is an increasing concave function $v_{i}(j)$ of the amount $j$ of goods he gets. We consider the following auction:

We will denote with $k_{i}(b)$ the units allocated to bidder $i$ under bid profile $b$. We will also denote with $p_{j}(b)$ to be the $j-th$ lowest price for which a unit was sold by the algorithm, i.e. the bid of the $j$-th from the end unit that was sold. The utility of a bidder is still quasi-linear with money:

We show that the greedy multi-unit auction is $(\frac{1}{2}\left(1-\frac{1}{e}\right),1)$-smooth thereby implying an efficiency guarantee of $\frac{e-1}{2e}\approx 1/3.16$ when studied in isolation.

Suppose that bidder $i$ deviates to stating that his $k_{i}^{*}$ highest marginal valuations are all $t$ for some randomly drawn $t$ according to the distribution with probability density function $f(t)=\frac{1}{\frac{v_{i}(k_{i}^{*})}{k_{i}^{*}}-t}$ and support $[0,\frac{v_{i}(k_{i}^{*})}{k_{i}^{*}}\left(1-\frac{1}{e}\right)]$. For his remaining marginal valuations he bids . Then the utility of player $i$ from this deviation is:

Since bidder $i$ bids positive only for his $k_{i}^{*}$ highest marginals we know that he is allocated at most $k_{i}^{*}$ units. Hence, $k_{i}(t,b_{-i})\leq k_{i}^{*}$ for all $t$. In addition by concavity we know that for any $k\leq k_{i}^{*}:\frac{v(k)}{k}\geq\frac{v(k_{i}^{*})}{k_{i}^{*}}$. Hence:

For any $j\in[1,k_{i}^{*}]$, if $t>p_{j}(b)$ then $k_{i}(t,b_{-i})\geq j$. Hence, we have:

Now we need to find the right pick of $j$ in our analysis, such that when adding the above inequality for all players then the negative part on the right hand side will be the total revenue of the auction at bid profile $b$.

Since prices $p_{j}(b)$ are increasing in $j$ we know that:

If we choose a $j$ such that $2j-1\leq k_{i}^{*}$ then:

Observe that since $k_{i}^{*}$ are integers, if we choose $j=\lceil\frac{k_{i}^{*}}{2}\rceil$ then we know that $j\leq\frac{k_{i}^{*}+1}{2}$ and therefore $2j-1\leq k_{i}^{*}$. Thus if we apply Inequality (18) for $j=\lceil\frac{k_{i}^{*}}{2}\rceil$ we get:

Last observe that since $\sum_{i}k_{i}^{*}=k$ and prices $p_{t}(b)$ are increasing in $t$: $\sum_{i}\sum_{t=1}^{k_{i}^{*}}p_{t}\leq\sum_{t=1}^{k}p_{t}(b)=\sum_{i}P_{i}(b)$. Hence, by summing over all players and using the latter inequality we get the theorem.

For sequential composition we require that the bidders are unit-demand over mechanisms: e.g. they have mechanism specific concave value functions and that their utility is the maximum over all mechanisms of the utility they get from each mechanism, $v_{i}(k_{i})=\max_{j}v_{ij}(k_{ij})$. Observe that such valuations are a generalization of the standard notion unit-demand valuations where players just want one unit. We could simulate unit-demand valuations with unit-demand over mechanisms by just saying that $v_{ij}(k_{ij})=\hat{v}_{ij}$ if $k_{ij}>=1$. Our notion of unit-demand valuations over mechanisms just says that you should pick the mechanism that gave you the maximum value for the units it gave you.

If we run $m$ greedy multi-unit auctions sequentially and bidders have unit-demand valuations over mechanisms then every CE and BNE achieves at least $\frac{e-1}{4e}\approx\frac{1}{6.32}$ of the expected optimal social welfare.

One could also think of running a second-price equivalent of Mechanism 5 which is described in Mechanism 6.

Markakis and Telelis studies exactly this auction and uses a no-overbidding assumption, where the willingness-to-pay of a player is the sum of his $k$ highest marginal bids if he is allocated $k$ units. Under this no-overbidding assumption and using similar analysis as in Theorem A.37 we can prove that this auction is weakly $\left(\frac{1}{2}\left(1-\frac{1}{e}\right),0,1\right)$-smooth, thereby implying an efficiency guarantee of $\frac{1}{4}\left(1-\frac{1}{e}\right)$. This largely improves upon the results of Markakis et al. where only a logarithmic bound in the number of units $O(\log(k))$ was proved for the case of mixed and Bayes-Nash equilibria. Our bound also has implications for budgets and simultaneous and sequential composition.

Uniform price auctions are frequently used in practice because they have the advantage that no-matter what the players bid, everyone pays the same price for the allocated items. Hence, they give a fairness feeling and also avoid any friction when someone was allocated the same unit at a different price.

In such an auction the willingness-to-pay of a player that received $k_{i}$ units and bid $b_{i}$ per unit is exactly $k_{i}b_{i}$ since in the worst case the highest losing bid could be just below your bid.

The Uniform Price Auction is conservatively and weakly

Denote by $B_{t}$ the bid of the $t$-th last unit sold. Similar to Mechanism 5 it holds that if $t>B_{j}$ then the player is allocated at least $j$ units. Thereby using similar analysis as in the proof of Lemma A.37 we can show that the above deviation yields utility at least:

Then by summing among all players we can derive:

We also get the same composability guarantees as Mechanism 5:

If we run $m$ uniform price auctions sequentially and bidders have unit-demand valuations over mechanisms then every CE and BNE achieves at least $\frac{e-1}{4e}\approx\frac{1}{6.32}$ of the expected optimal social welfare.

A.7 Combinatorial Auctions with XOS valuations

Consider a combinatorial auction setting with $k$ items and $n$ bidders who have submodular valuations. For such a setting Lehman et al. gave a greedy $2$-approximation algorithm. In this section we analyze a mechanism based on that greedy allocation. We will consider bidders that have XOS valuations on sets of items. One problem with analyzing the greedy algorithm as a mechanism is that it requires for the players to submit and commit to their whole valuation. That requires an exponential communication. Hence, we will consider here a simplification of the algorithm where the bidders are asked to submit only additive proxies to their valuations.

Remember that XOS valuations when specialized on valuations defined on sets of items are characterized by the following property: for any set $S$ there exists an additive valuation $v_{ij}^{S}$ such that $v_{i}(S)=\sum_{j\in S}v_{ij}^{S}$ and such that for any other set $T$: $v_{i}(T)\geq\sum_{j\in T}v_{ij}^{S}$.

The best known approximation factor to the problem of welfare maximization for XOS bidders is $1-\frac{1}{e}$ and was given by Feige .

Here we observe that the above mechanism that uses the greedy allocation rule with the restriction that the players submit additive proxies is equivalent to running $m$ simultaneous first price auctions with XOS valuations and thereby is $(1-\frac{1}{e},1)$-smooth. Therefore the efficiency guarantees that it provides are the same as the best approximation algorithm for the optimization problem.

Similarly, if instead of the first price we charged each player the minimum he had to bid to win each item, then that would be equivalent to simultaneous second-price auctions and therefore would be weakly $(1,0,1)$-smooth, leading to an efficiency guarantee of $1/2$.

Appendix B Relaxed Smoothness for General Games

Given such a game we are interested in studying how bad the social welfare can be at outcomes that correspond to well-established solution concepts in game theory and in comparison with the social welfare optimal outcome. Throughout this section we will denote with Opt the optimal social welfare value. We will quantify the efficiency of a solution concept using the notion of Price of Anarchy which is the ratio of the optimal social welfare over the worst expected equilibrium social welfare (since an equilibrium might correspond to a distribution over outcomes).

When is a game smooth? Roughgarden defined smoothness by the existence of a single socially aware strategy profile $s^{*}$ such that in any strategy profile $s$, an agent could close his eyes, forget what he and everyone else was doing previously and then play a socially-aware strategy $s_{i}^{*}$, and produce a good fraction of his share of the optimal outcome. More precisely, that such an effect is true in the aggregate.

A utility maximization game is $(\lambda,\mu)$-smooth if there exists a (possibly randomized) strategy $\mathbf{s}_{i}^{*}$ for each $i\in N$, such that for all strategy profiles $s\in\times_{i}S_{i}$:

The most important property about smooth games is that any Coarse Correlated Equilibrium of a $(\lambda,\mu)$-smooth game has expected social welfare at least $\frac{\lambda}{1+\mu}\text{{Opt}}$, i.e. the Price of Anarchy of Coarse Correlated Equilibria is at most $\frac{1+\mu}{\lambda}$ . Hence, the above states that if players are using no-regret learning strategies when playing a smooth game, then in the limit the expected social welfare of the empirical distribution of play will be approximately optimal.

Such a property though it holds for several natural classes of games might be too strong. A more natural class of deviations would allow the deviating player to condition his deviation at least on what he/she was doing previously.One could also allow the deviating player to condition his deviation on what everyone was doing prior to the deviation, i.e. on the whole strategy profile $s$, but such a property would imply a Price of Anarchy bound only for the Pure Nash Equilibria of the game and nothing more, not for learning outcomes, not for Bayesian version of the game, not even for mixed equilibria of the full information game. This is exactly the notion of conditional smoothness that we introduce:

A utility maximization game is conditionally $(\lambda,\mu)$-smooth if for any strategy profile $s$ there exists a (possible randomized) strategy $\mathbf{s}_{i}^{*}(s_{i})$ for all $i\in N$ such that:

However, the fact that we now allow players to condition their deviation on what they were doing in the previous strategy profile comes at a small loss. Specifically, the Price of Anarchy of Coarse Correlated Equilibria of a $(\lambda,\mu)$-conditionally smooth game could be much higher than $\frac{1+\mu}{\lambda}$. However, we can still get that the good Price of Anarchy is still achieved by all Correlated Equilibria of the game, and thereby it implies that when players are using No-Internal-Regret learning strategies then the expected social welfare of the empirical distribution will be approximately optimal.

The expected social welfare of any Correlated Equilibrium of a conditionally $(\lambda,\mu)$-smooth game is at least $\frac{\lambda}{1+\mu}\text{{Opt}}$. If all players are using No-Internal-Regret learning strategies then the expected social welfare is at least $\frac{\lambda}{1+\mu}\text{{Opt}}$.

A correlated equilibrium is a distribution $\mathbf{s}$ over strategy profiles such that for every player $i$, for every strategy $s_{i}$ in the support of $\mathbf{s}$ and for every other strategy $s_{i}^{\prime}$ in $S_{i}$, player $i$ doesn’t benefit from switching to $s_{i}^{\prime}$ whenever he was playing $s_{i}$. Since, no player has profit of deviating to $\mathbf{s}_{i}^{*}(s_{i})$ whenever he was playing $s_{i}$ we get:

The theorem follows by taking expectation over $s_{i}$ and adding over all players:

This definition makes a few basic assumptions about the class of Bayesian Games we consider: a players utility is affected by the other players’ types only implicitly through their actions and not directly from their types, the set of actions available to an agent doesn’t depend on their types, and the players’ types are distributed independently.

We will use the most dominant solution concept in incomplete information games, the Bayes-Nash Equilibrium (BNE). Our results hold for mixed Bayes-Nash Equilibria too, but for simplicity of presentation we are going to focus on Bayes-Nash Equilibria in pure strategies. A Bayes-Nash Equilibrium is a strategy profile such that each player maximizes his expected utility conditional on his private information.

Given an action profile $a$ and a type vector $t$ the social welfare of the game $SW^{t}(s)$ is at least the sum of the player’s utilities $\sum_{i}u_{i}^{t_{i}}(a)$. The welfare of a strategy profile $s$ is the expected welfare over the types

Given a type profile $t$ we denote with $\text{{Opt}}(t)$ the optimal social welfare for type profile $t$.

As our measure of inefficiency we will use the Bayes-Nash Price of Anarchy which is defined as the ratio of the expected optimal social welfare over the expected social welfare achieved at the worst Bayes-Nash Equilibrium:

B.2 Extension Theorem to Bayesian Setting

In this section we show that the inefficiency bound implied by the weaker notion of conditional smoothness that we introduced in this section also carries over to Bayesian versions of a game, i.e. if a Bayesian game is conditionally $(\lambda,\mu)$-smooth for each complete information game that corresponds to each instance of the type profile then the Bayes-Nash Price of Anarchy of the incomplete information game is also $\lambda/(1+\mu)$.

A Bayesian Game is conditionally-smooth if each induced complete information game is conditionally smooth in the sense of B.2.

A Bayesian game is $(\lambda,\mu)$-conditionally smooth if for any $t\in T$ and for any action profile $a\in A$ there exists a (possible randomized) action $\mathbf{a}_{i}^{*}(t,a_{i})$ for each $i\in N$ such that:

Next we prove our extension theorem, that if a full information game is conditionally-smooth, than the corresponding Bayesian game also has low price of anarchy. Note that the function $\mathbf{a}^{*}(t,s)$ allows the coordinate of player $i$ to depends on the whole type profile $t$, and not only the type of player $i$, as a result player $i$’s coordinate $\mathbf{a}_{i}^{*}(t,a_{i})$ cannot be directly used as deviation for that player in the Bayesian Game. Previous papers by Roughgarden and Syrgkanis managed to get around this problem by using a random sampling technique. However, those papers use the stronger definition of smoothness where the deviating strategy doesn’t depend on the previous action of the deviating player. Here we extend previous results for our weaker conditional smoothness property.

If a Bayesian Game is $(\lambda,\mu)$-conditionally smooth then it has Bayes-Nash Price of Anarchy at most $\lambda/(1+\mu)$.

Let $t$ be a type profile and $s(t)$ be a Bayes-Nash Equilibrium strategy profile that corresponds to type $t$. Let $\mathbf{a}^{*}(t,a)=(\mathbf{a}_{i}^{*}(t,a_{i}))_{i\in N}$ be the action profile designated by the smoothness property of the game for a type profile $t$ and an action profile $a$.