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

18
votes
0answers
389 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
405 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
150 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 ...
7
votes
0answers
60 views

What is the most effective strategy to win at this game?

The game is as follows. Alice secretly selects three real numbers $a_{1},a_{2},a_3$ such that $1\geq a_1\geq a_2\geq a_3\geq 0$ and $a_1+a_2+a_3=1$. Bob secretly selects three real numbers ...
6
votes
0answers
44 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
81 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 ...
5
votes
0answers
91 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 ...
5
votes
0answers
118 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 ...
5
votes
0answers
103 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 ...
4
votes
0answers
121 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
99 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
146 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
89 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
256 views

$n$ players of paper scissor rock

Suppose there are $n$ players $(3\leq{n})$ showing Paper, Scissor or Rock simultaneously. If there is no winner then there is no payoff to any player. If there are winners and losers (e.g. $k$ ...
4
votes
0answers
149 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
48 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
53 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 ...
3
votes
0answers
91 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
50 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
108 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
71 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
66 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
117 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
490 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
142 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
34 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
60 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
33 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
35 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
72 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, ...
2
votes
0answers
72 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
100 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 ...
2
votes
0answers
192 views

stable marriage algorithm problem

Better of the two Suppose that in the stable marriage problem with $n$ men and $n$ women, we have found two (possibly different) stable matchings $S$ and $T$. We will show how to combine $S$ and $T$ ...
2
votes
0answers
52 views

Showing $\frac{1+c}{a+b}\leq \varphi$, when $\frac{1}{1+b}\leq a\leq 1$, $\frac{c^2}{a+c}\leq b\leq 1$ and $0\leq c\leq 1$

The title pretty much says it all. Let $\varphi\triangleq\frac{1+\sqrt 5}{2}$ be the golden ratio. Let $a,b,c$ be some non-negative numbers such that: $\frac{1}{1+b}\leq a\leq 1$ ...
2
votes
0answers
45 views

Book or paper recommendation about “Rube Goldberg Mathematics” // e.g. Longest path problems

First: My question is not be very specific, since I lack a concrete overview, but my idea/thoughts in a nutshell: I would like to have a recommendation of a good book, paper or article about processes ...
2
votes
0answers
59 views

Game Theory: What are Best Strategies for High-Low game (game details are below)?

High Low game is one where one person picks a number between a range (say 1-100) and another person have to guess it. With each guess, s/he is told whether the guess was high, low or correct. If the ...
2
votes
0answers
77 views

Correlation of belief distributions from distinct signals

Anne and Bob are two Bayesians who initially share a non-degenerate prior about a binary state of the world. Anne observes some signal (i.e., an experiment in Blackwell's terminology) about the state ...
2
votes
0answers
81 views

A combinatorial game theory problem

In details, there are four bishops on a chessboard in two pairs. In each pair they sit in orthogonally adjacent squares. How many positions can there be to place the two pairs on the chessboard ...
2
votes
0answers
95 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
2
votes
0answers
19 views

Bingo based on number of hits on card?

I was wondering how many possible combinations there were to win based on the number of hits on a bingo card (25 spots, 1-75 etc.)? I know that if you get 1,2,3 hits on the card, there are no chances ...
2
votes
0answers
20 views

dimension of Weber set and selectope (as a operator)

Let $\Omega$ be a finite set of players. For a selector $\alpha:(2^{\Omega}-\{\emptyset\})\rightarrow\Omega$, we define a marginal value operator as a linear operator $m^{\alpha}$ ...
2
votes
0answers
120 views

Game theory: connect four?

Through Allis' solution etc... P1 can force a win if he places the first stone in the highlighted region. Assuming both players have perfect information, it will take 41 turns maximum (if I recall ...
2
votes
0answers
113 views

Game theoretical approach to other branches of mathematics

Are there some methods and ideas derived from game theory that are successfully applied to better (or more intuitively) understand theorems and proofs or tackling problems from other areas of ...
2
votes
0answers
90 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
2
votes
0answers
28 views

VCG - plynomial time algorithm when bidders are unit demand

Is there a polynomial time algorithm to run a VCG when bidders are unit-demand? I though to look at the Bipartite graph when the left side is the bidders the right is the items and the edges are the ...
2
votes
0answers
438 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 ...
2
votes
0answers
143 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
2
votes
0answers
45 views

How to find perfect equilibria in a finite game?

If we define a game with $n$ persons as below: (i) for each player $i$, he has his strategy set $S_i$, $|S_i|=m_i<\infty$, and denote $S=\Pi_iS_i$; (ii) $u_i:S\rightarrow\mathbb{R}$ is a payoff ...
2
votes
0answers
29 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 ...