# simultaneous_2nd_price_item_auctions_with_nounderbidding__6c855585.pdf

Simultaneous 2nd Price Item Auctions with No-Underbidding *

Michal Feldman and Galia Shabtai Tel Aviv University michal.feldman@cs.tau.ac.il, galiashabtai@gmail.com

We study the price of anarchy (Po A) of simultaneous 2nd price auctions (S2PA) under a new natural condition of no underbidding, meaning that agents never bid on items less than their marginal values. We establish improved (mostly tight) bounds on the Po A of S2PA under no underbidding for different valuation classes (including unit-demand, submodular, XOS, subadditive, and general monotone valuations), in both full-information and incomplete information settings. To derive our results, we introduce a new parameterized property of auctions, termed (γ, δ)-revenue guaranteed, which implies a Po A of at least γ/(1+δ). Via extension theorems, this guarantee extends to coarse correlated equilibria (CCE) in full information settings, and to Bayesian Po A (BPo A) in settings with incomplete information and arbitrary (correlated) distributions. We then show that S2PA are (1, 1)-revenue guaranteed with respect to bids satisfying no underbidding. This implies a Po A of at least 1/2 for general monotone valuation, which extends to BPOA with arbitrary correlated distributions. Moreover, we show that (λ, µ)-smoothness combined with (γ, δ)-revenue guaranteed guarantees a Po A of at least (γ + λ)/(1 + δ + µ). This implies a host of results, such as a tight Po A of 2/3 for S2PA with submodular (or XOS) valuations, under no overbidding and no underbidding. Beyond establishing improved bounds for S2PA, the no underbidding assumption sheds new light on the performance of S2PA relative to simultaneous 1st price auctions.

1 Introduction Simple auctions are often preferred in practice over complex truthful auctions. Starting with the seminal paper of Christodoulou, Kov acs, and Schapira (2008), a lot of effort has been given to the study of simultaneous item auctions. In simultaneous item auctions with n bidders and m items, every bidder i has a valuation function vi : 2[m] R+, where vi(S) is the value bidder i assigns to set S [m]. Despite the combinatorial structure of the valuation, bidders submit bids on every item separately and simultaneously. In simultaneous ﬁrst-price auctions (S1PA) every item is sold in a 1st-price auction; i.e., the highest bidder wins and

*For the full version, see https://arxiv.org/abs/2003.11857 (Feldman and Shabtai 2020). Due to space limitation, all missing statements and proofs are deferred to the full version. Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

pays her bid, whereas in simultaneous second-price auctions (S2PA) every item is sold in a 2nd-price auction; i.e., the highest bidder wins and pays the 2nd highest bid. Clearly, these auctions are not truthful; bidders don t even have the language to express their true valuations. The performance of these auctions is often quantiﬁed by the price of anarchy (Po A), which measures their performance in equilibrium. Speciﬁcally, the Po A is deﬁned as the ratio between the performance of an auction in its worst equilibrium and the performance of the optimal outcome. The price of anarchy in auctions has been of great interest to the AI community, see the inﬂuential survey of Roughgarden, Syrgkanis, and Tardos (2017), as well as recent work on learning dynamics in multi-unit auctions and games (Foster et al. 2016; Brˆanzei and Filos-Ratsikas 2019).

Po A and BPo A of S2PA: Background. The price of anarchy has been studied both in complete and incomplete information settings. In the former case, all valuations are known by all bidders. In the latter case, every bidder knows her own value and the probability distribution from which other bidder valuations are drawn. The common equilibrium notion in this case is Bayes Nash equilibrium, and the performance is quantiﬁed by the Bayesian Po A (BPo A) measure. There are pathological examples showing that the Po A of S2PA can be arbitrarily bad, even in the simplest scenario of a single item auction with two bidders (Christodoulou, Kov acs, and Schapira 2016). A common approach towards overcoming such pathological examples is the no overbidding (NOB) assumption, stating that the sum of player bids on the set of items she wins never exceeds its value. Consequently, all Po A results of S2PA use the NOB assumption. The Po A and BPo A of simultaneous item auctions depend on the structure of the valuation functions. An important class is that of subadditive (SA) valuations, also known as complement-free valuations, where v(S)+v(T) v(S T) for every sets of items S, T. A hierarchy of complementfree valuations is given in (Lehmann, Lehmann, and Nisan 2006), including unit-demand (UD), submodular (SM), XOS (XOS), and subadditive (SA) valuations, with the following strict containment relation: UD SM XOS SA (see Section 2.2 for formal deﬁnitions). Clearly, the Po A can only degrade as one moves to a larger valuation class. Po A and BPo A results under the no-overbidding as-

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

sumption for the different classes have been obtained by Christodoulou, Kov acs, and Schapira (2008) and followup work (Roughgarden 2009; Bhawalkar and Roughgarden 2011; Hassidim et al. 2011; Roughgarden 2012; Feldman et al. 2013; Syrgkanis and Tardos 2013; Christodoulou et al. 2016), and are summarized in Table 1. MON refers to the class of all monotone valuations.

1.1 No Underbidding (NUB) Let bi = (bi1, . . . , bim) denote the bid vector of bidder i, where bij is the bid of bidder i for item j, and let b = (b1, . . . , bn) be the bid proﬁle of all bidders. Consider the following example (taken from Christodoulou, Kov acs, and Schapira (2016)), showing that the Po A for unit-demand (UD) valuations is at most 1/2 (A valuation v is UD if there exist v(1), . . . , v(m), such that v(S) = maxj S v(j) for every set of items S).

Example 1.1. 2 bidders and 2 items, x, y. Bidder 1 is UD with values v1(x) = 2, v1(y) = 1. Bidder 2 is UD with values v2(x) = 1, v2(y) = 2. Consider the following bid proﬁle, which is a pure Nash equilibrium (PNE) that adheres to NOB: b1x = b2y = 0, and b1y = b2x = 1. Under this bid proﬁle, bidders 1 and 2 receive items y and x, respectively, for a social welfare of 2. The optimal welfare is 4.

Let us take a closer look at the Nash equilibrium in Example 1.1. In this equilibrium bidder 1 prefers item x, yet bids 0 on item x, and gets item y instead. Bidder 1 s marginal value for item x, given her current allocation (item y), is v1(x | y) = v1(xy) v1(y) = 1. Given her current allocation y, bidding 0 on item x is weakly dominated by bidding 1 on x. Indeed, if bidder 1 receives item x, in addition to item y, her additional value is 1 and she pays at most 1. Therefore, it is only natural for her to bid at least her marginal value. If a bidder bids on an item less than the item s marginal value, we say that she underbids (see Deﬁnition 4.1). In Example 1.1, bidder 1 underbids on item x. In Section 4 we show that underbidding in a 2nd price auction is weakly dominated in some precise technical sense. In what sense is the outcome in Example 1.1 an equilibrium? While a Nash equilibrium is a descriptive, static notion, it is based on the underlying assumption that players engage in some dynamics, where they keep best responding to the current situation until a stable outcome is reached. In this dynamics, it is not likely that a player would bid on an item less than its marginal value. This is exactly what the no-underbidding assumption captures. No-underbidding is not only a mere theoretical exercise. In second price auctions a lot of empirical evidence suggests that bidders tend to overbid, but not underbid (Kagel and Levin 1993; Harstad 2000; Cooper and Fang 2008; Roider and Schmitz 2012). It seems that laboratory second-price auctions exhibit substantial and persistent overbidding, even with prior experience (Harstad 2000). The no-underbidding assumption is also consistent with the assumption made by Nisan et al. (2011) that bidders break ties in favor of the highest bid that does not exceed their value. Yet, the POA literature employs no-overbidding as a standard assumption, and overlooked the no-underbidding phenomenon. The ob-

jective of this work is to better tie the theoretical work in this area to empirical evidence, by providing a theoretical foundation for the no-underbidding phenomenon. Intuitively, no underbidding can improve welfare performance, as it drives item prices up, so that items become less attractive to low-value players. Consequently, bad equilibria, in which items are allocated to players with relatively low value, are excluded. A natural question is:

Main Question. What is the performance (measured by Po A/BPo A) of simultaneous 2nd price item auctions under no underbidding?

1.2 Our Contribution

We ﬁrst introduce the notion of item no underbidding (i NUB), where no agent underbids on items (see Deﬁnition 4.4). One might think that by imposing both NOB and i NUB, the optimal welfare will be achieved. This is indeed the case for a single item auction (where the optimal welfare is achieved by imposing any one of these assumptions alone). However, even a simple scenario with 2 items and 2 unit-demand bidders can have a PNE with sub-optimal welfare. This is demonstrated in the following example.

Example 1.2. 2 bidders and 2 items, x, y. Bidder 1 is UD with values v1(x) = 3, v1(y) = 2. Bidder 2 is UD with values v2(x) = 2, v2(y) = 3. Consider the following PNE bid proﬁle, which adheres to both NOB and i NUB: b1x = b2y = 1, b1y = b2x = 2. Under this bid proﬁle, bidders 1 and 2 receive items y and x, respectively, for a social welfare of 4. The optimal welfare is 6. Thus, the Po A is 2/3.

Submodular Valuations Our ﬁrst result states that 2/3 is the worst possible ratio for SM valuations and bid proﬁles satisfying both NOB and i NUB, even in settings with incomplete information (with a product distribution over valuations), see Corollary 5.5.

Beyond Submodular Valuations The above bounds do not carry over beyond submodular valuations. Consider ﬁrst XOS valuations, deﬁned as maximum over additive valuations. In the full version we show that the (B)Po A of S2PA with XOS valuations under i NUB is θ( 1

m) . Moreover, for XOS valuations, i NUB may not provide any improvement over NOB alone. In particular, there exists an example where the Po A with NOB and i NUB is 1

2, matching the guarantee provided by NOB alone (see full version). To the best of our knowledge, this is the ﬁrst Po A separation between SM and XOS valuations in simultaneous item auctions (or even between UD and XOS). Beyond SA valuations, the Po A can be arbitrarily bad under bid proﬁles satisfying i NUB (see full version). To deal with valuations beyond SM, we consider a different no underbidding assumption, which applies to sets of items. For two sets S, T, the marginal value of T given S is deﬁned as v(T | S) = v(S T) v(S). A bidder is said to not underbid on a set S under bid proﬁle b if P j S bij vi(S | Si(b)). The new condition, set no underbidding (s NUB), imposes the set no underbidding condition on every

UD / SM XOS SA MON

Po A 1 2 1 2 [2016] 1 2 [2011] O 1 m [2011; 2013]

NOB i BPo A 1 2 1 2 [2016] 1 4 [2013] O 1 m [2011; 2013]

BPo A O 1 n1/4 [2011] O 1 n1/4 [2011] O 1 n1/4 [2011] O 1 n1/4 [2011]

Table 1: Previous results for Po A of S2PA under the NOB assumption. Po A is the price of anarchy under full information; i BPo A and BPo A are the Bayesian Po A under independent valuation distributions and correlated valuation distributions, respectively. This result assumes strong no-overbidding, i.e. the sum of player bids on any set of items never exceeds its value for that set. All results are tight, except those marked with . Results derived as a special case of a more general result (to their right) are marked with .

bidder i with respect to the set S = S i (v)\Si(b) (see Deﬁnition 4.5). With the s NUB deﬁnition, the 2

3 Po A extends to SA valuations in full information settings (see full version), and to XOS valuations even in incomplete information settings (with product distributions), see Corollary 6.1. For incomplete information we show that the BPo A of SA valuations is at least 1

2 for any joint distribution (even correlated) and it can be obtained in a much stronger sense, namely for every bid proﬁle with non-negative sum of utilities (even a non-equilibrium proﬁle) satisfying s NUB. This also holds for markets with arbitrary monotone valuations (see full version). The above results are summarized in Table 2.

Equilibrium existence Po A results make sense only when the corresponding equilibrium exists. We show that every market with XOS valuations admits a PNE satisfying s NUB and NOB. For SA valuations, a PNE satisfying NOB might not exist. However, under a ﬁnite discretized version of the auction, a mixed Bayes Nash equilibrium is guaranteed to exist, and we show that there is at least one bid proﬁle that admits both s NUB and NOB with arbitrary monotone valuation functions.

S1PA vs. S2PA Interestingly, our results shed new light on the comparison between simultaneous 1st and 2nd price auctions. Table 3 speciﬁes BPo A lower bounds for S1PA and S2PA under NOB, assuming independent valuation distributions. According to these results, one may conclude that S1PA perform better than their S2PA counterparts. Our new results shed more light on the relative performance of S2PA and S1PA. When considering both no overbidding and no underbidding, the situation ﬂips, and S2PA are superior to S1PA.1 For XOS valuations, the 1 1/e bound for S1PA persists, but for S2PA the bound improves from 1

e). For SA valuations and independent valuation distributions, S2PA under s NUB performs as well as S1PA (achieving BPo A of 1

2), however in S2PA the 1

2 bound holds also for correlated valuation distributions. For valuations beyond SA, S2PA performs better ( 1

2 for S2PA and less than 1

2 for S1PA).

1Note that no overbidding and no underbidding are not reasonable assumptions in 1st price auctions, where bidders pay their bids

2 Preliminaries 2.1 Auctions Combinatorial auctions In a combinatorial auction a set of m non-identical items are sold to a group of n players. Let Si be the set of possible allocations to player i, Vi the set of possible valuations of player i, and Bi the set of actions available to player i. Similarly, we let S S1 . . . Sn be the allocation space of all players, V = V1 . . . Vn be the valuation space, and B = B1 . . . Bn be the action space. An allocation function maps an action proﬁle to an allocation S = (S1, . . . , Sn) S, where Si is the set of items allocated to player i. A payment function maps an action proﬁle to a non negative payment P = (P1, . . . , Pn) R+, where Pi is the payment of player i. We assume that the valuation function vi : Si R+ of a player i, where vi Vi, is monotone and normalized, i.e., S T [m], vi(S) vi(T) and also vi( ) = 0. We let v = (v1, . . . , vn) be the valuation proﬁle. An outcome is a pair of allocation S and payment P and the revenue is the sum of all payments, i.e. R(b) = P i [n] Pi(b). We assume a quasi-linear utility function, i.e. ui(Si, Pi, vi) = vi(Si) Pi. We are interested in measuring the social welfare, which is the sum of bidder valuations, i.e., SW(S, v) = P i [n] vi(Si). Given a valuation proﬁle v, an optimal allocation is an allocation that maximizes the SW over all possible allocations. We denote by OPT(v) the value of SW under optimal allocation. Simultaneous item bidding auction. In a simultaneous item bidding auction (simultaneous item auction, in short) each item j [m] is simultaneously sold in a separate auction. An action proﬁle is a bid proﬁle b = (b1, . . . , bn), where bi = (bi1, . . . , bim) is an m-vector s.t. bij is the bid of player i for item j. The allocation of each item j is determined by the bids (b1j, . . . , bnj). We use Si(b) to denote the items won by player i and pj(b) to denote the price paid for item j by the winner of item j. As allocation and payment are uniquely deﬁned by the bid proﬁle, we overload notation and write ui(b, vi) and SW(b, v). In a simultaneous second price auction (S2PA), each item j is allocated to the highest bidder, who pays the second highest bid, i.e., Pi = P j Si(b) maxk =i bkj. In a simultaneous ﬁrst price auction (S1PA), each item j is allocated to the highest bidder, who pays her bid for that item, i.e., Pi = P j Si(b) bij. Ties are broken arbitrarily but consistently.

UD / SM XOS SA MON i NUB (B)Po A 1 2* Θ 1

m * arbitrarily bad* s NUB (B)Po A 1 2 1 2 1 2 1 2*

NOB+ Po A 2 3 2 3* 2 3 * 1 2* s NUB i BPo A 2 3 2 3* 1 2 1 2* BPo A 1 2 1 2 1 2 1 2*

Table 2: New results for Po A of S2PA. Po A is the price of anarchy under full information; i BPo A and BPo A are the Bayesian Po A under independent and correlated valuation distributions, respectively. This result assumes strong no-overbidding, i.e. the sum of player bids on any set of items never exceeds its value for that set. All results are tight. Results derived in this paper are marked with *. Results derived as special cases of more general result (to their right) are marked with .

UD / SM XOS SA MON

S2PA NOB 1 2 1 2 [2016] 1 4 [2013] O 1 m [2011; 2013]

e [2013; 2016] 1 2 [2013; 2016] 1 m [2011]

S2PA s NUB+NOB 2 3 2 3 1 2 (corr) 1 2 (corr)

Table 3: BPo A results for S1PA and S2PA. (corr) refers to bounds that hold also for correlated distributions. Results derived in this paper are marked with *. Results derived as special cases of more general results (to their right) are marked with .

Full information setting: solution concepts and Po A. In the full information setting, the valuation proﬁle v = (v1, . . . , vn) is known to all players. The standard equilibrium concepts in this setting are pure Nash equilibrium (PNE), mixed Nash equilibrium (MNE), correlated Nash equilibrium (CE) and coarse correlated Nash equilibrium (CCE), where PNE MNE CE CCE. Following are the deﬁnitions PNE and CCE, the deﬁnitions of MNE and CE are presented in the full version. As standard, for a vector y, we denote by y i the vector y with the ith component removed, and by (Ω) the space of probability distributions over a ﬁnite set Ω. Deﬁnition 2.1 (Pure Nash Equilibrium (PNE)). A bid proﬁle b B1 . . . Bn is a PNE if for any i [n] and for any b i Bi, ui(b, vi) ui(b i, b i, vi). Deﬁnition 2.2 (Coarse Correlated Nash Equilibriun (CCE)). A bid proﬁle of randomized bids b (B1 . . . Bn) is a CCE if for any i [n] and for any b i Bi,

Eb [ui(b, vi)] Eb h ui(b i, b i, vi) i .

For a given instance of valuations v, the price of anarchy (Po A) with respect to an equilibrium notion E is deﬁned as: Po A(v) = infb E Eb[SW (b,v)]

OP T (v) . For a family of valuations V, Po A(V) = minv V Po A(v).

Incomplete information setting: solution concepts and Bayesian Po A. In an incomplete information setting, player valuations are drawn from a commonly known, possibly correlated, joint distribution F (V1 . . . Vn), and the valuation vi of each player is a private information which is known only to player i. The strategy of player i is a function σi : Vi Bi. Let Σi denote the strategy space of player i and Σ = Σ1 . . . Σn the strategy space of all players. We denote by σ(v) = (σ1(v1), . . . , (σn(vn)) the bid vector

given a valuation proﬁle v. In some cases, we assume that the joint distribution of the valuations is a product distribution, i.e., F = F1 . . . Fn (V1) . . . (Vn). In these cases, each valuation vi is independently drawn from the commonly known distribution Fi (Vi). The standard equilibrium concepts in the incomplete information setting are the Bayes Nash equilibrium (BNE) and the mixed Bayes Nash equilibrium (MBNE):

Deﬁnition 2.3 (Bayes Nash Equilibriun (BNE)). A strategy proﬁle σ is a BNE if for any i [n], any vi Vi and any b i Bi, Ev i|vi[ui(σi(vi), σ i(v i), vi)] Ev i|vi[ui(b i, σ i(v i), vi)]

Note that if player valuations are independent, we can omit the conditioning on vi in Deﬁnition 2.3. The deﬁnition for MBNE is similar to BNE, but with another expectation over the strategy proﬁle σ (see deﬁnition in the full version). The Bayes Nash price of anarchy is:

BPo A = inf F, σ BNE Ev [SW(σ(v), v)]

Ev [OPT(v)]

The mixed BPo A is deﬁned similarly w.r.t. MBNE.

2.2 Valuation Classes Hereinafter we present the valuation functions considered in this paper. As standard, for a valuation v, item j and set S, we denote the marginal value of j, given S, as v(j|S); i.e., v(j|S) = v(S {j}) v(S). Similarly, the marginal value of a set S , given a set S, is v(S |S) = v(S S ) v(S). Following are the valuation classes we consider:

Unit-demand (UD): There exist values v1, . . . , vm s.t. v(S) = maxj S vj S [m].

Submodular (SM): S T [m] and j / T, v(j | S) v(j | T).

XOS (fractionally subadditive): There exists a set L of additive valuations {aℓ( )}ℓ L, s.t. S [m], v(S) = maxℓ L aℓ(S).

Subadditive (SA): S, T [m], v(S)+v(T) v(S T).

Monotone (MON): S T [m], v(S) v(T).

A strict containment hierarchy of the above valuation classes is known: UD SM XOS SA MON.

Lemma 2.4. For any SM function v and any sets S, S : P j S v(j | S) v(S | S).

In the full version we generalize the SM class to α SM, where the parameter α denotes how far the valuation is from a SM valuation, and generalize our results to α SM.

2.3 Smooth Auctions

We use the following smoothness deﬁnition, based on Roughgarden (2009); Roughgarden, Syrgkanis, and Tardos (2017):

Deﬁnition 2.5 (Smooth auction). An auction is (λ, µ) smooth for parameters λ, µ 0 with respect to a bid space B B1 . . . Bn, if for any valuation proﬁle v V1 . . . Vn and any bid proﬁle b B there exists a bid b i (v) Bi for each player i, s.t.: X

i [n] ui(b i (v), b i, vi) λ OPT(v) µ SW(b, v) (1)

It is shown in Roughgarden (2009); Roughgarden, Syrgkanis, and Tardos (2017) that for every (λ, µ) smooth auction, the social welfare of any pure NE is at least λ 1+µ. Via extension theorems, this bound extends to CCE in fullinformation settings and to Bayes NE in settings with incomplete information (under independent distribution of valuations). A standard assumption in essentially all previous work on the Po A of S2PA (Christodoulou, Kov acs, and Schapira 2016; Feldman et al. 2013; Roughgarden 2012, 2009; Bhawalkar and Roughgarden 2011) is no overbidding, meaning that players do not overbid on items they win. I.e.,

Deﬁnition 2.6 (No overbidding (NOB)). Given a valuation proﬁle v V1 . . . Vn, a bid proﬁle b B is said to satisfy NOB if for every player i it holds that P j Si(b) bij vi(Si(b)).

Theorem 2.7. (based on (Christodoulou, Kov acs, and Schapira 2016; Roughgarden 2009)): S2PA with XOS valuations is (1, 1) smooth, w.r.t. bid proﬁles satisfying NOB.

Theorem 2.7 implies a lower bound of 1

2 on the Bayesian Po A of S2PA with XOS valuations. This result is tight, even with respect to UD valuations in full information settings (Christodoulou, Kov acs, and Schapira 2016).

3 Revenue Guaranteed Auctions In this section we deﬁne a new parameterized notion called revenue guaranteed and infer results for the Po A of revenue guaranteed auctions in full information setting and pure NE. Similarly to the smoothness framework, we augment our results with two extension theorems, one for Po A with respect to CCE, and one for BPo A in settings with incomplete information. Moreover, the BPo A result holds also in cases where the joint distribution of bidder valuations is correlated (whereas previous BPo A results hold only under a product distribution over valuations). Combining the two tools of smoothness and revenue guaranteed, we get an improved bound.

Deﬁnition 3.1 (Revenue guaranteed auction). An auction is (γ, δ) revenue guaranteed for some 0 γ δ 1 with respect to a bid space B B1 . . . Bn, if for any valuation proﬁle v V1 . . . Vn and for any bid proﬁle b B the revenue of the auction is at least γ OPT(v) δ SW(b, v).

3.1 Full Information The following theorem establishes welfare guarantees on every pure bid proﬁle of a (γ, δ) revenue guaranteed auction in which the sum of player utilities is non-negative.

Theorem 3.2. If an auction is (γ, δ) revenue guaranteed w.r.t. a bid space B B1 Bn, then for any pure bid proﬁle b B , in which the sum of player utilities is non-negative, the SW is at least γ 1+δ of the optimal SW.

Proof. Using quasi-linear utilities and non-negative sum of player utilities, 0 P i [n] ui(b, vi) = P i [n] vi(Si(b)) P i [n] Pi(b) = SW(b, v) P i [n] Pi(b). By the (γ, δ) revenue guaranteed property, P i [n] Pi(b) γOPT(v) δSW(b, v). Punting it all together, we get:

0 SW(b, v) X

i [n] Pi(b) (1+δ)SW(b, v) γOPT(v).

(2) Rearranging gives: SW(b, v) γ 1+δOPT(v), as required.

Deﬁnition 3.1 considers pure bid proﬁles, but Theorem 3.2 applies to the more general setting of randomized bid proﬁles, possibly correlated, as cast in the following extension theorem.

Theorem 3.3. If an auction is (γ, δ) revenue guaranteed with respect to a bid space B B1 . . . Bn, then for any bid proﬁle b (B ), in which the sum of the expected utilities of the players is non-negative, the expected social welfare is at least γ 1+δ of the optimal social welfare.

The proof is identical to the proof of Theorem 3.2, except adding expectation over b to every term, using the fact the the auction is (γ, δ) revenue guaranteed for every b in the support of b, and using linearity of expectation. Clearly, in every equilibrium (including CCE) the expected utility of every player is non-negative. It therefore follows that the expected welfare in any CCE is at least γ 1+δ of the optimal social welfare.

For an auction that is both smooth and revenue guaranteed, we give a better bound on the price of anarchy:

Theorem 3.4. If an auction is (λ, µ) smooth with respect to a bid space B and (γ, δ) revenue guaranteed with respect to a bid space B , then the expected social welfare at any CCE (B B ) of the auction is at least λ+γ 1+µ+δ of the optimal social welfare.

Proof. Let b (B B ) be a CCE of the auction. Since the auction is (λ, µ) smooth with respect to a bid space B (Roughgarden 2009): X

i [n] Eb [ui(b, vi)] λ OPT(v) µ Eb [SW(b, v)]

From Equation (2) we get,

Eb [SW(b, v)] X

i [n] Eb [Pi(b)]

(1 + δ) Eb [SW(b, v)] γ OPT(v)

As utilities are quasi-linear, the left hand side of the above two inequalities are equal. Rearranging, we get: Eb [SW(b, v)] λ+γ 1+µ+δOPT(v), as required.

3.2 Incomplete Information: Extension Theorem

Following is an extension theorem for settings with incomplete information.

Theorem 3.5. If an auction is (γ, δ) revenue guaranteed with respect to a bid space B B1 Bn, then for every joint distribution F (V1 . . . Vn), possibly correlated, and every strategy proﬁle σ : V1 . . . Vn (B ), in which the expected sum of player utilities is non-negative, the expected social welfare is at least γ 1+δ of the expected optimal social welfare.

As the expected utility of each player is non-negative at any equilibrium strategy proﬁle, we infer that if an auction is (γ, δ) revenue guaranteed w.r.t. a bid space B , then for every joint distribution F (V1 . . . Vn), possibly correlated, the expected SW at any MBNE, σ : V1 . . . Vn (B ), is at least γ 1+δ of the expected optimal SW. For an auction that is both smooth and revenue guaranteed, we give a better bound on the price of anarchy, if the joint distribution F is a product distribution:

Theorem 3.6. If an auction is (λ, µ) smooth with respect to a bid space B and (γ, δ) revenue guaranteed with respect to a bid space B , then for every product distribution F, every mixed Bayes Nash equilibrium, σ : V1 . . . Vn (B B ), has expected social welfare at least λ+γ 1+µ+δ of the expected optimal social welfare.

Remark. In the full version we give an incomplete information deﬁnition of revenue guaranteed auctions, which allows us to get positive results for auctions that are revenue guaranteed only in expectation.

4 S2PA with No-Underbidding

We ﬁrst deﬁne what it means to underbid on an item. Let b j denote the bids of all bidders on items [m] \ {j}.

Deﬁnition 4.1 (item underbidding). Fix b j. Player i is said to underbid on item j if: bij < vi(j | Si(b j)), where Si(b j) = {k | k = j, bik = maxl {blk}}.

That is, we say that player i underbids on item j in a bid proﬁle b if i s bid on item j is smaller than the marginal valuation of j w.r.t the set of items other than j won by i. We next show that underbidding is weakly dominated in a precise sense that we deﬁne next. Consider a bid proﬁle b. Let b j be the bids of all bidders on all items except j, and let b ij be the bids on item j of all players, except player i.

Deﬁnition 4.2 (weakly dominated). A bid b ij is weakly dominated by bid bij, with respect to b j, if the following two conditions hold:

1. ui(bij, b ij, b j; vi) ui(b ij, b ij, b j; vi), b ij 2. There exists b ij such that inequality (1) holds strictly.

The following lemma shows that underbidding on an item is weakly dominated by bidding its marginal value.

Lemma 4.3. In S2PA, for every player i, every item j, and every bid proﬁle b j, underbidding on item j is weakly dominated by bidding bij = vi(j | Si(b j)), with respect to b j.

Motivated by the above lemma, we next deﬁne the notion of item no underbidding (i NUB):

Deﬁnition 4.4 (Item No-Under Bidding (i NUB)). Given a valuation proﬁle v V1 . . . Vn, a bid proﬁle b B satisﬁes i NUB if there exists a welfare maximizing allocation, S (v), such that for every player i and every item j S i (v)\Si(b) it holds that: bij vi(j | Si(b)).

We also deﬁne the notion of set no underbidding (s NUB):

Deﬁnition 4.5 (Set No underbidding (s NUB)). Given a valuation proﬁle v V1 . . . Vn, we say that a bid proﬁle b B satisﬁes s NUB if there exists a welfare maximizing allocation, S (v), such that for every player i, it holds that P j S bij vi(S | Si(b)), where S = S i (v)\Si(b).

In Section 5 we show that if valuations are submodular, every bid proﬁle that satisﬁes i NUB, also satisﬁes s NUB. The opposite is not necessarily true, as demonstrated in the full version. For unit-demand bidders, i NUB and s NUB coincide (as one can assume w.l.o.g. that every bidder receives a single item in an optimal allocation).

Lemma 4.6. Consider an S2PA and a valuation v. Let S (v) = (S 1(v), . . . , S n(v)) be a welfare-maximizing allocation. Then, for every bid proﬁle b the following holds:

j Si(b) pj(b)

j S i (v)\Si(b) bij

The following shows that s NUB is a powerful property.

Theorem 4.7. S2PA is (1, 1) revenue guaranteed w.r.t. bid proﬁles satisfying s NUB for any MON valuations.

Proof. In what follows, the ﬁrst inequality follows by Lemma 4.6, the second inequality follows by s NUB, and the last inequality follows by monotonicity of valuations: Pn i=1 P j Si(b) pj(b) Pn i=1 P j S i (v)\Si(b) bij Pn i=1 [ vi ( Si(b) (S i (v)\Si(b)) ) vi (Si(b)) ] = Pn i=1 [ vi( Si(b) S i (v) ) vi(Si(b)) ] Pn i=1 [ vi(S i (v)) vi(Si(b)) ] = OPT(v) SW(b, v)

The following follows from Theorems 4.7 and 3.5. Corollary 4.8. In an S2PA with monotone valuations, for every joint distribution F (V1 . . . Vn), possibly correlated, every mixed Bayes Nash equilibrium that satisﬁes s NUB has expected social welfare at least 1

2 of the expected optimal social welfare. Remark. In the full version we give incomplete information deﬁnition of no-underbidding strategy proﬁles, which allows us to get positive results for a wider strategy space.

5 S2PA with Submodular (SM) Valuations In this section we study S2PA with SM valuations. We ﬁrst show that for this class of valuations, the notion of i NUB sufﬁces for establishing positive results. Theorem 5.1. Every S2PA with SM valuations is (1, 1) revenue guaranteed w.r.t. bids satisfying i NUB. An immediate corollary from Theorems 3.5 and 5.1 is: Corollary 5.2. In an S2PA with SM valuations, for every joint distribution F (V1 . . . Vn), possibly correlated, and every strategy proﬁle σ that satisﬁes i NUB for which the expected sum of player utilities is non-negative, the expected social welfare is at least 1

2 of the expected optimal social welfare. The 1

2 bound is tight, even with respect to unit-demand valuations and even in equilibrium, as shown in the following proposition. Proposition 5.3. There exists an S2PA with UD valuations that admits a PNE satisfying i NUB, where the social welfare in equilibrium is 1

2 of the optimal social welfare.

Proof. Consider an S2PA with two unit demand players and 2 items, {x, y}, where v1(x) = 2, v1(y) = 1, v2(x) = 1 and v2(y) = 2. An optimal allocation gives item x to player 1 and item y to player 2, for a welfare of 4. Consider the following bid proﬁle b: b1x = 1, b1y = 100, b2x = 100 and b2y = 1. Player 1 wins item y for a price of 1, and player 2 wins item x for a price of 1. It is easy to see that b is a PNE that satisﬁes i NUB. The social welfare of this equilibrium is 2, which is 1

2 of the optimal social welfare.

For SM valuations, i NUB implies s NUB: Proposition 5.4. For every SM valuation v, every bid proﬁle b that satisﬁes i NUB also satisﬁes s NUB.

Proof. By i NUB, for every item j S i (v) \ Si(b), it holds that bij vi(j | Si(b)). It follows that P j S i (v)\Si(b) bij P j S i (v)\Si(b) vi(j | Si(b)) vi(S i (v) \ Si(b) | Si(b)). The last inequality follows by Lemma 2.4.

Therefore, Theorem 4.7 and Corollary 4.8 also apply to every SM valuation that satisﬁes i NUB. For proﬁles satisfying both i NUB and NOB, we get a better bound as a corollary from Theorems 5.1, 2.7, and 3.6. Corollary 5.5. In an S2PA with SM valuations, for every product distribution F, every mixed Bayes Nash equilibrium that satisﬁes both NOB and i NUB has expected social welfare at least 2

3 of the expected optimal social welfare. This result is tight. The bound of 2

3 for SM valuations is tight even with respect to a PNE with UD valuations (see Example 1.2). In the next section, we show that every S2PA with XOS valuations admits a PNE that satisﬁes both NOB and s NUB (Theorem 6.2). Since every submodular valuation is XOS, the existence result applies also to submodular valuations.

6 S2PA with XOS Valuations XOS Valuations under i NUB: For XOS valuations, i NUB does not imply s NUB, thus i NUB does not lead automatically to good Po A. An example with Po A of 2

m is given in the full version. XOS Valuations under s NUB: As Theorem 4.7 and Corollary 4.8 apply for MON valuation functions, the Po A is at least 1

2 with respect to bid proﬁles satisfying s NUB. An immediate corollary from Theorems 2.7, 4.7 and 3.6 is: Corollary 6.1. In an S2PA with XOS valuations, for every product distribution F, every mixed Bayes Nash equilibrium that satisﬁes both NOB and s NUB has expected social welfare at least 2

3 of the expected optimal social welfare. This result is tight (see Example 1.2). We next show that every S2PA with XOS valuations admits a PNE that satisﬁes both NOB and s NUB. Theorem 6.2. In S2PA with XOS valuations there always exists at least one PNE that satisﬁes both NOB and s NUB.

Proof. Christodoulou, Kov acs, and Schapira (2016) showed that every S2PA with XOS valuations admits a PNE satisfying NOB. We show that the same PNE satisﬁes s NUB as well. Let S (v) = (S 1(v), . . . , S n(v)) be a welfare maximizing allocation, and let a i be an additive valuation such that vi(S i (v)) = P j S i (v) a ij. Consider the bid proﬁle in which every player bids according to the maximizing additive valuation with respect to her set S i (v), i.e., bij = a ij for every j S i (v) and bij = 0 otherwise. One can easily verify that this bid proﬁle is a PNE that satisﬁes NOB. It thus remains to show that it also satisﬁes s NUB. Recall that s NUB imposes restrictions on the bid values of the set S = S i (v)\Si(b). Under the above bid proﬁle we have Si(b) = S i (v), i.e., S = and s NUB holds trivially.

Acknowledgments We thank Noam Nisan and Tomer Ezra for insightful comments. This project has received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation program (grant agreement No. 866132), and by the Israel Science Foundation (grant number 317/17).

References Bhawalkar, K.; and Roughgarden, T. 2011. Welfare Guarantees for Combinatorial Auctions with Item Bidding. In Randall, D., ed., Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, 700 709. SIAM. doi:10.1137/1.9781611973082.55. URL https://doi.org/10.1137/1.9781611973082.55.

Brˆanzei, S.; and Filos-Ratsikas, A. 2019. Walrasian Dynamics in Multi-Unit Markets. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 33, 1812 1819.

Christodoulou, G.; Kov acs, A.; and Schapira, M. 2008. Bayesian Combinatorial Auctions. In Aceto, L.; Damg ard, I.; Goldberg, L. A.; Halld orsson, M. M.; Ing olfsd ottir, A.; and Walukiewicz, I., eds., Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, 820 832. Springer. doi:10.1007/978-3-540-70575-8\ 67. URL https: //doi.org/10.1007/978-3-540-70575-8\ 67.

Christodoulou, G.; Kov acs, A.; and Schapira, M. 2016. Bayesian Combinatorial Auctions. J. ACM 63(2): 11:1 11:19. doi:10.1145/2835172. URL https://doi.org/10.1145/ 2835172.

Christodoulou, G.; Kov acs, A.; Sgouritsa, A.; and Tang, B. 2016. Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions. ACM Trans. Economics and Comput. 4(2): 9:1 9:33. doi:10.1145/2847520. URL https://doi.org/10.1145/2847520.

Cooper, D. J.; and Fang, H. 2008. Understanding overbidding in second price auctions: An experimental study. ECONOMIC JOURNAL 118(532): 1572 1595. ISSN 00130133. doi:{10.1111/j.1468-0297.2008.02181.x}.

Feldman, M.; Fu, H.; Gravin, N.; and Lucier, B. 2013. Simultaneous auctions are (almost) efﬁcient. In Boneh, D.; Roughgarden, T.; and Feigenbaum, J., eds., Symposium on Theory of Computing Conference, STOC 13, Palo Alto, CA, USA, June 1-4, 2013, 201 210. ACM. doi:10.1145/ 2488608.2488634. URL https://doi.org/10.1145/2488608. 2488634.

Feldman, M.; and Shabtai, G. 2020. Simultaneous 2nd Price Item Auctions with No-Underbidding. ar Xiv preprint ar Xiv:2003.11857 .

Foster, D. J.; Li, Z.; Lykouris, T.; Sridharan, K.; and Tardos, E. 2016. Learning in games: Robustness of fast convergence. In Advances in Neural Information Processing Systems, 4734 4742.

Harstad, R. M. 2000. Dominant strategy adoption and bidders experience with pricing rules. Experimental economics 3(3): 261 280.

Hassidim, A.; Kaplan, H.; Mansour, Y.; and Nisan, N. 2011. Non-price equilibria in markets of discrete goods. In Shoham, Y.; Chen, Y.; and Roughgarden, T., eds., Proceedings 12th ACM Conference on Electronic Commerce

(EC-2011), San Jose, CA, USA, June 5-9, 2011, 295 296. ACM. doi:10.1145/1993574.1993619. URL https://doi.org/ 10.1145/1993574.1993619. Kagel, J. H.; and Levin, D. 1993. Independent private value auctions: Bidder behaviour in ﬁrst-, second-and third-price auctions with varying numbers of bidders. The Economic Journal 103(419): 868 879. Lehmann, B.; Lehmann, D.; and Nisan, N. 2006. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior 55(2): 270 296. doi:10.1016/j. geb.2005.02.006. URL https://doi.org/10.1016/j.geb.2005. 02.006. Nisan, N.; Schapira, M.; Valiant, G.; and Zohar, A. 2011. Best-response auctions. In Proceedings of the 12th ACM conference on Electronic commerce, 351 360. Roider, A.; and Schmitz, P. W. 2012. Auctions with anticipated emotions: Overbidding, underbidding, and optimal reserve prices. The Scandinavian Journal of Economics 114(3): 808 830. Roughgarden, T. 2009. Intrinsic robustness of the price of anarchy. In Mitzenmacher, M., ed., Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 513 522. ACM. doi:10.1145/1536414.1536485. URL https://doi.org/ 10.1145/1536414.1536485. Roughgarden, T. 2012. The price of anarchy in games of incomplete information. In Faltings, B.; Leyton-Brown, K.; and Ipeirotis, P., eds., Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, 862 879. ACM. doi:10.1145/2229012. 2229078. URL https://doi.org/10.1145/2229012.2229078.

Roughgarden, T.; Syrgkanis, V.; and Tardos, E. 2017. The Price of Anarchy in Auctions. J. Artif. Intell. Res. 59: 59 101. doi:10.1613/jair.5272. URL https://doi.org/10.1613/ jair.5272.

Syrgkanis, V.; and Tardos, E. 2013. Composable and efﬁcient mechanisms. In Boneh, D.; Roughgarden, T.; and Feigenbaum, J., eds., Symposium on Theory of Computing Conference, STOC 13, Palo Alto, CA, USA, June 1-4, 2013, 211 220. ACM. doi:10.1145/2488608.2488635. URL https://doi.org/10.1145/2488608.2488635.