Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCumulative Games: Who is the current player?
74
0
0.0
(
0
)
Added by
Urban Larsson Dr
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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
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.
Zero-sum games have long guided artificial intelligence research, since they possess both a rich strategy space of best-responses and a clear evaluation metric. Whats more, competition is a vital mechanism in many real-world multi-agent systems capable of generating intelligent innovations: Darwinian evolution, the market economy and the AlphaZero algorithm, to name a few. In two-player zero-sum games, the challenge is usually viewed as finding Nash equilibrium strategies, safeguarding against exploitation regardless of the opponent. While this captures the intricacies of chess or Go, it avoids the notion of cooperation with co-players, a hallmark of the major transitions leading from unicellular organisms to human civilization. Beyond two players, alliance formation often confers an advantage; however this requires trust, namely the promise of mutual cooperation in the face of incentives to defect. Successful play therefore requires adaptation to co-players rather than the pursuit of non-exploitability. Here we argue that a systematic study of many-player zero-sum games is a crucial element of artificial intelligence research. Using symmetric zero-sum matrix games, we demonstrate formally that alliance formation may be seen as a social dilemma, and empirically that naive multi-agent reinforcement learning therefore fails to form alliances. We introduce a toy model of economic competition, and show how reinforcement learning may be augmented with a peer-to-peer contract mechanism to discover and enforce alliances. Finally, we generalize our agent model to incorporate temporally-extended contracts, presenting opportunities for further work.
Nash equilibrium is a central concept in game theory. Several Nash solvers exist, yet none scale to normal-form games with many actions and many players, especially those with payoff tensors too big to be stored in memory. In this work, we propose an approach that iteratively improves an approximation to a Nash equilibrium through joint play. It accomplishes this by tracing a previously established homotopy which connects instances of the game defined with decaying levels of entropy regularization. To encourage iterates to remain near this path, we efficiently minimize emph{average deviation incentive} via stochastic gradient descent, intelligently sampling entries in the payoff tensor as needed. This process can also be viewed as constructing and reacting to a polymatrix approximation to the game. In these ways, our proposed approach, emph{average deviation incentive descent with adaptive sampling} (ADIDAS), is most similar to three classical approaches, namely homotopy-type, Lyapunov, and iterative polymatrix solvers. We demonstrate through experiments the ability of this approach to approximate a Nash equilibrium in normal-form games with as many as seven players and twenty one actions (over one trillion outcomes) that are orders of magnitude larger than those possible with prior algorithms.
We study the problem of computing Stackelberg equilibria Stackelberg games whose underlying structure is in congestion games, focusing on the case where each player can choose a single resource (a.k.a. singleton congestion games) and one of them acts as leader. In particular, we address the cases where the players either have the same action spaces (i.e., the set of resources they can choose is the same for all of them) or different ones, and where their costs are either monotonic functions of the resource congestion or not. We show that, in the case where the players have different action spaces, the cost the leader incurs in a Stackelberg equilibrium cannot be approximated in polynomial time up to within any polynomial factor in the size of the game unless P = NP, independently of the cost functions being monotonic or not. We show that a similar result also holds when the players have nonmonotonic cost functions, even if their action spaces are the same. Differently, we prove that the case with identical action spaces and monotonic cost functions is easy, and propose polynomial-time algorithm for it. We also improve an algorithm for the computation of a socially optimal equilibrium in singleton congestion games with the same action spaces without leadership, and extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques, which computational experiments show to scale quite well.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
