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
0answers
22 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 ...
0
votes
0answers
24 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 ...
1
vote
0answers
40 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 ...
1
vote
0answers
30 views
+100

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
23 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 ...
0
votes
1answer
15 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
23 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
23 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
18 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
25 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 ...
0
votes
1answer
32 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
0answers
53 views

Door game between alice and bob

Alice and Bob are taking a walk in the Land Of Doors which is a magical place having a series of N adjacent doors that are either open or close. After a while they get bored and decide to do ...
1
vote
2answers
41 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
56 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
19 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, ...
16
votes
9answers
454 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
48 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
23 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
15 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
23 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
2answers
74 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
43 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
53 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
247 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
32 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 ...
3
votes
1answer
54 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
457 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
14 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
118 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
41 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
40 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
33 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
99 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
37 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
340 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 ...
5
votes
2answers
72 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
85 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 ...
0
votes
1answer
33 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
16 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
126 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
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
126 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 ...
1
vote
1answer
61 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
62 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
54 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
38 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
53 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
75 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?