Questions tagged [game-theory]
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].
3,145
questions
1
vote
0
answers
30
views
Question on John von neumann's minimax theorem.
in the process of proving the theorem there is this step
Suppose $Κ(x,y):X\times Y\rightarrow \mathbb{R}$ continous function and strictly convex wrt $y$ and strictly concave wrt $x $ where $X\times Y$ ...
- 29
0
votes
0
answers
21
views
Modified Balls in Bins Game Theory Problem
There are 3N players playing N gambles and each player has the same amount of money.
For each game, each player could choose to bet some money (from 0 to 100%). The player who placed the highest bet ...
0
votes
0
answers
39
views
Is the Game of Life predictable?
I played the Game of Life intensively for a while. I tried to keep things alive from all kinds of initial configurations and succeeded up to about 1000 iterations maximally. Everything died all the ...
- 156
2
votes
0
answers
35
views
correct terminology for "dead-end game"
Apologies if this question has an obvious answer! My research is in pure math, but I've started to think about some applied problems that are similar to this game. The player arranges numbers 1-19 ...
- 121
3
votes
0
answers
60
views
Winner of impartial King placing game
The game is played on an $n\times n$ board. Two players take turns placing kings, such that no two kings attack each other. The last player to move wins. If $n$ is odd, I think the game is a win for ...
- 31
1
vote
0
answers
53
views
I canot find what does $\langle,\rangle$ mean in a cooperative game theory book [closed]
Does anyone know what here on the page 83 it holds that $ \langle x,y\rangle\geq \langle x,y'\rangle$ in taking the minimum ?
I.e. I cannot find the notation $\langle,\rangle$ in the book.
- 3,598
-1
votes
0
answers
42
views
Convex games and a convex function $f:\mathbb{N}\to\mathbb{R}$
I'm stocked with this exercise in Game Theory...
A function $f:\mathbb{N}\to\mathbb{R}$ is called convex if $\forall i,j,k\in\mathbb{N}$ such that $i\le j\le k$ and $j<k$,
$f$ satisfies $\left(k-i\...
- 11
1
vote
0
answers
30
views
Is the minimizer of this function always rational?
Let $M$ be a skew-symmetric $n \times n$ matrix of integers. Let $S$ be the (convex) set of all $p \in \mathbb R^n$ such that:
$p_{i} \ge 0$ for all $i$
$\sum_{i} p_{i} = 1$
$(Mp)_{i} \ge 0$ for all $...
- 283
1
vote
1
answer
35
views
Combining Rate of Winning | Multiplication or Addition
Problem
Imagine I play the lottery and have a $2\%$ rate of winning. My friend also plays the lottery and has a $1\%$ rate of winning. Whoever wins, we will share the prize.
We could think our ...
- 113
0
votes
2
answers
88
views
The win rate of three player rotation battle
Three players $A,B,C$ are playing a game.
Players play against each other in round, the order of battle is
$$AB \to BC \to CA \to AB \to \cdots$$
Players need to win two consecutive rounds to win the ...
- 863
0
votes
0
answers
26
views
Branches evaluation in infinite binary tree
I have been thinking about a proposition on infinite trees, which seems to be false but I can't find any counterexample.
The problem :
Let $T$ be an infinite binary tree, where all nodes are of ...
- 23
1
vote
0
answers
46
views
Assume unknown tennis players B & D in three set match. Find Relation in $p$ [Probability B wins First Set] & $q$ [Probability Match ends in two sets]
Problem
If we assume that two completely unknown tennis players B and D are facing each other in a three set match.
Let $p$ be the probability that B wins the first set
Let $q$ be the probability ...
- 29
4
votes
3
answers
168
views
Construct a fair game with a $N$ sided die
You have a $N$ sided die. And $X$ players. You have to devise a game, such that only one player wins and every player is equally likely to win.
Also, the game should be finite (there shouldn't be a ...
- 4,491
0
votes
0
answers
10
views
mixed strategies when strategic space is convex
I am new to game theoretic concepts. I have read that "in a two player zero sum game, if the strategy space of a Player is convex then she may need not consider any mixed strategies". Can ...
- 11
0
votes
0
answers
11
views
Model team strength based on outcome of games
Say I have four teams, $A, B, C,$ and $D$.
I have a data set that looks roughly like
teamOne
teamTwo
win?
A
B
1
C
B
0
...
...
...
D
A
1
where whether a team is teamOne or teamTwo is random and ...
- 121
0
votes
0
answers
9
views
Mechanism Design problem about IC and IR conditions
here
I have some doubts about the mechanism-design exercise in the image. Since there are 2 options that B can choose to default, not default, and 2 types including type 1, type 2, and having loan, ...
0
votes
0
answers
19
views
Why Nash or correlated equilibrium require complete information?
In games of complete information, there are common solution concepts such as Nash equilibrium and correlated equilibrium. The idea is that each player is playing a best response.
My question is - Why ...
- 1
-4
votes
1
answer
73
views
0
votes
0
answers
13
views
PUCT Analoge for Adversarial Bandits
Many people are familiar with PUCT, the multi-armed bandits algorithm that produces good results (logarithmic regret) in the stochastic regime that utilizes 'predictions' of the best arm. This ...
0
votes
0
answers
32
views
Can one use Combinatorial Game theory in PvP video games, specifically Fighting games?
I have always loved the idea of combinatorial games like Chess and Go, and in my head, I always believed that Fighting games can follow that same logic. So I decided to start writing a simple High ...
0
votes
0
answers
29
views
Optimal strategy to win this football match
You're the trainer of a football team playing an opponent, and you can let your team play either in a defensive tactic, or an attacking one. You can switch between tactics at any moment, as often as ...
- 301
3
votes
1
answer
76
views
A game with numbers modulo $N$
Let $N\geq 4$ be a fixed positive integer. Two players, $A$ and $B$ are forming an ordered set $\{x_1,x_2,...\},$ adding elements alternatively. $A$ chooses $x_1$ to be $1$ or $-1,$ then $B$ chooses $...
- 874
1
vote
1
answer
86
views
Picking k numbers from 1 - 100
Assume A and B play a game with C.
C will pick a random number from $1$ to $100$, and A and B both pick $k$ different integers between $1$ and $100$ inclusive.
Say A picks $a_1, a_2, \ldots, a_k$, B ...
- 323
0
votes
1
answer
26
views
How to find the Nash equilibria of a game with continuous strategy spaces
Let $u, w \geq 0$. Let the payoff function $f_1: [0, u] \times [0, w] \to \mathbb{R}$ for player $1$ be defined as $$f_1(a, b) = \frac{u - a}{1+e^{a-b}} $$
for $a \in [0, u]$ and $b\in [0, w]$.
...
- 314
-2
votes
1
answer
47
views
Game Theory problem with n piles and 2 players, one player selects 2 piles, the other takes from one of them
Player 'A' and player 'B' play with n piles of stones. 'A' starts the game. He chooses 2 piles, the 'B' takes an arbitrary (but nonzero) number of stones from one of them. Then 'B' selects two piles ...
- 1
1
vote
1
answer
33
views
Conditional expectation of max{Y,r} given Y < x
I have difficulties computing the following conditional expectation:
$$E[\max \{Y_1,r\}|Y_1 < x]$$
the CDF of $Y_1$ is G(`).
I browse other questions that deal with only one part of the conditional ...
- 45
1
vote
1
answer
79
views
Are there any non-trivial stable tournaments?
In graph theory, a tournament is a graph where every pair of vertices are connected by exactly one directed edge.
In this problem, each tournament represents the possible outcomes of a two-player ...
- 2,210
0
votes
0
answers
21
views
Looking for reference for minimax solution of 2p zero-sum game, NxN choices
The game in this wikipedia section https://en.wikipedia.org/wiki/Minimax#Example, also see here at Math.SE Minimax solution for Zero-Sum Game, is easily generalized to an NxN game. Let A be an NxN ...
- 23
0
votes
0
answers
21
views
Public/private knowledge in auctions.
Consider three firms that engage in a first-price auction. Firm $i$'s payoff when firm $j$ wins the auction is $S_{i,j}$.
The winning firm $i$ has to pay its bid and faces transaction costs $\tau_i+\...
- 41
5
votes
1
answer
75
views
A Combinatorial Game Riddle - two players dividing towers
I have recently been struggling on a riddle- it's a Nim type of game.
In front of two players, there are $n_1, n_2, \dots, n_k$ height towers ($k$ towers, each of them of some integer height).
On each ...
- 51
0
votes
1
answer
25
views
Game Theory - What is the equilibria?
I think i'm braindead from the amount of time i've stared at this. What is the equilibria in each of the scenarios in this? and preferably the subgame perfect equilibrium? Is there even any, as player ...
2
votes
1
answer
85
views
What was so "Groundbreaking" about Bellman's Equations?
In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this ...
- 1,688
0
votes
0
answers
22
views
Mixed Strategy Nash Equilibria of 2x3 Game
The setup of this game is very similar to the setup of the game in another question I found (Find all mixed-strategy Nash Equilibria of 2x3 game.):
$$\begin{array}{c|c|c|c}
& \text{L} & \...
0
votes
0
answers
22
views
When M is a payoff matrix what does $\max\limits_{i} \min\limits_{j} M_{ij}$ and $ \min\limits_{j} \max\limits_{i} M_{ij}$ mean exactly?
I am reading a book on randomized algorithms leading up to Yao's Technique and I stumbled on the following min/max notation for some payoff matrix $M$:
$$\color{green}{(1)}: \max\limits_{i} \min\...
- 269
0
votes
0
answers
30
views
Computation of Nash equilibrium in a concave game
so we have the game $(N,(S_{i})_{i\in N},(\varphi_{i})_{i\in N})$ where :
$\bullet\:N$ is the set of players
$\bullet\:S_{i}=[a_{i},b_{i}]$ the set of strategies for each player $i\in N$
$\bullet\:\...
- 1
0
votes
0
answers
13
views
Name of a simple communication / coordination game
Is there a name for the game with extensive form given in the image below? Are there any references that study it? I am not well versed in game theory so I would appreciate any pointers. I am sure it ...
- 177
1
vote
2
answers
39
views
Rarity ratio for an object
I'm not sure of the terms, but let me explain the problem with a simple example.
Suppose there is a certain set of parameters for random generation of an object, in this case a colored geometric ...
- 23
0
votes
1
answer
32
views
Problem of auction
This is a real-life problem around me...
I, with two roommates, am going to rent a house of price $T$. The house rented has three rooms, one of them is larger and two of them are smaller. We agree ...
- 2,536
2
votes
1
answer
41
views
Why is minimax always greater or equal to maximin?
Let $f(x,y)$ be a function representing a game, we define the maximin : $\underline{f} = \max
_{x∈X} \min
_{y∈Y}
f(x, y)$ and the minimax $\overline{f} = \min
_{y∈Y} \max
_{x∈X}
f(x, y)$. It is said ...
- 996
1
vote
1
answer
48
views
An Extension of Gambler's Ruin
Suppose there is a gambler who has $n$ dollars gambles for infinitely many times. The payoff of the $t^{th}$ round is $X_t$, which is an integer beween $-1000$ and $1000$. We know that $\mathbb{E}[X_t|...
- 13
2
votes
1
answer
27
views
Equivalent representation of a system of linear (in)equalities
I am reading about the equivalence between zero-sum games and LPs from Adler's 2012 paper.
Right after lemma 3, he writes that it is equivalent to represent
$$
(\mathsf{A}) := \{x:Ax=b\} = \{x:Ax\geq ...
- 2,370
2
votes
0
answers
48
views
Game theory - Strategic Games - Incomplete Information problem
Player $A$ and Player $B$ contribute hours towards building a house. If player $A$ contributes $x ≥ 0$ hours and player $B$ contributes $y ≥ 0$ hours, then the value of the house will be $x + y + \...
- 21
0
votes
0
answers
20
views
Game theory: Probability of moving up to the next level in a game vs probability of moving down a level
In a game, Adam starts out with $600, 000$ coins. If you win a game the prize is $50,000$ coins: if you lose the game you lose $50,000$ coins. Adam's win $\%$ over many thousands of games is known to ...
- 12.2k
1
vote
1
answer
31
views
Does every perfect information game in extensive form have a Nash equilibrium?
I have been struggling to reason whether this is true. Given a perfect information in extensive form (say chess or many such board games), is it guaranteed that there exists a pure strategy Nash ...
- 113
3
votes
1
answer
77
views
Winning strategy for a game, solution verification
Let $n \in \mathbb{N}$. Two players play a game. Both players have to write a $0$ or a $1$ each move. A player loses if his last number created a sequence of length $n$ that already existed (also if ...
- 119
0
votes
0
answers
34
views
How do you find this pure-strategy Nash Equilibria in this public good game?
I am having trouble with question 2 of this exercise.
Consider a public good game with two consumers who have identical marginal valuation 0 < θ < 1 for the public good. The public good is ...
- 1
0
votes
0
answers
21
views
Under which conditions is the subgame perfect nash equilibrium unique?
Suppose that we have a finite complete information game, under which conditions is there a unique subgame perfect nash equilibrium (if it exists)? Does it matter if the game is perfect information?
0
votes
0
answers
38
views
Guess 2/3 of the average, but your payout is what you initially guessed.
The "Guess $\frac{2}{3}$ of the average" is a game where $k$ people choose a number between 0 and 100 inclusive, and the person with the closest answer to $\frac{2}{3}$ of the average wins. ...
- 31
2
votes
0
answers
45
views
Show that B can always win a polynomial game
A polynomial $f(x) = x^4 + * x^3 + * x^2 + * x+1$ has three undetermined coefficients denoted by stars. The players A and B move alternately, replacing a star by a real number until all stars are ...
- 893
0
votes
0
answers
27
views
Are my steps correct in showing a particular mixed strategy is not a Nash equilibrium
2 players play a (zero-sum) game of rock paper scissors. The payoff matrix is given in the form of the table below (note all payoffs are made in terms of the row player i.e. if row player picks rock ...
- 640