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

2
votes
1answer
59 views

Game theory books on learning e.g. Fictitious play

I'm looking for some text books on learning in game theory. So far I only found The Theory of Learning in Games by Fudenberg and Levine. Are there others you can recommend?
0
votes
0answers
62 views

what is the definition of pure strategy of zero sum games?

what is the definition of pure strategy of zero sum games? I tried to google for results, but no clear definition came up . EDIT: I found a definition in a game theory book . told me exactly what I ...
1
vote
2answers
76 views

Game theory expected value

We play a game involving two players. Each player calls a number 1 or 2. If the sum of these numbers are odd (i.e. equal to 3), then player 1 gets 3 points and player 2 loses 3 points. If the sum of ...
1
vote
1answer
49 views

How to note down an infinite game where strategy gets changed at a certain point

I have to write a proof concerning a grim trigger in an infinite Prisoners' Dilemma game. I can write the utility for both players cooperating infinitely. But suppose at some turn $n$ one player ...
0
votes
1answer
160 views

Nim Sum Game Variant

Suppose there are black and white balls in a box. The initial number of white balls is m and the initial number of black balls is n. This is a two player game. Each player can do the following taking ...
2
votes
0answers
219 views

Game theory: connect four?

Through Allis' solution etc... P1 can force a win if he places the first stone in the highlighted region. Assuming both players have perfect information, it will take 41 turns maximum (if I recall ...
2
votes
0answers
121 views

Game theoretical approach to other branches of mathematics

Are there some methods and ideas derived from game theory that are successfully applied to better (or more intuitively) understand theorems and proofs or tackling problems from other areas of ...
4
votes
4answers
278 views

A conjecture about Nash Equilibria in multiplayer games involving card drafting

A deck of $N$ cards is used to play a 4-player game. The game begins with each player being randomly dealt 7 cards from the deck. They then take turns according to a set of rules, after which a single ...
1
vote
0answers
93 views

Putnam game theory question

There are $n\ge1$ boxes in a line where $n$ is an odd integer. Two players, Connor and Andrew, are playing a game. On a turn, you can place a stone in a box OR take a stone out of a box and place a ...
4
votes
1answer
58 views

Optimal decision in game of Memory

Suppose two players are playing a game of Memory with $2n$ tiles consisting of $n$ distinct pairs. (To play, you publically reveal two tiles. If they match, you keep them and take another turn; if ...
2
votes
1answer
210 views

Counting all possible board positions in Quoridor

I'm trying to figure out how many possible board positions there are for the game Quoridor. I think sorting out the legal positions from the illegal positions will be difficult, so to start I'm trying ...
0
votes
1answer
146 views

How to write induction proof of Sprague-Grundy function for subtration game?

So lets say that S={1,2,3} I find the sequence of Sprague-Grundy function. How do I justify my answer using induction?
3
votes
0answers
59 views

Simple undetermined games

We know that, under AC, there exists a game in which two players play finite numbers and neither one has winning strategy. There are also such undetermined games when we consider players playing ...
2
votes
1answer
125 views

Monty Hall problem extended with expectations i.e. prior probabilities

I am fascinated by the Monty Hall problem and its variants such as N-doors version here. Now suppose expectations. How does the Monty Hall problem changes with expectations? Simple example ...
2
votes
0answers
109 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
3
votes
0answers
116 views

Maximizing dot-product score by asking queries

Let $a>b>0$, and let $T=\{a,b\}^n$ be the set of all $n$-tuples each entry of which is $a$ or $b$. Let $X\subseteq\{0,1\}^n$ with $|X|>1$, and let $f:T\rightarrow X$ be a function. For each ...
1
vote
1answer
50 views

dominated strategy can never be used in mixed strategy nash equilibrium

dominated strategy can never be used in mixed strategy nash equilibrium. how to prove it? Sounds like obvious, but how to write the proof mathematically correct?
1
vote
1answer
211 views

Second-price sealed-bid auction uniformly independent with unknown value

a disclaimer before the question: this is a homework problem. I just want some help/push in the right direction, I'm kind of stuck! The problem is as follows: In a second-price sealed-bid auction for ...
0
votes
1answer
96 views

Find the nim-sum of all numbers from 1 to ((2^n)-1) where n >1 is a natural number

I started learning nim sum , the examples given in class were all two number kind of problem . What should I do with this kind of problem ?
1
vote
1answer
49 views

$3\times 3$ matrix game where PI has a totally mixed optimal strategy, but also has an optimal strategy which is not totally mixed.

I am asked to give an example of a $3\times 3$ matrix game where PI has a totally mixed optimal strategy, but also has an optimal strategy which is not totally mixed. So I know that ...
1
vote
1answer
54 views

Updating in game with normal distribution

In a game from the following paper, it is stated that Player $i$ observes a private signal $x_i = \theta + \epsilon_i$. Each $\epsilon_i$ is independently normally distributed with mean $0$ and ...
1
vote
2answers
63 views

Strategy In auction bidding

I was at an auction recently where three autograph signatures of Marilyn Monroe were up for auction, not as a single lot, but in three separate lots. The three lots were virtually identical, and all ...
1
vote
1answer
101 views

Battle Ship Winning Algorithm - Optimal Strategy

I have an $8 \times 8$ grid. I have three ships that are $4$ long, $3$ long, and $2$ long. Is there an algorithm that can ensure a win every time? Oh! Most importantly, you must know the number of ...
1
vote
1answer
698 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
246 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
66 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
223 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
313 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
105 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 ...
3
votes
0answers
60 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
129 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
677 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
305 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
179 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
117 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
86 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
279 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
406 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
413 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
358 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 ...
5
votes
3answers
225 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
64 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
146 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 ...