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

1
vote
2answers
145 views

What is the probability of going bankrupt in roulette?

Imagine that the bank has the money $M_1$ and the player has the money $M_2$. The rules are the following: You win with a chance of $\frac{17}{36}$ and lose with $\frac{19}{36}$ each round. Now you ...
0
votes
5answers
170 views

Some examples of applications of Game Theory

I'm approaching my junior year of HS now, and I'm looking for a good science fair project to do. I love mathematics, so I decided to a category of mathematics that can help base logical conclusions to ...
0
votes
1answer
63 views

Number of ways in a Nim game such that First Player always wins

Given $n$ piles of coins in a Nim game, how do I find the number of ways of making the first move under optimal play such that Player 1 always wins?
0
votes
1answer
71 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
2
votes
1answer
163 views

Game theory: Mixed Strategies and Nash Equilibrium

So I've recently become interested in game theory, and I've visited this site to help me understand what exactly game theory is and the applications of it. In the lesson, they use an example of ...
-1
votes
1answer
218 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
11
votes
5answers
673 views

The Price is Right optimal play

The following situation happened on the Price is Right and I was curious about the optimal response. The rules are: A contestant rolls a wheel with 5 cent increments from 5 - 100 (20 numbers total). A ...
1
vote
0answers
19 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
1answer
40 views

The strategies yielding a zero-sum game's value

Let $m, n \in \mathbb{N}_1 := \{1, 2, \dots\}$ and let $\mathbf{A} \in \mathbb{R}_{m \times n}$ be a real, $m \times n$ matrix. Denote by $\Gamma$ the two-players, zero-sum game, whose payoff matrix ...
0
votes
3answers
95 views

How do we reduce a matrix in game theory?

Here we have $$\left[\begin{array}{}8 &3 &0 &5\\ 0 & 4& 4& 1\end{array}\right]$$ and I heard col2 $$\left[\begin{array}{}3\\4\end{array}\right]$$ is dominated by col3 ...
49
votes
8answers
11k views

Why do people lose in chess?

Zermelo's Theorem, when applied to chess, states: "either white can force a win, or black can force a win, or both sides can force at least a draw [1]" I do not get this. How can it be proven? ...
6
votes
2answers
901 views

John Nash's Hex proof

I am reading a book on Combinatorial Game Theory that describes a proof by John Nash that Hex is a 'first player' win, but I find the proof very confusing. This proof uses a strategy-stealing ...
0
votes
1answer
53 views

Prove that a Modified Cantor Distribution is Atomic.

Consider a measurable space $\{\mathcal{I},\mathcal{B}\}$, where $\mathcal{I} = [0,1]$ and $\mathcal{B}$ are the Borel sets on $\mathcal{I}$. And also, denote $\mathcal{C}$ as the cantor set on ...
3
votes
2answers
556 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
82 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
81 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
98 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
109 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
53 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
274 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
185 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
120 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
107 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
138 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
43 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
78 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
53 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
62 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
121 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
98 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 ...
58
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
95 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
137 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
66 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
97 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
171 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
185 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
324 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 ...