{'fraction_non_alphanumeric': 0.04212173320320367, 'fraction_numerical': 0.01318337438614429, 'mean_word_length': 4.171192822238244, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Auctions Between Regret-Minimizing Agents

We analyze a scenario in which software agents implemented as regret-minimizing algorithms engage in a repeated auction on behalf of their users. We study first-price and second-price auctions, as well as their generalized versions (e.g., as those used for ad auctions). Using both theoretical analysis and simulations, we show that, surprisingly, in second-price auctions the players have incentives to misreport their true valuations to their own learning agents, while in the first-price auction it is a dominant strategy for all players to truthfully report their valuations to their agents.


Introduction
This paper deals with the following common type of scenario: several users engage in a repeated online auction, where each of them is assisted by a learning agent. A typical example is advertisers that compete for ad slots: typically, each of these advertisers enters his key parameters into some advertiser-facing website, and then this website's "agent" participates on the advertiser's behalf in a sequence of auctions for ad slots. Often, the auction's platform designer provides this agent as its advertiser-facing user interface. In cases where the platform's agent does not optimize sufficiently well for the advertiser (but rather, say, for the auctioneer), one would expect some other company to provide a better (for the advertiser) agent. A typical learning algorithm of this type will have at its core some regret-minimization algorithm [41,11], such as "multiplicative weights" (see [2] and references therein), "online gradient descent" [73], or some variant of fictitious play [14,63], such as "follow the perturbed leader" [39,47]. In particular, for ad auctions, there is empirical data showing that bids are largely consistent with no-regret learning [55,61].
While one's first intuition would be that an auction that is well designed for "regular" users would also work well for such agent-assisted users, it turns out that this is often not the case. In this paper we study how basic auction formats perform in terms of revenue and economic efficiency when software agents are doing the repeated bidding for the users. Specifically, we assume that each of the human bidders enters his valuation into a regret-minimizing software agent, and then the agent engages in a long sequence of auctions, attempting to maximize utility for the human user. We present both simulation results and theoretical analysis for several types of auctions: firstprice, second-price, and generalized first-and second-price auctions (for multiple ad slots). We study both classic regret-minimizing algorithms like multiplicative weights or follow the perturbed leader, as well as the consequences of the regret-minimization property itself.
Before presenting our results, let us say what exactly we are looking at when studying a long sequence of auctions played by software agents. While one might hope that there is some kind of convergence to fixed bids or distributions, it is well known that regret-minimization dynamics in many games need not converge [21,42,62,6,5]. For example, in our context, Figure 1a shows the  dynamics of a simulation of a generalized first-price auction for two slots where the two bidders have the same value. (Throughout the dynamics, both agents bid nearly the same value and thus only a single bid-line is visible.) As one may clearly see, the dynamics do not converge. What we wish to study is the thing that is important to the auctioneer and to the bidders: the long-term distribution of the tuple of bids. For example, Figure 1b shows a density map of the empirical pair of bids in this simulation. The empirical distribution of the tuple of bids determines the average winning frequencies and prices, which in turn determine the users' utilities and the auctioneer's revenue over the whole sequence of auctions. While there may not always be a theoretical guarantee that this empirical distribution converges either, one may still theoretically analyze properties that it may have in various cases as well as study it through simulations.
It is well known that in any game and for any regret-minimizing dynamics the distribution of tuples of bids approaches a "coarse correlated equilibrium" [39,41,72,11] (CCE), but as the space of CCEs is quite wide, this often does not suffice for an analysis of parameters of interest like the revenue or social welfare. For example, both for the first-and second-price auctions, there exist multiple (full information) CCEs, with different revenues and different social welfare [29]. One of the contributions of this work, presented in Section 4, is the identification of a refinement of the class of CCEs which we term co-undominated, to which alone a large class of regret-minimizing algorithms ("mean-based" ones, as defined in [13]) may converge in any game. In some cases this refinement suffices for an analysis, and for specific regret-minimization algorithms like multiplicative weights we may get an even finer analysis.
While there has been some work on the behavior of no-regret dynamics in auctions [22,7,30,23], we do not know of previous analysis of the average utilities and revenue of standard no-regret dynamics in standard auction formats. The closest paper conceptually to ours is [30], which manages to analyze these for no-regret dynamics that are preceded by a long pure exploration phase by all agents. Here we provide theoretical analysis and simulations for standard regret-minimization algorithms (without a pre-exploration phase), sometimes getting very different results. In a companion paper [48] we discuss the convergence of regret-minimizing agents and analyze the incentives of the users of such agents in a general game-theoretic setting.

Second-Price Auctions
To demonstrate the difficulty, let us start by looking at the easiest-to-analyze auction: a secondprice auction of a single item among two users. It is well known [71,28] that such an auction is (dominant-strategy) incentive compatible, i.e., that no bidder ever has any incentive to misreport his value to the auctioneer. Such truthful bidding will result in an efficient allocation where the player with the higher value wins and pays a price equal to the value of the lower player.
So now let us look at our scenario, where the two (human) users each report their value to a software agent (one agent for each player), and then the two (software) agents repeatedly engage in auctions, each agent attempting to optimize for its own user according to the value reported to it. (We assume that each auction in the sequence is for the same type of item, and that the values of the players for this type of item are fixed and additive over the items won.) What do we expect to happen in this case? Specifically: Is it in the best interest of users to report their true values to their agents? Will the player with the higher value always win? Will he pay a price equal to the value of the lower player? While positive answers to these three questions may seem to be trivially true, this turns out not to be the case, and only the second question gets a positive answer, while the answers to the first and third questions are negative. Theorem 1. For two bidders with values v > w with multiplicative-weights agents that engage in a sequence of second-price auctions on their behalf with discrete bid levels, the distribution of bids of the high player converges to uniform in the range (w, v], while the distribution of the bids of the low player converges to a distribution that has full support on [0, w]. In particular, in the limit, the high player always wins and pays an average price that is strictly less than the second price. Figure 2a shows the dynamics of multiplicative-weights learning agents in a second-price auction, where the values of the two agents are v = 1 and w = 0.5, and Figure 2b shows the long-term distribution of bids of each of the two agents that indeed behave as the theorem states: the highvalue agent always wins -except for a small number of auctions in the initial phase -and the average price he pays is about 0.27 (which is well below w). This is very much in contrast to the results of [30] that show that if we start with a sufficiently long pure exploration phase in which all agents bid uniformly, then dominant strategies are indeed reached. While the proved and observed lack of convergence to the dominant strategies may be surprising, the explanation is simple: while the dominant strategies do form a Nash equilibrium of the game, there are other (full-information) Nash equilibria of this game where the first player bids arbitrarily above the second price and the second player underbids arbitrarily. 1 Regret dynamics do not necessarily choose the former and so we do get some distribution over the "low revenue" equilibria.
The fact that the average price paid is well below the second price has immediate implications for a human user that has a value that lies between the average price in these dynamics and the actual second price. Such a user will gain from misreporting (exaggerating) his value to his own agent. In this example, a player with value, say, v = 0.4 that bids truthfully against a second player with value w = 0.5 will always lose, whereas misreporting his value as v = 1 will lead to these simulated dynamics (as in Figure 2), making him always win and achieve a strictly positive utility Figure 3: Dynamics of multiplicative-weights agents playing a repeated first-price auction, where agent 1 has value v and agent 2 has value w. The solid lines show running-window averages of the bids of each agent over a window of 100 auctions. on average. One can continue this analysis, viewing the reports of the users to their own agents as defining a "meta-game" between the users, and study the reached equilibrium. In a companion paper [48], we define and study this type of "meta-game" in a general context, and in Section 5 we analyze it for the second-price auction. 2 In Appendix A.1 we also demonstrate that these types of phenomena happen not only with multiplicative-weights algorithms, but also with other classic regret-minimization learning algorithms such as "follow the perturbed leader" (FTPL). We also show in Section 5 that the same phenomena happen in a generalized second-price (GSP) auction similar to the auctions used by search engines to sell ad slots in search result web pages. One may well wonder whether the advertiser-optimizing software supplied by the search engines indeed optimizes for the advertiser (in the sense of regret minimization), and whether the search engines lose revenue by using such a generalized second-price auction. 3

First-Price Auctions
We now turn our attention to basic first-price auctions (for a single good). What do we expect to happen in a repeated first-price auction between two regret-minimizing algorithms with values v ≥ w? Our basic intuition may be that they reach some kind of (full information) equilibrium of the first-price auction. It is well known that the only pure Nash equilibrium is where the low bidder bids his value (up to an ) and the high bidder bids more than that. This means that we would expect the high player to win (almost always) and pay (close to) the second price. Mixed Nash and correlated equilibria of the first-price auction are also known to yield the same outcome (namely, the high player always wins and pays the second price) [29].  (Figure 3b) between two multiplicative-weights algorithms that indeed converge to this outcome. 4 The missing element in this intuition is that regret-minimization dynamics need not converge to a Nash equilibrium (or even a correlated equilibrium) but may reach an arbitrary coarse correlated equilibrium, and it turns out that the first-price auction also has other coarse correlated equilibria [29], and in many of these coarse correlated equilibria the revenue is well below the 2 Spoiler: there are multiple possible equilibria in which the high player exaggerates his value as much as possible and the low player reports anything below a maximum value that is less than twice the true value of the high player. 3 Practically, as the number of advertisers may be large, with some distribution on the participants' values in each auction, the revenue loss should be smaller than in our simulations. Still, it is far from clear that this loss is small. 4 It should be noted, though, that this convergence in the symmetric case is very slow, perhaps the slowest that we have seen in our simulations. second price, and sometimes even the low player wins. While in [29] these coarse correlated equilibria were analyzed in a continuous setting, they also exist with simple discrete bidding levels. For example, consider an auction with v = w = 1; the reader may verify that the distribution that gives equal weights to the following four pairs of bids is a coarse correlated equilibrium: {(0, 0), (0.46, 0.46), (0.64, 0.64), (0.73, 0.73)}. It is true in general that for every CCE there exist some regret-minimizing algorithms that converge to it ( [54], see also [48]). Specifically, in our setting, consider agents that start by playing a sequence of bids that converge to the desired CCE (according to some fixed-in-advance schedule); each software agent proceeds this way as long as the other agent does, and in the case of any deviation reverts to a standard regret-minimizing algorithm. Thus, regret-minimizing agents need not converge to the "second-price outcome" in general. 5 We are able to prove, however, that a large class of regret-minimizing algorithms, defined in [13] and called "mean-based" algorithms, may converge only to this second-price outcome. Informally, algorithms from this class cannot put too much probability on actions that previously performed poorly.
Theorem 2. In a repeated first-price auction between two mean-based regret-minimizing agents with possible bid levels that are a discrete -grid, if the dynamics converge to any single distribution, then the high player wins with probability approaching 1 and pays an average price that converges to the second price (up to O( )).
Following our simulations, we conjecture that the assumption that the dynamics converge (a notion defined formally in Section 3) is not really required, at least for the multiplicative-weights algorithm.
As opposed to the case of the second-price auction where our results were in contrast to those with an additional pre-exploration phase [30], here we get the same type of result but for natural algorithms, without requiring this additional exploration phase.
A rather direct corollary of the fact that we get the second-price outcome is that from the point of view of the human users that report their values to their regret-minimizing agents, they observe a second-price auction. Since this auction is incentive compatible, we get that there is never any incentive for a user to misreport his value to his own agent (up to a vanishing loss in the long term). Recall that this is in contrast to the case of the second-price auction described above.

Generalized First-Price Auctions
We now proceed to the more complex generalized first-price (GFP) auction. Specifically, we focus our attention on the following first price two-slot auction: two "ad slots" are being sold in an auction to two bidders. The "top" ad slot has a "click-through rate" of 1, while the "bottom" ad slot has a click-through rate of 0.5. Each of the bidders has a value "per click" and so his value for the bottom slot is exactly half of his value for the top slot.
Our first result is the analysis of the (mixed) Nash equilibrium of this game. While there has been much work on equilibria in related auction settings (e.g., [19,27,29,44]), to the best of our knowledge, this paper is the first to successfully analyze the Nash equilibrium of a generalized first-price auction.
Theorem 3. Assume w.l.o.g. that v ≥ w. In the unique Nash equilibrium of the two-slot auction described above, the players mix their bids x, y, respectively, according to the following cumulative density functions with support [0, w/2].
The expected payoffs are u 1 = v/2 + (v − w)(1 − ln(2)), and u 2 = w/2. 5 Note that if one considers only dynamics of algorithms that minimize conditional ("internal") regret which are known to approach the polytope of correlated equilibria [31,32,41,11] (rather than minimizing unconditional ("external") regret), then, since correlated equilibria of the first-price auction yield the second-price outcome [29], the empirical average of such joint dynamics would approach the second-price outcome.  Running an actual simulation of multiplicative-weights agents participating in such an auction with v = w = 1 shows that the agents do not get even close to any uncoupled mixing profile as this Nash equilibrium. Figure 1a shows the dynamics of a (typical) simulation. Throughout the dynamics, both agents bid nearly the same and thus only a single bid-line is visible. Figure 1b shows the density of the empirical pair of bids. The lack of convergence to a Nash equilibrium is not surprising since we only expect to reach a CCE of the game, not necessarily the Nash equilibrium.
Most of Section 7 is devoted to studying the equilibrium that is actually reached by multiplicativeweights algorithms. We observe via simulations that the bid distribution of the high bidder agrees with the computed distribution of the Nash equilibrium F (x) = x w−x , but that the other player's bid is strongly correlated with the high player's bid (rather than independent of it as in the Nash equilibrium). In fact, we see that in the achieved equilibrium the low player either bids (almost) identically to the first player or bids (close to) 0, where the probability of the latter is proportional to the ratio between the high and low bids. As we show in Section 7, our closed-form formulas agree well with the simulation results, but we do not have a complete theoretical analysis of this and such an analysis seems to be difficult.
The closed-form formulas do allow us, however, to analytically compute the achieved winning probabilities and prices in this auction and thus also the users' payoffs from different reports in the "meta-game" where the users report their values to their respective agents. In particular, we see that even with true reports, the users' average utilities are (slightly) higher than in the Nash equilibrium, implying that their agents achieved some sort of implicit collusion. Demonstrating an analysis of strategic reports of the users to their agents, Figures 4a and 4b show the utilities that users with a true value of 1 would get from strategically reporting different values to their own agent as a reply to two fixed reports (0.54 and 2) 6 of the other user. We first see the very close agreement of the closed-form formulas with the actual simulation results. Second, these results demonstrate the equilibrium in the meta-game where one bidder exaggerates his bid as much as possible, while the other one underbids somewhat. Calculating the utilities of the players in this meta-game equilibrium reveals that severe implicit collusion occurs, where the users capture 89% of the total welfare, leaving only 11% to the auctioneer (in contrast to 33% to the auctioneer in the Nash equilibrium and 31% to the auctioneer in the equilibrium reached for truthful reports).

Further Related Work
Regret minimization in repeated strategic interactions and in online decision problems has been extensively studied in the literatures of game theory, machine learning, and optimization. Early regret-minimizing algorithms were related to the notion of fictitious play [14,63] (a.k.a. "follow the leader"), which in its basic form does not guarantee low regret, but whose smoothed variants, such as "follow the perturbed leader" (FTPL) [39,46,47,37] or "follow the regularized leader" (FTRL) [67], are known to guarantee adversarial regret of O( √ T ) in T decisions. Another common approach to regret minimization is the "multiplicative-weights" algorithm which has been developed and studied in many variants (see [2] and references therein). Similar ideas of regret minimization apply both in settings in which players observe full feedback on their past actions and forgone actions (the experts-advice setting) and in the multi-armed bandit setting, where feedback is available at every step only for the action that was selected at that step, and in which variants of multiplicative weights (such as EXP3 [3,50]) and other algorithms have been developed.
Regret minimization has also been widely studied in auctions, with two prominent lines of work focusing on the econometric problem of inferring structural parameters of the utilities of the bidders [55,58,59,35], and on the price of anarchy in classic auction formats and in combinatorial auctions when the bidders are no-regret learners [10,64,68,16,43,22,65]. Other works deal with the design of automated bidding algorithms for auctions with more complex factors, such as budget constraints [7,24], or the utilization of regret minimization ideas for optimizing reserve prices [66,53,17], and in [61,1] regret-minimization algorithms were used to predict bidder behavior. Importantly, [55,61] provide concrete empirical evidence from large ad auction datasets showing that actual bidder behavior is consistent with no-regret learning.
The standard first-price and second-price auctions have been widely studied in auction theory [49,52]. Their generalized versions for multiple items have been studied and applied in ad auctions (also called "position auctions") [28,70,12,45]. Most prior works mainly discussed the Nash equilibria of the auctions or their best-response dynamics, and did not study the dynamics when players use regret-minimization algorithms. One notable exception is [30]; however, as discussed in the introduction, they analyze a different setting in which the actual play of the agents is preceded by a pure exploration phase in which all bidders bid uniformly, which leads to different convergence results than those we show for standard interaction between the algorithms.
Finally, there is a growing body of work studying various aspects of interactions between strategic players and learning algorithms, including learning from strategic data [15,40,20,26,38,51,36], Stackelberg games [34,9], security games [57,56,33], recommendation systems [69,8], and optimization against regret-minimizing opponents [25,13]. Notably, we use the formalism of meanbased learning algorithms defined in [13], who also study an auction setting. Their setting, however, is basically different from ours. They consider a game in which a strategic seller seeks revenuemaximizing auction strategies against a regret-minimizing buyer, while we consider fixed auction rules and study the interactions between regret-minimizing buyers and the strategic considerations of their users. Lastly, in a companion paper [48], we formalize a "meta-game" model for general strategic settings in which human users select parameters to input into their learning agents that play a repeated game on their behalf, and we analyze this model for simple games with general regret-minimizing agents. Our discussion in the present paper on the incentives of players to misreport their valuation to their own bidding agents is directly related to this meta-game model.

Preliminaries
We consider repeated auction settings in which the same group of bidding agents repeatedly play an auction game with a fixed auction rule and the same set of items are being sold at each repetition of the game. The valuation of every agent, assigned to it by its user, is constant throughout the dynamics, and the utilities are additive. I.e., a bidder with value v for an item who wins k such items has total value kv. Player values and bids are assumed to be on an -grid, i.e., to be multiples of a minimum value > 0 (e.g., 1 cent). We assume that agents cannot overbid, and in all auction formats if agents place equal bids, ties are broken uniformly at random.
First-price and second-price auctions are defined in the standard way: the auction sells a single item, and b 1 > b 2 > ... > b n denotes the bids of n bidders. Bidder s ∈ [n] with the highest bid (bidding b 1 ) wins the auction, and pays a price p to the auctioneer. In the first-price auction the winner pays his bid: p = b 1 , and in the second-price auction the winner pays the amount of the next highest bid: p = b 2 . The utility for player s with value v s is then v s − p when winning the item, and zero otherwise. For further details on these auction formats see, e.g., [60]. Generalized auctions for multiple items are defined in the relevant sections.
We study agents that use regret-minimization algorithms. The regret of player i at time T , given a history of bids (b 1 , ..., b T ), is defined as the difference between the optimal utility from using a fixed bid in hindsight and the actual utility: i is the bid of player i at time t and b t −i denotes the bids of the other players at time t. As usual, regret-minimization algorithms are stochastic, and whenever we talk about the limit behavior, we consider a sequence of algorithms 7 with T → ∞ and with probability approaching 1. An agent i is said to be "regret-minimizing" if R T i /T → 0 almost surely as T → ∞. In our simulations we mainly present the multiplicative-weights algorithm, as defined in [2]. The results apply equally both to the Hedge algorithm (often also referred to as multiplicative weights in the literature) and to the linear version of the algorithm. Appendix A presents simulations with additional algorithms.
We use the following notations to describe the empirical dynamics of the agents' bids. Denote by ∆ the space of probability distributions over bid tuples in an auction with discrete bid levels. We use p T t ∈ ∆ to denote the empirical distribution of bids after t rounds in a sequence of T ≥ t auctions, and denote by p T t (b) the empirical frequency of a bid tuple b after round t. When we discuss convergence of the dynamics we consider the following definition: Definition 1. The dynamics "converge to a distribution" p ∈ ∆ if for every > 0 there exists T 0 ( ) s.t. for every T > T 0 w.p. at least 1 − it holds that for every T < t ≤ T , |p T t − p| < . Intuitively, this means that after a sufficiently long time, the time-average distribution stabilizes and remains close to a stationary distribution. Notice that the convergence of the cumulative empirical distribution to a joint distribution does not imply the convergence of the probability of play of any single agent to a distribution on its own actions 8 (a stronger notion of convergence studied, e.g., in [6,30,23]). See also [48] for a discussion of yet weaker notions of convergence.

Co-Undominated Coarse Equilibria
In this section we define a refinement of the concept of coarse correlated equilibria, which we call "co-undominated CCE." For simplicity, the definitions are given for two-player games; their generalization is straightforward. Intuitively, those are CCEs in which players do not use strategies that are weakly dominated relative to the distributions of the opponents. Formally: Definition 2. Let A, B denote subsets of the action spaces of the two players in a two-player game. Action i ∈ A of player 1 is called weakly-dominated-in-B by action i of player 1 if: ∀j ∈ B : u 1 (i, j) ≤ u 1 (i , j), and: ∃j ∈ B : u 1 (i, j) < u 1 (i , j). 7 This follows most of the literature that looks at regret-minimizing algorithms with a fixed horizon T and looks at a sequence of such algorithms as T → ∞. Typically, and specifically for the case of multiplicative weights, the "update parameter" depends on T but remains fixed over all time steps 1 ≤ t ≤ T of the algorithm with horizon T . While it is alternatively possible to consider a single regret-minimizing algorithm that has an infinite horizon and uses a decreasing update parameter [4,18], such a definition does not "play well" with the notion of mean-based algorithms [13] that we use below, and so we do not use it. 8 Notice also that convergence to a distribution p does allow for the existence of an unlimited number of accumulation points (other than p), as long as all these points together have zero probability in the limit. However, the impact of such accumulation points on the average utilities and revenue is vanishing in the long run. Definition 3. Let p i,j be a CCE of a (finite) two-player game with action spaces I, J. Denote its support (A, B) by A = {i ∈ I|∃j ∈ J with p i,j > 0} and B = {j ∈ J|∃i ∈ I with p i,j > 0} (A is a subset of I and B is a subset of J). A CCE is called co-undominated if no strategy in its support is weakly dominated relative to the support of the other player, i.e., if for every i ∈ A, and every i ∈ I, action i is not weakly-dominated-in-B by i , and similarly for B.
We show that these types of equilibria are closely connected to a family of learning algorithms called "mean-based." For completeness, we cite their definition ( [13], Definition 2.1): Definition 4. (Mean-based learning algorithm [13]). Let σ i,t = t t =1 u i,t , where u i,t is the utility of action i at time t. An algorithm for the experts problem or the multi-armed bandits problem is γ(T )-mean-based if it is the case that whenever σ i,t < σ j,t − γ(T )T , then the probability that the algorithm pulls arm i in round t is at most γ(T ). We say an algorithm is mean-based if it is γ(T )-mean-based for some γ(T ) = o(1).
The above definition from [13] considers a fixed value T . To clarify the definition further when considering a series of T -values and the limit T → ∞, we say that an algorithm family A T , parametrized by T , is mean-based if there exists a series (γ(T )) ∞ T =1 such that γ(T ) → 0 as T → ∞, and each algorithm in the series (A T ) ∞ T =1 is γ(T )-mean-based. The following lemma connects between mean-based regret-minimization algorithms and coundominated CCEs. This result is general for any game (not only auctions), and will be useful for our analysis in the following sections. Lemma 1. Consider the dynamics of any mean-based regret-minimizing agents playing a repeated finite two-player game. If the dynamics converge to a distribution p, then p is a co-undominated CCE.
Proof. Consider any finite two-player game played repeatedly by two mean-based regret-minimizing agents, and assume that the dynamics converge to a distribution p ∈ ∆. First, as is well known, since the agents are minimizing regret, p must be a CCE (otherwise some agent must remain with positive average regret in the limit). Next, assume by way of contradiction that action i of player 1 (w.l.o.g.) is weakly dominated by action i of player 1 in the support of player 2, and that i is in the support of player 1. Let us use u(i, j) to denote the utility for player 1 when player 1 bids i and player 2 bids j, and u t (i) to denote the utility for player 1 from using the bid i at time t, given the actual (empirical) action of player 2 at time t. Thus, for every action j of player 2 with Pr b∼p (b 2 = j) > 0 it holds that u(i, j) ≤ u(i , j), and there exists an action j 0 of player 2 with Pr b∼p (b 2 = j 0 ) = q 0 > 0 such that u(i, j 0 ) < u(i , j 0 ), and Pr b∼p (b 1 = i) = p 0 > 0.
To bound ∆ T t from below, let us consider the case where |p T t − p| = 2 and all the difference between the two distribution vectors in concentrated on action profiles in which the dominating action i has zero utility and the dominated action i has a utility of 1. Thus ∆ T t > (1 − )q 0 δt − t, and therefore . For every t > T 1 = √ · T with probability more than 1 − 2 , it holds that p T t (i) < 2 √ .
Proof : By claim 1 above, for every t > T , in the event that |p T t − p| ≤ it holds that ∆ T t > t ≥ 2 T , and thus from the mean-based property of player 1, it follows that the probability that action i is chosen at time t + 1 is less than γ(T ) < 2 . From the convergence assumption, this holds with probability at least 1 − for any t > T . Thus, with high probability (at least 1 − ) the empirical average number of times that action i is chosen in rounds T, ..., t is not far from its expectation of 2 , which is less than . To bound p T t (i) from above, consider the "worst case" where p T T (i) = 1 (until time T ). Thus, for t > T 1 , with probability more than 1 − 2 it holds that We thus have by claim 2 that with probability more than 1 − 2 , p T T (i) < 2 √ , and since we have that Pr |p T T − p| > > 1 − 2 , in contradiction to the convergence assumption. Therefore, the dominated action i cannot be in the support of player 1. This holds for the other player as well, and thus the distribution p must be co-undominated.
Remark: Notice that this argument can be extended also to the case where the dynamics converge to p with a strictly positive probability that may be less than 1.

Second-Price and GSP Auctions
We consider agents that play repeated second-price auctions (for a single item) and GSP auctions (for multiple items; see, e.g., [28]). Our analysis starts with the simple second-price auction, which is known to be dominant-strategy incentive compatible; i.e., it is a dominant strategy for all players to bid their true values. We show that in the setting where regret-minimizing agents play the auction on behalf of their users, the outcomes are different from this truthful equilibrium.
Specifically, Theorem 1 shows that when the auction is played between two multiplicativeweights agents, in the limit, although the high player always wins the auction (as in the truthful equilibrium), he pays a price that is strictly less than the second price. Before proceeding to the proof, we consider the following technical restatement of the theorem.
Theorem. (Restatement of Theorem 1): In the repeated second-price auction with discrete bid levels that are multiples of and players using multiplicative-weights algorithms with values v > w, in the limit the dynamics converge to a joint distribution in which for the "high player" with value Proof. First, observe that for the low player, bidding w weakly dominates all other bids, and so the probability assigned to this bid does not decrease in any update of the weights. Thus, the probability that the low player bids exactly w is at least 9 1/(w/ + 1).
Since the low player bids w at least 1/(w/ + 1) of the time (with high probability), every bid that is less than w of player 1 loses the auction at this frequency, while an alternative bid of w + always wins, yielding positive utility. Thus, every O(w/η ) steps the probability that the high player bids w or less decreases at least by a constant factor.
Hence, we can deduce that the expected number of times that the high player bids below w is a constant, since it is bounded by the sum of a geometric series. In light of this observation, we can look at the bid distribution of the low player. Whenever the high player bids above w, the weights of all bids do not change (since all bids would yield zero utility). The weights are updated only in those cases where the high player bids below w. Since this happens only a finite number of times, the ratio of probabilities between any two bids of the low player remains bounded by a constant. Thus, every bid of the low player remains with positive probability in the limit (and at any time). Since whenever a bid j of the low player would win the auction, every bid k > j would also win the auction, it follows that P r Finally, since all bids above w have the same utility at every step (as the payment is the second price), all weight updates of every bid above w are exactly equal, and so the distribution of bids of the high player in the limit is uniform between w + and v.  In addition to the above result that explicitly shows that dynamics of multiplicative-weights agents converge to these forms of distributions, our analysis from the previous section allows us to show that for two agents implemented as any mean-based regret minimization algorithms, whenever the dynamics of the agents converge to a coarse correlated equilibrium, it must be an equilibrium in which the agent with the higher valuation always wins.

Lemma 2.
In the repeated single-item second-price auction with discrete bid levels that are multiples of and two players with values v > w, in any co-undominated CCE the player with the higher valuation v always wins the auction.
Proof. Denote the high player with value v as player 1 and the low player with value w as player 2. Assume that the players are in a CCE in which there is positive probability that player 1 loses the auction. Thus, there exist i 0 , j 0 such that 0 = u 1 (i 0 , j 0 ) < u 1 (w + , j 0 ) = v − j 0 . If for all j ∈ B (B being the support of player 2) it holds that u 1 (i 0 , j) ≤ u 1 (w + , j), then w + weakly dominates i 0 , leading to a contradiction with the co-undominated CCE condition. If we assume the contrary, we have that there exists j ∈ B such that u 1 (i 0 , j) > u 1 (w + , j). This is impossible since bidding w + wins the auction and gives utility v − j, while any other bid gives either the same utility or zero. Therefore, in any co-undominated CCE the high player always wins.
These theoretical results are consistent with simulation results, as can be seen in Figure 2 that shows the bid dynamics of two multiplicative-weights agents playing a repeated second-price auction for a single item. The first player has value 1 for the item and the second player has value 0.5. In the very beginning, bids are close to uniform and there are some auctions in which player 2 bids higher than player 1 and wins the item with positive utility. However, after a short learning phase player 1 learns to bid higher than the value 0.5 of player 2 and to always win the auction. Figure 2b shows the empirical bid densities of the two players. It can be seen that the high player bids uniformly between his value and the value of the low player. The basic reason for this is that under the second-price payment rule, all these bids are equivalent. The bids of player 2 are not uniform, but have more weight on higher bids. This is despite the fact that in the long-term dynamics player 2 always loses, getting zero utility, and so all his bids should also be equivalent. The reason for this form of the distribution is that the multiplicative-weights algorithm (and other algorithms like FTPL) keep a "memory" of the history of play: in the initial phase there was a finite number of auctions in which player 2 got positive utility. These winnings were associated with higher bids. Thus, in the initial phase higher bids get higher weight, and after this phase all bids yield exactly the same feedback (of zero utility), and therefore the distribution remains skewed toward the higher bids. This intuition is formalized in the proof of Theorem 1 above. Figure 5a shows a very similar picture also in the generalized second-price auction with multiple items. Interestingly, there is a narrow bid range (centered at the bid 0.4 in Figure 5b) in which the bid supports of both bidders overlap, but, as can be seen by the distribution of bid differences at all times (in green), the bids are correlated such that despite the overlapping bid ranges, the player with the higher valuation still almost always wins the auction. Now let us consider the point of view of the human users that report their values to their regretminimizing agents playing a repeated second-price auction on their behalf. Although this auction is known to be incentive compatible, in light of the results shown above on the dynamics of the agents, from the point of view of the human users the second-price outcomes are not obtained, and thus these users do not observe a second-price auction. Hence, in the repeated second-price auction that is implemented with regret-minimizing agents it can be beneficial for players to misreport their true valuations.
To demonstrate this, let us return to our example from the introduction in which two players compete in a repeated second-price auction using multiplicative-weights agents. The first player has value 0.4 and the second player has value 0.5. Figure 2c shows the expected utility for player 1 over a period of 50,000 auctions from inputting different values v into his agent. It can be seen that when v is sufficiently high above the value 0.5 of player 2, the utility of player 1 is positive and increases for yet higher values; i.e., for a fixed value of the low player, the high player pays a lower price as he declares a higher value. For very high values of the high player, the high player's agent almost never bids below the low value, and so the distribution of bids of the low player remains very close to uniform. As the high declaration decreases, the probability that the high player's agent bids below the low value increases, and this is what drives the increase in the probability of the low player's agent bidding higher values.
It follows that the best reply of the high player in the meta-game is always as high a declaration as possible, as long as the low player's declaration is below a maximum value that is less than twice the true value of the high player, and under which the dynamics lead to a positive average utility for the high player. The low player (almost) always loses and so all declarations that cause him to lose are equivalent. These can lie anywhere between 0 and the declaration of the high player. The truthful declaration is certainly one possible best reply in the full information game, but notice that there is little to suggest selecting it specifically since it is a best reply only if it leads to a loss, and is in no way a dominant strategy if the value of the other player is not known. We thus can identify a whole set of possible equilibria of the meta-game, but do not see a natural way to select one of these as the outcome of user behavior in the meta-game. Notice that the revenue is close to half of the low declared value (when the high declaration is very high) and thus we cannot give a reasonable prediction of the revenue in equilibrium.

First-Price Auctions
In this section we present our analysis of first-price auctions leading to Theorem 2. We begin by showing that in the first-price auction in any co-undominated CCE, all bids of the high-value player are close to the second price. This is formalized in the following lemma.
Lemma 3. For the first-price auction with discrete bid levels that are multiples of with player values v ≥ w > 2 , in any co-undominated CCE, the support of the "high player" with value v is in [w − 2 , ..., w + ]. Additionally, when is small compared to the difference in values v − w, the player with the higher value v almost always wins the auction.
To prove Lemma 3, we start by analyzing the symmetric case of bidders with equal values, which is technically slightly different. The proof of the next lemma is deferred to Appendix B. We now proceed to prove Lemma 3.
Proof. (Lemma 3): Denote the value of player 1 as v and the value of player 2 as w and assume w.l.o.g. that v ≥ w. Lemma 4 deals with the symmetric case v = w > 2 . Here we will show that when v > w > 2 , bids that are not in [w − 2 , ..., w + ] cannot be in the support of player 1.
First, for any support B of player 2, any bid b > w + is strictly dominated for player 1 by bidding w + . Thus, in any co-undominated CCE, the high player does not bid above w + .
Next, let b 1 , b 2 be the lowest bids of the players in the support and let B 1 , B 2 be the highest bids in the support, and assume that b 1 < w − 2 . We will consider the following cases: Here player 1 plays a pure strategy and so the CCE condition implies that player 2 must best-reply to it. Thus, for b 1 = B 1 < w − 2 , we must have b 2 = B 2 = b 1 + , which is not an equilibrium, since player 1 would then always lose and thus prefers using a fixed bid w − 2 . Therefore, it must be that b 1 < B 1 .
Here, if b 1 = b 2 < w − 2 then b 1 is strictly dominated by b 1 + (b 1 loses unless player 2 bids b 2 , in which case player 1's utility is (v − b 1 )/2 due to the tie, but then v − (b 1 + ), which this player gets from bidding b 1 + , is better). Thus, we have b 1 = b 2 ≥ w − 2 .
Case III: b 1 < b 2 . In this case b 1 always loses and always gets a utility of 0. Thus, due to the co-undominated CCE condition, player 1 must get zero utility for every bid in his support and every bid in player 2's support, and so he gets zero utility. This leads to a contradiction since player 1 can bid w and have positive utility in every auction.
Here b 2 always loses and always gets zero utility. Thus, due to the co-undominated CCE condition, player 2 must get zero utility for every bid in the support. However, player 2 can bid w−2 and have a positive utility of 2 in every auction in which player 1 bids b 1 , a contradiction.
Hence, the support of the high player must be in [w − 2 , ..., w + ]. Next, let us show that the high player (with value v) wins the auction with probability approaching 1 when the grid step is small compared to the differences in values. Assume that there is positive probability p that player 1 bids a and player 2 bids b and a ≤ b. We know that w − 2 ≤ b ≤ w, and w − 2 ≤ a ≤ w + , and denote δ = v − w > 2 . On the one hand, the expected utility for player 1 from bidding a in a sequence of T auctions is at most T · (1 − p)(v − w + ). On the other hand, the utility for player 1 from placing a fixed bid of w + , which always wins the auction, is T · (v − w − ). Thus, from the CCE condition it follows that p ≤ 2 v−w+ , and therefore p approaches zero as /δ approaches zero, i.e., as the grid becomes small compared to the difference in values.
Using this result together with Lemma 1 that connects between mean-based learning agents and co-undominated CCEs, we can readily prove Theorem 2.
Proof. (Theorem 2): Consider a first-price auction with discrete bid levels that are multiples of with players with values v ≥ w > 2 that repeatedly play the auction using mean-based regret minimization algorithms. By Lemma 1, if the dynamics converge to a CCE, then it must be a co-undominated CCE. By Lemma 3, in the first price auction in such an equilibrium both players bid close to the low value w (up to 2 ), and the player with the higher value v wins with probability approaching 1 as /(v − w) → 0.

Generalized First-Price Auctions
We analyze GFP auctions where two "ad slots" are being sold to two bidders. The "top" ad slot has a "click-through rate" of 1, while the "bottom" ad slot has a click-through rate of 0.5. That is, a bidder with value v that wins the top slot and pays p (per click) gets a utility of v − p, and the bidder that gets the bottom slot and pays p (per click) gets a utility of v/2 − p/2. The auction uses the first-price rule: the bidder that bids highest gets the top slot and the low bidder gets the bottom slot, and each pays their bid per click. That is, if the first player has value v and bids x while the second player has value w and bids y, then the utility of the first player is v − x if x > y and is (v − x)/2 if x < y, while the utility of the second player is w − y if y > x and is (w − y)/2 if y < x. (In the case of a tie, x = y, let us assume that we toss a coin for the top slot, in which case the utility of the first bidder is 3 · (v − x)/4, and the utility of the second bidder is 3 · (w − y)/4.) We start with the proof of Theorem 3 on the Nash equilibrium of the GFP auction, and then proceed to analyze the empirically observed distributions obtained by the agents.

Nash Equilibrium
Proof. (Theorem 3): Denote the bid density function of player 1 in a Nash equilibrium by f (x) and the bid density function of player 2 in a Nash equilibrium by g(y), and denote the respective cumulative density functions by F (x) and G(y). First, observe that every bid y > w/2 of the second player is dominated by y = 0. Therefore, the support of the distributions f (x), g(y) is in 10 [0, w/2]. Next, the expected utility to player 1 from bid x, assuming that player 2 plays according to g(y), where the first term is the expected payoff from winning the first slot in the auction, and the second term is the expected payoff from getting the second slot. The expected utility to player 2 from bid y, assuming that player 1 plays according to In equilibrium the derivatives of the utilities must satisfy With another derivative, we obtain differential equations for f and g. We also replace the variable names by their original notations: The solution to these equations is of the form f (x) = c1 (w−x) 2 , g(y) = c2 (v−y) 2 , where c 1 , c 2 are constants that depend on the boundary conditions. The normalization constraint yields the unique The integrals of these density functions lead to the cumulative densities stated in the theorem.
The utilities to the two players, with values v to player 1 and w to player 2 such that v ≥ w, in the Nash equilibrium are then given by the following integrals. u N E

Coarse Correlated Equilibria
As discussed in the introduction, the dynamics of multiplicative-weights agents with equal values v = w = 1 yield, on average, the Nash equilibrium distribution as stated in Theorem 3; however, unlike in the mixed equilibrium, here bids are highly correlated. Throughout the dynamics, as shown in Figure 1a, both agents bid nearly the same, and the bids do not converge. The lack of convergence to a Nash equilibrium is not surprising since we expect to reach only a CCE of the game, and not necessarily the Nash equilibrium. So let us analyze the empirically selected CCE. The fact that the empirical bids are all concentrated on the diagonal may be understood by considering best-reply dynamics, which may be viewed as a primitive ancestor of our no-regret dynamics. The best reply to a bid x is always either x + , or 0 if x is more than half the player's value. Thus, in such dynamics we will tend to see bids that progress like (x, x + , x + 2 , x + 3 , ...) until x reaches w/2, at which point the second player will resort to bidding 0, and then the bids (c) Gains from manipulation by the high-agent user with a true value of 1. Figure 6: Generalized first-price auctions played by multiplicative-weights agents with high value v ≥ 1 (for agent 1) and low value w = 1 (for agent 2). will rise gradually again. This is indeed exactly the dynamics that we see in Figure 1a. Looking at the empirical distribution of x when v = w = 1, it seems to be identical to the distribution 1−x derived for the Nash equilibrium. Indeed, we prove that the diagonal distribution (x, x) where x is thus distributed is a CCE of the auction with v = w = 1. The formal statement of this result is deferred to Appendix C. We should note, though, that the above F is not the only distribution yielding a CCE and that we cannot theoretically justify why this particular one is the empirical distribution observed. One should also note that the utility obtained by the two agents in this CCE is 3/4 · ln(2) ∼ = 0.52, which is (slightly) higher than the utility of 0.5 that two players would obtain in the Nash equilibrium. We might view this as a weak form of implicit collusion between the agents in the auction.
If one looks at no-regret dynamics when v = w, then the empirical distribution obtained is a bit more complex: not only do we see bids on the diagonal, but we also see bids where the low agent bids 0. This is shown in Figure 6a for the case v = 2, w = 1. That is, in most rounds of the repeated auction either the two agents place nearly equal bids or the low agent bids zero. We call such distributions "nearly diagonal." Empirically we see that the distribution on x (the bid of the agent with high value v) remains similar to the "Nash equilibrium-derived" distribution F (x) = x w−x , while the probability of bidding on the diagonal, i.e., of the low agent bidding y = x rather than y = 0, decreases like w/v as v increases relative to w. Figure 6b depicts the empirical fraction of non-zero bids placed by the low agent as a function of the declared value v of agent 1 when w = 1; the dotted line in the figure shows the comparison to the function 1/v.
We thus consider the following to be our "prediction" of the outcome of the agent dynamics. First a value x is chosen according to the cumulative distribution F (x) = x w−x and then the high agent (the one with value v, where v ≥ w) bids x and the low agent bids x with probability w/v and bids 0 otherwise. We emphasize that we do not have a theoretical justification for this prediction and leave the rigorous derivation of the distribution selected by the agent dynamics as an open problem. Figure 6c compares the empirical utilities of the players to those implied by the Nash equilibrium and to those implied by our prediction. As we see, while the observed empirical utilities are very far from those in the Nash equilibrium, they agree with our prediction quite well.

Equilibria of the Meta-game
We now proceed to study the "meta-game" faced by the users, each of whom needs to report his value to his own multiplicative-weights regret-minimization algorithm. Our analysis concerns the case where the true valuations of the players are 1 and 1 and their declarations to their agents are v and w. Assuming that the agents reach the "equilibrium" predicted by our nearly diagonal distribution model, we can calculate the players' utilities. Our analysis allows us then to identify the ( -)Nash equilibria of the meta-game. The formal details of this analysis are deferred to Appendix C. In the equilibrium of the meta-game, the high player declares an arbitrarily high value v and the low player declares a fixed value w = 1/(6 · (1 − ln(2)) ∼ = 0.54, and the utilities that they get, respectively, in this equilibrium are 5/6 − O(1/v) and 1/2 + O(1/v). (If there exists a maximum allowed value for v this is exactly an equilibrium, and otherwise it is an -equilibrium, where = O(1/v).) The interesting point of this analysis is that the two players are locked in a type of hawk-dove game: there are two possible equilibrium points depending on which player is the high bidder and which is the low one. Each player prefers to be the high player and to let the other player be the low player. However, if they both declare high values, then they both suffer and get negative utility.
This theoretically predicted behavior is indeed borne out in simulations. Figure 4a shows the average payoffs of the two players when player 1 uses a fixed "high" declaration v = 2 as a function of the declaration w of the other player. Figure 4b shows the payoffs when player 2 uses the equilibrium declaration w = 1/(6 · (1 − ln(2))) as a function of the declaration v of player 1. It can be seen that the nearly diagonal distribution model is consistent with the empirical payoffs, and that the predicted equilibrium of the meta-game is indeed empirically an equilibrium as the best replies of the players behave as predicted: the best-reply of the "low player" is obtained at w ∼ = 0.54 (marked in red in Figure 4a), and the payoff of the "high player" is increasing in the declaration v, approaching 5/6 ∼ = 0.83 for high declaration values (Figure 4b). These results are robust for different player parameters and several other learning algorithms such as linear or exponential multiplicative weights, FTPL, and FTPL with a recency bias.
To summarize, we succeeded to identify (and empirically validate) the outcome of dynamics of multiplicative-weights agents in this auction with any two values. This allowed us to analyze the equilibrium in the meta-game induced on users that have identical true values. We found two such equilibria where, in each of them, one player takes the role of the high player, declaring the maximum possible value to his agent, and the other player declares a value of 0.54 fraction of the true value. Significantly, in each of these equilibrium points the users capture 8/9 ∼ = 89% of the welfare, leaving only 11% to the auctioneer. This outcome exhibits significant implied collusion between the users and, in fact, suggests that such an auction platform encourages collusion, probably against the interests of the platform designer.

A Additional Simulations
Our simulations show similar convergence results for different variants of multiplicative weights and FTPL algorithms. The following figures show the bid dynamics in second-price and first-price auctions when the first agent has a value of v = 1 and the second agent has a value of 0.5, for the Hedge algorithm and FTPL. We also look at simulations with a variant of FTPL with a recency bias that uses a geometric discount on the (perturbed) history of play. In all these different dynamics, in the second-price auction the high player always wins the auction and pays a price that is, on average, well below the actual second price of 0.5, and in the first-price auction the high player always wins and pays the second price.

B First-Price Auctions
Proof. (Lemma 4): Let b 1 , b 2 be the lowest bids of the players in the support and let B 1 , B 2 be the highest bids in the support. Consider the following cases: Case I: b 1 = B 1 (or symmetrically b 2 = B 2 ). In this case player 1 plays a pure strategy and so the CCE condition implies that the second player must best-reply to it. Therefore unless Here, if b 1 = b 2 < v − 2 then b 1 is strictly dominated by b 1 + (b 1 loses unless player 2 bids b 2 , in which case player 1's utility is (v − b 1 )/2 due to the tie, but then v − (b 1 + ), which this player gets from bidding b 1 + , is better).
Case III: w.l.o.g. b 1 < b 2 . Then b 1 always loses and always gets utility 0. Thus, due to the coundominated CCE condition, player 1 must get 0 utility for every bid in his support and every bid in player 2's support, and so he gets zero utility. We thus must have b 2 = B2 = v since otherwise a fixed bid of v − for player 1 would beat staying in the given CCE, leading to a contradiction.

C Generalized First-Price Auctions
Here we provide further details of our analysis of GFP auctions. We state and prove Theorem 4, showing that the diagonal bid distribution (x, x) with the Nash equilibrium marginal distributions (as were shown in Theorem 3) is indeed a CCE of the auction game. We then continue with the formal details of our analysis of the Nash equilibria of the meta-game between the users of regret-minimizing agents that repeatedly play the auction for the nearly diagonal bid distribution.

C.1 Diagonal Coarse Correlated Equilibrium
Next we formally show, in Theorem 4, that the diagonal distribution discussed in the introduction is indeed a CCE. In this equilibrium both bidders place equal bids in every auction that are distributed according to the Nash density function F (x) = x 1−x . We begin with a lemma that formalizes the CCE condition for the case of diagonal distributions (x, x), and then proceed to the proof of the theorem.
Lemma 5. Consider the GFP auction with two items with click-through rates (1, 1/2) played by two players with values-per-click (v, w). Assume w.l.o.g. that v ≥ w, and assume that ties are broken uniformly at random. A diagonal bid distribution (x, x), with support [0, w/2] and density f (x) and cumulative distribution F (x), is a coarse correlated equilibrium of the auction game if and only if the following two inequalities hold: 3 Proof. First, in the case where both players play according to f , i.e., the bids are (x, x) where x ∼ f (x), the utility of the player with value v from bidding x is 3/4 · (v − x) and the utility of the player with value w is 3/4 · (w − x). The expected utilities are then given by the integrals on the left-hand side of the two inequalities. In a coarse correlated equilibrium these expected utilities, of the players must be greater than or equal to the maximum expected utility that each player could obtain by playing a fixed bid, assuming that the other player bids according to the distribution f . Notice that for the player with the high value v, any bid x 0 > w/2 gives lower utility than bidding w/2 (assuming that the other player plays according to f ), and for the player with the low value w, any bid x 0 > w/2 is strictly dominated by bidding 0. Therefore, it is sufficient to look only at fixed bids x 0 ≤ w/2 for both players.
The expected utility of the player with value v from bidding a fixed bid x 0 is: F (x 0 ) · (v − x 0 ) + (1 − F (x 0 )) · (v − x 0 )/2 = 1/2 · F (x 0 ) + 1 (v − x 0 ), and the expected utility of the player with value The next result specifies the equilibria of the meta-game, in which users select values to report to their regret-minimizing agents. Proposition 1. Consider the GFP auction as in Lemma 6. Denote the declared values of agents 1 and 2 by v and w, respectively. Assume w.l.o.g. that v ≥ w, and that the agents of these players converge to the nearly diagonal distribution (x, y) as in Lemma 6.
If there is a maximum value declaration M > 1 1−ln (2) , then the meta-game with these dynamics has two Nash equilibria in which the players declare (  (2)) ). If the value declarations are not bounded, then for any > 0 every declaration profile in which one player declares 1 6(1−ln (2)) and the other player declares a value h > 1/ is an -Nash-equilibrium of the meta-game.
Let M > 1 1−ln (2) and assume (w.l.o.g. about switching the names of players 1 and 2) that player 1 declares v = M and that player 2 declares w = 1 6(1−ln (2)) . We have shown already that player 1 has lower utility if he declares any declaration lower than M that is still above w (since the derivative of the utility is positive), and that player 2 has less utility if he declares any other declaration that is still less than or equal to v (since this is not his maximum point). We now need to show that no player prefers to unilaterally switch positions, i.e., that player 1 would not prefer to declare below w, and that player 2 would not prefer to declare above M . This can be seen directly from the utility functions derived above. On the one hand, when player 1 declares v = M (and player 2 declares w), player 1 has utility u 1 (v, w) = 5 6 1 − On the other hand, if player 1 declares w or less (thus taking the role of the low player), then he has utility at most 5 8 . Hence the high player (player 1) would not prefer to declare less than M , whether this is below or above w (but he would prefer to declare values higher than M if this is possible, as shown above).
Next, when player 2 declares w = 1 6(1−ln (2)) , he has utility more than 1/2. If player 2 declares above player 1, i.e., above M , he has negative utility and therefore he would not prefer to take the role of the high player, and his best reply, given that player 1 declares v = M , is w = 1 6(1−ln (2)) . If M is the maximum possible declaration in the meta-game, then v = M is also the best reply of player 1, given that player 2 declares w = 1 6(1−ln (2)) . That is, when there is a maximum declaration M > 1 1−ln (2) , the two declaration profiles in which one player declares M and the other declares  (2)) are Nash equilibria of the meta-game.
If declarations are not bounded from above, let > 0, and let M = 1 24 (1−ln (2)) . Assume w.l.o.g. that player 1 is the high player and declares v = M , and player 2 is the low player and declares w = 1 6(1−ln(2)) . We have already shown that in this profile player 2 is best-replying to player 1, but player 1 would prefer to increase his declaration. To show an -equilibrium, we claim that player 1 cannot increase his utility by more than from any other declaration. From the expression of the utility stated above it follows that the utility of player 1 from declaring v = M , assuming player 2 does not change w, is u 1 = 5 6 1 − 1 24M (1−ln(2)) = 5 6 1 − . Since u 1 is monotonically increasing with v (given that w remains fixed) and in the limit v → ∞ player 1's utility is 5/6, player 1 cannot increase his gains (compared with his gains when declaring v = M ) by more than with any declaration. Therefore, every declaration profile w = 1 6(1−ln (2)) and v ≥ 1 24 (1−ln(2)) (and specifically, also v > 1/ ), or vice versa, is an -Nash equilibrium of the meta-game.