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].

Filter by
Sorted by
Tagged with
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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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\...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
-4 votes
1 answer
73 views

Calculate card percentage return [closed]

No sorry this isn’t how things work around here
user avatar
  • 13
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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]$. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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+\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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} & \...
user avatar
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\...
user avatar
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\:\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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|...
user avatar
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 ...
user avatar
  • 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 + \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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?
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
63