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

31
votes
0answers
611 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 ...
12
votes
0answers
434 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 ...
8
votes
0answers
104 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 ...
8
votes
0answers
153 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
56 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
108 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
111 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
192 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
67 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 ...
5
votes
0answers
131 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 ...
4
votes
0answers
43 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
92 views

Winning Strategy with Addition to X=0

Problem: Two players play the following game. Initially, X=0. The players take turns adding any number between 1 and 10 (inclusive) to X. The game ends when X reaches 100. The player who reaches 100 ...
4
votes
0answers
147 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
103 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
141 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
4
votes
0answers
152 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
94 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
178 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
19 views

Construct a game with only pure strategy nash equilibrium.

I'm trying to construct a normal-form game with $2$ players such that it satisfies the following three properties: $1)$ Each player has exactly $4$ strategies. $2)$ The game has exactly $4$ Nash ...
3
votes
0answers
50 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 ...
3
votes
0answers
90 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
80 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, ...
3
votes
0answers
114 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
56 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
113 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
82 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 ...
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
123 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
568 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
156 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
23 views

Optimal Strategies in a Quantum Game

I've been playing around with problems involved in introductory quantum game theory, but I am having problems figuring out strategies in this one game. For background, consider the 2x2 Pauli spin ...
2
votes
0answers
22 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
22 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
120 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
60 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 ...
2
votes
0answers
89 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
49 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
35 views

What are the optimal mixed strategies for this game?

Fix $k < n$ positive integers, and two players play the following game: each player picks a positive integer between 1 and $n$. If the two numbers picked are within $k$ of each other, the larger ...
2
votes
0answers
44 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
27 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
44 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 ...
2
votes
0answers
100 views

A fashion victim puzzle

Consider $n \in \mathbb{N}$ fashion-sensitive kids, each wearing a T-shirt; for simplicity, kid $i \in \{1, \ldots, n\}$ initially wears shirt $i$. Tastes over the shirts are summarized in an $n ...
2
votes
0answers
37 views

Expected Value in modified Let-it-Ride

Let-it-Ride is a casino table game which you can read about here: http://wizardofodds.com/games/let-it-ride/ This page also has expected values done for the normal game! In my modified version, ...
2
votes
0answers
129 views

Cournot competition: profit maximizer vs. market share maximizer

Today during an informal conversation with an established business researcher, I learned such a fact: In the classical Cournot competition model, if one player is a profit-maximizer, the other ...
2
votes
0answers
96 views

Finding the core of a coalition game

I need to find the core of a 3-player coalition game graphically, given that $v(\phi)=0$, $v(1) = 9, v(2)=8, v(3) = 9, v({1,2}) = 14, v({1,3})=15, v({2,3}) = 13, v({1,2,3}) = 21$ So I'm following the ...
2
votes
0answers
64 views

Cournot Oligopoly in Bayesian Game Theory

I have this Cournot game in which $n$ firms produce quantities $q_1, \ldots, q_n$ with respective marginal costs $c_1, \ldots, c_n$. They all sell at price $P=1-(q_1 + \cdots + q_n)$. For any $i$ ...
2
votes
0answers
81 views

Price of anarchy for selfish routing games with polynomial latency functions

I have a question regarding selfish routing games. For the case where we have affine latency functions I was able to calculate a worst case price of anarchy (PoA) of $4/3$. However, now assume $L_d$ ...
2
votes
0answers
92 views

How to find optimal strategies for infinite betting games?

Suppose we have a game structure of the following form: Game: You have an $n-$sided die. At any point in the game, there is a "value" associated to the rolls that have already occurred. You can ...
2
votes
0answers
112 views

Is it possible to calculate the balanced cost of parameters' increase in card game? How?

I wonder if it's possible to calculate the balanced cost of parameters' increase for the card game. Game rules: Each player draw 7 cards at the beginning of the game and then one card each turn ...