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

learn more… | top users | synonyms

53
votes
0answers
1k views

Identification of a curious function

During computation of some Shapley values (details below), I encountered the following function: $$ f\left(\sum_{k \geq 0} 2^{-p_k}\right) = \sum_{k \geq 0} \frac{1}{(p_k+1)\binom{p_k}{k}}, $$ where ...
12
votes
0answers
202 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 ...
9
votes
0answers
79 views

Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you ...
7
votes
0answers
138 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 ...
5
votes
0answers
86 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
229 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 ...
4
votes
0answers
97 views

Saddle Points on Matrices

Let $n$, $m$ be positive integers. Suppose that $A$ is a $2$ x $n$ or an $m$ x $2$ matrix and that it has a saddle point. Show that among the saddle points of $A$ there exists at least one which ...
4
votes
0answers
61 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
127 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
77 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
232 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
92 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
50 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
183 views

Is there any hope to solve the game chess?

I heard about an estimate how many legal positions there are in a chess game. There are roughly ${10}^{40}$. Is it realistic that this amound of positions can be checked in the near future ? Or is ...
3
votes
0answers
42 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
63 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
101 views

Unexpected hanging paradox maxmin strategies

I have a question about strategies of the players of Unexpected hanging paradox (I am very sorry for a long topic, topic exist already for a while, during this time I try to develop idea how to solve ...
3
votes
0answers
97 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
339 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
121 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
30 views

Who has a winning strategy in “knight” and why?

Perhaps, this game is already known, but I did not find anything about it, I call it "knight". The rules : Player 1 chooses the starting square of a knight on a normal 8x8 - chessboard. The ...
2
votes
0answers
25 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
286 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
125 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
33 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
89 views

The name of a game from the 2013 Putnam

Does the following game from the 2013 Putnam have an official name? Based on my searches, it seems to have been created just for the exam. Let $n\geq 1$ be an odd integer. Alice and Bob play the ...
2
votes
0answers
50 views

Optimally Efficient Tournament Strategies

Consider a fair symmetric game between two players that always results in exactly one of the players winning, i.e. there are no ties. When two players $P$ and $Q$ play each other, $P$ wins with a ...
2
votes
0answers
67 views

Is there a game of perfect information that only has a mixed strategy equilibrium?

It is known that certain simultaneous games, say, matching pennies with no pure strategy equilibrium, have a mixed strategy equilibrium. Is simulaneous move at some stage a necessary ingredient of ...
2
votes
0answers
168 views

What is the (expected) outcome of this hybrid auction?

A certain hybrid auction can be accurately modelled as follows. There are $n$ risk-neutral, rational participants $i=1,2,\ldots,n$, and a guy called Zerro: $i=0$. Each, except Zerro, has a private ...
2
votes
0answers
131 views

Comparing Nash equilibrium and Pareto optimal actions

Suppose that $(x_{i}, x_{j})$ identify actions for two players $(i,j)$. If we define Pareto optimal actions by $$h(x_i) +h(x_j)- \eta[p(x_i)+p(x_j)]=2\gamma$$ and Nash equilibrium actions by ...
2
votes
0answers
159 views

A dynamic Stackelberg game - general characterization

my question is about general representation of a dynamic Stackelberg game which is played in continuous time. We have maximization problems of two agents who play this game. Agents are 'Leader' and ...
2
votes
0answers
198 views

Explanation of Mixed Strategy Definition in Game Theory

Definition: Let $(N, A, u)$ be normal-form game, and for any set $X$ let $\Pi(X)$ be the set of all probability distributions over $X$. Then the set of fixed strategies for player $S_i=\Pi(A_i)$. ...
2
votes
0answers
135 views

Game Theory - Extensive Zero-Sum Game Property Proof

How I might I go about to prove (or disprove, but I believe that this is true) the following: We call a 2-player extensive game $\Gamma$ a zero-sum game if the sum of the 2 payoffs for an terminal ...
2
votes
0answers
108 views

proof using (fixed point theorem)

I am seeking to solve for a Nash equilibrium in pure strategies $(d_2,d_2)$ involving two players, $1$ and $2$. Given that $h'(.)$ is s strictly decreasing and continuous function, $\Phi(d_1-d_2)$ ...
2
votes
0answers
678 views

How can I bid optimally on bitcoinauction.us?

The website www.bitcoinauction.us hosts a bidding game with a prize. Note that it's not a real auction because you don't get your bid back if you're outbid. The game works as follows: The game ...
1
vote
0answers
42 views

Uniqueness of solution for a system of differential equations

A friend of mine working on Auction Theory needs to establish uniqueness of solution (up to initial and boundary conditions) of a system of differential equations of the form $$ ...
1
vote
0answers
12 views

Distribution of coalition cost among coalition members (game theory) on the basis of contribution in coalition

Does any one know or point out the method or technique used for the distribution of the coalition cost among the coalition members depending upon their contributions in the coalition. In other words, ...
1
vote
0answers
50 views

Game Theory - Bayes Rule, Sequential Game

I am trying to solve the following model, but I get a few weird results. Sorry if it is too long... Nature moves first and with probability $p$ assigns player's 1 type to be High ($1-p$ for Low) ...
1
vote
0answers
37 views

What is the optimal strategy?

There are $m+n+1$ cards numbered $1,2,\ldots m+n+1$. Participants A and B respectively get $m$ and $n$ cards. Meanwhile, they only know what they get. The remaining card is face down on the desk. ...
1
vote
0answers
36 views

Two person zero sum problem, help/guidance needed..

I'm a computer science student and I have this problem I need to solve for my games theory course. I don't have an example to follow, or use as guidance, and my colleagues are not very helpful( as in, ...
1
vote
0answers
32 views

How do we determine the saddle point in game theory?

I am a little confused of why this works. If a$_i$$_j$ is positive, row player pays the column, and vice versa. \begin{bmatrix} 3 & -5 & 6\\ -2 & 1 & 8 \\ 3 & -6 & ...
1
vote
0answers
24 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
1
vote
0answers
46 views

Is the expected utility function linear?

Given the definition of the mixed extension of a finite game as in the link below (only first 7 lines): How to find perfect equilibria in a finite game? We define the expected utility function in the ...
1
vote
0answers
32 views

Game theory:Baye's rule for tournament

I'm having challenge with the following computations from the book I'm using. How are the steps obtain from the preceding step? In the expressions below, $E_i$ and $E_j$ are independent, random ...
1
vote
0answers
40 views

Game Theory - Voting

In this setup there are 4 candidates running. For a candidate to be eliminated, the candidate needs to receive less than 1/3 of the votes when paired up with another candidate. This process ...
1
vote
0answers
73 views

Proof that 12 in a row tic-tac-toe is a tie game?

How can be it proved that tic-tac-toe on an infinite grid (winning with 12 in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)? There is a hint: to use ...
1
vote
0answers
22 views

Minimum number of steps to guess an item in a database

Let's say I have a database of N*N size (N rows N columns) My friend wants me to guess the location of an item. We start by binary guess, means I ask him if it is in upper half, he says yes or no, if ...
1
vote
0answers
46 views

Game theory Zero Sum Game Proof

Zerosum games. A coailitional game with transferable payoff is zerosum if $v(S) + v(N - S) = v(N)$ for every coalition $S$; it is additive if $v(S) + v(T) = v(S \cup T)$ for all disjoint $S$ and $T$. ...
1
vote
0answers
50 views

Dilemma at the dining table

I created this problem while I was having my supper a few days back. So there maybe flaw in the formulation. Please point them out as you see one. Suppose, there is a circular dining table with ...
1
vote
0answers
37 views

On a certain type of card game

Suppose two players are playing a card game, which is described as follow. Each player is allowed to construct their own decks of exactly $n$ cards with an additional repeatable card, where each ...