The study of competitive and non-competitive games, equilibrium concepts such as Nash equilibrium, and related subjects. Combinatorial games such as Nim are under [tag:combinatorial-game-theory], and algorithmic aspects (e.g. auctions) are under [tag:algorithmic-game-theory].

learn more… | top users | synonyms

45
votes
0answers
825 views

The Right Triangle Game

I am looking for a deeper understanding, particularly the optimum strategy and the maximum score as a function of grid size, of the following (single-player) game played with an $n$ by $m$ grid: ($6 ...
14
votes
0answers
456 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
10
votes
0answers
121 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
9
votes
0answers
158 views

Is there a totally asymmetric 2P $0$-sum game with all payoffs $\pm1$, with a unique Nash eq. which assigns positive probability to each strategy?

Is there a totally asymmetric 2-player zero-sum game with all payoffs $\pm1$, with a unique Nash equilibrium which assigns positive probability to each strategy? By totally asymmetric, I mean that ...
6
votes
0answers
82 views

Progressive Dice Game

You have a fair, regular 6-sided dice. The game is played for $n$ turns. Each turn you make a roll and gain that many points the rolled side is showing, then do one of the following: ...
6
votes
0answers
74 views

Game, stealing edges in a graph.

I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows: Alice and Bob play a game. ...
6
votes
0answers
58 views

Undetermined game of length $\omega_1+\omega$, without choice

On the following page, Taranovsky is talking about his "Determinacy Maximum" axiom: http://web.mit.edu/dmytro/www/DeterminacyMaximum.htm He also justifies the choice of the name, by pointing out that ...
6
votes
0answers
115 views

Fastest way to meet, without communication, in a toroidal palace?

I was interested by a similar question asked here, but wanted to pose a slightly different variant that avoids some of the pitfalls and ambiguities in the first question in order to ask something more ...
6
votes
0answers
145 views

Guess the number of a liar

Sue picks a number from 0 to 3. Tom asks questions about the number, with yes/no answers. For example, "Is it odd" or "Is it 3?" If Sue picked X, she is allowed to lie at most X times. For example,...
6
votes
0answers
116 views

Apple game question

Player A and Player B play a game. On the middle of the table there is a pot full of $N$ apples of different weights. Player A starts first and chooses an apple and starts eating it. Losing no time ...
5
votes
0answers
204 views

Cutting a Banach-Tarski Cake

I was reading a cake-cutting problem here (not really related, so I won't link to it), and for some reason, this variation occurred to me. I have no idea whether this problem is even well-formed: ...
5
votes
0answers
73 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
4
votes
0answers
34 views

Optimal strategy in an idealized dating scenario

The question I have is in some ways a variation on the stable marriage problem adapted to the situation of dating. Suppose there are $n$ boys and $n$ girls, where every boy ranks the girls from $1$ ...
4
votes
0answers
190 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
4
votes
0answers
55 views

A Game Between a Panda and a Polar Bear

I've been working on some problems related to Bayesian games, and I reached this dynamic game that I have been having some problems with. Consider a game where a polar bear and panda bear are choosing ...
4
votes
0answers
161 views

Is there a closed-form expression for Shapley value of glove game?

Suppose we have a coalition game with transferable utilities, with $m$ players having a right-handed glove and $n$ players having a left-handed glove. The value of a coalition is equal to the number ...
4
votes
0answers
109 views

StackEgg optimal algorithm

What is the minimum number of days that is needed to complete the StackEgg game? (It's on the right if anyone didn't notice.) There are four markers (Questions, Answers, Users, Quality) I believe each ...
4
votes
0answers
573 views

What is the highest possible score in 2048 hard?

There is a variant of the popular game 2048, called 2048 hard or 2048 impossible, which automatically places each new tile in the hardest possible location. Is this variation possible to solve, and if ...
4
votes
0answers
153 views

algebraic or homotopical proof for Kakutani fixed point theorem

As Kakutani fixed point theorem is a genral case of Brouwer fixed point theorem, and one can read the proof from homotopy theory books. I wonder if there is any proof for the Kakutani using homotopy ...
4
votes
0answers
96 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
0answers
195 views

Understanding Blackwell's Approachability Theorem

I'm not super solid on my linear algebra, so I am getting lost in the discussions of halfspaces. Can someone give me an intuitive explanation (possibly with a concrete toy problem) of Blackwell's ...
3
votes
0answers
103 views

Mathematical game with numbers

We invented a mathematical game, which i am going to explain here. The first player choose a natural number, lets call it $n$ (if you play it for real, you must choose a sufficiently big number so ...
3
votes
0answers
72 views

A simple betting game

Consider the following betting game: Two players each have 100 cents to bet. If one player bets more than the other then that player gains a point and the other player loses a point. The goal of the ...
3
votes
0answers
69 views

Prisoner's Dilemma and Centipede Game - what's wrong with this analysis?

This is an analysis which to me seems trivial, but which I very rarely see brought up in any discussion of games like The Prisoner's Dilemma or The Centipede Game which are well known for having '...
3
votes
0answers
65 views

Compute shooting targets for the gunmen

This is an extension of the well known "3 gunmen puzzle": N gunmen with hitting probabilities in (0,1] take turns to shoot at each other. Firing order is fixed (gunman 1 shoots first, then gunman ...
3
votes
0answers
53 views

Prove that the set of $(m \times n)$-matrix games is dense and open

Show that the set of $(m \times n)$-matrix games with unique optimal strategies is dense and open. Let $\mathbb{R}^{nm}$ be a $nm$-vector space of all matrix games and let $M \subset \mathbb{R}^{...
3
votes
0answers
99 views

Auction Design : Multiple lots, one win max per bidder, not regret

This is a real life game theory problem. I have to organize an auction. There is a finite number of lots, which are not equivalent. There is a finite number of bidders; the number of bidders is ...
3
votes
0answers
84 views

Should I maximize points in the beginning of a long match?

I have a question that may really be about mathematical modelling as much as math itself, but I will try to give it a formulation suited for this site. Suppose that I am going to play some game, $G$,...
3
votes
0answers
124 views

Approximate the unit ball in an infinite-dimensional Hilbert space, by compact sets?

Are there some common ways to approximate the unit ball in an infinite-dimensional Hilbert space, by compact sets? (note that the unit ball isn't compact.) My goal is to prove a statement which holds ...
3
votes
0answers
60 views

Simple undetermined games

We know that, under AC, there exists a game in which two players play finite numbers and neither one has winning strategy. There are also such undetermined games when we consider players playing ...
3
votes
0answers
117 views

Maximizing dot-product score by asking queries

Let $a>b>0$, and let $T=\{a,b\}^n$ be the set of all $n$-tuples each entry of which is $a$ or $b$. Let $X\subseteq\{0,1\}^n$ with $|X|>1$, and let $f:T\rightarrow X$ be a function. For each $\...
3
votes
0answers
61 views

Simple Dice Game - Optimal Mixed Strategy

Just started an introductory course in game theory, and here is a problem we have been talking about. So here is the description of the game. Two players, each player starts by placing \$1 each into ...
3
votes
0answers
35 views

Minimum number of steps to guess an item in a database given a liar

Let's say I have a database of $N\times N$ size ($N$ rows and $N$ columns). My friend wants me to guess the location of an item. We start by binary guess, meaning I ask him if it is in upper half and ...
3
votes
0answers
90 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
3
votes
0answers
49 views

Decisive equivalence of collections of probability measures

Working on the optimal decision theory in stochastic setting, I've found out that the following notion of equivalence is very useful. Let $(X,\mathscr A)$ be a measurable space, and let $\mathrm b\...
3
votes
0answers
67 views

Terminology questions about a game where one may “save his progress” at the cost of a turn.

The game is for $p$ players who each start at square $1$. Each turn, a player can either roll an $m$-sided dice or place a marker on his current square. If he rolls $x\in\{2,\ldots, m\}$, he ...
3
votes
0answers
127 views

mixed vs behavior strategies for zero-sum game with infinite extensive form

edit: No responses to this post after a week, so I'm cross-posting it to cstheory.stackexchange here. I'm looking for a known theorem stating that, for appropriate kinds of two-player zero-sum games ...
3
votes
0answers
618 views

Simple game with coins - strategy

Let's play a game: There are $n$ stacks of coins in a row. $i$-th stack consists of $d_i$ coins. Two players: $\text{Player1},\text{Player2}$ make moves alternately. Player in his turn can only take ...
3
votes
0answers
167 views

Optimal strategy in a VCG auction with partial collusion?

Suppose you control the bid prices in a multiple-item VCG auction for a partial coalition of bidders. Each bidder is only allowed to win one item out of the set of multiple items, which are all ...
2
votes
0answers
48 views

Find a Mixed-strategy Nash equilibrium in an all-pay auction

This is an all-pay auction (Highest bidder wins the object, all players pay what they bid, player 1 wins all ties): Player 1 has $300$ dollars, Player 2 has $500$ dollars, the object being auctioned ...
2
votes
0answers
26 views

Are there any types of tournaments that allow for absences?

I'm trying to organize an online tournament with about 50 people that will span across 1 or 2 months, and inevitably some people won't be able to play their match every week. Is there a tournament ...
2
votes
0answers
27 views

A Generalized Mechanism for Gale-Shapley

I am working on some problems in my applied graph theory course, and we have just gotten to matching problems. We are currently working on a graph problem where instead of there being two types of ...
2
votes
0answers
238 views

How can all players in the Starcraft 2 Grandmaster league win more than they lose?

Starcraft 2 is a competitive online strategy game where players compete in leagues with other players of similar skill. The most difficult and highest league is the Grandmaster (GM) league, which ...
2
votes
0answers
109 views

Game theory, Book by Tirole and Fudenberg, Never a weak best response,unclear example

In this book, I have the following problem: on page 446, there is a sentence: Note that $(0.9,0.9)$ is not removed by NWBR, as D is not dominated after C is deleted. I do not understand this "as". ...
2
votes
0answers
51 views

Replicator equation for mixed strategies?

The the replicator equation is usually defined for pure strategies. More specifically, the replicator eqn for $n$ strategies is given by: \begin{equation} \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} a_{...
2
votes
0answers
37 views

Why doesn't the frequency of a strategy reach zero under the replicator dynamics?

Background The replicator equation with $n$ strategies is given by the differential equation: \begin{equation} \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} a_{ij}x_{j} - \phi \right) \qquad i = 1, \...
2
votes
0answers
78 views

Game Theory Duel Problem

We have the following duel problem: http://mathoverflow.net/questions/75318/the-duel-problem (You can read about it here). We have $P:\frac12, \frac23, \frac34, 1$, Q: $\frac14, \frac13, \frac12, 1$. ...
2
votes
0answers
50 views

Queen moves — The Squared Chain Puzzle

Karl Scherer made the interesting Squared Chain Puzzle. Start with a $7\times7$ board, with a queen somewhere. Make a legal move with the queen, placing coins over all squares visited. For subsequent ...
2
votes
0answers
32 views

Ideal Card Game

I have invented a very interesting card game. All the cards from 2 to 10 (in four colours) are divided evenly between the two players (the deck is shuffled before dealing the cards, of course). Now ...
2
votes
0answers
46 views

Optimal strategy to escape spotlight

Here is the setup. A prisoner is being held in the center a circular yard with radius $r$ and can run in any direction at some velocity $v$, there is a spotlight which illuminates a line on the circle ...