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

0
votes
0answers
6 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
213 views

Existence of Saddle Point of a Matrix (Shapley's Theorem)

A $m\times n$ matrix $M=(a_{ij})_{m\times n}$ with real entries is said to have a pure saddle point at $(i_0,j_0)$ if $\min_j \max_i (a_{ij}) = \max_j \min_i (a_{ij}) = a_{i_0j_0}$. Here the notation ...
1
vote
2answers
47 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 ...
2
votes
1answer
27 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
votes
1answer
225 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 ...
1
vote
1answer
229 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? ...
5
votes
1answer
114 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, ...
4
votes
1answer
103 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
0answers
31 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 ...
0
votes
0answers
13 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 ...
14
votes
1answer
447 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" ...
-2
votes
0answers
14 views

Mathematics of Poker (Study Partner) [closed]

Hey guys (and girls), Would anybody here be interested in working through the latter half of the book "Mathematics of Poker" together/possibly doing some other game theory things related to poker ...
18
votes
2answers
318 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 ...
3
votes
1answer
49 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 ...
0
votes
0answers
12 views

Formula for Value of Games Without Saddle Points

I've read that the value of a game with payoff matrix [ a b ] [ c d ] that has no saddle points is (ad − bc)/(a + d − b − c). Does anyone know what the general ...
5
votes
2answers
68 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
1answer
32 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
94 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 ...
1
vote
1answer
39 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 ...
377
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 ...
4
votes
0answers
38 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 ...
0
votes
0answers
35 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 ...
0
votes
1answer
433 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 ...
3
votes
1answer
713 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 ...
4
votes
1answer
375 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$ ...
0
votes
1answer
79 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
3
votes
1answer
380 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
94 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 ...
0
votes
1answer
31 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
119 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
11 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
43 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
125 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
34 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
77 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
57 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
58 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
60 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
0answers
52 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
518 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
57 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
37 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
148 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
29 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
51 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
42 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
321 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 ...
1
vote
1answer
57 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
148 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
64 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): ...