Pareto efficiency,simple game stability,and social structure in finitely repeated games

Simple game (sensu Brown and Vincent, 1987) evolutionary theory, when coupled with social structure measured as non‐random encounter of strategy “clones”, often permits equilibrium refinement leading to Pareto superior outcomes (e.g., Axelrod, 1981; Myerson et al., 1991), a foundational goal of economic game theory (Myerson, 1991: 370–375). This conclusion, derived from analyses of one‐shot and infinitely repeated games, fails for finitely repeated games. While mutant cluster invasion enhances Pareto efficiency of equilibria in the former, it can depress Pareto efficiency in the latter. Cooperative equilibria of finitely repeated games (under economic analysis) can be susceptible to cluster‐invasion by even more Pareto efficient strategies which are not themselves evolutionarily stable. Evolutionary (simple) game theory's ability to eliminate Pareto inferior Nash equilibrium strategies induces vulnerabilities foreign to economic analysis. Simple game analysis of finitely repeated games suggests that social structure, modeled as perennial invasion by mutant‐clusters, can induce cyclic invasion, saturation, and loss of cooperation.     

Coalitions and payoffs in three‐person sequential games: Initial tests of two formal models

In this paper we develop two formal models predicting coalitions and payoffs among rank striving players in a sequential three‐person game. We test the models’ predictions with data from a laboratory study of eleven male triads. Each triad plays a sequence of games; in each game a two‐person coalition forms and divides the coalition's point value between the two coalition partners. Participants know that the sequence of games will end without warning at a randomly chosen time; at the sequence's end each player's monetary payoff is a linear function of the rank of his accumulated point score, relative to those of the other members of his triad. The complexity of this situation prevents players and analysts from representing it as a single game; thus they are unable to use n‐person game theory to identify optimal strategies. Consequently, we assume that players, unable to develop strategies that are demonstrably optimal in the long run, adopt certain bargaining heuristics and surrogate short run objectives.

The two models follow the same basic outline; they differ, however, in the planning horizon they assume players to use. Proceeding from a priori assumptions concerning each player's decision calculus and the bargaining process, the two models state the probability that each coalition forms and predict the point divisions in the winning coalition. The laboratory data provide consistently strong support for the predictions of both models.     

N‐person Prisoner's Dilemma†

Multi‐person versions of Prisoner's Dilemma are widely applicable in the social sciences. Examination of two important classes of real‐world situations reveals that although both can appropriately be called Prisoner's Dilemma, they have incompatible payoff structures. Thus Prisoner's Dilemma games constitute an important but apparently ambiguous set of models.

We therefore undertake a taxonomy of multi‐person Prisoner's Dilemma. Some aspects of the well‐studied two‐person case provide a useful beginning for the task. In the general multi‐person form, however, some properties of the two‐person game are found incompatible with others and so are dropped. Additional properties are suggested by strategic considerations and the associated social phenomena. We demonstrate interdependencies among the various properties and relate some of them to a simple graphical representation.     

On the optimality of the uniform random strategy

Biased Maker‐Breaker games, introduced by Chvátal and Erd?s, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container‐type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H‐building games studied by Bednarska and ?uczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Efficient Winning Strategies in Random‐Turn Maker–Breaker Games

We consider random‐turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A p‐random‐turn positional game is a two‐player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is p ). We analyze the random‐turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erd?s in 1987), the Hamilton cycle game and the k‐vertex‐connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of p for which he typically wins the game, assuming optimal strategies of both players.     

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC‐nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC‐nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC‐nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC‐net rules. We present read‐once MC‐nets, a new class of MC‐nets that is provably more compact than basic MC‐nets, while retaining the attractive computational properties of basic MC‐nets. We show how the techniques we develop for read‐once MC‐nets can be applied to other domains, in particular, computing solution concepts in network flow games on series‐parallel networks (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

New equilibria for noncooperative two‐person games

New equilibrium concepts for noncooperative two‐person games are introduced and examined. Although these equilibria coincide with the Nash equilibria in all constant‐sum games, they differ significantly in other cases. In particular, for finite repetitions of the prisoner's dilemma, some cooperating strategy combinations become equilibria.     

Assignment games,chromatic number,and exchange theory

The exchange networks that social psychologists have studied can usefully be represented as game theoretic 2‐sided assignment games. Conceiving of these networks as 2‐sided assignment games opens up the possibility of studying N‐sided assignment games and games without cores. 2‐sided assignment games are special in that they always have cores, stable solutions in which every individual and subgroup behave rationally.

The implicit assignment of positions to categories of an N‐sided assignment game is related to coloring a graph. The color classes form sets of positions with potentially related interests. Color equivalence is compared to structural, regular, automorphic, and ecological positional equivalence.     

N-person Nim andn-person Moore's Games

We present one way of definingn-person perfect information games so that there is a reasonable outcome for every game. In particular, the theory of Nim and Moore's games is generalized ton-person games.     

Biased games on random boards

In this paper we analyze biased Maker‐Breaker games and Avoider‐Enforcer games, both played on the edge set of a random board . In Maker‐Breaker games there are two players, denoted by Maker and Breaker. In each round, Maker claims one previously unclaimed edge of G and Breaker responds by claiming b previously unclaimed edges. We consider the Hamiltonicity game, the perfect matching game and the k‐vertex‐connectivity game, where Maker's goal is to build a graph which possesses the relevant property. Avoider‐Enforcer games are the reverse analogue of Maker‐Breaker games with a slight modification, where the two players claim at least 1 and at least b previously unclaimed edges per move, respectively, and Avoider aims to avoid building a graph which possesses the relevant property. Maker‐Breaker games are known to be “bias‐monotone”, that is, if Maker wins the (1,b) game, he also wins the game. Therefore, it makes sense to define the critical bias of a game, b ^*, to be the “breaking point” of the game. That is, Maker wins the (1,b) game whenever and loses otherwise. An analogous definition of the critical bias exists for Avoider‐Enforcer games: here, the critical bias of a game b ^* is such that Avoider wins the (1,b) game for every , and loses otherwise. We prove that, for every is typically such that the critical bias for all the aforementioned Maker‐Breaker games is asymptotically . We also prove that in the case , the critical bias is . These results settle a conjecture of Stojakovi? and Szabó. For Avoider‐Enforcer games, we prove that for , the critical bias for all the aforementioned games is . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,651–676, 2015     

A complete analysis of Black-White Hackendot

RecentlyÚlehla [1980] gave a complete analysis of an impartial two-person combinatorial game called Hackendot which was invented by von Neumann. In this note we consider a partizan (or unimpartial) variation of Hackendot. Úlehla's analysis uses the Sprague-Grundy theory for disjunctive sums of impartial games. Our analysis employs Conway's theory for disjunctive sums of partizan games, two certain “biased” ways of “adding” dyadic rationals, and the usual addition of numbers.     

Formal verification of tail distribution bounds in the HOL theorem prover

Tail distribution bounds play a major role in the estimation of failure probabilities in performance and reliability analysis of systems. They are usually estimated using Markov's and Chebyshev's inequalities, which represent tail distribution bounds for a random variable in terms of its mean or variance. This paper presents the formal verification of Markov's and Chebyshev's inequalities for discrete random variables using a higher‐order‐logic theorem prover. The paper also provides the formal verification of mean and variance relations for some of the widely used discrete random variables, such as Uniform(m), Bernoulli(p), Geometric(p) and Binomial(m, p) random variables. This infrastructure allows us to precisely reason about the tail distribution properties and thus turns out to be quite useful for the analysis of systems used in safety‐critical domains, such as space, medicine or transportation. For illustration purposes, we present the performance analysis of the coupon collector's problem, a well‐known commercially used algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

A GAME-THEORETIC PROOF OF ANALYTIC RAMSEY THEOREM

We give a simple game-theoretic proof of Silver's theorem that every analytic set is Ramsey. A set P of subsets of ω is called Ramsey if there exists an infinite set H such that either all infinite subsets of H are in P or all out of P. Our proof clarifies a strong connection between the Ramsey property of partitions and the determinacy of infinite games.     

Monotonicity of the core and value in dynamic cooperative games

We examine behavior of the core and value of certain classes of cooperative games in which a dynamic aspect is introduced. New players are added to the games while the underlying structure is held constant. This is done by considering games that satisfy properties like convexity, or games that are derived from optimization problems in which a player's addition can be defined naturally. For such games we give conditions regarding monotonicity of the core and value.     

The emergence of cooperation in tie strength models

In this paper, we propose a tie strength model to explain the emergence of cooperation in spatial prisoner's dilemma games, assuming that cooperators preferentially allocate their investments to friends with strong ties. Two types of prisoner's dilemma models are examined in this study: the traditional two-strategy model considering only cooperators and defectors; the expanded three-strategy model consisting cooperators, defectors and extortioners. The results show that tie strength model contributes to the promotion of cooperation in both types of prisoner's dilemma games. However, we point out that the influence of the investment preference is quite different in the two prisoner's dilemma game settings. In the two-strategy prisoner's dilemma game, only small preference contributes to the promotion of cooperation. Once this preference exceeds a critical value, cooperation will be prohibited. We explain this phenomenon by arguing that extremely strong investment preference undermines the ability of cooperative clusters to resist defectors. Moreover, we extend the analysis into the three-strategy case and discover that the catalytic effect of extortioners can eliminate this first up and then down trend in the two-strategy model. The equilibrium fraction of cooperators is always positively correlated to the level of investment preference in three-strategy models.     

Digital game‐based learning for K–12 mathematics education: A meta‐analysis

Digital games (e.g., video games or computer games) have been reported as an effective educational method that can improve students' motivation and performance in mathematics education. This meta‐analysis study (a) investigates the current trend of digital game‐based learning (DGBL) by reviewing the research studies on the use of DGBL for mathematics learning, (b) examines the overall effect size of DGBL on K‐12 students' achievement in mathematics learning, and (c) discusses future directions for DGBL research in the context of mathematics learning. In total, 296 studies were collected for the review, but of those studies, only 33 research studies were identified as empirical studies and systematically analyzed to investigate the current research trends. In addition, due to insufficient statistical data, only 17 out of the 33 studies were analyzed to calculate the overall effect size of digital games on mathematics education. This study will contribute to the research community by analyzing recent trends in significant DGBL research, especially for those who are interested in using DGBL for mathematics education.     

On Burenkov's extension operator preserving Sobolev–Morrey spaces on Lipschitz domains

We prove that Burenkov's extension operator preserves Sobolev spaces built on general Morrey spaces, including classical Morrey spaces. The analysis concerns bounded and unbounded open sets with Lipschitz boundaries in the n‐dimensional Euclidean space.     

Regular simple games

Using Kelley's intersection number (and a variant of it) we define two classes of simple games, the regular and the strongly regular games. We show that the strongly regular games are those in which the set of winning coalitions and the set of losing coalitions can be strictly separated by a finitely additive probability measure. This, in particular, provides a combinatorial characterization for the class of finite weighted majority games within the finite simple games. We also prove that regular games have some nice properties and show that the finite regular games are exactly those simple games which are uniquely determined by their counting vector. This, in particular, generalizes a result of Chow and Lapidot.     

Action learning versus strategy learning

This article seeks to ascertain whether the strategy‐learning model of Hanaki, Sethi, Erev, and Peterhansl (2003) better accounts for observed behavior than do the various action‐learning models. It does so by measuring the goodness‐of‐fit of the models' predictions against published experimental results for such games as Coordination, Prisoner's Dilemma, and Chicken. The fit is measured via the mean squared deviation (MSD) between the observed behavior and the one predicted by the model. The results show that, for Chicken, the strategy‐learning model fits the observed data much better than do the action‐learning models. The best action‐learning model, on the other hand, fits the observed data well in Coordination. Overall, the strength of the strategy‐learning model is best shown in games where alternations between the two stage‐game Nash equilibria are often observed in the laboratory experiments. © 2004 Wiley Periodicals, Inc. Complexity 9: 41–50, 2004