Sixty-seven years of the Nash program: Time for retirement?

Serrano, Roberto Article Sixty-seven years of the Nash program: Time for retirement? SERIEs - Journal of the Spanish Economic Association Provided in Cooperation with: Spanish Economic Association Suggested Citation: Serrano, Roberto (2021) : Sixty-seven years of the Nash program: Time for retirement?, SERIEs - Journal of the Spanish Economic Association, ISSN 1869-4195, Springer, Heidelberg, Vol. 12, Iss. 1, pp. 35-48, https://doi.org/10.1007/s13209-020-00221-5 This Version is available at: https://hdl.handle.net/10419/286528 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. https://creativecommons.org/licenses/by/4.0/ SERIEs (2021) 12:35–48 https://doi.org/10.1007/s13209-020-00221-5 ORIGINAL ARTICLE Sixty-seven years of the Nash program: time for retirement? Roberto Serrano1 Received: 8 June 2020 / Accepted: 3 August 2020 / Published online: 27 August 2020 © The Author(s) 2020 Abstract The Nash program is an important research agenda initiated in Nash (Econometrica 21:128–140, 1953) in order to bridge the gap between the noncooperative and cooperative counterparts of game theory. The program is thus turning sixty-seven years old, but I will argue it is not ready for retirement, as it is full of energy and one can still propose important directions to be explored. This paper completes and updates previous surveys, and suggests several directions for future research. Keywords Nash program ·Bargaining ·Implementation JEL Classification C71 ·C72 ·C78 1 Introduction The Nash program is an important research agenda initiated in Nash (1953). It is intended to bridge the gap between the noncooperative and cooperative counterparts of game theory. The program is thus turning sixty-seven years old, but I will argue it is not ready for retirement yet. Judging by the number of papers that it has produced recently, it is still full of energy. A rough count of papers in the Nash program, cited here and published or listed as working papers since my previous survey in 2005, is the following: I thank Juan D. Moreno-Ternero and two anonymous referees for comments and encouragement. Geoffroy de Clippel and Rajiv Vohra gave helpful suggestions. I am indebted to Claus-Jochen Haake and Walter Trockel for encouraging me to write this paper. Claus-Jochen also gave me the idea for the title. Xu Zhang and Zeky Murra-Anton provided great research support with their literature review and reading of papers. BRoberto Serrano [email protected] 1Department of Economics, Brown University, Providence, RI, USA 123 36 SERIEs (2021) 12:35–48 Year Number of papers 2006 3 2007 4 2008 6 2009 4 2010 6 2011 3 2012 7 2013 5 2014 5 2015 7 2016 2 2017 4 2018 3 2019 5 2020 5 More importantly, exciting directions to be explored are waiting for good papers to be written. Many results can be found in the several decades of the program, and the reader is referred to Serrano (2005,2008,2014) for complementary surveys and commentaries. This paper completes and updates these previous pieces, and suggests several directions for future research. To avoid repetitions, and given that I see this paper as a new chapter in the saga of previous surveys I have written on the subject, I will spare the reader of the section on preliminaries that introduces mathematical notation. I refer the reader to those papers for it. Nonetheless, I have attempted to make the material contained here sufficiently informative and self-contained so that the reader can gain an appreciation of the recent progress made in the program. The plan of the paper is thus the following. Section 2is devoted to interpretations and new directions for the Nash program, while Sect. 3consists of a list of recent contributions to it. Section 4contains a few suggestions for new research. As is always the case in surveys, the list of papers mentioned here will be incomplete and I apologize in advance to the authors of those worthy contributions that surely I will have missed. 2 Interpretations and new directions The initial interpretation of the Nash program, as formulated in Nash (1953), was to describe the strategic rules of negotiation underlying an axiomatic solution. According to this view, the primitive is a given axiomatic solution and the goal is to enhance its understanding, by obtaining it as a result of a completely different approach. This is indeed a valuable exercise in its own right and has led to the noncooperative implementation of the main cooperative solutions in different domains of coalitional games, including the Nash bargaining solution, the Kalai–Smorodinsky bargaining solution, the Shapley value, the nucleolus, the core, the bargaining set, or the kernel. (It is remarkable that, after so many years, missing from this list is the von Neumann– Morgenstern stable set, for which only an early paper by Harsanyi (1974) suggested an approach, never explored in the Nash program.) Each of these results has improved 123 SERIEs (2021) 12:35–48 37 our understanding of these solutions, which can now be seen in a different light, instead of being evaluated on the basis of their definitions or the axioms that lead to them. The noncooperative negotiation procedures so proposed usually depend on the data of the coalitional game, i.e., typically on the characteristic function. These prevent them from being useful to a planner who lacks such information. However, for many of them, those procedures can be adapted to make them independent of such details. According to this view, the Nash program is seen as a part of the theory of implementation or mechanism design, thus enhancing the potential use for the program. One advantage of the mechanisms in the Nash program, when compared to more abstract mechanisms in the general theory of implementation, is their simplicity, a good desideratum for the design of institutions. These ideas were developed in several papers, following different ways to get into the “black box” of the characteristic function, by endowing it with an outcome structure. These included Serrano (1997a), Dagan and Serrano (1998), Bergin and Duggan (1999), and Trockel (2002a,b). In a broader interpretation, the Nash program should be viewed as a framework to keep the dialogue between the two main branches of game theory always open. Ultimately, as social scientists, what we should be aiming for is to produce a useful set of tools in order to shed light on a host of different problems relevant to societies. This tool box by now contains a number of useful approaches (axiomatic, strategic, evolutionary, experimental, computational), and an approach that emphasizes connections among different areas can only enhance our understanding of the problems we study and the solutions we propose. See Aumann (1987) for a similar perspective, emphasizing the importance of uncovering relationships among seemingly distant concepts in science. Another related approach that blends noncooperative and cooperative gametheoretic ideas is that of coalition formation; see Ray and Vohra (2015) for an excellent survey. In this literature, the separating line between the two counterparts of game theory becomes blurred, which is a good thing, because it forces us to question some of the basic assumptions of the theory. For example, coalitional equilibrium concepts can be defined in the strategic-form or extensive-form of a game, or the assumption of binding agreements, often associated with the cooperative approach, is also used in noncooperative games. This is an active area of research that will continue to produce interesting work, and I view this “blurring the border” logic very much close to the foundational idea of the Nash program. The experimental methods in economics and game theory have become very popular in recent decades, and they constitute a nice complement to empirical evidence from the field. In the end, testing different theoretical results in the laboratory is desirable, in order to either validate or question theoretical progress. As in any healthy science, such dialogue between theorists and empiricists should be encouraged. For instance, Nash et al. (2012) presents an interesting application of the Nash program in the experimental laboratory, specifically, the treatment of the agency model that Nash himself studied during the last years of his life. For another related contribution, Anbarci and Feltovich (2012) takes a variant of the Nash demand game (Nash 1953) to the laboratory. In social choice and legislative bargaining, there is a vast experimental literature as well. For instance, there have also been experimental tests of theoretical results in different bargaining models, including the comparison of open and closed- 123 38 SERIEs (2021) 12:35–48 amendment rules in Frechette et al. (2003), or demand bargaining versus alternating offers in Frechette et al. (2005), just to give two prominent examples. Given the large volume of experimental research being produced today, I would expect to see much interesting work emphasizing this connection in the next years. Generating empirical evidence in the field would be probably harder, as one would have to check how closely the data available could be approximated by a characteristic function, a task that seems quite challenging. Mechanisms in the Nash program could be used as “launching platforms” to extend the theory to larger domains. Indeed, in domains in which the axiomatic approach has difficulties finding solutions, the analysis of the strategic-form or extensiveform bargaining procedures of the Nash program may be a way to make progress in finding predictions, which can then orient axiomatically-based researchers. For example, the extension of certain solutions from the transferable-utility domain to the nontransferable-utility domain may be sometimes challenging, because there are multiple ways to propose such an extension, or because such an extension may not be clear. For each of these two cases, respectively, Hart and Mas-Colell (1996) provides an answer based on the Nash program for the Shapley value, and Serrano (1997b)for the kernel. In the analysis of games in partition function form, which model coalitional externalities, one could attempt to extend the Shapley value. Maskin (2003) proposes a procedure based on the Nash program that implements the Shapley value in 3-player characteristic functions, and uses the procedure to calculate its subgameperfect equilibrium (SPE) when the underlying environment is a partition function. Interesting properties of the solution, such as efficiency or lack thereof, are uncovered as a function of the presence of positive or negative externalities. And as already mentioned, one additional nice feature of many mechanisms in the Nash program is simplicity, which should always be a desideratum in terms of increasing their applicability in real-world situations. If, instead of just stability or efficiency, one would consider other normative goals as embodied in the different cooperative solutions, one could see applications of the Nash program procedures akin to market design, which we could call bargaining design. Bargaining design, as a part of design economics (Roth 2002), could be an additional tool in the allocation of goods and services. On the other hand, Salas-Fumás (2019) offers a criticism, since in the author’s view, the Nash program does not pay enough attention to issues of transaction costs in the implementation of solutions, suggesting instead an alternative management/governance system to solve bargaining problems. 3 Recent contributions The Nash program is alive and kicking. As a proof of its health, I list its many recent contributions, organized by solution concepts to which they apply or domains of problems where they have been obtained. Within each subsection, the list is pretty much chronological. Of course, one could have opted for different criteria to organize these papers. Indeed, (a) some results are obtained as limits are taken (discount rate; deadlines) and some are exact implementations; (b) some results are proved under the assumption of complete information, others are written for incomplete information 123 SERIEs (2021) 12:35–48 39 environments; (c) some assume that the number of players is fixed, and others take as parameters the number of players on each side of the bargaining table; (d) some assume a continuum of alternatives and others a finite set of alternatives; and so on. Clearly, opting for one of these criteria would lead to a different organization of the material, but in the end, the reader should be driven to consult the original papers, which is the whole point of a good survey. 3.1 The Nash solution The Nash solution is remarkably the one that continues to produce most of the new results in the Nash program. For an assessment of the lessons learned from mechanisms leading to the Nash solution, versus other bargaining solutions, the reader is referred to Serrano (2005). We proceed to list the additions to this body of work. In Güth et al. (2004), an option of waiting is added to the noisy Nash demand game; in equilibrium, there is always commitment not to wait and conditions are found under which the equilibrium converges to the Nash solution. Trockel (2005) presents a market-based noncooperative foundation of the Nash solution, emphasizing the fairness property of the Nash product. In Gómez (2006), a distortion game is proposed where players report their utility functions to an arbitrator, equilibrium outcomes coincide with the entire Pareto frontier, but where adding uncertainty to the game, an approximate implementation of the Nash solution obtains. Although previous results had shown that the Nash solution does not satisfy Maskin monotonicity, by defining a correspondence based on the solution instead of its realizations, Haake and Trockel (2010) restore Maskin monotonicity, hence allowing the Nash implementation of the social choice correspondence that encompasses the Nash solution (they show a strengthening of monotonicity, which is also sufficient for Nash implementability). Okada (2010) allows for players to form coalitions and defines what he calls the Nash core (payoffs to which no coalition can improve upon, anticipating the Nash solution payoffs for the complement coalition). He shows that the Nash solution arises in equilibrium if and only if it belongs to the Nash core, a result one should expect given the consistency of the Nash solution (see, e.g., Krishna and Serrano 1996). In Matveenko (2011), a bargaining game inspired by Shapley’s λ-transfer method, brings ideas of utilitarianism and egalitarianism of an arbitrator to get to the Nash bargaining solution. Van Essen (2014) proposes a model where parties make errors in formulating their demands; in the unique Nash equilibrium with trade, payoffs converge to the Nash solution as errors become negligible. And to close for now the list of papers that connect with Nash’s symmetric solution, Duman and Trockel (2016) offers a variant of Rubinstein’s alternating-offers procedure to obtain an exact support of the Nash solution in SPE, although its interpretation as a sound implementation exercise applies only to very restricted classes of preferences. Britz et al. (2010) studies a multilateral bargaining game with a general protocol to appoint proposers and obtains the weighted (or asymmetric) Nash solution as the limit of stationary SPE outcomes when the probability of breakdown goes to zero. Anbarci and Sun (2013) obtains the class of asymmetric Nash solutions in sequential versions of the Nash demand game. A learning approach is followed by In (2014), 123 40 SERIEs (2021) 12:35–48 which demonstrates that the fictitious-play process almost always converges in the Nash demand game, although no condition is found for its convergence to the equilibrium that selects the Nash solution. Britz et al. (2014) and Kawamori (2014) provide approximate implementations of the weighted Nash solution in stationary SPE of a multilateral bargaining game where the probability of being the next proposer is a function of who rejects the previous proposal. In Xie (2015), a search-based market model is studied, which yields in equilibrium a generalized Nash solution, where the weights depend on the number of market participants on each side. Harstad (2018) proposes a pledge-and-review bargaining game (each party quantifies its own contribution— to a public good, for example—before the set of pledges must be accepted). The procedure yields asymmetric Nash solutions, and the author illustrates its use in the comparison between the climate agreements of Kyoto in 1997 and Paris in 2015. Hu and Rocheteau (2020) propose a unified approach to the Nash solution and Kalai’s proportional solution in a negotiation game with limited liability, as a function of the rounds of negotiations being few or many, respectively. 3.2 Other solutions to pure bargaining problems Haake (2009) provides two support results of the Kalai–Smorodinsky solution in the context of a market for object division. In the former, strategic-form games are derived with a unique Nash equilibrium; in the latter, moves are sequential in the extensive form, and all subgame perfect equilibria yield the Kalai–Smorodinsky solution. Fiaccadori (2008) uses the alternating-offers procedure to make the point that, when the disagreement costs are high, one obtains the Kalai–Smorodinsky solution, while if they are small, the equilibrium yields the Nash solution; this is again in the spirit of “action at a distance” or lack thereof, in the words of Nash (1953); see again Serrano (2005) for a discussion. Anbarci and Boyd (2011) offers a variant of the Nash demand game, specifying exogenous breakdown probabilities, that yields the Kalai–Smorodinsky solution. Based on a symmetric arbitration scheme, Rong (2012) offers two implementations of the Kalai–Smorodinsky solution as discounting is removed. In the first, a simultaneous-offer game is proposed and in the second, the focus is an alternatingoffers game. In both, the symmetric arbitration solution is used to decide the outcome whenever players disagree. Spinnewijn and Spinnewyn (2015) allows for claims at the bargaining table to be revised and obtains the Nash (or Kalai–Smorodinsky) solution when no (or all) revisions are allowed, respectively. The sequential Raiffa solution has also received some attention. Trockel (2011) provides its exact noncooperative support: the game has an infinity of weakly subgame perfect equilibria whose payoff vectors coincide with that of the sequential Raiffa solution. Driesen et al. (2017) studies a continuous-time version of Stahl’s alternatingoffers game with a deadline and shows that as the deadline goes to infinity, the SPE payoff converges to the continuous Raiffa solution. A variety of results have led to a number of different bargaining solutions. With a finite set of alternatives, Anbarci (2006) studies the “alternate strike” and the “voting by alternating offers and vetoes” procedures, and shows that their SPE outcomes converge to the equal-area bargaining solution as the number of uniformly-distributed 123 SERIEs (2021) 12:35–48 41 alternatives goes to infinity. Dasgupta and Maskin (2007) explores the implications of destructive power in bargaining, replaces Nash’s independence of irrelevant alternatives (IIA) and Kalai–Smorodinsky’s monotonicity with a new deletion axiom, and obtains a solution very different from Nash’s, both axiomatically and strategically. Forgó and Fülöp (2008) studies variants of well-known procedures, such as the Nash demand game or the Rubinstein alternating-offers game, to implement the L-Nash solution, which is the limit of the Nash solution as the disagreement payoffs go to negative infinity in a given direction (one could generate any point on the Pareto frontier for arbitrary directions, which, in the alternating-offers procedure, requires to adjust the relative discounting of the players appropriately). Herings and Predtetchinski (2010) presents a bargaining model over points in the unit interval and shows an intriguing result, since the equilibrium outcomes do not converge to any known bargaining solution. Vo and Li (2012) frames bargaining as a problem in propositional logic where bargainers have ordinal preferences, and proposes axiomatic and strategic foundations of a solution based on minimal concession of argumentation-based negotiations (proposals incorporate logical arguments to back them). In a world in which multiple tasks are to be performed in alternative facilities, an instance of a multi-issue bargaining problem, Gu et al. (2013) proposes a mechanism that yields a solution with a different efficiency–fairness trade-off than Nash’s (a different point in the Pareto frontier). Ju (2013) studies a bid-offer–counteroffer procedure in a stark context consisting of only two alternatives and finds a unique SPE with an outcome that combines the utilitarian and egalitarian solutions. Abreu and Pearce (2015) studies the two-stage game proposed in Nash (1953) and formalizes an equilibrium selection, providing a more complete analysis of the “bargaining with variable threats” problems; the analysis is extended to repeated and stochastic games with contracts. Vidal-Puga (2015)offersa noncooperative approach to the Shapley–Shubik ordinal solution in three-player problems. Yeung (2017) proposes a cooperative optimization solution—a general social welfare function in the bargaining problem—which differs from other known bargaining solutions and obtains it as the equilibrium outcome of his procedure. In the tradition of evolutionary game theory, Hwang et al. (2018) studies learning processes based on the logit rule—a perturbed best-reply dynamics rule—played in coordination games. The paper obtains the egalitarian bargaining solution as the long-run norm if there are intentional biases (where a deviation to a different strategy depends on the last payoff received); this result is to be contrasted with Young (1993), which obtains the Nash solution when deviations do not exhibit such a dependence. Qin et al. (2019) implements selections of the Nash set (multi-valued Nash solutions) in the absence of convexity of the feasible set of utilities. Mizukami and Wakayama (2020)investigates implementation in dominant strategies and finds a negative result: along with welfarism, it is equivalent to the class of dictatorial solutions. 3.3 Games in characteristic-function form We begin here with papers that contribute to the Shapley value. Kamijo (2008) obtains the Shapley value, the Owen value, and their weighted versions, in a noncooperative game within a framework of hierarchical and horizontal coalition structures. Ju and 123 42 SERIEs (2021) 12:35–48 Wettstein (2009) discusses a unifying bidding approach where players bid to become the proposer and offers implementation results of the Shapley, consensus, and equalsurplus values. Ju (2012) builds on the procedure in Pérez-Castrillo and Wettstein (2001) in three ways, with different protocols of rejection and renegotiation, all of them leading to the Shapley value in SPE. Chessa (2019) implements the Shapley value in expectation using a Groves mechanism that takes care of incentive compatibility. Nash (2008,2009) studies a game using the agency method, by which a partially accepted proposal means that the proposer becomes the agent of the accepting party in further negotiations; see Krishna and Serrano (1996, Section 8) for a related discussion. Miyakawa (2008), following the same steps as in Hart and Mas-Colell (1996), studies a variant of their procedure to obtain the equal-split solution. In Serrano and Shimomura’s (2006) last section, a result of implementation of the average prekernel is reported, in which each player is asked to evaluate a payoff, in ignorance of which player will be bargaining with her if she rejects it; hence, equilibrium payoffs are “acceptable in average.” Chang and Hu (2017) provides an implementation of the kernel in SPE of a game with bilateral encounters of players where the Davis–Maschler reduced game determines the outside options, much like Serrano (1997b). Burguet and Caminal (2020) offers a closely related idea, by proposing a new solution concept that they call SCOOP (solution with consistent outside options), in which the Nash solution obtains for each subset of players in a problem where the random disagreement payoffs are required to be the players’ outside options in different coalitions. The solution may be probabilistic for some games, and it is built on such endogenous disagreement payoffs, which must be consistently constructed across different coalitions. The paper proposes a coalitional bargaining protocol, where the SCOOP is approximately obtained in stationary equilibria as discounting is removed. And we close this subsection with core-based ideas. The coalitional Nash bargaining solution, defined as the point in the core that maximizes the players’ payoff product, is found in Compte and Jehiel (2010) as the limit of the efficient stationary equilibrium payoff (when it exists) of their coalitional bargaining game with discounting. Nieva (2015) provides a version of the same result, but where the stage game consists of simultaneous demands. Rogna (2017) proposes a related game of “burning coalitions” in which coalitions dissolve after partial disagreements, leading to points centrally located in the core (he calls this solution the mid-central core). Chander and Wooders (2020) investigates connections between perfect equilibria of extensive-form games and the core through the notion of the gamma-core. 3.4 Incomplete-information environments An important class of problems that is likely to receive much attention in the near future is that of environments with incomplete information. For this class, Forges and Serrano (2013) includes a treatment of different approaches related to the Nash program, as well as cooperation issues in noncooperative Bayesian games; see also a previous survey by Forges et al. (2002). Kalai and Kalai (2013) studies general issues of cooperation and competition in two-player strategic-form games and extends the analysis to a class of problems with 123