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

2
votes
0answers
69 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
100 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 ...
0
votes
0answers
28 views

Mixed strategy approximations in a large game

I'm new to game theory and was thinking about how to find mixed strategies for a particular game, and furthermore how to find good mixed strategy approximations of a game that may be too large to ...
1
vote
1answer
24 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
44 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
0answers
27 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
28 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 ...
0
votes
0answers
29 views

problem solving strategy excerises

given 5 bowls with the following amount of balls inside: 1 in the first, 3 in the second, 5 in the third, 7 in the fourth, and 9 in the fifth. There are two players, each player in turn is permitted ...
1
vote
1answer
39 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
44 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
64 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 ...
0
votes
1answer
49 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
607 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
52 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
42 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
22 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 ...
1
vote
2answers
26 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 ...
3
votes
1answer
84 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
54 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
91 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
257 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
40 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
26 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
78 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 ...
14
votes
1answer
486 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" ...
0
votes
0answers
45 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
1answer
140 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
54 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 ...
4
votes
0answers
49 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
42 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
115 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
84 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
376 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
124 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 ...
0
votes
1answer
133 views

Subtraction game between alice and bob [closed]

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 ...
1
vote
2answers
42 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 ...
0
votes
0answers
21 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 ...
2
votes
3answers
153 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
45 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
128 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
38 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 ...
1
vote
1answer
69 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
69 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
61 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
43 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
61 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 ...
2
votes
2answers
547 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
51 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
82 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 ...
9
votes
1answer
221 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 ...