Search

In this article, we study the achievement of polytechnic higher education students in exploring a random game, considering the following objectives: 1) evaluate students' performance in exploring the game, and 2) identify students' difficulties in exploring the game. The study included 49 students attending an engineering course's 2nd or 3rd year at a higher education institution in northern Portugal. The data resulted from students solving several tasks about random games in a brief questionnaire, with only one of these tasks being studied here. From the results obtained, it is worth noting that the students performed unsatisfactorily in exploring the game, which resulted in several student difficulties, namely by not explaining the origin of the values they presented, by determining incorrect probabilities, and by making other errors, such as are errors in calculation and interpretation of what was requested. Therefore, given the unsatisfactory results of the study, it is essential to deepen the training of students regarding the definition, understanding, and application of the notion of random game. To this end, exploring random games in the classroom can improve student achievement since they are rarely explored there. [ABSTRACT FROM AUTHOR]

We consider finite two-player normal form games with random payoffs. Player A's payoffs are i.i.d. from a uniform distribution. Given p ∈ [ 0 , 1 ] , for any action profile, player B's payoff coincides with player A's payoff with probability p and is i.i.d. from the same uniform distribution with probability 1 − p. This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive p , asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability. [ABSTRACT FROM AUTHOR]

We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence—the order in which players update their actions—is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games. [ABSTRACT FROM AUTHOR]

We calculate the frequency of games with a unique pure strategy Nash equilibrium in the ensemble of n-player, m-strategy normal-form games. To obtain the ensemble, we generate payoff matrices at random. Games with a unique pure strategy Nash equilibrium converge to the Nash equilibrium. We then consider a wider class of games that converge under a best-response dynamic, in which each player chooses their optimal pure strategy successively. We show that the frequency of convergent games with a given number of pure Nash equilibria goes to zero as the number of players or the number of strategies goes to infinity. In the 2-player case, we show that for large games with at least 10 strategies, convergent games with multiple pure strategy Nash equilibria are more likely than games with a unique Nash equilibrium. Our novel approach uses an n-partite graph to describe games. [ABSTRACT FROM AUTHOR]

An experiment was conducted on a sample of 5 0 0 randomly generated symmetric bimatrix games with size 1 2 and 1 5. Distribution of support sizes and Nash equilibria are used to formulate a conjecture: for finding a symmetric NEP it is enough to check supports up to size 4 whereas for nonsymmetric and all NEPs this number is 3 and 2 , respectively. If true, this enables us to use a Las Vegas algorithm that finds a Nash equilibrium in polynomial time with high probability. [ABSTRACT FROM AUTHOR]

We study point-rationalizable and rationalizable strategies in random games. In a random n × n symmetric game, an explicit formula is derived for the distribution of the number of point-rationalizable strategies, which is of the order n in probability as n → ∞. The number of rationalizable strategies depends on the payoff distribution, and is bounded by the number of point-rationalizable strategies (lower bound), and the number of strategies that are not strictly dominated by a pure strategy (upper bound). Both bounds are tight in the sense that there exists a payoff distribution such that the number of rationalizable strategies reaches the bound with a probability close to one. We also show that given a payoff distribution with a finite third moment, as n → ∞ , all strategies are rationalizable with probability one. Our results qualitatively extend to two-player asymmetric games, but not to games with more than two players. [ABSTRACT FROM AUTHOR]

The analysis of equilibrium points in random games has been of great interest in evolutionary game theory, with important implications for understanding of complexity in a dynamical system, such as its behavioural, cultural or biological diversity. The analysis so far has focused on random games of independent payoff entries. In this paper, we overcome this restrictive assumption by considering multiplayer two-strategy evolutionary games where the payoff matrix entries are correlated random variables. Using techniques from the random polynomial theory, we establish a closed formula for the mean numbers of internal (stable) equilibria. We then characterise the asymptotic behaviour of this important quantity for large group sizes and study the effect of the correlation. Our results show that decreasing the correlation among payoffs (namely, of a strategist for different group compositions) leads to larger mean numbers of (stable) equilibrium points, suggesting that the system or population behavioural diversity can be promoted by increasing independence of the payoff entries. Numerical results are provided to support the obtained analytical results. [ABSTRACT FROM AUTHOR]

The analysis of equilibrium points is of great importance in evolutionary game theory with numerous practical ramifications in ecology, population genetics, social sciences, economics and computer science. In contrast to previous analytical approaches which primarily focus on computing the expected number of internal equilibria, in this paper we study the distribution of the number of internal equilibria in a multi-player two-strategy random evolutionary game. We derive for the first time a closed formula for the probability that the game has a certain number of internal equilibria, for both normal and uniform distributions of the game payoff entries. In addition, using Descartes' rule of signs and combinatorial methods, we provide several universal upper and lower bound estimates for this probability, which are independent of the underlying payoff distribution. We also compare our analytical results with those obtained from extensive numerical simulations. Many results of this paper are applicable to a wider class of random polynomials that are not necessarily from evolutionary games. [ABSTRACT FROM AUTHOR]

We consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. Our proposed algorithm is a modified Fictitious Play algorithm that can be implemented distributedly, and its stable points are the pure Nash equilibria of a given game. Our goal is to design a utility function for a non-cooperative game, such that all of its pure Nash equilibria have close to optimal global performance. This will make the algorithm close to optimal while requiring no communication between users. We propose a novel technique to analyze the Nash equilibria of a random interference game, determined by the random channel gains. Our analysis is asymptotic in the number of users. First, we present a natural non-cooperative game where the utility of each user is his achievable rate. It is shown that, asymptotically in the number of users and for strong enough interference, this game exhibits many bad equilibria. Then, we propose a novel non-cooperative M frequency-selective interference channel game as a slight modification of the former, where the utility of each user is artificially limited. We prove that even its worst equilibrium has asymptotically optimal weighted sum rate for any interference regime and even for correlated channels. This is based on an order statistics analysis of the fading channels that is valid for a broad class of fading distributions (including Rayleigh, Rician, m-Nakagami, and more). We carry out simulations that show fast convergence of our algorithm to the proven asymptotically optimal pure Nash equilibria. [ABSTRACT FROM AUTHOR]

Given a skew-symmetric matrix, the corresponding two-player symmetric zero-sum game is defined as follows: one player, the row player, chooses a row and the other player, the column player, chooses a column. The payoff of the row player is given by the corresponding matrix entry, the column player receives the negative of the row player. A randomized strategy is optimal if it guarantees an expected payoff of at least 0 for a player independently of the strategy of the other player. We determine the probability that an optimal strategy randomizes over a given set of actions when the game is drawn from a distribution that satisfies certain regularity conditions. The regularity conditions are quite general and apply to a wide range of natural distributions. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the mean number $$E(n,d)$$ of internal equilibria in a general $$d$$ -player $$n$$ -strategy evolutionary game where the agents' payoffs are normally distributed. First, we give a computationally implementable formula for the general case. Next, we characterize the asymptotic behavior of $$E(2,d)$$ , estimating its lower and upper bounds as $$d$$ increases. Then we provide a closed formula for $$E(n,2)$$ . Two important consequences are obtained from this analysis. On the one hand, we show that in both cases, the probability of seeing the maximal possible number of equilibria tends to zero when $$d$$ or $$n$$ , respectively, goes to infinity. On the other hand, we demonstrate that the expected number of stable equilibria is bounded within a certain interval. Finally, for larger $$n$$ and $$d$$ , numerical results are provided and discussed. [ABSTRACT FROM AUTHOR]

Abstract: The formula given by McLennan [The mean number of real roots of a multihomogeneous system of polynomial equations, Amer. J. Math. 124 (2002) 49–73] is applied to the mean number of Nash equilibria of random two-player normal form games in which the two players have M and N pure strategies respectively. Holding M fixed while , the expected number of Nash equilibria is approximately . Letting , the expected number of Nash equilibria is , where is a constant, and almost all equilibria have each player assigning positive probability to approximately 31.5915 percent of her pure strategies. [Copyright &y& Elsevier]

An Astumian game is defined by a finite Markov chain with state space S with precisely two absorbing states, the winning and the losing state. The other states are transient, one of them is the starting position. The game is said to be losing (respectively fair respectively winning) if the probability to be absorbed at the winning state is smaller than 0.5 (respectively = 0.5 respectively larger than 0.5). Astumian's paradox states that there are losing games on the same state space S a stochastic mixture of which is winning. (By "stochastic mixture" we mean that in each step one decides with the help of a fair coin whether to use the transition probabilities of the first or the second game.) Most of our results concern fair games. Mixtures are systematically investigated. Rather surprisingly, the winning probability of the mixture of fair games can be arbitrarily close to zero (or to one). Even more counter-intuitive are examples of definitely losing games (this means that the winning probability is exactly zero) such that the winning probability of the mixture is arbitrarily close to one. We show, however, that such extreme examples are possible only if one tolerates huge running times of the game. As a natural generalization one can also consider arbitrary mixtures: the fair coin is replaced by a biased one, with probability λ respectively 1-λ one plays with the first respectively the second game. It turns out that fair games exist such that — depending on the choice of λ — the λ-mixture can be fair, losing or winning. [ABSTRACT FROM AUTHOR]

Fix finite pure strategy sets S1,…,Sn, and let S1 = × … × Sn. In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in Rs. For given nonempty T1 ⊂ S1,…, Tn ⊂ Sn we give a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support Ti. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets Ti. The second may be construed as the "probability" that such an equilibrium remains an equilibrium when the strategies in the sets Si \ Ti become available. [ABSTRACT FROM AUTHOR]

We discuss some aspects of Astumian suggestions that combination of biased games (Parrondo's paradox) can explain performance of molecular motors. Unfortunately the model is flawed by explicit asymmetry overlooked by the author. In addition, we show that the paradoxical behaviour of Parrondo games can be compensated by adjusting the stakes (e.g. by introducing compensatory payments). [ABSTRACT FROM AUTHOR]

I give a simple analysis of the game that I previously published in Scientific American which shows the paradoxical behavior whereby two losing games randomly combine to form a winning game. The game, modeled on a random walk, requires only two states and is described by a first-order Markov process. [ABSTRACT FROM AUTHOR]

Copyright of OR Spectrum is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We point out that the analysis of Piotrowski and Sladkowski of the paradox described by Astumian has a flaw since they consider a different game. [ABSTRACT FROM AUTHOR]

It is already known that two simple losing games can derive a winning game when randomly combined. This special behaviour is known as Parrondo's Paradox, or the Parrondo effect. In this paper we estimate the volume of the parameter space that determines the Parrondo effect. In other words, how often two randomly chosen games are losing while their proper combination is leading to a winning game. Results for a typical class of relevant games indicate that the Parrondo effect is very unusual, because it appears with a probability of 0.0306%. By adding two more dimensions to the parameter space, the family of regions that exhibit the Parrondo effect is studied. [ABSTRACT FROM AUTHOR]