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

learn more… | top users | synonyms

1
vote
1answer
611 views

Relationship between regular Nim and Lasker's Nim

So I'm trying to do qn $6$ (on pg I-13) about staircase Nim in Game Theory by Ferguson Game Theory, Ferguson and it's asking to prove that $(x_1, x_2, \ldots, x_k) \in P $ only if $(x_1, x_3, x_5, ...
15
votes
8answers
3k views

Understanding the solution of a riddle about lions and sheep.

I heard a riddle once, which goes like this: There are N lions and 1 sheep in a field. All the lions really want to eat the sheep, but the problem is that if a lion eats a sheep, it becomes a sheep. ...
2
votes
1answer
74 views

Does the first player never lose this numbers game?

There is an even number of numbers in a row. Two players cross out numbers one by one from left or right. It is not allowed to cross out a number in the middle. Only left or right. After all numbers ...
0
votes
3answers
241 views

Game Theory Voting Utilities

! So far, I've managed to come up with this solution: ! But as far as here...I can convert this into payoffs, however I'm unsure of how to figure out the Nash equilibria as when we convert from ...
1
vote
0answers
53 views

Prove that a mixed strategy in two player, zero sum, matrix game must exist (alternative proof)

So I am having a trouble with this game theory proof. I feel pretty good with my answer for part 1, but I am not really sure how to get started on the rest of it. Any help would be appreciated. Let ...
2
votes
2answers
64 views

Can a game with negative expectation still have a positive utility?

Intuitively, I think not. But I can't clearly prove why. Specifically, I've been thinking about lottery games, where the expectation is obviously negative. But can the utility of hitting the jackpot ...
2
votes
1answer
101 views

Resources for understanding game trees?

I am trying to make an AI to solve the popular game $2048$, and I think that the theory of game trees would help me quite a bit in this endeavor. The only issue is that most of the results I've found ...
2
votes
1answer
72 views

Coin-tossing games

Suppose that you start off with $100$ dollars. You toss a coin $10$ times and guess it right $5$ times and lose $5$ times (the order of the outcomes is not known). It is known that every time you ...
1
vote
2answers
220 views

Probability that 20 sided die beats 12 sided die with reroll

Alice rolls a 12 sided die (the faces labeled 1 through 12) and Bob rolls a 20 sided die (the faces labeled 1 through 20). After seeing their roll (but not the other person's roll), each person can ...
-1
votes
1answer
310 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
0
votes
0answers
102 views

Game theory (2 player, random number) question

So we have a game in which 2 players, P1 and P2, are randomly given a number $x_1,x_2\in [0,1]$. Each player first antes \$1, are given their numbers, and then P1 can choose to bet any value $B$, or ...
2
votes
0answers
57 views

Simple Dice Game - Optimal Mixed Strategy

Just started an introductory course in game theory, and here is a problem we have been talking about. So here is the description of the game. Two players, each player starts by placing \$1 each into ...
3
votes
1answer
128 views

Introductory texts in abstract algebra, and game theory taking non-standard approaches

I like to see subjects from different angles. For example in linear algebra I'm reading through Axler's text (which takes a proof based approach for math students), but I'm also checking out a text on ...
15
votes
1answer
669 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
5
votes
1answer
299 views

Nash equilibrium unique in repeated prisoner dilemma with discount factor neither too high nor too low

On page 47 of George J. Mailath and Larry Samuelson's Repeated Games and Reputations: Long-Run Relationships (See here), the stage game of repeated prisoner dilemma in which player 1 chooses the row, ...
1
vote
1answer
162 views

What is the sprague-grundy value of these games?

This is a follow-up question of my previous question : Optimal strategy for this Nim generalisation? Consider the following game: There are a number of piles of stones. On each turn a player can ...
10
votes
0answers
114 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
2
votes
1answer
82 views

Odd number of equlibria in a bimatrix game

Most matrix simultaneous games have odd number of equilibria. However, there are cases where this might not be true. How can I identify these cases? Do they have an specific property? Consider for ...
4
votes
2answers
270 views

Guess the smallest number

Three people play a game where each of them writes down a positive integer at the same time. The one who writes a unique and smallest number wins one dollar from every other person. This means if two ...
0
votes
0answers
399 views

Game theory: Bidding strategy during an auction in a card game

I'm trying to create a mathematical model for the auction process in a card game called Pitch. The specific question I'm interested in solving is: Let $p_i$ represent the probability of a specific ...
18
votes
2answers
408 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
2answers
346 views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
2
votes
2answers
54 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 ...
4
votes
3answers
218 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. ...
1
vote
0answers
63 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
145 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$ ...
1
vote
1answer
104 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
88 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. ...
0
votes
1answer
68 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 ...
0
votes
1answer
54 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 ...
1
vote
1answer
133 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 ...
5
votes
2answers
5k 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?
1
vote
1answer
104 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 ...
1
vote
1answer
325 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 ...
11
votes
1answer
433 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 ...
1
vote
1answer
161 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
157 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
198 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
321 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
162 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
129 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
249 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
325 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
1k 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
1answer
23 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
45 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
220 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 ...
50
votes
8answers
13k 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
1k 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
56 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 ...