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
1answer
80 views

Finding cut-off point for utility function

OK, so apologies for the easy question, but I'm new to this! This is somewhere between elementary algebra, and beginner's game theory. The question comes from a paper I read here (see p. 193): ...
3
votes
2answers
91 views

State-Space Complexity of RISK board game

I want to calculate the (state-space) complexity of the RISK board game. Online I found a thesis that outlines that complexity (page 34). Here is the summary: Let M denote the maximum number of ...
1
vote
2answers
118 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
136 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
48 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
53 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
106 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
200 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
481 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
16 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
35 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
62 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 ...
45
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
639 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
51 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
135 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
69 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
68 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
53 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
67 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
88 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
33 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
62 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 ...
12
votes
1answer
203 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
67 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
97 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
80 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
101 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
120 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
34 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
26 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
18 views

Can we prove constructively that $\epsilon$-equilibrium converges to (mixed strategy) Nash equilibrium?

We know that by using standard classical mathematics, $\epsilon$-equilibrium does converge to exact (mixed strategy) Nash equilibrium as $\epsilon$ becomes smaller. My question is, can we prove this ...
0
votes
0answers
47 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
41 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
43 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
101 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
76 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
38 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
40 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
190 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 ...
55
votes
3answers
5k 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
88 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
60 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
111 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
32 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
44 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
38 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
58 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
43 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
122 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 ...