Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSingle-Player and Two-Player Buttons & Scissors Games
158
0
0.0
(
0
)
Added by
Kyle Burke
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the computational complexity of the Buttons & Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for $C = 2$ colors but polytime solvable for $C = 1$. Similarly the game is NP-complete if every color is used by at most $F = 4$ buttons but polytime solvable for $F leq 3$. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-play
rate research
Read More
Combinatorial Game Theory (CGT) is a branch of game theory that has developed almost independently from Economic Game Theory (EGT), and is concerned with deep mathematical properties of 2-player 0-sum games that are defined over various combinatorial structures. The aim of this work is to lay foundations to bridging the conceptual and technical gaps between CGT and EGT, here interpreted as so-called Extensive Form Games, so they can be treated within a unified framework. More specifically, we introduce a class of $n$-player, general-sum games, called Cumulative Games, that can be analyzed by both CGT and EGT tools. We show how two of the most fundamental definitions of CGT---the outcome function, and the disjunctive sum operator---naturally extend to the class of Cumulative Games. The outcome function allows for an efficient equilibrium computation under certain restrictions, and the disjunctive sum operator lets us define a partial order over games, according to the advantage that a certain player has. Finally, we show that any Extensive Form Game can be written as a Cumulative Game.
Nonlocality, one of the most remarkable aspects of quantum mechanics, is closely related to Bayesian game theory. Quantum mechanics can offer advantages to some Bayesian games, if the payoff functions are related to Bell inequalities in some way. Most of these Bayesian games that have been discussed are common interest games. Recently the first conflicting interest Bayesian game is proposed in Phys. Rev. Lett. 114, 020401 (2015). In the present paper we present three new conflicting interest Bayesian games where quantum mechanics offers advantages. The first game is linked with Cereceda inequalities, the second game is linked with a generalized Bell inequality with 3 possible measurement outcomes, and the third game is linked with a generalized Bell inequality with 3 possible measurement settings.
We consider a scenario in which two reinforcement learning agents repeatedly play a matrix game against each other and update their parameters after each round. The agents decision-making is transparent to each other, which allows each agent to predict how their opponent will play against them. To prevent an infinite regress of both agents recursively predicting each other indefinitely, each agent is required to give an opponent-independent response with some probability at least epsilon. Transparency also allows each agent to anticipate and shape the other agents gradient step, i.e. to move to regions of parameter space in which the opponents gradient points in a direction favourable to them. We study the resulting dynamics experimentally, using two algorithms from previous literature (LOLA and SOS) for opponent-aware learning. We find that the combination of mutually transparent decision-making and opponent-aware learning robustly leads to mutual cooperation in a single-shot prisoners dilemma. In a game of chicken, in which both agents try to manoeuvre their opponent towards their preferred equilibrium, converging to a mutually beneficial outcome turns out to be much harder, and opponent-aware learning can even lead to worst-case outcomes for both agents. This highlights the need to develop opponent-aware learning algorithms that achieve acceptable outcomes in social dilemmas involving an equilibrium selection problem.
In this paper we introduce novel algorithmic strategies for effciently playing two-player games in which the players have different or identical player roles. In the case of identical roles, the players compete for the same objective (that of winning the game). The case with different player roles assumes that one of the players asks questions in order to identify a secret pattern and the other one answers them. The purpose of the first player is to ask as few questions as possible (or that the questions and their number satisfy some previously known constraints) and the purpose of the secret player is to answer the questions in a way that will maximize the number of questions asked by the first player (or in a way which forces the first player to break the constraints of the game). We consider both previously known games (or extensions of theirs) and new types of games, introduced in this paper.
In 2002, Benjamin Jourdain and Claude Martini discovered that for a class of payoff functions, the pricing problem for American options can be reduced to pricing of European options for an appropriately associated payoff, all within a Black-Scholes framework. This discovery has been investigated in great detail by Soren Christensen, Jan Kallsen and Matthias Lenga in a recent work in 2020. In the present work we prove that this phenomenon can be observed in a wider context, and even holds true in a setup of non-linear stochastic processes. We analyse this problem from both probabilistic and analytic viewpoints. In the classical situation, Jourdain and Martini used this method to approximate prices of American put options. The broader applicability now potentially covers non-linear frameworks such as model uncertainty and controller-and-stopper-games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
