{'fraction_non_alphanumeric': 0.03739383229778259, 'fraction_numerical': 0.012896881947215414, 'mean_word_length': 4.18226128055535, 'pattern_counts': {'":': 1, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Cost of Simple Bidding in Combinatorial Auctions

We study a class of manipulations in combinatorial auctions where bidders fundamentally misrepresent what goods they are interested in. Prior work has largely assumed that bidders only submit bids on their bundles of interest, which we call simple bidding: strategizing over the bid amounts, but not the bundle identities. However, we show that there exists an entire class of auction instances for which simple bids are never optimal in Bayes-Nash equilibrium, always being strictly dominated by complex bids (where bidders bid on goods they are not interested in). We show this result for the two most widely used auction mechanisms: first price and VCG-nearest. We also explore the structural properties of the winner determination problem that cause this phenomenon, and we use the insights gained to investigate how impactful complex bidding may be. We find that, in the worst case, a bidder's optimal complex bid may require bidding on an exponential number of bundles, even if the bidder is interested only in a single good. Thus, this phenomenon can greatly impact the auction's outcome and should not be ignored by bidders and auction designers alike.


Introduction
Combinatorial auctions (CAs) are used in settings where multiple heterogeneous goods are being auctioned off to multiple bidders . In contrast to simpler designs like simultaneous ascending auctions, a CA allows bidders to express arbitrarily complex preferences over bundles of goods, including substitutes and complements preferences. CAs are frequently used in practice, for example for the sale of industrial procurement contracts (Sandholm 2013) or for selling TV ad slots (Goetzendorff et al. 2015).
One of the key challenges in CA design is to find a mechanism that provides bidders with good incentives. At first sight, the well-known VCG auction (Vickrey 1961, Clarke 1971, Groves 1973 may look like a suitable mechanism, given that it is efficient and strategyproof. Unfortunately, VCG can produce very low or even zero revenue in domains with complements . Therefore, the CA designs used in practice are typically non-strategyproof mechanisms. † Some of the ideas presented in this paper were also described in a one-page abstract that was published in the conference proceedings of the 22nd ACM Conference on Economics and Computation (EC'21) (Bosshard and Seuken 2021). this artificial restriction is lifted and bidders are allowed to make bids on arbitrary bundles of goods (which we call complex bidding), bidders may be able to significantly increase their utility, and the different strategies may considerably change the auction's equilibrium outcome.
The need for complex bidding cannot arise in full information settings, where all bidders know each others' values: Day and Milgrom (2008) showed that for any auction using a core-selecting payment rule, there always exist Nash equilibria in semi-sincere bids, which are a form of simple bids where the bidder simply underreports her true value for each bundle by the same amount.
It is straightforward to extend these results to show that even outside Nash equilibria, a bidder always has a best response that is a semi-sincere bid, against any bid profile of the other bidders.
Thus, we will focus exclusively on the incomplete information (Bayesian) case.
Our main conceptual contribution is to provide an explanation of why and how complex bidding manipulations work (Section 4). To provide some intuition, consider a simple first-price single-item auction. When submitting a bid, bidders must make a trade-off between winning more often vs.
obtaining a higher profit when winning. In Section 4.1, we provide a small but striking example to demonstrate that this logic does not need to apply when the strategy space becomes multidimensional. In that case, a bidder can place a complex bid which can be interpreted as containing multiple "conditional" bids placed on the same bundle of goods, such that only the most beneficial of these bids becomes part of the winning allocation. With complex bidding, a bidder can extract the highest possible profit, while still always winning her desired bundle when it is profitable. We provide a computational interpretation of complex bidding which suggests that the culprit of this strategic vulnerability is the fact that the auctioneer makes an ex-ante commitment to use an efficient allocation rule, i.e., to solve the winner determination problem optimally.
We next show that this is a general and robust phenomenon (Section 5). For this, we define a class of sealed-bid auction instances based on the well-known LLG domain , using either first price or VCG-nearest as the payment rule. We prove that, in any Bayes-Nash equilibrium (BNE) of an auction instance in this class, at least one bidder must submit a complex bid; thus, BNEs in simple strategies cannot exist.
Given this understanding of complex bidding, we then explore how impactful it can be for one bidder to deviate from a simple bid to a complex one, holding the other bidders' bid distributions fixed (Section 6). We prove that the strategy space of a CA has enough room allowing bidders to make conditional bids that are ex-post optimal in each of an exponential number of world states that may materialize. It follows that the amount of utility gain from complex bidding manipulations can be very significant in the worst case. A bidder who is interested in a single good (and thus has the simplest type of valuation possible) may be incentivized to bid on exponentially many bundles of goods, and increase her utility by an exponential amount in the process. Thus, even bidders who only have a localized interest in a few goods cannot avoid having to reason about the entire bundle space of the CA, contradicting the original design goals of CAs as described by Milgrom (2007) and Cramton (2013).
We construct this exponential separation both for the first price and VCG-nearest payment rules. This is especially surprising for the latter, given that VCG-nearest is a minimum revenue core-selecting rule and thus minimizes the total potential gains of bidders deviating from their bids (Day and Raghavan 2007). Our results imply that this joint minimization can still leave individual bidders with very high incentives to deviate, by setting their payment very high (equal to first price) for no good reason.
Importantly, these incentives for bidders do not arise from some special property of the mechanism, e.g., being iterative, only eliciting part of the bidders' preferences, or being restricted in some other way. Rather, the bidders make rational use of the large strategy space provided to them by a direct revelation mechanism, i.e., a sealed-bid CA with no limits on the number of bundles reported.

Related Work
The incentives of bidders in sealed-bid CAs have been extensively studied. Among papers that study manipulations where bidders make use of the strategy space of an auction in unintended ways, the work by Cantillon and Pesendorfer (2007) stands out. They study a multi-item first price reverse auction where strategic price discrimination occurs. In this auction, a bidder wants to sell two goods for which she has linear costs (the cost of producing both goods is the sum of individual costs), but makes a combinatorial bid that offers a bundle discount, thus misrepresenting the relationship between the goods as being complementary. They fit their model to data from London bus route auctions, finding that bidders indeed might be engaging in this manipulation deliberately.
Cantillon and Pesendorfer further observe that the optimization problem the bidder faces in some combinatorial auctions is equivalent to the multi-product monopolist pricing problem (McAfee et al. 1989). Thus, the incentives to exploit the complexity of the strategy space can arise on both sides of the market. Also from the auctioneer's perspective, the optimal mechanism design problem in CAs has recently been studied in terms of revenue guarantees for simple mechanisms and bounds on the menu size for obtaining near-optimal revenue (Babaioff et al. 2020(Babaioff et al. , 2021. In real-world CAs (e.g., spectrum auctions), bidders are typically much better informed about their own values than their competitors' (Milgrom 2004). This motivates a Bayesian analysis of auctions, where bidders know their own value but only have distributional information regarding the other bidders' values. This is the standard model in the analytical literature, which has mostly focused on characterizing BNEs in small sealed-bid auction domains (Baranov 2010, Goeree and Lien 2016, Ausubel and Baranov 2020a). There has also been a surge in the development of algorithms to find BNEs (or rather, ε-BNEs) numerically (Rabinovich et al. 2013, Bosshard et al. 2018, Bichler et al. 2021. Such algorithms have been used to search through entire design spaces of auction rules for the most favorable mechanisms (Bünz et al. 2018). What these approaches have in common is that they assume (either explicitly or implicitly) that bidders only bid on their bundles of interest, and thus the complex bidding manipulations we describe in this paper fall outside their scope by definition.
The work most related to our is that of Beck and Ott (2013). They introduce a phenomenon called overbidding, in which a bidder bids above her true value for at least some bundles. This stands in contrast to our definition of complex bidding, where a bidder cannot make a bid on a bundle for which her marginal value (given any sub-bundle) is zero. The two types of bid are similar in spirit, but not identical: a bid can be an overbid, complex, both or neither. Beck and Ott construct an auction instance with an artificial "favored-bidder" payment rule, in which the only BNE contains overbids. Upon inspection, these bids also turn out to be complex, according to our terminology. Unfortunately, Beck and Ott do not show any results under incomplete information with a payment rule actually used in practice, and they do not explore the extent to which their examples generalize.
Our work is also related in spirit to a recent thread of research that aims to understand what makes mechanisms "simple to play" (Li 2017, Pycia and Troyan 2019, Börgers and Li 2019. That research focuses on strategyproof mechanisms, whether or not they are obviously strategyproof (OSP), and what differences in bidder behavior arise between OSP and non-OSP mechanisms. In contrast, we apprach the same high-level question from a different angle: we only consider nonstrategyproof mechanisms, and attempt to distinguish between simple manipulations, which can reasonably be expected from the bidders (e.g., bid shading), and complex ones, which should not (e.g., increasing the dimensionality of their bid).

Formal Model
A combinatorial auction (CA) is a mechanism used to sell a set M = {1, 2, . . . , m} of goods to a set N = {1, 2, . . . , n} of bidders. Each bidder i's preferences over bundles are captured via the bidder's valuation v i . Specifically, for each bundle of goods K ⊆ M , we let v i (K) ∈ R ≥0 denote bidder i's value for bundle K. We normalize these values such that v i (∅) = 0. We assume that valuations satisfy free disposal, i.e., for any pair of bundles K, K it holds that: We consider one-shot sealed-bid auction formats. Each bidder submits a bid b i to the auction, which is a (possibly non-truthful) declaration of her whole valuation. The bid profile b = (b 1 , . . . , b n ) is the vector of all bids from all bidders, and the bid profile of every bidder except bidder i is denoted b -i . We require bids to be submitted using the XOR bidding language (Nisan 2006). Thus, each bid is a set containing zero or more atomic bids (K, β), where K is a bundle and β ∈ R ≥0 the reported value for bundle K. Because of the free disposal assumption, the reported value of any bundle for which no atomic bid was submitted is implicitly inferred to be the maximum reported value of any of its sub-bundles, or zero if there exist no such sub-bundles. To simplify the notation, we write an XOR bid {(K, β), . . . , (K , β )} as (K, β) ⊕ . . . ⊕ (K , β ). Furthermore, with a slight abuse of notation, we let b i (K) denote the value β which bidder i has explicitly (or implicitly) reported for bundle K.
The CA has an allocation rule X, determining an allocation x = X(b), where x i = X i (b) denotes the bundle assigned to bidder i. We require the resulting allocation to be feasible, i.e., ∀i, j ∈ N : x i ∩ x j = ∅, and we let A denote the set of all feasible allocations. We only consider efficient allocation rules, i.e., rules that produce an allocation that maximizes reported social welfare (which is the sum of bidders' reported values). 2 The CA also has a payment rule p which is a function assigning a payment p i (b) ∈ R ≥0 to each bidder i. Together, the allocation x and the payment vector p are called the auction outcome.
Given a bidder's valuation v i and a bid profile b of all bidders, we let u i (v i , b) denote bidder i's utility obtained from the auction's outcome. We assume that the utility function is quasi-linear of

Payment Rules and the Core
In this paper, we analyze two CA payment rules: first-price and VCG-nearest.
Definition 1. Given allocation rule X and bid profile b, bidder i's first-price payment is: (1) To define VCG-nearest payments, we must first introduce VCG payments and the core. For this, we define the set of feasible allocations when only considering a set of goods K ⊆ M as A K . We define the reported social welfare achieved by a subset L ⊆ N of bidders when only using goods K ⊆ M as follows: (2) Using this notation, we can now define standard VCG payments.
Definition 2. Given allocation rule X and bid profile b, bidder i's VCG payment is: In words, i's payment is the reported social welfare achievable by all other bidders if i was not present, minus the welfare they achieve in the presence of i.
Note that we define bidder i's VCG payments based on the bid profile b and not based on the valuation profile v. This allows us to compute what the VCG payments would have been, even if a payment rule other than VCG is used in the auction itself. Furthermore, note that VCG i (b) only depends on bidder i's bid b i via i's allocated bundle K = X i (b). We can thus equivalently write the VCG payment as VCG i (b -i , K). This is convenient when we later interpret this quantity as i's winning threshold for bundle K, i.e., for bidder i, VCG i (b -i , K) is the minimum bid she must submit on that bundle to win it, regardless of the payment rule.
The Core. Informally, a payment vector p is said to be outside the core if a coalition of bidders is willing to pay more for the goods than what the mechanism currently charges the winners. To avoid such outcomes, Day and Milgrom (2008) introduced the idea of core-selecting payment rules that restrict payments to be in the revealed core (i.e., the core with respect to reported values).
Definition 3. Given allocation rule X and a bid profile b, an auction outcome is in the revealed core if X is efficient, the payments p(b) are individually rational, i.e., ∀i p i (b) ≤ b i (X i (b)), and the following additional core constraints are satisfied: where X L is the set of goods collectively allocated to the set of bidders L. 3 A payment rule is called core-selecting if it always produces outcomes in the revealed core.
Note that the first-price payment rule is core-selecting, because Equation (4) always holds. 4 Among all payment vectors in the core, the minimum revenue core (MRC) is the set of payment vectors that minimize the sum of the payments of all bidders. We are now ready to define the second payment rule we study in this paper.
Definition 4. Given an allocation rule X and a bid profile b, the VCG-nearest payment rule computes the vector of payments in the minimum revenue core that minimizes the L 2 distance to the VCG payment vector (computed based on bid profile b).

Simplicity of Bids and Valuations
In this work, we are primarily interested in a bidder's incentive to deviate from a "simple" subset of the strategy space and make use of more elaborate strategies outside this subset.
We call a bid simple if it only contains atomic bids on those bundles for which the bidder has a genuine interest in every good, which means that the true value of the bundle cannot be explained by a strict subset of the goods within that bundle. Formally, a simple bid can only contain an atomic bid on bundle K if Given a valuation v i , we let B s (v i ) denote the set of simple XOR bids, and we let B c denote the set of all possible (complex) XOR bids. Note that B c does not depend on v i , and always contains all of B s (v i ). When clear from context, we sometimes use the term complex bid to refer to non-simple bids exclusively, i.e., B c \ B s (v i ). 5 Remark 1. Some readers may wonder why our definition of complex bidding is not broader, e.g., by requiring that simple bids not only disallow bids on bundles that violate (5), but also bids implying a valuation for a bundle K that is any amount above the true marginal valuation of that . Many of our results could indeed be adapted to hold under such an expanded definition. However, it is surprisingly difficult to broaden the definition of complex bidding without making it too broad and capturing some bids that are strategically very straightforward as well. We provide an example and further discussion of this issue in the electronic companion (Section EC.1). Our definition ensures that it only includes bids that are highly unnatural, and thus makes it easier to crisply identify the phenomenon we study in this paper.

Expected Utility and Best Responses
We consider CAs in a Bayesian setting where bidder i knows her own valuation v i , but she only has probabilistic information (i.e., a prior) over all other bidders' bids, represented by the random variable B -i . Given this uncertainty, the goal of bidder i is to submit a bid that maximizes her expected utilityū i , which is defined as We call the highest possible expected utility that can be achieved with any bid in B s (v i ) the simple best response utility, given bȳ A bid is a simple best response if it is in B s (v i ) and achieves the simple best response utility. 6 Analogously, we call the highest possible expected utility that can be achieved with any bid in B c the complex best response utility or just the best response utility, given bȳ A bid is a complex best response if it achieves the complex best response utility.

Bayes-Nash Equilibrium
In Sections 4 and 5, we will analyze the behavior of bidders in equilibrium. For this, we consider the situation where each bidder's valuation is a random variable V i with a probability distribution that is common knowledge. Bidder i is the only one to know V i 's realization v i , and applies a strategy where s i is a function mapping valuations to bids and is also common knowledge. We can then define a (complex) Bayes-Nash equilibrium in the standard way: Definition 5. A Bayes-Nash equilibrium (BNE) is a strategy profile s * = (s * 1 , . . . , s * n ) for which it holds that For bidders who only play simple bids, we can define an analogous equilibrium concept where strategies must map all valuations to simple bids: Definition 7. A simple BNE is a strategy profile s * consisting only of simple strategies and for which it holds that

What Drives Complex Bidding under Incomplete Information?
In this section, we provide a detailed structural analysis of why complex bidding is often incentivized in CAs. As mentioned above, when bidders have full information about each others' valuations, bidder i's set of best responses always includes at least one simple bid. Thus, complex bidding can only be useful to a bidder under incomplete information.
We will show that complex bidding can help the bidder deal with uncertainty, increasing her profit while decreasing the risk of not winning her desired goods. To strengthen this intuition, we first present an example where, in Bayes-Nash equilibrium, a complex bid allows one of the bidders to obtain a much better result than any simple bid. We then take a single-agent perspective and look at the optimization problem that a given bidder faces, to help us understand the structural effects that create the incentives for complex bidding. Table 1 Auction instance where a complex strategy is better than all simple strategies for bidder 1. Bidders 1 and 2 have a 50% chance (independently) to have either their low or their high value.

Bidder
Valuation

Example
Consider the following auction, which is a version of a standard setting known as LLG (locallocal-global), using the VCG-nearest payment rule. To simplify the exposition, we use very simple, discrete value distributions for the bidders. In Section 5, we show that our findings apply to much richer distributions as well.
Example 1. We have two local bidders and one global bidder, bidding on two goods. The global bidder has value 1 for the bundle {1, 2} but 0 for any single good. It is known that the global bidder has a dominant strategy to bid truthfully (Beck and Ott 2013). The local bidders are interested in the singleton bundles {1} and {2}, respectively, and have a 50% chance of having either a low or high value, independently of each other. The detailed valuations are given in Table 1, and the BNEs listed there are derived in the electronic companion (Section EC.2).
In the simple BNE, the local bidders win 25% of the time, namely when both their valuations are high. In that case, they outbid the global bidder, and they split the core payment of 1 evenly between them, because they both bid 1/2. In the complex BNE, the locals still win and split the payment in the high-high case. But additionally, when bidder 1 has a high value and bidder 2 has a low value, bidder 1 wins over bidder 3 with her bid on the global bundle (as we break ties in favor of bidder 1). Thus, bidder 1 receives her desired good and pays 1, which increases her total expected utility from 0.35 to 0.45.
So, why does bidder 1 not simply increase her bid to 1 under simple bidding? This would have two effects: increasing her utility in the high-low case by allowing her to win (just as in the complex BNE), but decreasing her utility in the high-high case, because her higher bid causes her payment to increase. 7 Adding these two effects together, bidder 1 is better off when bidding only 1/2. As a result, the simple BNE allocates the goods inefficiently 25% of the time: in the high-low case, bidder 3 receives the goods, even though bidder 1 has strictly higher value for them. In contrast, the complex BNE always produces the efficient allocation, and also yields higher expected revenue for the auctioneer. 8 We next investigate in more detail why and how Example 1 works, and we show that its underlying logic is robust and thus applicable to many auction domains. In fact, this example is just one auction instance from a whole class of auctions covered by Theorem 2.

Winning Thresholds and Signals
We now take a look at the optimization problem that a single bidder faces in an auction when keeping the strategies of the other bidders fixed, and we interpret complex bidding in that context.
Given bids b -i , every bundle K has an associated VCG payment VCG i (b -i , K), which bidder i cannot affect with her bid. The efficient allocation rule dictates that a bid can only become part of a winning allocation if the welfare this bid adds to the allocation is at least as large as the welfare that it would displace. The latter amount is exactly the VCG payment. Thus, VCG i (b -i , K) is the minimum amount that bidder i must bid to win bundle K (assuming she makes no bid on any other bundle), and bidder i's payment must be at least this winning threshold for any core-selecting payment rule. 9 In an incomplete information setting, the bids b -i are uncertain and represented by the random variable B -i . Thus, the winning thresholds VCG i (B -i , K) are also random variables. Since the distribution of B -i is common knowledge, the distribution of VCG i (B -i , K) has a CDF F K i that is known to bidder i. Now observe that, for an auction with the VCG payment rule, the utility obtained by a singleminded bidder who bids truthfully on bundle K is simply the area under the graph of F K i . To illustrate this geometrically, we return to Example 1, where the distribution B -i is discrete and thus F K i is a step function ( Figure 1a). The dark red area corresponds to the event of probability 50% that bidder 2 has a high value, where the wining threshold for bidder 1 is 0.5. The contribution of that event to bidder 1's expected utility under VCG is 0.5 · (1.2 − 0.5) = 0.35. Likewise, the light red area corresponds to the event that bidder 2 has a low value, and the contribution to bidder 1's expected utility is 0.5 · (1.2 − 1) = 0.1. Bidder 1's total expected utility under VCG is the sum of these two terms, i.e., 0.35 + 0.1 = 0.45. This reasoning generalizes to continuous distributions, where we integrate over an infinite number of possible realizations of VCG i (B -i , K) ( Figure 1b).
For payment rules other than VCG, a given bid only captures part of the area under the curve.
For example, with the first price payment rule, the utility obtained in each realization of B -i

Figure 1
Geometric intuition for bidder i's utility under the VCG payment rule. The total expected utility corresponds to the area under the curve of F K i and to the left of vi(K).
from Example 1. The dark red slice corresponds to the event of probability 50% where b 2 ({2}) = 0.5 and thus only spans from b i (K) to v i (K), and the utility between VCG i (B -i , K) and b i (K) is lost. When aggregating over all realizations of B -i , the expected utility obtained is a rectangle, corresponding to the multiplication of a specific payoff v i (K) − b i (K) targeted by the bid, times the probability ) of winning with that bid. Now, if bidder i was only allowed to bid on bundle K, she would simply need to find the bid that yields the largest rectangle fitting under the graph of F K i (Figure 2a), and her optimization problem would thus be reduced to a single dimension. However, we claim that in the full strategy space of the auction, the bidder can place multiple atomic bids in such a way that the total utility captured is the union of the rectangles formed by multiple different bids (Figure 2b), which potentially captures much more utility than a single rectangle.
To see how this can be achieved, we first imagine a situation where bidder i somehow managed to obtain information about the other bidders' bids b -i from the auctioneer, before having to submit her own bid b i . It is clear that this information can be highly beneficial to bidder i, as it resolves all her uncertainty about B -i , allowing her to make a bid that is optimal ex-post: high enough to win, but not so high that she misses out on potential profit.
In our model, the bidder cannot actually obtain this information from the auctioneer directly, of course. However, the auctioneer does guarantee that the efficient allocation rule will be used, and thus the distributions of the winning thresholds VCG i (B -i , K) can be calculated in advance by bidder i, based on knowing the distribution of B -i . Using this fact, bidder i can place a carefully constructed complex bid that allows her to simulate the actions she would take if she did have privileged information about B -i . To see this, we need to consider the correlation structure between the random variables VCG i (B-i, K) and B -i . Coming back to Example 1, it is easy to check that 1 (a) Expected utility achievable with a simple bid. 1 Expected utility achievable with a correctly constructed complex bid.
which implies that We highlight that VCG itself, a feature that arises because the first two bidders must "cooperate" to win, i.e., the sum of their bids must jointly overcome the third bidder's bid for the goods.
Bidder 1 can exploit this correlation and place a bid b 1 that conditions on the realization of B 2 ({2}) through the identity (14), even though at the time of placing b 1 , B 2 ({2}) has not been realized yet from her perspective. This is achieved by placing the XOR bid for any value t * > 0. In the winner determination problem, bidder 1's second atomic bid will be more competitive than her first one exactly when which due to (14) corresponds to Thus, bidder 1 always offers a low bid of β for her desired good, but increases this bid by t * exactly when needed, namely when b 2 ({2}) = 0 and she has to overcome bidder 3's bid by herself. In the complex BNE, bidder 1 chooses β and t * optimally, and as a result wins her desired bundle 100% of the time, never paying more than VCG.
More generally, it is possible for bidder i to condition on the realization of B -i whenever she is interested in a bundle K, and there exists another bundle S such that is inversely correlated with VCG i (B -i , K). We emphasize that such dynamics always arise when some of the other bidders' bids make it easier (rather than harder) for bidder i to become a winner.
This is a very common occurrence, and the LLG domain is just the smallest auction domain exhibiting this effect.
A more computational way of thinking about this phenomenon is that bidder 1 does not bid a fixed numerical value, but (figuratively) provides a computer program as a bid (Algorithm 1). This "bid-program" gets executed in an environment where the marginal demand for bundle S given bundle K as expressed in (18) is readily accessible, and the bid-program can use this information as a binary signal, to select one of two possible atomic bids to be submitted to the auctioneer, and retracting the other. In Section 6, we will construct a more complicated signal that allows the bidder to adapt her bid to be optimal for each of an exponential number of winning thresholds, by placing exponentially many atomic bids.
The manipulation we have discussed is structurally unavoidable whenever some of the winning thresholds are negatively correlated in the way shown; the computation that exposes the signal must be performed by any auctioneer who commits to always allocating the goods efficiently, because this commitment already fixes how the winning thresholds VCG i (B -i , K) are calculated, regardless of the payment rule used in the auction.

Complex Bidding Dominates Simple Bidding in BNE
In the previous section, we have shown that complex bidding can arise in the presence of a signal, and we argued that such signals arise naturally in CAs. To substantiate this claim, we now introduce a class of auction domains for which simple bidding is always dominated by complex bidding, in the sense that any BNE which might exist cannot entirely consist of simple strategies. We show this for the two most commonly used payment rules, first-price and VCG-nearest.
The class of auction domains we define next is a generalization of Example 1. It has the same combinatorial structure as the LLG domain: there is a global bidder with a known valuation for a bundle of two goods, and two local bidders who must cooperate to jointly win the goods. However, we impose a few special conditions on the bidders' valuations. In particular, we require two features that incentivize complex bidding: (1) a local bidder's valuation can be high enough to want to win even without the other local bidder, and (2) that other bidder's valuation can be low enough that the first bidder cannot always count on her help.
These conditions are fulfilled in many scenarios, e.g., when the two local bidders have value distributions that are i.i.d. uniform on the interval [0, 2], with the global bidder having a fixed value of 1. As we aim to impose as few restrictions as possible on bidders' value distributions, we formalize the conditions in a minimal way, such that they also apply to more involved domains where valuations are non-uniform, correlated with each other, and so on.
Definition 8. An auction domain belongs to the LLG-A class if • There are 2 goods and 3 bidders.
• The following relations hold for the bidders' valuations: -Bidder 1 can have a high value (higher than bidder 3): -When bidder 1 has high value, bidder 2 does not always have 0 value: -Bidder 3 can have the highest value for the goods: -When bidder 1 has high value, bidder 2 can have arbitrarily low value: We now show our first main result, namely that for any auction instance in LLG-A, in any BNE, there is at least one bidder who plays a complex strategy for some of her valuations. Thus, BNEs consisting only of simple strategies do not exist.
Theorem 1. In any auction domain of the LLG-A class, when using the first price payment rule, every BNE s * contains at least one strategy s * i that is not simple.
Proof. The proof is structured as follows. We focus exclusively on the case where v 1 ({1}) > 1, and we assume that we are at a strategy profile s * that is a simple BNE. Given these shapes, we construct a complex best response for bidder 1 that captures strictly more utility than s * 1 (v 1 ), showing that s * is not a (complex) BNE. First, note that the global bidder must make a deterministic bid, so we have that b 3 = {({1, 2},β)} for someβ ≤ 1. Because we are in simple BNE, we must haveβ > 0: Under first price, bidding above one's value is always strictly dominated, so due to (21), the local bidders must sometimes jointly bid below 1. Therefore, settingβ = 1 − ε yields strictly positive utility to bidder 3 and thus dominatesβ = 0, which always yields 0 utility due to our tiebreaking definition.
Similarly, because we are in simple BNE, bidder 2 cannot always bid zero: in that case, bidder 1's simple best response would clearly be to bidβ whenever her value is strictly aboveβ. This in turn means that any bid by bidder 2 that is strictly larger than 0 wins with positive probability, and thus strictly dominates the zero bid whenever bidder 2's value is above zero, which happens with positive probability due to (20).
Given these arguments, we claim that bidder 1's winning thresholds have the following shapes: is a step function going directly from 0 to 1 atβ.
• F {1} 1 also reaches 1 exactly atβ, but it is not such a step function.
Regarding the shape of F {1,2} 1 , we argue as follows: this function must be 0 belowβ, because any bid from bidder 1 in this region always loses to the global bidder's bid. Aboveβ, if the probability of winning was lower than 1, it would imply that bidder 2 bids strictly higher thanβ with positive probability, which cannot happen in a simple BNE under first price, as it is strictly dominated by reducing the bid toβ, which is already high enough to guarantee that bidder 2 always wins.
Regarding the shape of F is clearly 1, because bidder 1 is guaranteed to win even without any assistance from bidder 2.
Having established the shape of the winning thresholds for bidder 1, we consider bidder 1's simple best response b 1 = s 1 (v 1 ) = ({1}, β), and we split the remainder of the proof into two cases 10 To see this, we compare the utility obtained by a bid strictly above the true value with a truthful bid. In realizations of B-2 where both bids would win, the latter bid obtains stricty more utility as it has a lower payment. In cases where the latter bid is not high enough to win, the VCG payment (i.e., the winning threshold), is above the true value, and thus the utility obtained by the bidder under the former bid would be negative.
depending on the value of β, and show that in both cases, there is a complex bid that is strictly better than ({1}, β).
Case 1 (β <β): In this case, the following complex bid is a better response: We split the realizations of bidder 2's bid B 2 into four subcases, depending on what bidder 1 wins. First, with some probability q 1 , bidder 1 is allocated {1} under b 1 , and in that case she is also always allocated {1} under b 1 . This is because the two local bids jointly sum up to at least β + ε, and so are at least as competitive as bidder 1's second atomic bid, and we assume that ties are broken in favor of having more winners. Second, third and fourth, if bidder 1 would be allocated nothing under b 1 , then under b 1 she has three possible allocations, {1}, {1, 2} and ∅, with probabilities q 2 , q 3 and q 4 , respectively. It follows that the expected utility of bidder 1 under b 1 and b 1 isū Subtracting the former from the latter, the difference in expected utility is Observe that q 1 < 1 due to (22) and the fact that bidder 2 never bids strictly above her value. We also have that q 4 = 0, because bidder 1's second atomic bid ({1, 2},β + ε) implies that any winning allocation must have bid at leastβ + ε. This is higher than bidder 3's bid by construction, and bidder 2's bid is also always at mostβ, since this strictly dominates any higher bid in simple BNE under first price. It follows that either q 2 > 0 or q 3 > 0, and thus (25) is larger than 0 for small enough ε.
Case 2 (β ≥β): We can assume WLOG that β =β, because this is always strictly better for is not a step function, we can always find a number 0 < β <β such that the Connecting the proof of Theorem 1 back to our insights from Section 4, it becomes clear that the reason complex bidding is favored in the LLG-A class is that the situation where bidder 1 wins her good by competing alone against bidder 3 requires a fundamentally different approach than when bidder 1 wins together with bidder 2, and only a complex bid can simultaneously optimize for these two scenarios.
We next introduce an analogue of Theorem 1, but for the VCG-nearest payment rule. For this, we define a second class of auction domains that is almost identical to LLG-A, except that it adds one additional constraint to bidders' valuations.
Definition 9. An auction domain belongs to the LLG-B class if it belongs to the LLG-A class, and additionally, bidder 2's value for {2} is strictly smaller than 1, i.e., v 2 ({2}) < 1.
For this class, the equivalent of Theorem 1 also holds, when we additionally assume that the global bidder bids b 3 = ({1, 2}, 1). This is a very minimal and reasonable assumption, as it is known that truthful bidding is a dominant strategy for the global bidder (Beck and Ott 2013).
Theorem 2. In any auction domain of the LLG-B class, when using the VCG-nearest payment rule, every BNE s * where the global bidder bids truthfully contains at least one strategy s * i that is not simple.
To keep the notation consistent, we still denote the global bidder's bid asβ, even though we know thatβ = 1. To prove the theorem, we must first characterize the VCG-nearest payments in the LLG-B class. We do this in the electronic companion (Section EC.3), where we show that for a large set of bid profiles (including all those that occur in the proof of Theorem 2), the VCGnearest payments are exactly halfway between VCG and first price, with the first price portion being capped byβ: Geometrically, this means that, for a given bid, bidder i obtains an expected utility corresponding to the whole first price rectangle below F K i , plus exactly half the area to the left of that rectangle (Figure 3). This fact makes it less surprising that VCG-nearest does not prevent incentives for complex bidding from arising, because the payments produced by this rule require the bidders to submit shaded bids to avoid overpaying, just like for first price. With this in mind, we can now proceed to the proof.
Proof of Theorem 2. The proof proceeds analogously to that of Theorem 1. When we derived the constraints on the shape of F  Utility obtained by bidder 1 under the VCG-nearest payment rule, in case 2 in the proof of Theorem 2, when the optimal simple bid is above the global bidder's thresholdβ.
(a) The optimal simple bid captures all the area under the curve to the right ofβ, and exactly half the area to the left ofβ.
(b) The optimal complex bid also captures all the area to the right ofβ, and strictly more than half the area to the left ofβ. and then that b 2 ({2}) ≤ v 2 ({2}). Under first price, this was very straightforward. We now show the same for VCG-nearest as follows: the first inequality follows from the second, due to our new assumption (26). For the second inequality, we combine (26) and Lemma EC.2 to show that the payment strictly increases when going from the truthful bid to a higher one, and thus the argument we made for first price also applies.
Case 1 (β <β): This case proceeds exactly like in the proof of Theorem 1, except that we need to make use of the just established fact that b 2 ({2}) ≤β to show that q 4 = 0. We then use Lemma EC.3 to determine the payments and thus show that b 1 = ({1}, β + ε) ⊕ ({1, 2},β + ε) obtains more expected utility than b 1 in the limit ε → 0. If we want b 1 to yield strictly higher utility than b 1 , we need to ensure that since we have the obvious identity |E| + |F | = |Z|. Now, it is clear that and Lemma EC.2 tells us that the VCG-nearest payments are exactly between VCG and first price, so |A| = |B| and |X| = |Y |. Thus, (29) can be rewritten to which can be combined with (28) and simplified to |D| > |C|.
The only thing still to be shown is that there always exists β such that (31)  in the open interval [0,β). By definition of a supremum, there must exist β such that F {1} 1 (β ) > s/2. But this means that the area between β andβ is at most s · (β − β ), and |D| = F {1} 1 (β ) · (β − β ) is strictly more than half of that.
Theorem 2 provides a strong headwind for the conventional wisdom that VCG-nearest makes bidding in a CA particularly easy. Furthermore, we observe that the same logic underlying the incentives for complex bidding also applies in situations where all other bidders simply report truthfully: Proposition 1. In an auction domain of the LLG-B class, under the first price or VCG-nearest payment rules, bidder 1's best response against the truthful strategy profile This result immediately follows by the same arguments of the proofs of Theorems 1 and 2, and we therefore omit a formal proof.

Exponential Separation of Utilities with Simple vs. Complex Bids
So far, we have established that complex bidding is systematically incentivized in many auction instances. We now ask a natural follow-up question: can we put a bound on how large this effect is in the worst case? In Section 4, we showed that a bidder can exploit the correlations between winning thresholds induced by the winner determination problem as a signal to activate the best among two conditional bids. At first sight, we might hope that there is a tight upper bound on Construction of the distribution F K 1 used in Theorem 3. The area under the curve is shaped such that no simple bid can capture a large fraction of the total utility, but a complex bid with exponentially many atomic bids can capture the whole area. how much utility can be gained via complex bidding -maybe a factor two, given that the signal we used was only binary. However, as we show next, it is possible for a signal to encode many more than just two different world states, thus leading to a much larger increase in utility.
We now return to the point of view we adopted in Section 4.2, considering a single bidder i's decision problem when faced with a fixed distribution of bids B -i . This helps us better understand just how large a complex bid can get (in terms of the number of XOR atoms), and still have each of those atoms be relevant for the total utility obtained by the bidder. For this, we construct a family of auction instances (i.e., a series of auctions, parameterized by m, the number of goods being sold). Surprisingly, we show that the size of the optimal complex bid can be exponential in m, and the complex best response utility is exponentially larger than the simple best response utility.

First Price
We first state this result for the first price payment rule: Theorem 3. There exists an auction family F (m) with m goods and using the first price payment rule, such that for some single-minded bidder i and bid distribution B -i , we have that Furthermore, the complex best response must contain Θ(2 m ) times more atoms than the simple best response.
Before we proceed to the proof of Theorem 3, we provide an overview of the main proof ideas.
The full proof can be found below in Section 6.2. We construct an auction instance where the bid profile B -1 encodes a signal that reveals the exact winning threshold VCG 1 (B -1 , {m + 1}) to bidder 1. Given this signal, bidder 1 can make a separate atomic bid for each possible realization of the winning threshold, and pack them into one XOR bid in such a way that the atomic bids do not interfere with each other, i.e., each of them wins if and only if its associated threshold is realized.
To maximize the ratio of the simple and complex best response utilities, we lay out the realizations of the winning thresholds along a geometric series. See Figure 4 for a graphical representation of our construction. To minimize the utility of the simple best response, we balance F {m+1} 1 such that the payoff obtained by a bid is inversely proportional to the winning probability. Consequently, all simple bids yield the same (low) expected utility, regardless of the bid amount. Conversely, to maximize the complex best response utility, we ensure that there are exponentially many different winning thresholds, and that the utility rectangles associated to each of them overlap very little with each other. Thus, each atomic bid in the complex best response obtains almost as much utility as the simple best response by itself.

Proof of Theorem 3 (First Price)
We introduce an auction family, i.e., a single-parameter series of instances F (m + 1) of increasing size. 11 Let m ∈ N. For i ∈ R + , let f (i) := 1 − 1 2 i , let C be a large constant, and let K be the powerset of the first m goods, i.e., the set of all bundles K ⊆ {1, . . . , m} which do not contain good m + 1.
Then, let σ be a bijective function such that In other words, σ assigns a rank to each bundle in K, such that this ranking forms a total order consistent with the partial order induced by the subset relation.
Definition 10. The auction family F (m + 1) is given as follows: 1. The auction has 3 bidders and m + 1 goods.
2. Bidder 1 has value 1 for bundle {m + 1}, and no interest in any other bundle.
3. Bidder 2 always bids C on the bundle of all goods.

Bidder 3 bids
where j is a random variable chosen from {1, . . . , 2 m } with probability proportional to 2 j . This can be achieved by normalizing 2 j with the factor 2 m j=1 2 j = 2 2 m +1 − 2. 5. The allocation rule is efficient, and the payment rule is first-price.
The bidders of this auction family and the relation of their bundles to each other are shown in Table 2. To understand the asymptotic behaviour of this auction family, we first need to understand the strategic landscape that bidder 1 is presented with. For this, we must formally define which Table 2 Bundle bids made by different bidder types in auction family F (m + 1). Bidder 1 works together with bidder 3 (the helper). If bidder 1 bids f (i), they can jointly defeat the competitor whenever i ≥ j. Bidder 1 can make additional bundle bids that include more goods, and those bids are active whenever they do not overlap with the helper's bid.

Bidders
Goods Signalling Goods Prize 1 . . . m m + 1 bids even have a chance of winning. For our next definition, recall that W (b, L, K) is the reported social welfare achieved when coalition L jointly wins the goods K.
Definition 11. Given a bid profile b, a bundle K is active for bidder 1 if m + 1 ∈ K and In words, a bundle is active whenever it does not matter (for winner determination), whether bidder 1 makes an atomic bid on her original bundle of interest {m + 1} or on bundle K. In the latter case, she would just win some unneeded goods on top of good m + 1. It follows that bidder 1 can combine any bid on an active bundle with the bid by bidder 3, to jointly overcome the threshold needed to win against bidder 2. Given this definition, we now characterize the auction's possible outcomes in the following lemma.
Lemma 1. In the auction family F (m + 1), let b 1 be a bid for bidder 1, and let K * be the active bundle with the highest atomic bid in b 1 . Furthermore, assume that bidder 1's bids on other bundles are not too high, i.e., ∀K = K * : b 1 (K) ≤ 1.
Proof. Because bidder 1's bids are capped at 1, she cannot win without the help of bidder 3. It is always a feasible allocation to give all goods to bidder 2, for a reported social welfare of C. This welfare is exceeded by a combination of bidder 1 and 3's bids exactly when the bid on the largest active bundle K * is at least f (i) for some i ≥ j.
Note that due to the first-price payment rule, bidder 1's payment does not depend on the identity of K * , but only on the bid amount b 1 (K * ). Furthermore, if b 1 contains any atomic bid larger than 1, bidder 1 would either never win with this bid, making it irrelevant, or she would win with negative utility. Thus, we can assume WLOG that b 1 fulfills the assumption of Lemma 1, and we can easily compute the utility obtained by bidder 1 for any given realization of j. With this information, we can now establish bidder 1's simple and complex best response utilities.
Proof. Bidder 1's payment increases monotonically in i, so it is optimal for her to bid exactly on one of the levels f (i) for i ∈ N, where the winning probability makes a discrete jump. Note that any bid between two bid levels (or above level f (2 m )) is strictly worse than the next lower bid level.
For a bid of f (i), bidder 1 wins whenever i ≥ j and has a utility of 1 − (1 − 1 2 i ) = 1 2 i (because the payment rule is first-price and utilities are quasi-linear). Recall that the probability distribution of j is proportional to 2 j . Thus, bidder 1's expected utility for any 1 Lemma 3. In auction family F (m + 1), bidder 1's best response utility is Θ 2 m 2 2 m .
Proof. Since bidder 1's payment is independent of the winning bundle's identity, her utility is maximized when she bids in such a way that for each j, she wins with an atomic bid that offers just the minimum amount needed to win. This bound can be achieved by bidding as follows: For each bundle K that contains good m + 1 (i.e., all bundles not contained in K), bidder 1 adds an atomic bid (K, f (σ(M \ K))) to her bid. This bid is just high enough to win when the signal is j = σ(M \ K). Furthermore, this atomic bid does not win with any other realization of the signal.
We show this by case split over the realizations of j. Case 1: We have that j = σ(M \ K ) for some K ⊃ K. Since K = K, there exists at least one good that is in K but not in K . Any bundle bid on K cannot win because it is not active (it overlaps with bidder 3's bid on M \ K ), and would need to be at least C. Case 2: We have that j = σ(M \ K ) for some K ⊃ K. The bundle bid on K is dominated (in the winner determination problem) by the bundle bid on K , because (due to σ respecting the partial order of K and f being monotonic), we have that It follows that for each realization of j, the highest active bid is f (j). Applying Lemma 1, the expected utility is thus With these lemmas in place, we can now prove the exponential separation for the first price payment rule.
Proof of Theorem 3. Consider the family of auctions F (m + 1). The total number of goods is m + 1 = Θ(m). Using Lemmas 2 and 3, the ratio of the simple and complex best response utilities of bidder 1 is It follows from Lemma 2 by union bound that Θ(2 m ) atoms are needed to achieve the complex best response utility.

VCG-nearest
It turns out that, as in Section 5, the equivalent result for VCG-nearest also holds: Theorem 4. There exists an auction family F (m) with m goods and using the VCG-nearest payment rule, such that for some single-minded bidder i and bid distribution B -i , we have that Furthermore, the complex best response must contain Θ(2 m ) times more atoms than the simple best response.
The proof for Theorem 4 proceeds along the same lines as for Theorem 3, except that we need to construct the auction family in such a way that the payment rule behaves very badly for bidder 1. Showing this requires some additional technical work, such as a detailed analysis of all the core constraints involved, and we provide the proof in the electronic companion (Section EC.4).
Theorems 3 and 4 are striking results because they demonstrate that even a single-minded bidder can make productive use of the entire exponentially large strategy space offered by CAs. Thus, we cannot provide an upper bound on the profitability of complex bidding manipulations better than 2 m . 12 It is still possible that a tighter bound (e.g., a constant factor difference between the simple and complex best response utility) could be established in BNE. However, any result in this direction will require an explicit analysis of the equilibrium conditions, as the single bidder perspective we take does not impose strong enough constraints on the problem.

Discussion
Our results from Sections 5 and 6 are structural in essence: they are mostly derived from the combinatorial properties of the winner determination problem, and the way that multiple atomic bids from the same bidder compete with each other, based on their relative strength compared to the winning thresholds of their respective bundles. This is a fundamental property of CAs, independent of more superficial aspects of the problem, and thus very difficult to avoid.
For convenience and clarity, we have provided our definition of simple and complex bidding with respect to the XOR bidding language. However, it is possible to define complex bidding only in terms of the marginal bids implied by whatever bidding language is used to report the valuations to the auctioneer. In Section 6, our results regarding the size of a bid (in terms of number of atomic bids) do depend on the bidding language, but can easily be adapted to other languages such as OR*. The remainder of our results only require that the bidding language be fully expressive, able to represent all possible valuations.
Our results in Section 5 are "almost tight": for the LLG-B class, conditions (19) and (20) are required for bidder 1 to have any incentives for complex bidding under the VCG-nearest payment rule. In the absence of either condition, bidder 1's strategy space collapses to one dimension.
For LLG-A and first price, the same idea holds in principle, with some technical caveats. Thus, the LLG-A and LLG-B classes cannot be made substantially larger, as they already cover most situations where a bidder has incentives for complex bidding in LLG-like domains. The fact that the global bidder has a fixed valuation is also not essential, and only made to simplify our analysis and make our findings cleaner.
To ground the significance of our results, we point out that LLG-like dynamics often arise naturally in real-world auctions. For instance, Ausubel and Baranov (2020b) provide examples of zero-revenue outcomes that have occured in spectrum auctions, where the bidders exhibit valuations closely mimicking LLG-like settings in the assignment stage of the combinatorial clock auction.
Regarding our results from Section 6, we note that Theorems 3 and 4 immediately translate to deviations from truthful bidding as well, by simply setting the valuations of bidders 2 and 3 such that the bid profile used in the proof is truthful. This contradicts the argument found in the literature that straightforward truthful bidding is a reasonable strategy under this rule (Cramton 2013, Milgrom 2007. The equivalent of Theorem 4 might also hold for other minimum-revenue core-selecting payment rules. Many of the arguments in the proof are not specific to VCG-nearest but simply establish that the shape and location of the core can be forced to be very asymmetric between bidders. Thus, any payment rule that computes payments by projecting a reference point to the core "from below" is potentially vulnerable to the same construction. However, some minimum-revenue core-selecting payment rules such as nearest-bid (Ausubel and Baranov 2020a) project to the minimum-revenue core "from above," and might thus be less susceptible to such asymmetric constructions, creating fewer incentives for complex bidding.

Conclusion
In this paper, we have analyzed the existence and magnitude of complex bidding manipulations in CAs. These manipulations are highly counter-intuitive, but they are incentivized, because they enable bidders to circumvent the uncertainty they face regarding the bids of others. We have presented two pieces of evidence that complex bidding can be a major issue: first, there exist entire classes of auction domains where simple bidding is dominated by complex bidding in BNE. Second, the large strategy space available to bidders in a CA allows them a lot of room to manipulate via complex bids, leading to an exponential utility increase in the worst case.
It is particularly surprising that VCG-nearest does not provide any protection against this manipulation, given that it is a minimum-revenue core-selecting payment rule. In particular, we have shown that, in the domains we have studied, VCG-nearest can be forced to behave identically to first price for some of the bidders, losing its conceptual similarity to second price payment rules.
It is an interesting topic for future work to study whether other core-selecting payment rules are much better behaved in this sense or whether this is a fundamental property of all such rules.
Our findings raise many questions for practical auction design, given that the strategic behavior we describe could interfere with efficiency and price discovery, and might give a major advantage to the most sophisticated bidders. Taking a broader mechanism design point of view, we note that any mechanism that produces efficient outcomes (even if only in BNE) must implicitly or explicitly solve the winner determination problem, and must produce the signals that our manipulation depends on. It is thus natural to ask in what kind of form these signals are represented in different mechanisms, and whether there are principled ways how this information can be isolated and made inaccessible to bidders.
While our exponential separation of utility is an extreme example that we do not expect to encounter as-is in practice, the logical pathway underpinning it is quite robust. Therefore, we expect that opportunities for complex bidding manipulations also arise in real-world CAs, especially in settings with heterogeneous bidders and sufficiently rich valuations. However, many practical applications of auctions use domain-specific bidding languages, or impose other restrictions on bidders' strategies. For example, spectrum auctions typically have a bound on the size of bids on the order of 500 atomic bids (Ausubel and Baranov 2017). Under these types of constraints, it might be possible to establish bounds on how profitable complex bidding manipulations can be. Similarly, the benefit of complex bidding could be bounded in terms of the structure and complexity of bidders' value distributions that arise in different application domains. Taking such considerations into account, we believe it might be possible to design mechanisms and bidding languages that make it hard to report valuations that are unnatural or overly complex, while still allowing for enough expressivity for bidders to accurately report their true valuations. Succeeding at this difficult task would preserve the known advantages of combinatorial auctions, while restoring the natural desideratum of simplicity.

EC.1. Example Auction with Natural Overbidding
In this section, we provide an example of a bid that at first glance appears it should be a complex bid: it contains bundle bids on two bundles such that the marginal bid on the larger bundle exceeds the marginal valuation of that bundle. However, upon closer inspection, it is actually a very reasonable way for a bidder to behave. As the present paper focuses on describing complex bidding manipulations in the most crisp and clear way possible, we consider such edge cases to be simple bids, and we leave a detailed exploration of the boundary between complex bidding and other forms of overbidding to future work.
Example EC.1. Consider an auction with two bidders and two goods, and the first price payment rule. Bidder 1 has the following valuation: Bidder 2 makes a bid that has equal probability of taking on each of two possible realizations: The bid B 2 creates two possible worlds, and depending which of those worlds is realized, bidder 1 needs to win a different bundle to maximize her profit. The example is set up in such a way that the larger bundle is won with a narrower profit margin than the smaller one. Thus, bidder 1's best response to B 2 requires a marginal overbid on good 2 given good 1, i.e., the increase in the bid when going from bundle {1} to bundle {1, 2} is larger than the corresponding increase in value.
We formalize this reasoning below.
Proposition EC.1. Bidder 1's best response to b 2 is a bid b 1 for which it holds that It is easy to see that this bid fulfills (EC.1), and it achieves an expected utility of 4 + 3 − 3ε 2 → 3.5. Now, let b 1 be any other bid for which (EC.1) does not hold. We show by case split that b 1 achieves strictly less expected utility than b * 1 . Case 1: b 1 ({1, 2}) < 6. The expected utility is at most 3: under the first realization of b 2 , the maximum possible utility (VCG payoff) is 6 for bundle {1} and 5 for bundle {1, 2}. Under the second realization of b 2 , b 1 does not win and the utility achieved is 0.

EC.2. BNE proofs for Example 1
Lemma EC.1. The strategy profiles given in Table 1 are a simple and complex BNE, respectively.
Proof. Bidder 3 has a dominant strategy to bid truthfully (Beck and Ott 2013). In both BNEs, bidder 2's expected utility is Any bid lower than 0.5 would reduce the probability of winning (and thus the utility) to 0. Bids strictly between 0.5 and 1 would increase the payment per Lemma EC.2. A bid of 1.0 or more would make bidder 2 win even when bidder 1 has low valuation, but in this case bidder 2's payment would be above her value, further decreasing total utility. In the case of a complex bid, a bundle bid on {1, 2} below 1 never wins and does not affect the payments, and at 1 or above it again leads to negative utility.
The argument for bidder 1 is identical for the simple BNE, except when the bid is at least 1, where we explicitly compute the expected utility to be Proof. It is easy to check that The main core constraint is the one imposed by the global bidder, requiring the joint payment of the locals to be at leastβ: The extra amount that the locals need to jointly pay on top of VCG is Even if the whole missing amount was paid by bidder i, the payment would be min(b i ({i}),β) which still falls inside i's IR constraint. The only other core constraints are the VCG constraints and a pair of constraints weaker than VCG. Thus, the point on the MRC closest to VCG is the one that increases payments from VCG evenly for both local bidders, and the VCG-nearest payment is: for 0 ≤ β <β and ε ≥ 0, then if both local bidders win, the VCG-nearest payment of local bidder i Proof. The core constraints involving bidder i on the blocking side are: where j is the other local bidder. We note that the first of these constraints (which corresponds to bidder j's VCG payment) is the only relevant one, since p 3 ≤ 0 by IR. If we set ε = 0, bidder ec4 e-companion to Bosshard and Seuken: Cost of Simple Bidding 1's second atomic bid could be removed without changing that first constraint, and thus we can apply Lemma EC.2 to establish the V CGN payments as claimed. To extend the result to ε > 0, note that both the shape of the core and the VCG payments are independent of ε, and thus the V CGN payments must also be independent of ε, since they are calculated only based on those two things.

EC.4. Proof of Theorem 4
The main difference between the proof of Theorems 3 and 4 is that we construct a more complicated auction family with more bidders, to make sure that the VCG-nearest payment behaves identically to first-price for bidder 1. This is achieved by moving the core far away from the VCG payments of other bidders, causing the projection onto the minimum revenue core to prioritize reducing the payments of those other bidders over that of bidder 1. Lemma EC.4 (the analogue of Lemma 1) must take into account many core constraints to characterize bidder 1's payments.
We adapt the family of auction instances F (m + 1) used in the previous section, as follows: Definition EC.1. Let m, L, σ, f (i), C and j be given as in Definition 10. Then, the auction F (m + 3) is given as follows: 1. The auction has 5 bidders and m + 3 goods.
6. The allocation rule is efficient. For ease of presentation, ties are broken in favor of bidder 1 when relevant. 7. The payment rule is VCG-nearest.
The bidders of this auction family and the relation of their bundles to each other are shown in Table EC.1. The first three bidders are in direct competition with bidder 4, and outbid her easily.
However, bidder 1 must now also outbid bidder 5, for which she needs an atomic bid on an active bundle of at least f (j).
The shape of the core is depicted in Figure EC.1, showing that bidder 1's payments are identical to first-price. The proof proceeds similarly to the first-price case.
Lemma EC.4. In the auction family F (m + 3), let b 1 be a bid for bidder 1, and let K * be the bundle with the highest active bid in b 1 . Furthermore, assume that bidder 1's bids on other bundles are not too high, i.e., ∀K = K * : b 1 (K) ≤ 1.
Then, bidder 1 wins bundle K * if b 1 (K * ) ≥ f (j), and her payment is (EC.14) Bundle bids made by different bidder types in auction family F (m + 3). Bidder 1 wins her desired good m + 1 whenever i ≥ j, i.e., she outbids the competitor. Bidder 1 can make additional bundle bids that include more goods, and those bids are active whenever they do not overlap with σ −1 (j).

Bidders
Goods Signalling Goods Prize Helper Goods 1 . . . m m + 1 m + 2 m + 3 Protagonist 1 f (i) Helper Bidders The core in auction family F (m + 3). Bidders 2 and 3 are symmetrical, so we show their joint payment on one axis. Since VCG-nearest minimizes L2 distance to VCG, it is easy to see that the optimal solution is to charge bidder 1 as much as the individual rationality constraint will allow.
f (i) Otherwise, bidder 1's allocated bundle does not include good m + 1.
Proof. Because bidder 1's bids are capped at 1, she can never win with a bid that is blocked by bidders 2,3 or 5. It is clear that bidders 2 and 3 always win their respective bundles, and bidder 4 never wins. It follows that good m + 1 is won by one of the remaining two bidders. Bidder 1 outbids bidder 5 exactly when she has an active bundle on which she bids above f (j).
Next, we derive the core constraints (and the VCG payments). There are 5 bidders and thus 2 5 − 1 = 31 core constraints. Since bidder 4 always loses, any constraint corresponding to blocking coalition L with 4 / ∈ L is dominated by the constraint of coalition L ∪ {4}. This accounts for 16 core constraints, leaving 15.
We next deal with the remaining constraints that involve bidder 5 on the left hand side. Let K be the bundle with the highest bid of bidder 1 (not necessarily active). Then, the 8 constraints are: p 1 + p 3 + p 5 ≥ C − C = 0, (EC.20) p 2 + p 3 + p 5 ≥ C − b 1 (K * ), (EC.21) Of these constraints, the first one is the VCG constraint, which dominates the 3rd and 4th constraints. The 7th and 8th constraints are dominated by constraints introduced below, and the rest are 0.
The remaining 7 core constraints are: (EC.29) The first of these is bidder 1's VCG constraint, which dominates the 4th and 5th.
In summary, the VCG payment vector is as follows: VCG 1 = f (j), (EC.30) VCG 2 = 0, (EC.31) VCG 3 = 0, (EC.32) VCG 4 = 0, (EC.33) (EC.34) and the relevant core constraints (other than VCG and IR constraints) are: p 2 + p 3 ≥ C − b 1 (K * ), (EC.35) p 1 + p 2 + p 3 ≥ C. (EC.36) We now derive the VCG-nearest payments. It is clear that bidder 5's VCG-nearest payment is her VCG payment, since any increase in payment does nothing to help fulfill any of the other constraints. Furthermore, the VCG-nearest payment must be symmetric for bidders 2 and 3, since e-companion to Bosshard and Seuken: Cost of Simple Bidding ec7 they only occur together in any constraint that is not dominated by another constraint. Any asymmetric payment vector in the core could be brought closer to VCG by balancing p 2 and p 3 , without violating any constraints. Therefore, the VCG-nearest payment can be characterized by a single parameter ∆ as follows: p 1 = ∆, (EC.37) p 4 = 0, (EC.40) The distance from VCG to p in terms of ∆ is (EC.42) Taking the derivative w.r.t. ∆, we get so the distance is minimized at ∆ = 2f (j) + C 3 .
(EC.44) When b 1 (K * ) is below this threshold, this payment is outside the core (due to bidder 1's IR constraint). In that case, the derivative is negative over the whole domain [0, b 1 (K * )], so the optimal solution is ∆ = b 1 (K * ).
For this particular auction, bidder 1's payment is a function of only j, independent of the identity of K * , just like in the first-price case. Computing bidder 1's simple and complex best response utilities is now completely analogous to what we did in the previous section.
Proof of Theorem 4. Consider the family of auctions F (m + 3). The total number of goods is m + 3 = θ(m). Using Lemmas EC.5 and EC.6, the ratio of the simple and complex best response utilities of bidder 1 is Θ 1 2 2 m 2 m 2 2 m = Θ 1 2 m . (EC.45)