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

3
votes
2answers
398 views

Is the Nash Equilibrium example in a “Beautiful Mind” accurate?

I was wondering if the Nash Equilibrium example shown in the movie A Beautiful Mind is accurate? and if not, what's wrong with it? Thanks
1
vote
0answers
81 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
1answer
86 views

Finding mixed nash equlibrium

In the following game I found one pure nash equilibrium: $(R, r)$: $\begin{array}{r|ccc} A\backslash B & l & m & r\\ \hline L & (-10, 4) & (10, 0) & (-1, -1)\\ M & (0, 10) ...
1
vote
2answers
79 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
0
votes
1answer
93 views

Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
0
votes
1answer
105 views

Can We Tell Which of These Strategies are Dominated?

This is the strategic form for a zero-sum game; it reflects player 1's expectations. I need to reduce this strategic form from 4x4 to 2x2 by eliminating the dominated strategies. All the examples ...
3
votes
1answer
48 views

Combination of supermodular and submodular functions

Suppose the production function $v(x,y)$ is increasing and submodular in both arguments, and the production function $c(x,y)$ is increasing and supermodular in both arguments ($x,y \geq 0$). Is the ...
2
votes
1answer
70 views

What is the difference between reinforcement learning, trial and error, and fictitious play?

I have three question about three algorithms. I have a game with $n$ players. The action space of player $i$ is given by $\mathcal{A}_i=\{a_1, a_2, \cdots, a_m\}=\mathcal{A}$. The joint action space ...
13
votes
1answer
272 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
1
vote
4answers
73 views

Nash Equilibrium and Limits in Game Theory

I am sure the solution to this is easy, but I can't work it out. Suppose we have an extremely simple game: There is only 1 player, who announces a number in the set [0,1]. His payoff is equal to his ...
4
votes
1answer
165 views

Expected revenue obtained by the Vickery auction with reserve price $1/2$

I would like to prove that the expected revenue of the Vickery auction with reserve price $1/2$ is $5/12$ when there are one item and two bidders the distribution of valuations are uniformly between ...
1
vote
1answer
108 views

How to calculate the expected utility for $3$ player game?

I do not understand how to calculate the expected utility of $3$ or more players game. For a $2$ player game, it is easy. Suppose I have two action $\{A, B\}$ and my opponent has two action $\{C, ...
4
votes
1answer
106 views

Prevent Alice from building a tower of height k

Alice and Bob take turns playing the tower of babel game, with Alice starting. In this game Alice has $m$ parcels of land. In each of Alice's turns she receives $n$ blocks and decides to distribute ...
4
votes
1answer
134 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 ...
0
votes
1answer
42 views

Maximum payoff for safe bet

I'm having a hard time choosing a good strategy for this problem: assume that you have $m$ money that you can bet on $n$ mutually exclusive outcomes, all with unknown probabilities, and that each ...
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 ...
0
votes
0answers
73 views

Matrix Saddle Points and Dominance

I was teaching myself about dominance relations and saddle points after a friend of mine started discussing it with me and how it can be used in games. I wanted to know how to prove a problem like ...
3
votes
1answer
52 views

Computing a revenue for VCG auction

I would like your help with the following question regarding computing a revenue for a seller of an VCG (vickrey clarke groves) auction, I'm really new to this auctions\game theory so I'd really ...
0
votes
3answers
53 views

Definitions of noncooperative and cooperative games.

These days I have read many descriptions of a noncooperative game like the one below. A noncooperative game is a game in which players are unable to make enforceable contracts outside of the ...
2
votes
4answers
118 views

How does one explain basic probability theory to a layman?

I have recently been involved in a number of discussions with people with little or no background in mathematics when we considered a problem of the following shape. A random event is going to ...
2
votes
1answer
93 views

Reverse Hex board game winning strategy

I just wanted to know the winning strategy to this question: In a reverse Hex board game I know it means where the player who first forms a path between his/her edges loses. Find a winning ...
0
votes
0answers
40 views

Game theory problem… I think…

I need some help with the following: Let's say I'm running a store of electronic devices (call it Store $A$). and let's say that right next to me, there's another electronic devices store (store $B$) ...
1
vote
1answer
42 views

Game theory - Pure ESS test

Let $A \in \mathbb{R}^n$ describe a symmetric game with $n$ strategies. For the sake of clarity, I call symmetric game a two-player game where payoff matrices are the same for both players. Suppose ...
12
votes
4answers
205 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
57
votes
3answers
6k views

Mathematical research of Pokémon

In competitive Pokémon-play, two players pick a team of six Pokémon out of the 718 available. These are picked independently, that is, player $A$ is unaware of player $B$'s choice of Pokémon. Some ...
3
votes
1answer
92 views

Guessing a number among K

Consider two players $a$ and $b$. Player $a$ moves first and picks a number $n\in\{0,1,2,...,K\}$. Then moves player $b$ who guesses at the number picked by $a$. If the guess is correct, $b$ wins a ...
0
votes
1answer
63 views

Winning or Non-losing strategy for A or B

Find a winning or a non-losing strategy for the following game: Consider $25$ sticks arranged in a $5$ x $5$ square. Players alternately take any number of sticks from a single row or column. At ...
1
vote
2answers
132 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
0
votes
2answers
35 views

Why you randomize your opponents payoff in a mixed nash equilibrium?

I wanted to understand the justification more intuitively -- if that is possible. For example, I'm in a abstract game with another opponent and there is no pure strategy equilibrium: why do I ...
1
vote
2answers
62 views

Finding optimal mixed strategy

I have to find an optimal mixed strategy for the 'column' player, who mixes with the probabilites $q_1,q_2,q_3$. What is known is the optimal mixing of the 'row" player. The game is a zero-sum game, ...
1
vote
0answers
40 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. ...
0
votes
1answer
88 views

The potential function of Prisoner's Dilemma

As in the famous example of "Prisoner's Dilemma" like this If the potential function is defined as: (V(q,q), V(q,c), V(c,q), V(c,c)) q = quiet, c = confess, V is the potential. So should the order ...
0
votes
1answer
46 views

Chase game with doubling cube

Consider the following 2-player game: Each player has some score. Taking turns, each player gets added to his score a uniform random on (0,1). If after this addition that player is ahead by at least ...
0
votes
0answers
164 views

Application of Markov Chain to Game of Life Board Game

I need to calculate the expected outcomes for the Game of Life. I believe that if I multiply the probability of landing on a particular square with the payoff of said square and add up all these ...
1
vote
1answer
166 views

Finding Nash Equilibria for this Bimatrix Game

Consider the following Bimatrix Game a b c d -----|------------------------------------------- T (1,4) ( 4,3) (0,2) (1,0) B ...
0
votes
1answer
36 views

Decide the Nash Equilibrium

If two people collaborate on a work: the (3,3) means if neither of them do any work, then, they have to be put on detention for 1 hour and then both of them still have to finish the same 2-hour work ...
7
votes
4answers
314 views

Can Nash Equilibrium be more than two?

In the Prisoner's Dilemma example, we know that there is only one Nash Equilibrium. That is both of them confess. Is it possible that there are two Nash equilibrium in one example? Can you roughly ...
0
votes
1answer
71 views

An algorithm to rate players in team?

I would like to design an algorithm to rate players in a team sport. One team of N players plays a match against another team of N players. The individual players will possibly change, from match to ...
0
votes
0answers
84 views

What is the lowest possible score in $2048$, $4\times4$ and $5\times5$ board if the computer plays to try to make you win the game?

What is the lowest possible score in $2048$, $4\times4$ and $5\times5$ board if the computer plays such that it wants you to win the game? I got to the $32$ tile in a $5\times5$ board now with a low ...
1
vote
0answers
49 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, ...
0
votes
5answers
172 views

game theoretic die rolls

Suppose player X has a 6 sided die and player Y has a 10 sided die. They each get two rolls and they can each choose to stop rolling on either one of the rolls, taking the number on that roll. Whoever ...
1
vote
1answer
132 views

Finding pure strategy and pay off matrix in game theory

"A two person games begins with the random selection of an integer $x$ from the set {$1,2,3$}, each choice is equally likely. Then the two players, not knowing the value of $x$, simultaneously select ...
0
votes
0answers
27 views

de Bono's L-game modification

I am trying to find out if a simple modification od de Bono's L-game is still infinite if two players are perfect. Modified rule is that there no neutral pieces but, there is one piece for each player ...
4
votes
2answers
486 views

simple games with cute winning strategies?

Im thinking of games of two players ($A$ goes first and $B$ second) like the following: There are 35 chips in a table, during each turn a player can remove 1,2,3 or 4 chips. Prove player $B$ can ...
0
votes
0answers
20 views

Dual proof in Zero sum games

Say Player 2 is $P: max \sum_1^n x_j $ subject to $Ax \leq b$. I believe the Dual problem for this would be $D: min \sum_1^n y_j$ subject to $A^T y \geq 1$. Player 1's problem would be $max \{min ...
2
votes
0answers
407 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 ...
3
votes
2answers
154 views

Alice and Bob card game

I came across this puzzle online in an online Princeton thingy (course?): Alice writes down two integers between 0 and 100 on two cards. Bob gets to select one of the two cards and see its value. ...
9
votes
3answers
738 views

Optimal Strategy for Rock Paper Scissors with different rewards

Imagine Rock Paper Scissors, but where winning with a different hand gives a different reward. If you win with Rock, you get \$9. Your opponent loses the \$9. If you win with Paper, you get \$3. ...
1
vote
1answer
50 views

need help with zero sum game

Tom chooses an integer in {1,2,3} and Bob chooses an integer in {2,3,4}. If the chosen numbers are the same, no money changes hands If the numbers are different the person who picks the bigger number ...
2
votes
1answer
465 views

Solving a 3x3 payoff matrix

I need some help solving the value of this payoff matrix and finding the optimal strategy: $$ \begin{matrix} 1 & 2 & 4 \\ -1 & 5 & 3 \\ 3 & 3 & ...