All Questions
Tagged with combinatorial-game-theory game-theory
56 questions
28
votes
7
answers
6k
views
Why is game theory formulated in terms of equilibrium instead of winning strategies?
Game theory, on the outset, seems to invite the questions,
"what can I do to win" or "how do I beat my opponent?"
So many people who are not familiar with game theory look to game ...
- 479
27
votes
4
answers
3k
views
Alice and Bob playing on a circle
I want to solve this problem:
Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:
Alice takes one ...
- 379
27
votes
1
answer
1k
views
Players alternate moving a $\{\swarrow,\uparrow,\rightarrow\}$ piece on a chessboard
Edit $4.$ $-$ Proposing to reopen the question (the related competition should be over by now).
Edit $3.$ $-$ I have just found out that the linked competition (see the "Edit $1$.") is still ...
- 611
22
votes
5
answers
3k
views
Irreversible chess
Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
- 223
21
votes
1
answer
825
views
Who wins the Rubik's cube game?
This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).
Solver and Spoiler take turns making 90 degree twists (starting with Solver). ...
- 6,403
20
votes
1
answer
1k
views
A Ramsey avoidance game
Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...
- 3,004
19
votes
5
answers
1k
views
When is a game tree the game tree of a board game?
This question arises from what I find interesting in the recently
asked question What is a chess piece
mathematically?
My answer to that question was that mathematically, game pieces are
in general ...
- 236k
18
votes
1
answer
1k
views
Removing pawns - the game
Here is a simple game I've invented (if the idea is not fresh, then please let me know):
The game is played on a board.
The board has some (finite) number of lines drawn on it.
A pawn is placed on ...
- 291
18
votes
2
answers
3k
views
Determine or estimate the number of maximal triangle-free graphs on $n$ vertices
Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...
user39815
17
votes
1
answer
2k
views
What does "game theory" cover and how should it be called?
There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things:
Combinatorial game theory dealing with certain ...
- 32.5k
16
votes
12
answers
11k
views
Are there any interesting connections between Game Theory and Algebraic Topology?
I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? ...
- 809
16
votes
1
answer
750
views
Is the game Hanabi NEXPTIME-complete?
The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards ...
- 10.1k
12
votes
1
answer
361
views
An averaging game on finite multisets of integers
The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...
- 50.8k
10
votes
2
answers
328
views
For which number of pairs is it an advantage to start in memory
Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned ...
- 883
10
votes
0
answers
386
views
For which set $A$, Alice has a winning strategy?
Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/for-which-set-a-alice-has-a-winning-strategy
Alice and Bob are playing a game. They take an integer $n>1$, and partition the ...
- 1,462
9
votes
1
answer
2k
views
Are there any interesting connections between game theory and engineering?
I am doing a senior project and it must be based off game theory, but I am having trouble finding any connections to engineering, possibly structural, or architectural, maybe even civil or mechanical. ...
- 93
9
votes
1
answer
389
views
Ordered Nim game
Consider the following variant of Nim:
There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$.
A move consists of removing a positive ...
- 91
8
votes
1
answer
230
views
Name of a game : Remove two chips from a vertex or one chip from both ends of an edge
Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a ...
- 17.9k
8
votes
2
answers
372
views
A game of singletons
Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:
Alice picks $m$ sets, each of which has $k$ items.
Bob colors some items in green.
Bob's score is the number ...
- 3,559
8
votes
0
answers
82
views
$2$-for-$2$ asymmetric Hex
This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...
- 181
7
votes
1
answer
572
views
JUSTICE & INJUSTICE — two 2-player finite games
There is a non-empty finite set $\ K,\ $ say, of plates. Initially, there are $\ p_0(k)\ $ stones on the $k$-th plate, where
$\ p_0(k)\in\mathbb Z_{_{\ge0}}\ $ for each $\ k\in K.$
So far, it is like ...
- 4,786
7
votes
2
answers
671
views
Determinacy of (infinite, possibly loopy) combinatorial games
I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...
- 32.5k
6
votes
1
answer
330
views
Anything known about the Grundy Ordinal of Sylver's Coinage
Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:
The two players take turns naming positive integers that are not the
sum of ...
- 6,403
5
votes
1
answer
475
views
Resources-Aware Combinatorial Game Theory
First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter).
Now the question:
**is there such a thing as the study of ...
- 7,853
5
votes
0
answers
306
views
Generalization of Sprague-Grundy Theorem
In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
- 1,129
5
votes
0
answers
216
views
Analysis of Nim-Like Game? [closed]
There are a finite number of heaps, each with a finite number of counters. Two players take turns; on each move, they may remove exactly one counter from any heap, and also, if the heap is of size $n$,...
- 151
4
votes
1
answer
1k
views
Who wins this two player game of making squares?
Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. ...
- 547
4
votes
2
answers
426
views
Study of Hex on the Torus
Hex is usually played on a parallelogram shaped board. What if you play it on a Torus?
One thing I notice is that the idea of connecting opposite sides doesn't make much sense anymore, since a torus ...
- 6,403
4
votes
1
answer
785
views
Nash Equilibrium in general graphical game
Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.
user39815
4
votes
1
answer
432
views
"Infinity": A card game based on prime factorization and a question
I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
- 3,144
4
votes
0
answers
180
views
Two-player item picking game
Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...
- 41
4
votes
0
answers
149
views
Combinatorial fairness property in division of goods
Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
- 388
3
votes
3
answers
2k
views
Motivation for the Sprague-Grundy theorem
The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.
What does the equivalence relation thus defined tell us ...
- 163
3
votes
2
answers
617
views
Negative of combinatorial game
I am having problem understanding what negative of a combinatorial game $G$ exactly means in combinatorial game theory. Does it mean that if I have normal game, if I create inverse, i.e., $-G = \{-G^R ...
- 31
3
votes
2
answers
209
views
A "Markov game"
I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $...
- 4,786
3
votes
1
answer
234
views
Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?
Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...
- 2,618
3
votes
2
answers
180
views
Satisfier-Falsifier games
In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...
- 3,559
3
votes
1
answer
337
views
Minimal Birthdays
In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.
Suppose we define the quasi-birthday ...
- 1,129
3
votes
1
answer
315
views
Difficulty of 3-color forest Hackenbush
"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...
- 32.5k
3
votes
0
answers
89
views
Projective plane finite game
This is a 2-person game.
Let $\ P\ $ be any arbitrary projective space (of any dimension $\ \ge2$ and any cardinality, etc., but typically, let it be a finite plane over a field). Let $\ S_0\subseteq ...
- 4,786
3
votes
0
answers
715
views
Nimbers and Surreal Numbers [closed]
I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...
- 1,129
2
votes
2
answers
1k
views
Generalized Sprague-Grundy Theorem
Hey,
I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
- 37
2
votes
3
answers
842
views
Simulating Mixed Nash Equilibria
I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.
Can someone please tell me how do I ...
- 213
2
votes
0
answers
309
views
Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy? [closed]
Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...
2
votes
0
answers
96
views
On subset of Deterministic games
Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...
- 13.9k
1
vote
2
answers
291
views
Do restricted Nim-like games have winning strategies?
Considering a Nim-like game to be:
There are three piles $A,B,C$, and the amount of their elements are $|A|=2, |B|=5, |C|=6$;
There are 2 players. Each time a player can either take $x (1\leq x \leq ...
1
vote
1
answer
135
views
Effective way to find Nash equilibrium
Is there any good algorithm for finding Nash equilibrium point, for one and repeated game theory? Thansk a lot for giving me some guidance.
- 781
1
vote
1
answer
168
views
Perturbation of the value of a general-sum game at a equilibirium
Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
- 1,127
1
vote
0
answers
132
views
Are gaps and loopy games interchangeable in the Surreal Numbers?
The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
1
vote
0
answers
136
views
Nim variant with minimum number of objects?
I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...
- 111