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

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
4
votes
2answers
87 views

Banach-Mazur Game: Proof about winning strategies

I have to hold a presentation about the Banach-Mazur-Game to undergraduates this week. It should all stay very simple, so I will mainly only talk about the "original" Banach-Mazur Game on ...
374
votes
25answers
51k views

Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an ...
0
votes
1answer
25 views

Do all equilibria in 2 player zero sum games have the same distribution over outcomes

I know that in a 2 player zero sum game all equilibria give each player the same expected value, but is it the case that they also induce the exact same distribution over payoffs? Or might there be ...
2
votes
3answers
103 views

Chess and mathematics

I have to choose a research-like project to follow the next year. Because I'm a chess enthusiast, I was thinking of trying to tackle an (open) problem related to chess, and relevant to mathematics. ...
0
votes
0answers
10 views

How to Find Symmetric Equilibrium Bidding Strategy in Mixed Auction?

N-bidders take part in a mixed auction (mix of first- and second-price auctions). The highest bidder (bidder 'i') wins and pays a*b_i + (1-a)*(max b_j) ('i' is not equal to 'j'), where 'a' is fixed ...
1
vote
0answers
41 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 $$ ...
7
votes
1answer
120 views

All games determined + ZF inconsistent

Let $A$ be a nonempty set, $T\subset A^\mathbb{N}$ a nonempty pruned tree and $X\subset [T]$. The game $G_{A}(T,X)$ is played as follows: Player I and Player II take turns playing $a_{0},a_{1},\dots$ ...
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
2answers
72 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
4answers
52 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 ...
1
vote
1answer
50 views

Subtraction Game

I recently read about the Nim Subtraction Game. I have a variant, Suppose you have N stones and two players Alice and Bob, who can choose to pick either 1 stones or K stones. If Alice plays first when ...
1
vote
1answer
56 views

Economic Applications of Game Theory

I'm currently looking at this course in economic game theory. However, when attempting this example: In this question you are asked to price a simplified version of mortgage-backed securities. ...
1
vote
1answer
220 views

Reduce the payoff matrix using (weakly) dominated strategies

Below is the payoff matrix of a game. Use the principle of elimination of (weakly) dominated strategies to simplify the payoff matrix. What is the optimal solution of the game for the row player? ...
0
votes
0answers
51 views

I'm looking for a formula to be applied on a game

I've been working on a game and I need to implement a feature, but I still haven't found a good formula for it. The problem is the following: Each team has X points, and all teams are able to ...
1
vote
3answers
498 views

Chance of Winning In Tic Tac Toe

I'm sure everyone knows how to play the game of tic-tac-toe. I have just been wondering what's the probability of winning if one player started his or her move by putting his mark in the middle?
2
votes
2answers
52 views

Computer software for solving mixed strategy Nash equilibrium

Is there any computer software available for solving for mixed strategy Nash equilibria for two players given each player's payoff matrix?
0
votes
1answer
33 views

Generalized Tournament Model

Consider an $n$-player simultaneous game ($n\geq2$). Each player $i$ chooses a costly bid, $q_i\in R_+$. There are $p<n$ prizes to be awarded to the $p$ bidders with the highest bids. Bids are ...
2
votes
3answers
144 views

Precise definition of a “game of incomplete information” (Game Theory)

Question: In game theory, what is the precise definition of a "game of incomplete information"? What I've found so far: In the standard first year graduate economics textbook on microeconomics ...
0
votes
1answer
28 views

Probability - choosing best strategy

Am I going about this problem the right way? In a certain game a participant is allowed three attempts to score a hit. In three attempts he must alternate which hand he uses: thus he has two ...
1
vote
1answer
48 views

Minimum excluded ordinal

I'm trying to understand some concepts of game theory. So far I've understood how the game of nim works, at least the most basic form: as long as the current game has value > 0 the current player can ...
1
vote
1answer
41 views

In Courty and Li (2000) “Sequential Screening”, what justifies the last equation in Lemma 3.2?

Regarding the article "Sequential Screening," in Review of Economic Studies, 2000 by Courty and Li: In Lemma 3.2, the last equality states that ...
12
votes
2answers
309 views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
0
votes
1answer
423 views

Game Theory. Repeated Games. Strategy set.

I'm reading the book "Strategic games" by Krzysztof R. Apt. I have a question about the strategies in Prisoner Dilemma repeated game. On page 63 there is expression: "In the first round each player ...
1
vote
1answer
51 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
8
votes
1answer
141 views

The Goblin Game

Goblin Game is a Magic: the Gathering card. The full text of the spell is: Each player hides at least one item, then all players reveal them simultaneously. Each player loses life equal to the ...
4
votes
1answer
361 views

The Notion Of Degenerate Two Player Game

I try to get the intuitive understanding of the notion "degenerate two player game". Definition. A two-player game is called non degenerate if no mixed strategy of support size $k$ has more than $k$ ...
1
vote
1answer
60 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
68 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 ...
3
votes
1answer
674 views

Mixed Strategy Nash Equilibrium of Rock Paper Scissors with 3 players?

It seems like most game theory tutorials focus on 2-player games and often algorithms for finding Nash equilibria break down with 3+ players. So here is a simple question: Is ...
0
votes
5answers
94 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 ...
1
vote
2answers
104 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
1answer
33 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?
2
votes
1answer
47 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 ...
0
votes
1answer
33 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 ...
-1
votes
1answer
180 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
414 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 ...
46
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? ...
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, ...
16
votes
3answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
1
vote
1answer
27 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
41 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 ...
1
vote
1answer
49 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 ...
0
votes
1answer
42 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 ...
4
votes
2answers
511 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 ...
1
vote
1answer
55 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
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) ...
0
votes
1answer
71 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 ...
4
votes
4answers
367 views

Cutting the cake problem if the value measures are not finitely additive

Background I have (rather recently) dabbled in game theory. I need it to design an algorithm to share chores. Obviously this is a kind of cake-cutting problem. So far, I have fought my way through An ...
1
vote
1answer
41 views

How to solve this problem? Distributed Game theory?

I have this problem: We dispose of some resources, say $\{f_1, f_2, \dotsc, f_m\}$; We have some agents or players, say $\{\mathrm{p}_1, \mathrm{p}_2, \dotsc, \mathrm{p}_n\}$; Every player has some ...