Search · four archives
Search · four archives
14 papers · ranked by Valyu relevance
Alistair Benford, Per Kristian Lehre
Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). However, the successful application of CoEAs for game playing is difficult due to pathological…
Stephen Fenner, John A. Rogers
Poset games have been the object of mathematical study for over a century, but little has been written on the computational complexity of determining important properties of these games. In this introduction we develop the fundamentals of combinatorial game theory and focus for the most part on poset games, of which…
Hiyu Inoue, Shin-nosuke Kadowaki, Shun-ichi Kimura, Haruki Wada
We consider Subtraction Nim, where two players have exactly the same options, but which is partizan in the sense that at the game ending, a partizan rule is applied for the decision of the winner. We consider the following example: Let $S$ be the set of removable numbers, which is a non-empty finite subset of positive…
Koki Suetsugu
In this paper, we considered impartial games on a simplicial complex. Each vertex of a given simplicial complex acts as a position of an impartial game. Each player in turn chooses a face of the simplicial complex and, for each position on each vertex of that face, the player can make an arbitrary number of moves.…
Kyle Burke, Matthew Ferland, Shang‐Hua Teng
The concept of nimbers—a.k.a. Grundy-values or nim-values—is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games…
Hashimoto, Kengo
A combinatorial game is a two-player game without hidden information or chance elements. The main object of combinatorial game theory is to obtain the outcome, which player has a winning strategy, of a given combinatorial game. Positions of many well-known combinatorial games are naturally decomposed into a disjunctive…
Javier Cembrano, Felix Fischer, Max Klimm
We study mechanisms that select a subset of a set of agents based on nominations among them. The goal is to maximize the minimum number of nominations received by any selected agent, subject to an impartiality constraint that the selection of a particular agent must be independent of the nominations cast by that agent.…
Daniel Rehsmann
We address the optimal allocation of stochastically dependent resource bundles to a set of simultaneous contests. For this purpose, we study a modification of the Colonel Blotto Game called the Tennis Coach Problem. We devise a thoroughly probabilistic method of payoff representation and fully characterize equilibria…
Itai Maimon
We construct several definitions of imbalance and playability, both of which are related to the existence of dominated strategies. Specifically, a maximally balanced game and a playable game cannot have dominated strategies for any player. In this context, imbalance acts as a measure of inequality in strategy, similar…
Andreas Darmann, Gaia Nicosia, Ulrich Pferschy, Joachim Schauer
Title: Highlights 1. • A game theoretic version of the Subset Sum problem is considered. 2. • Two agents take turns to fill a shared knapsack with their items. 3. • Natural heuristic strategies are proposed and analyzed from a worst-case perspective.
Oliver Biggar, Iman Shames
In this paper, we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly…
Matthew C. King, Noah A. Rosenberg
How many ways are there to arrange the sequence of games in a single-elimination sports tournament? We consider the connection between this enumeration problem and the enumeration of “labeled histories,” or sequences of asynchronous branching events, in mathematical phylogenetics. The possibility of playing multiple…
Benjamin James Dyson, Cecile Musgrave, Cameron Rowe, Rayman Sandhur
To examine the behavioural and neural interactions between objective and subjective performance during competitive decision-making, participants completed a Matching Pennies game where win-rates were fixed within three conditions (win > lose, win = lose, win < lose) and outcomes were predicted at each trial. Using…
Anton M. Unakafov, Thomas Schultze, Igor Kagan, Sebastian Möller + 2 more
Real-world agents, such as humans, animals and robots, observe each other during interactions and choose their own actions taking the partners’ ongoing behaviour into account. Yet, classical game theory assumes that players act either strictly sequentially or strictly simultaneously (without knowing the choices of each…