The existence of perfect equilibrium in discontinuous games

Carbonell-Nicolau, Oriol Article The existence of perfect equilibrium in discontinuous games Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Carbonell-Nicolau, Oriol (2011) : The existence of perfect equilibrium in discontinuous games, Games, ISSN 2073-4336, MDPI, Basel, Vol. 2, Iss. 3, pp. 235-256, https://doi.org/10.3390/g2030235 This Version is available at: https://hdl.handle.net/10419/98498 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/3.0/ Games 2011,2, 235-256; doi:10.3390/g2030235 OPEN ACCESS games ISSN 2073-4336 www.mdpi.com/journal/games Article The Existence of Perfect Equilibrium in Discontinuous Games Oriol Carbonell-Nicolau Department of Economics, Rutgers University, 75 Hamilton Street, New Brunswick, NJ 08901, USA; E-Mail: [email protected]; Tel.: +1-732-932-7363; Fax: +1-732-932-7416 Received: 18 February 2011; in revised form: 27 April 2011 / Accepted: 27 June 2011 / Published: 15 July 2011 Abstract: We prove the existence of a trembling-hand perfect equilibrium within a class of compact, metric, and possibly discontinuous games. Our conditions for existence are easily verified in a variety of economic games. Keywords: trembling-hand perfect equilibrium; discontinuous game; infinite normal-form game; payoff security 1. Introduction A Nash equilibrium is trembling-hand perfect if it is robust to the players’ choice of unintended strategies through slight trembles. That is, in a world where agents make slight mistakes, trembling-hand perfection requires that there exist at least one perturbed model of low-probability errors with an equilibrium that is close to the original equilibrium, which is then thought of as an approximate description of “slightly constrained” rational behavior, or what could be observed if the players were to interact within the perturbed game. In this regard, a Nash equilibrium that is not trembling-hand perfect cannot be a good prediction of equilibrium behavior under any “conceivable” theory of (improbable, but not impossible) imperfect choice. Ever since it was coined by Selten [1], trembling-hand perfection has been a popular solution concept. However, the fact that Selten’s treatment is valid only for finite games poses a problem, since many strategic settings are most naturally modeled as games with a continuum of actions (e.g., models of price and spatial competition (Bertrand [2], Hotelling [3]), auctions (Milgrom and Weber [4]), and patent races (Fudenberg et al. [5])). There have been attempts to use the notion of trembling-hand perfection in infinite economic games to rule out undesirable equilibria (examples include provision of public goods (Bagnoli and Lipman [6]), Games 2011,2236 credit markets with adverse selection (Broecker [7]), budget-constrained sequential auctions (Pitchik and Schotter [8]), and principal-agent problems (Allen [9])).1However, absent a theory of trembling-hand perfection for infinite games (and given that a well-accepted formulation for finite games has long been available), there has been a general tendency to study limits of sequences of trembling-hand perfect equilibria in discretized, successively larger versions of the original (infinite) game at hand (e.g., Bagnoli and Lipman [6], Broecker [7]).2While this is a legitimate approach to trembling-hand perfection in infinite games, Simon and Stinchcombe [10] have shown that similar limit-of-finite approaches have limitations as general solution concepts even in continuous games. Moreover, since there are alternative formulations of trembling-hand perfection for infinite games, confining attention to a limit-of-finite approach, without any comparison with other concepts, seems unsatisfactory. For continuous games, Simon and Sinchcombe [10] offer several notions of trembling-hand perfection and compare their properties. However, infinite economic games often exhibit discontinuities in their payoffs, and a treatment for this kind of games is not available. For instance, most of the above references feature discontinuous games. In the presence of discontinuities, existence of trembling-hand perfect equilibria is not guaranteed by standard arguments. By adapting arguments from Carbonell-Nicolau [11], this paper addresses the issue of existence for an infinite-game extension of Selten’s [1] original notion of trembling-hand perfection. This extension corresponds to Simon and Stinchcombe’s [10] strong approach when the universe of games is restricted by continuity of the players’ payoffs. Building on the existence results obtained here, a companion paper, Carbonell-Nicolau [12], compares the properties of various notions of trembling-hand perfection within families of discontinuous games, and states the analogue of the standard characterization of trembling-hand perfection for finite games (e.g., van Damme [13], p. 28), in terms of the strong approach and other formulations. This characterization is restated in Section 2. We first illustrate that the existence of trembling-hand perfect equilibria depends crucially on the existence of Nash equilibria in Selten perturbations. Selten perturbations are perturbed games in which the players choose any strategy in their action space with positive probability. The strategy spaces in Selten perturbations of infinite, discontinuous games exhibit peculiarities that prevent a straightforward application of the results available in the literature on the existence of Nash equilibria. In fact, in Section 2we show that Selten perturbations need not inherit Reny’s [14] better-reply security from the original game. Even the available strengthenings of better-reply security—payoff security or uniform payoff security, along with upper semicontinuity of the sum of payoffs—do not generally give better-reply security (or some of its generalizations) in Selten perturbations. Thus, one must either rely on an appropriate generalization of the main existence theorem of Reny [14] or impose a suitable strengthening of better-reply security. We seek conditions on the payoffs of a game that prove useful in applications and imply better-reply security—and hence the existence of Nash equilibria—in Selten perturbations. Ideally, to avoid dealing with expected payoffs (defined on mixed strategies) and the weak 1For instance, sometimes the Nash equilibrium concept is too weak to sustain a given result, and the notion of trembling-hand perfection constitutes a natural refinement of the set of Nash equilibria. Beyond its intuitive appeal, trembling-hand perfection is weaker than other refinements, and therefore permits more general theories. 2Allen [9] and Pitchik and Schotter [8] finitize their respective games at the outset, rather than approaching an infinite game by a series of successively larger finite games. However, their models are most conveniently analyzed in terms of continua of actions. Games 2011,2237 convergence of measures, one would like to have conditions that can be verified using the payoffs of the original game, rather than its mixed extension. Carbonell-Nicolau [11] introduces a condition—termed Condition (A)—that is used to prove the existence of a pure-strategy trembling-hand perfect equilibrium. This condition is used here to establish the existence of a mixed-strategy trembling-hand perfect equilibrium. While the current paper adapts arguments from [11], the results obtained here are not implied by those of [11]. We shall provide a detailed comparison with the results in [11] in Section 2. Roughly speaking, Condition (A) is satisfied when there exists, for each player i, a measurable map f:Xi→Xi, where Xirepresents player i’s action space, with the following two properties: (1) for each pure strategy xiof player i, there is an alternative pure strategy f(xi)such that given any pure action profile y−iof the other players, the action f(xi)almost guarantees the payoff player ireceives at (xi, y−i), even if the other players slightly deviate from y−i; and (2) given any pure action profile y−i of the other players, there is a subset of generic elements of Xi(which may depend upon y−i) such that given any generic pure strategy xiof player i, the action profile (xi, z−i), where z−iis a slight deviation from y−i, almost guarantees the payoff player ireceives at (f(xi), z−i). We show that this condition gives payoff security of certain Selten perturbations (Lemma 2). We then combine this finding with known results to establish the existence of a trembling-hand perfect equilibrium in discontinuous games (Theorem 2). In addition, we derive (as in Carbonell-Nicolau [11]) corollaries of these results in terms of two independent conditions—generic entire payoff security and generic local equi-upper semicontinuity—that imply the existence of a map fwith the above properties. In applications, verifying the two independent conditions can prove easier than checking Condition (A), for Condition (A) typically requires constructing a measurable map and verifying two conditions that depend on one another (via the said measurable map).3The alternative hypothesis does not explicitly require the measurability of the map f, and proves easy to verify in applications. The hypotheses of the main existence theorems are satisfied in many economic games and are often rather simple to verify. This is exemplified in Section 3. 2. Perturbed Games and Perfect Equilibria Ametric game is a collection G= (Xi, ui)N i=1, where Nis a finite number of players, each Xi is a nonempty metric space, and each ui:X→Ris bounded and Borel measurable with domain X: = ×N i=1Xi. If in addition each Xiis compact, Gis called a compact metric game. In the sequel, by X−iwe mean the set ×j6=iXj, and, given i,xi∈Xi, and x−i= (x1, ..., xi−1, xi+1, ..., xN)∈X−i we slightly abuse notation and represent the point (x1, ..., xN)as (xi, x−i). The mixed extension of Gis the game G= (Mi, Ui)N i=1 3Constructing a measurable map can sometimes be cumbersome, especially if pure strategies are, say, maps between metric spaces rather than points in Euclidean space. Games 2011,2238 where each Mirepresents the set of Borel probability measures on Xi, endowed with the weak* topology, and Ui:M→Ris defined by Ui(µ) : = ZX uidµ where M: = ×N i=1Mi. Henceforth, the set ×j6=iMjis denoted as M−i, and given i,µi∈Mi, and µ−i= (µ1, ..., µi−1, µi+1, ..., µN)∈M−i we sometimes represent the point (µ1, ..., µN)as (µi, µ−i). Given xi∈Xi, let δxibe the Dirac measure on Xiwith support {xi}. We sometimes write, by a slight abuse of notation, xiin place of δxi. For δ∈[0,1] and (µi, νi)∈M2 i (1 −δ)νi+δµi denotes the member σiof Mifor which σi(B) = (1 −δ)νi(B) + δµi(B)for every Borel set B. When νi=δxifor some xi∈Xi, we sometimes write (1 −δ)xi+δµifor (1 −δ)νi+δµi. Similarly, given (ν, µ)∈M2 (1 −δ)ν+δµ denotes the point ((1 −δ)ν1+δµ1, ..., (1 −δ)νN+δµN) where ν= (ν1, ..., νN)and µ= (µ1, ..., µN). A number of definitions of trembling-hand perfection for infinite normal-form games have been proposed (cf. Simon and Stinchcombe [10], Al-Najjar [15]). For continuous games, the refinement specification considered here is equivalent to the strong approach in [10] and to the formulation in [15]. In this paper, we focus on the issue of existence. In passing, we also illustrate certain limitations of what appears to be a natural approach to the question of existence of trembling-hand perfect equilibria in discontinuous games. This is done more transparently if we frame our discussion in terms of just one notion of trembling-hand perfection. A companion paper, Carbonell-Nicolau [12], compares the various notions of trembling-hand perfection and studies their properties, and contains the analogue of the standard three-way characterization of trembling-hand perfection for finite games (e.g., van Damme [13], p. 28), which will be stated here after several definitions. Before presenting the formal definition of trembling-hand perfection, we need some terminology. A Borel probability measure µion Xiis said to be strictly positive if µi(O)>0for every nonempty open set Oin Xi. For each i, let c Mistand for the set of all strictly positive members of Mi. Set c M: = ×N i=1 c Mi. For νi∈c Miand δ= (δ1, ..., δN)∈[0,1)N, define Mi(δiνi) : = {µi∈Mi:µi≥δiνi} and M(δν):=×N i=1Mi(δiνi). Given δ= (δ1, ..., δN)∈[0,1)Nand ν= (ν1, ..., νN)∈c M, the game Gδν =Mi(δiνi), Ui|M(δν)N i=1 is called a Selten perturbation of G. We often work with perturbations Gδν satisfying δ1=· · · =δN. When referring to these objects, we simply write Gδν with δ=δ1=· · · =δN. Games 2011,2239 Definition 1. A strategy profile x= (x1, ..., xN)∈Xis a Nash equilibrium of Gif for each i, ui(x)≥ui(yi, x−i)for every yi∈Xi. Given a game G= (Xi, ui)N i=1, a Nash equilibrium of the mixed extension Gis called a mixed-strategy Nash equilibrium of G. By a slight abuse of terminology, we sometimes refer to a mixed-strategy Nash equilibrium of Gsimply as a Nash equilibrium of G. Definition 2. A strategy profile µ∈Mis a trembling-hand perfect (thp) equilibrium of Gif there are sequences (δn),(νn), and (µn)with (0,1)N3δn→0,νn∈c M, and µn→µ, where each µnis a Nash equilibrium of the perturbed game Gδnνn. In words, µis a thp equilibrium of Gif it is the limit of some sequence of exact equilibria of neighboring Selten perturbations of G. Intuitively, Selten perturbations of Gmay be interpreted as “models of mistakes”, i.e., formal descriptions of strategic interactions where any player may “tremble” and play any one of her actions. The requirement that µbe the limit of some sequence of equilibria of perturbations of Gsays that there exists at least one model of (low-probability) mistakes that has at least one equilibrium close to µ, so that µis an approximate description of what the players would do (at the said equilibrium) were they to interact in the perturbed game. Remark 1. Note that, in Definition 2, we do not require that µbe a Nash equilibrium of G. It is well-known that, for continuous games, the fact that a strategy profile µis the limit of some sequence of equilibria of Selten perturbations of Gguarantees that µis a Nash equilibrium of G. While we do not impose continuity of payoff functions, we shall show that our conditions also ensure that the limit point is an equilibrium.4 For µ∈M, let Bri(µ)denote player i’s set of best responses in Mito the vector of strategies µ: Bri(µ):=σi∈Mi:Ui(σi, µ−i)≥sup %i∈Mi Ui(%i, µ−i) Consider the following distance function between members of Mi: ρs i(µ, ν) : = sup B |µ(B)−ν(B)| Definition 3 (Simon and Stinchcombe [10]).Given  > 0, a strong -perfect equilibrium of Gis a vector µ∈c Msuch that for each i ρs i(µ i, Bri(µ)) <  A strategy profile in Gis a strong perfect equilibrium of Gif it is the weak* limit as n→0of strong n-perfect equilibria. 4In Definition 2, each µnis an exact equilibrium of the perturbed game Gδnνn. Should one insist upon requiring that these equilibria be exact? While letting each µnbe an n-equilibrium (with (n, δn)→0) would still give a (weak) refinement of Nash equilibrium, any Nash equilibrium would survive this weakening of Definition 2. In fact, given a Nash equilibrium µof G, take ν∈c Mand a sequence (0,1) 3δn→0, and observe that each (1 −δn)µ+δnν= ((1 −δn)µ1+δnν1, ..., (1 −δn)µN+δnνN) is an n-equilibrium of Gδnνfor some n→0, and we have (1 −δn)µ+δnν→µ. Games 2011,2240 The following result is taken from Carbonell-Nicolau [12] and establishes the relationship between trembling-hand perfection and strong perfection in the presence of payoff discontinuities. The equivalence of (1)-(3) is analogous to the standard characterization of trembling-hand perfect equilibria for finite games (e.g., van Damme [13], p. 28). Theorem 1. For a metric game, the following three conditions are equivalent. (1) µis a trembling-hand perfect equilibrium of G. (2) µis a strong perfect equilibrium of G. (3) µis the limit of a sequence (µn)in c Mwith the property that for each iand every  > 0 µn ixi∈Xi:Ui(xi, µn −i)≥sup yi∈Xi Ui(yi, µn −i)≥1− for any sufficiently large n. The following example illustrates that the set of thp equilibria of an infinite game may well be a strict refinement of the set of Nash equilibria. Example 1. Consider the two-player game G= ([0,1],[0,1], u1, u2), where u1and u2are defined by u1(x1, x2):=x1(1 −2x2)and u2(x1, x2) : = −x1x2 2. It is easily seen that the strategy profile (0,1) is a Nash equilibrium of G. Note however that u2(x1,0) ≥u2(x1, x2),for all (x1, x2)∈[0,1]2 and that the inequality is strict if x1>0. Therefore, player 2’s best response to any tremble of player 1 in any Selten perturbation of Gcannot be the action 1. Thus, the equilibrium (0,1) is not thp. The graph of Gis the set ΓG: = (x, α)∈X×RN:ui(x) = αi,for each i The graph of the mixed extension G,ΓG, is defined analogously. The closures of ΓGand ΓGare denoted by ΓGand ΓGrespectively. Given {A, B} ⊆ R3ε, we write A>ε and A > B −ε if a > ε, for all a∈A, and a > b −ε, for all (a, b)∈A×B, respectively. The definitions of A≥εand A≥B−εare analogous. The following definition is taken from Reny [14]. Definition 4. The game Gis better-reply secure if for every (x, α)∈ΓGsuch that xis not a Nash equilibrium of G, there exist i,yi∈Xi, a neighborhood Ox−iof x−i, and β∈Rsuch that ui(yi, Ox−i)≥β > αi. Games 2011,2241 The following proposition is analogous to Proposition 1 in Carbonell-Nicolau [11].5It suggests that the existence of Nash equilibria surviving trembling-hand perfection depends crucially on the existence of Nash equilibria in Selten perturbations of G. Proposition 1. Suppose that Gis a compact, metric game. If Gis better-reply secure and there exists (α, µ)∈(0,1) ×c Msuch that Gδµ has a Nash equilibrium for every δ∈(0, α], then Gpossesses a trembling-hand perfect equilibrium, and all trembling-hand perfect equilibria of Gare Nash. Proof. Let (α, µ)be as in the statement of the proposition. Then, for large n, each Gn−1µpossesses a Nash equilibrium %n. Because %n∈Mand Mis sequentially compact, we may write (passing to a subsequence if necessary) %n→%for some %∈M. Therefore, %is a thp equilibrium of G. To see that all thp equilibria of Gare Nash, suppose that %is a thp equilibrium of G, and let %nbe the corresponding sequence of equilibria in Selten perturbations, i.e., each %nis a Nash equilibrium of Gδnµn, where δn→0,µn∈c M, and %n→%. We wish to show that %is a (mixed-strategy) Nash equilibrium of G. To this end, we assume that %is not an equilibrium and derive a contradiction. Because %n→%and each uiis bounded, we may write (passing to a subsequence if necessary) (%n,(U1(%n), ..., UN(%n))) →(%, (α1, ..., αN)) (1) for some α: = (α1, ..., αN)∈RN. Consequently, (%, α)∈ΓG, so if %is not a Nash equilibrium of G, then, since Gis better-reply secure, some player ican secure a payoff strictly above αiat %. That is, for some σi∈Mi, some neighborhood O%−iof %−i, and some γ > 0 Ui(σi, σ−i)≥αi+γ, for all σ−i∈O%−i We therefore have, in view of (1) Ui(σi, %n −i)> Ui(%n) + β for any sufficiently large nand some β > 0. Consequently, because δn→0, for large enough nwe have Ui(1 −δn i)σi+δn iµn i, %n −i> Ui(%n) thereby contradicting that %nis a Nash equilibrium in Gδnµn. In light of Proposition 1, it is only natural to ask whether the machinery developed within the literature on the existence of Nash equilibria in discontinuous games can be employed to show that Selten perturbations of Gpossess Nash equilibria. Reny ([14], Theorem 3.1) proves that a compact, metric, quasiconcave, and better-reply secure game possesses a Nash equilibrium.6If Gis a compact, metric game, then, for (δ, µ)∈[0,1) ×c M,Gδµ is a compact, metric game.7In addition, Gδµ is easily 5The reader is referred to the discussion following the statement of Theorem 2for a comparison between Proposition 1 and Proposition 1 in [11]. 6A game G= (Xi, ui)N i=1 is quasiconcave if each Xiis a convex subset of a vector space and for each iand every x−i∈X−i,ui(·, x−i)is quasiconcave on Xi. 7If Xiis compact and metric, the weak* topology on Micoincides with the topology induced by the Prokhorov metric on Mi. Hence, if Xiis nonempty, compact, and metric, then Mi(δiµi)is nonempty and metric. In addition, if Xiis nonempty, compact, and metric, Mi(δµi)is a nonempty convex subset of the weakly* compact set Mi. It is easy to check that Mi(δµi) is strongly closed, and therefore (Dunford and Schwartz ([16], Theorem V.3.13, p. 422)) weakly* closed, so Mi(δµi)is weakly* compact. Games 2011,2242 seen to be quasiconcave. Consequently, a Selten perturbation Gδµ possesses a Nash equilibrium if it is better-reply secure. This observation, together with Proposition 1, gives the following lemma. Lemma 1. If Gis a compact, metric game and there exists (α, µ)∈(0,1) ×c Msuch that Gδµ is better-reply secure for every δ∈[0, α], then Gpossesses a trembling-hand perfect equilibrium, and all trembling-hand perfect equilibria of Gare Nash. In general, verifying the existence of (α, µ)∈(0,1)×c Msuch that Gδµ is better-reply secure for every δ∈[0, α]is cumbersome, for it entails dealing with expected payoffs, defined on mixed strategies, and the weak* convergence of measures. Consequently, rather than imposing better-reply security directly on Gδµ, one would like to have conditions on the payoffs of the original game Gthat (1) prove useful in applications and (2) imply better-reply security in perturbations of G. Unfortunately, Gδµ need not inherit better-reply security from G, and even standard strengthenings of better-reply security—payoff security or uniform payoff security (to be defined below), along with upper semicontinuity of PN i=1 ui—do not generally give the desired property in Gδµ. The following definition is taken from Reny [14]. Definition 5. The game Gis payoff secure if for each ε > 0,x∈X, and i, there exists yi∈Xisuch that ui(yi, Ox−i)> ui(x)−εfor some neighborhood Ox−iof x−i. It is well-known (Reny [14], Proposition 3.2) that payoff security of Gand upper semicontinuity of PN i=1 uiensure better-reply security of G. However, payoff security of Gand upper semicontinuity of PN i=1 uineed not give better-reply security of the mixed extension G. The following example illustrates this point. Example 2 (Sion and Wolfe [17]).Consider the game G= ([0,1],[0,1], u1, u2), where u1(x1, x2):=       −1if x1< x2< x1+1 2, 0if x1=x2or x2=x1+1 2, 1otherwise. and u2: = −u1(Figure 1). Figure 1. Example 2: The payoff functions of G. Figure 1. Example 2: The payoff functions of G (0,0) (1,0) (1,1) (0,1) (0,0.5) (0.5,1) 1 -1 1 0 Games 2011,2249 This is clearly true if pi= 0, for ui≥0. Assume pi>0, and choose ai∈Owith 0< ai< pisufficiently close to pito ensure that π(ai)> π(Opi)−εfor some neighborhood Opiof pisatisfying {ai} ∩Opi=∅. Now fix p−i∈[0,4], and pick a neighborhood Op−iof p−isatisfying the following: •If p−i> ai, then Op−i∩ {ai}=∅. •If p−i≤ai, then Op−i∩Opi=∅. It is straightforward to verify that (5) holds. Finally, Gis generically locally equi-upper semicontinuous. In fact, take i,x−i∈[0,1], xi∈[0,1] \ {2, x−i}, and ε > 0. We only consider the case when xi< x−iand xi<2, for the other cases can be dealt with similarly. If xi< x−iand xi<2, we have ui(yi, y−i) = yi(8 −yi)for all (yi, y−i)∈Vxi×Vx−iand for some neighborhoods Vxiand Vx−iof xiand x−irespectively, so it is clear that there exists a neighborhood Oxiof xisuch that for every yi∈Oxithere is a neighborhood Ox−iof x−isuch that ui(yi, y−i)< ui(xi, y−i) + εfor all y−i∈Ox−i. Because Gis generically locally equi-upper semicontinuous and entirely payoff secure, Corollary 1 can be invoked to establish the existence of a thp equilibrium. Example 5 (all-pay auction).There are Nbidders competing for an object with a known value equal to 1. The highest bidder wins and every bidder pays his bid. Ties are broken via an equal probability rule. Given a profile of bids (b1, ..., bN)∈[0,1]N, the winning bid is maxi∈{1,...,N}bi. This situation can be modeled as an N-person normal-form game G= (Xi, ui)N i=1, where Xi= [0,1] and ui(b1, ..., bN):=   1 #W(b1,...,bN)−biif bi= maxj∈{1,...,N}bj, −biif bi<maxj∈{1,...,N}bj. where W(b1, ..., bN):=i:bi= maxj∈{1,...,N}bj. This game is generically locally equi-upper semicontinuous. To see this, fix iand b−i∈X−i, and choose any bi∈[0,1] \b−iand any ε > 0, where b−i: = maxj∈{1,...,N}\{i}bj. We only consider the case when bi< b−i, for the case when bi> b−ican be handled analogously. Take a neighborhood (bi−δ, bi+δ)of bisuch that (bi−δ, bi+δ)∩b−i=∅and δ < ε. For each ai∈(bi−δ, bi+δ)∩[0,1] and for every a−i∈X−iin a neighborhood Ob−iof b−isuch that ci<max j∈{1,...,N}\{i}cj,for all (ci, c−i)∈(bi−δ, bi+δ)×Ob−i we have ui(ai, a−i) = −ai <−bi+δ <−bi+ε =ui(bi, a−i) + ε We now show that Gis generically entirely payoff secure.15 Fix a player i, and choose ε > 0, bi∈(0,1), and a neighborhood Oof bi(we omit the case when bi∈ {0,1}, which is easy to handle). 15This game fails entire payoff security. Games 2011,2250 We wish to show that there exist ai∈Oand a neighborhood Obisuch that for all b−i∈[0,1]N−1, there is a neighborhood Ob−iof b−ifor which ui(ai, Ob−i)> ui(Obi, b−i)−ε(6) Choose ai∈O∩(bi, bi+ε), and fix a neighborhood Obiof bisuch that Obi⊆[0,1],ai∈[0,1] ∩ (bi, bi+ε), and {ai} ∩ Obi=∅. Pick any b−i∈[0,1]N−1, and let Ob−ibe a neighborhood of b−iwith the following property: if maxj∈{1,...,N}bj≤bi, then Ob−i∩ {ai}N−1=∅. It is easy to verify that the choices of ai,Obi, and Ob−iyield Equation (6). Finally, it is routine to verify that the sum of the bidders’ payoffs is continuous. Hence, Corollary 1 gives a thp equilibrium. Example 6 (catalog games).Page and Monteiro [23] consider a common agency contracting game in which firms compete for the business of an agent of unknown type t∈T, where Tis a Borel subset of a separable, complete, and metric space. The distribution of types is represented by a Borel probability measure µdefined on T. There are two firms competing simultaneously in prices and products. The set of products each firm can offer is represented by a compact metric space X, and it is assumed that X contains an element 0, which denotes “no contracting”. The universe of prices that a firm can charge is denoted by D: = 0, d, with d > 0. The agent can only contract with one firm and can choose to abstain from contracting altogether. Given i∈ {1,2}and a closed subset Xiof X, let Ki: = Xi×D be the feasible set of products and prices that a firm ican offer. Assume the existence of a fictitious firm i= 0 with feasible set K0: = {(0,0)}. The agent chooses to abstain from contracting by choosing to contract with firm i= 0. Each firm icompetes by offering the agent a nonempty, closed subset Ci⊆Ki, a catalog, of products and prices. Thus, each firm i’s action space is P(Ki), the compact, metric space of catalogs, equipped with the Hausdorff distance. The utility of a type tagent who chooses (i, x, p)∈ {0,1,2}×Ciis denoted as vt(i, x, p); we have vt(i, x, p):=0if i= 0 and vt(i, x, p):=ut(i, x)−pif i∈ {1,2}. It is assumed that utility is measurable in type tand continuous in contract choice (i, x, p). The agent’s choice set given catalog profile (C1, C2)is given by Γ(C1, C2) : = {(i, x, p) : i∈ {0,1,2},(x, p)∈Ci} A type tagent chooses (i, x, p)∈Γ(C1, C2)to maximize her utility: max (i,x,p)∈Γ(C1,C2)vt(i, x, p) Define v∗(t, C1, C2) : = max (i,x,p)∈Γ(C1,C2)vt(i, x, p) and Φ(t, C1, C2) : = arg max (i,x,p)∈Γ(C1,C2) vt(i, x, p)16 16It is shown in [23] that v∗is measurable in types and continuous in catalog profiles, while the correspondence Φis jointly measurable in types and catalog profiles and upper hemicontinuous in catalog profiles. Games 2011,2251 The map v∗(t, ·)represents a type tagent’s indirect utility function over profiles of catalogs, while Φ(t, ·) gives the type tagent’s best responses to each catalog profile. The j-th firm’s profit function is given by πj(i, x, p) =    p−cj(x)if j=i, 0otherwise. where the cost function cj(·)is bounded and lower semicontinuous. Let π∗ j(t, C1, C2) : = max (i,x,p)∈Φ(t,C1,C2)πj(i, x, p) Firm j’s expected payoff under catalog profile (C1, C2)is Πj(C1, C2) : = ZT π∗ j(·, C1, C2)dµ The game G= (P(Ki),Πi)is an upper semicontinuous, compact game. Moreover, an argument similar to that provided in the proof of Theorem 5 of [23] to establish uniform payoff security of Gcan be utilized to prove that Gsatisfies Condition (A). Consequently, by Theorem 2, the game possesses a thp equilibrium. Example 7 (provision of public goods).Bagnoli and Lipman [6] study the following contribution game. There are Ifinitely many agents. By a slight abuse of notation, the set of agents is denoted by I. Each agent i∈Iis endowed with an amount of wealth wi>0. A collective decision d∈ {0,1}must be made (say, d= 1 designates the decision to provide streetlight, d= 0 represents the decision not to provide it ). An outcome is a social decision together with an allocation of the private good (wealth) among the agents. The set of feasible outcomes is (d, x)∈ {0,1} × RI +:Pi∈Ixi≤Pi∈Iwi−c(d) The utility of agent iif outcome (d, x)is implemented is denoted by vi(d, xi); here, each viis assumed strictly increasing in dand continuous and strictly increasing in xi. The cost of adopting decision dis c(d), where c(0) = 0 and c(1) = c > 0. The agents simultaneously choose a contribution to the public project, each agent i’s contribution being an element of Si: = [0, wi]. Let wdenote the vector of endowments. Given a profile s= (si)i∈I of contributions, the public project is undertaken if Pi∈Isi≥c, in which case the realized outcome is (1, w −s); otherwise (i.e., if Pi∈Isi< c) the outcome (0, w)obtains. Let S: = ×i∈ISi. The associated normal-form game is G= (Si, ui)i∈I, where ui:S→Ris defined by ui(s):=   vi(1, wi−si)if Pisi≥c, vi(0, wi)if Pisi< c. Bagnoli and Lipman[6] uses an equilibrium concept, termed undominated perfect equilibrium, that eliminates the set of weakly dominated strategies in the original game and applies the notion of trembling-hand perfection to the resulting game. To avoid defining trembling-hand perfection in infinite games and dealing with the issue of existence, Bagnoli and Lipman work with approximating finite versions of G. Games 2011,2252 Specifically, assuming vi(0, wi)=0for each i(a normalization that does not affect generality) and vi(1,0) <0for each i(so that we do not need to consider cases when some agents would like to contribute more than their wealth), we can define aiimplicitly by vi(1, wi−ai)=0. Assume Pi∈Iwi> c. Clearly, the elimination of the interior of the set of weakly dominated strategies in Gremoves all si∈Sisuch that si> ai. Consider the “subgame” gof Gin which i’s strategy space is restricted to [0, ai]and gis otherwise identical to G. Bagnoli and Lipman replace each Siby finite counterparts of varying grid sizes, and consider sequences of finite games in which the grid size converges to zero. They define an undominated perfect equilibrium in Gas the limit of some sequence of undominated perfect equilibria of approximating finite versions of G. The authors’ main result is that the game form Gfully implements the core of the associated economy in undominated perfect equilibrium (i.e., any undominated perfect equilibrium of Ginduces a core allocation and vice versa). In view of our results, one may ask the following: Can one apply the characterization exercise conducted in [6] directly on the infinite game g? Can one obtain a similar theorem on the full implementation of the core in terms of trembling-hand perfection? While answering these questions requires a thorough analysis, Theorem 2can be used to establish the existence of a thp equilibrium in g. It is easily seen that the restriction of uito [0, ai]is upper semicontinuous, so the sum of payoffs for gis upper semicontinuous. We now show that gis entirely payoff secure. Take i,ε > 0,si∈[0, ai], and a neighborhood Oof si. We need to show that there exist bi∈Oand a neighborhood Osiof sisuch that for every s−i∈ ×j6=i[0, aj], there is a neighborhood Os−ifor which ui(bi, Os−i)> ui(Osi, s−i)−ε(7) The cases when si∈ {0, ai}are easy to handle, so suppose that si∈(0, ai). Take bi∈Owith ai> bi> siclose enough to sito ensure that vi(1, wi−bi)> vi(1, wi−Osi)−ε for some sufficiently small neighborhood Osi. Given s−i∈ ×j6=i[0, aj], fix a neighborhood Os−iwith the following property: if Pjsj≥c, then bi+Pj6=iesj≥cfor all es−i∈Os−i. Now, verifying that the choices of bi,Osi, and Os−igive (7) is straightforward. Finally, we show that gis generically locally equi-upper semicontinuous. For each i, let µibe the normalized Lebesgue measure over [0, ai]. Fix iand s−i∈ ×j6=i[0, aj]. Consider the set of all si∈[0, ai] such that Pjsj6=c, a set that has full Lebesgue measure (i.e., it has µi-measure 1), and take any siin this set, and ε > 0. We only consider the case when Pjsj> c (the case when Pjsj< c can be dealt with analogously). Clearly, we may choose a neighborhood Osiof siin [0, ai]such that bi+Pj6=isj> c and vi(1, wi−bi)< vi(1, wi−si) + εfor all bi∈Osi. Further, given bi∈Osi, we may choose a neighborhood Os−iof s−iin ×j6=i[0, aj]such that bi+X j6=i bj> c < si+X j6=i bj,for all b−i∈Os−i Games 2011,2253 Consequently, for every b−i∈Os−i, we have ui(bi, b−i) = vi(1, wi−bi)< vi(1, wi−si) + ε=ui(si, b−i) + ε In light of Theorem 2, therefore, we obtain the non-emptiness of the set of trembling-hand perfect equilibria in g. 4. Proof of Lemma 2 To begin, we state a number of intermediate results. Given a metric space Xand Y⊆X,P(Y)denotes the set of Borel probability measures on Y, and P∗(Y)is the subset of finitely supported measures in P(Y)that assign rational values to each Borel set. Lemma 4 (Carbonell-Nicolau [11], Lemma 6).Let Xbe a compact metric space. Suppose that f:X→Ris bounded and Borel measurable. For each µ∈P(X)and every ε > 0, there exists ν∗∈P∗(X)∩Nε(µ)such that |RXfdµ−RXfdν∗|< ε. Lemma 5 (Carbonell-Nicolau [11], Lemma 7).Suppose that Gis compact, metric, and satisfies Condition (A). Then there exists (µ1, ..., µN)∈c Msuch that for each iand every ε > 0there is a map f:Xi→Xisuch that the following is satisfied: (i)For each xi∈Xiand every σ−i∈M−i, there is a neighborhood Oσ−iof σ−isuch that Ui(f(xi), Oσ−i)> Ui(xi, σ−i)−ε (ii)For every σ−i∈M−i, there is a neighborhood Vσ−iof σ−isuch that Ui(µf i, p−i)< Ui(µi, p−i) + ε for all p−i∈Vσ−i, where µf i∈Miis defined by µf i(B):=µi(f−1(B∩f(Xi))). Lemma 2.Suppose that a compact, metric game Gsatisfies Condition (A). Then there exists µ∈c M such that Gδµ is payoff secure for every δ∈[0,1). Proof. Fix δ∈[0,1), and let µ= (µ1, ..., µN)∈c Mbe the measure given by Condition (A). We fix ε > 0,σ= (σ1, ..., σN)∈M(δµ), and i, and show that there exists νi∈Mi(δµi)such that Uiνi, Oσ−i> Ui(σ)−εfor some neighborhood Oσ−iof σ−i. Lemma 5gives a Borel measurable map f:Xi→Xisatisfying the following: (i) For every yi∈Xi, there is a neighborhood Oσ−iof σ−isuch that Ui(f(yi), Oσ−i)> Ui(yi, σ−i)−ε 4. (ii) There is a neighborhood Vσ−iof σ−isuch that Ui(µf i, p−i)< Ui(µi, p−i) + ε 2for all p−i∈Vσ−i, where µf i∈Miis defined by µf i(B):=µif−1(B∩f(Xi)) Claim 1. There exists a neighborhood Oσ−iof σ−isuch that ZXi Uif(·), Oσ−idσi>ZXi Ui(·, σ−i)dσi−ε 2 Games 2011,2254 Proof. By (i), for every yi∈Xithere is a neighborhood Oσ−iof σ−isuch that Uif(yi), Oσ−i> Ui(yi, σ−i)−ε 4 For each n∈N, define Xn i: = [ ν−i∈N1 n(σ−i)yi∈Xi:Ui(f(yi), ν−i)) < Ui(yi, σ−i)−ε 4 Each Xn iis Borel measurable. In fact, Lemma 4gives Xn i=[ ν−i∈N1 n(σ−i)∩P∗(X−i) Xi(ν−i)(8) where Xi(ν−i) : = yi∈Xi:Ui(f(yi), ν−i)) < Ui(yi, σ−i)−ε 4. Now, since uiand fare Borel measurable, for each ν−i∈N1 n(σ−i)the set Xi(ν−i)is Borel measurable. Therefore, each Xn iis (by (8)) a countable union of Borel sets, and hence a Borel set itself. Now observe that we have TnXn i=∅and X1 i⊇X2 i⊇ · · · . Consequently, for any large enough n, σi(Xn i) sup (ν,ρ)∈M2 [Ui(ν)−Ui(ρ)] <ε 4 Hence, for any sufficiently large n, ZXi Ui(f(·),N 1 n(σ−i))dσi =ZXi\Xn i Ui(f(·), N1 n(σ−i))dσi+ZXn i Ui(f(·), N1 n(σ−i))dσi >ZXi\Xn i Ui(·, σ−i)dσi+ε 4+ZXn i Ui(f(·), N1 n(σ−i))dσi > Ui(σi, σ−i)−ε 2 as desired.  Because σ∈M(δµ), there exists, for each i,%i∈Misuch that σi= (1 −δ)%i+δµi. Define pf i: = (1 −δ)%f i+δµiand υf i: = (1 −δ)%f i+δµf i where %f i∈Miis defined by %f i(B):=%i(f−1(B∩f(Xi))). By (ii), there exists a neighborhood Oσ−iof σ−isuch that Ui(µi, p−i)> Ui(µf i, p−i)−ε 2,for all p−i∈Oσ−i This, together with the definitions of pf iand υf i, gives, for any p−iin some neighborhood of σ−i Ui(pf i, p−i) = (1 −δ)Ui(%f i, p−i) + δUi(µi, p−i) >(1 −δ)Ui(%f i, p−i) + δUi(µf i, p−i)−ε 2 =Ui(υf i, p−i)−ε 2 (9) Games 2011,2255 In addition, the definition of υf iand the equality σi= (1 −δ)%i+δµientail Ui(υf i, p−i) = ZXi Ui(·, p−i)dυf i = (1 −δ)ZXi Ui(·, p−i)d%f i+δZXi Ui(·, p−i)dµf i = (1 −δ)ZXi Ui(f(·), p−i)d%i+δZXi Ui(f(·), p−i)dµi =ZXi Ui(f(·), p−i)dσi (10) Consequently, for every p−iin some neighborhood of σ−iwe have Ui(pf i, p−i)> Ui(υf i, p−i)−ε 2 =ZXi Ui(f(·), p−i)dσi−ε 2 > Ui(σi, σ−i)−ε Here, the first inequality follows from (9), the second inequality is given by Claim 1, and the equality is a consequence of (10). Hence, because pf i∈Mi(δµi),Gδµ is payoff secure.  Acknowledgements I am indebted to Efe Ok for his insights and encouragement; Efe read previous drafts and provided detailed comments. I also thank Rich McLean and Joel Sobel for several conversations, several anonymous referees for very useful remarks, and seminar participants at Barcelona Jocs and Rutgers for their comments. Part of this research was conducted while the author was visiting Universitat Aut` onoma de Barcelona. The author is grateful to this institution for its hospitality. References 1. Selten, R. Reexamination of the perfectness concept for equilibrium points in extensive games. Int. J. Game Theory 1975,4, 25-55. 2. Bertrand, J. Th´ eorie math´ ematique de la richesse sociale. J. Savants 1883, 499-508. 3. Hotelling, H. The stability of competition. Econ. J. 1929,39, 41-57. 4. Milgrom, P.; Weber, R. A theory of auctions and competitive bidding. Econometrica 1982,50, 1089-1122. 5. Fudenberg, D.; Gilbert, R.; Stiglitz, J.; Tirole, J. Preemption, leapfrogging, and competition in patent races. Eur. Econ. Rev. 1983,22, 3-31. 6. Bagnoli, M.; Lipman, B.L. Provision of public goods: Fully implementing the core through private contributions. Rev. Econ. Stud. 1989,56, 583-601. 7. Broecker, T. Credit-worthiness tests and interbank competition. Econometrica 1990,58, 429-452. 8. Pitchik, C.; Schotter, A. Perfect equilibria in budget-constrained sequential auctions: An experimental study. Rand J. Econ. 1988,19, 363-388. 9. Allen, B. Using trembling-hand perfection to allieviate the interlinked principal-agent problem. Scand. J. Econ. 1988,90, 373-382. Games 2011,2256 10. Simon, L.K.; Stinchcombe, M.B. Equilibrium refinement for infinite normal-form games. Econometrica 1995,63, 1421-1443. 11. Carbonell-Nicolau, O. On the existence of pure-strategy perfect equilibrium in discontinuous games. Games Econ. Behav. 2011,71, 23-48. 12. Carbonell-Nicolau, O. Perfect and limit admissibe perfect equilibria in discontinuous games. J. Math. Econ. (forthcoming). 13. Van Damme, E.E.C. Stability and Perfection of Nash Equilibria; Springer-Berlag: Berlin, Germany, 2002. 14. Reny, P.J. On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 1999,67, 1029-1056. 15. Al-Najjar, N. Strategically stable equilibria in games with infinitely many pure strategies. Math. Soc. Sci. 1995,29, 151-164. 16. Dunford, N.; Schwartz, J.T. Linear Operators, Part I: General Theory; John Wiley and Sons: New York, NY, USA, 1957. 17. Sion, M.; Wolfe, P. On a game without a value. In Contributions to the Theory of Games, Volume III; Dresher, M., Tucker, A.W., Wolfe, P., Eds.; Princeton University Press: Princeton, NJ, USA, 1957. 18. Carmona, G. On the existence of equilibria in discontinuous games: Three counterexamples. Int. J. Game Theory 2005,33, 181-187. 19. Monteiro, P.K.; Page, F.H. Uniform payoff security and Nash equilibrium in compact games. J. Econ. Theory 2007,134, 566-575. 20. Barelli, P.; Soza, I. On the existence of Nash equilibria in discontinuous and qualitative games. 2008, (mimeo). 21. Baye, M.R.; Tian, G.; Zhou, J. Characterizations of the existence of equilibria in games with discontinuous and non-quasiconcave payoffs. Rev. Econ. Stud. 1993,60, 935-948. 22. Baye, M.R.; Morgan, J. Winner-take-all price competition. Econ. Theory 2002,19, 271-282. 23. Page, F.H.; Monteiro, P.K. Three principles of competitive nonlinear pricing. J. Math. Econ. 2003, 39, 63-109. c 2011 by the author; licensee MDPI, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).