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

learn more… | top users | synonyms

2
votes
1answer
608 views

What is the probability that the loser has won exactly $k$ games when the match is over?

Adam and Eve play a series of games of tennis, stopping as soon as one as them has won $n$ games. Suppose that they are evenly matched and that Adam wins each game with probability $1/2$, ...
2
votes
0answers
24 views

A Generalized Mechanism for Gale-Shapley

I am working on some problems in my applied graph theory course, and we have just gotten to matching problems. We are currently working on a graph problem where instead of there being two types of ...
2
votes
3answers
45 views

Terminology for a game in which Black and White have the same “probability” to win

Consider a game between two players, Black and White. The game is sequential and ends after finitely many moves. White moves first. The game ends either in the victory of one of the players or in a ...
0
votes
1answer
29 views

Calculations for grid based games

For a grid game to match items in chains of 3 or more, how can a difficulty be calculated? I have a number of moves, and a grid with a cell count and an element type count n, e.g. 6 different ...
0
votes
2answers
36 views

Does a game need below-average players

I am no mathematician, just a programmer and gamer who thought about this problem. I reckoned it's more relevant here than one of the gaming-SEs, as it's not really about any particular game, but ...
1
vote
1answer
55 views

Who will win the game?

There are two players $A$ and $B$. There are two bags with $n_1$ and $n_2$ things in it. $A$ will start the game and can take out $x$ where $1\leq x \leq \min(n_1,n_2)$ number of things from either ...
1
vote
1answer
21 views

SPNE of a finitely repeated game

So I have this little game between two players, played T times without any discouting factor with the following payoff table: now if T is 2, is there a SPNE where (B,L) is being played first round? ...
2
votes
1answer
79 views

A game involving a Poisson process

Let T > 1. We observe a Poisson process of rate 1 on the time interval (0, T ). Each time a point occurs, we may decide to stop. Our goal is to stop at the last point which occurs before time T; if ...
3
votes
2answers
56 views

Nash equilibrium: comparing different definitions

A Nash equilibrium seems to be defined in different ways in different books. Sometimes a Nash equilibrium refers to a single strategy (Definition $1$ below) and sometimes a Nash equilibrium is defined ...
2
votes
0answers
223 views

How can all players in the Starcraft 2 Grandmaster league win more than they lose?

Starcraft 2 is a competitive online strategy game where players compete in leagues with other players of similar skill. The most difficult and highest league is the Grandmaster (GM) league, which ...
3
votes
2answers
72 views

What is the axiom of quasideterminacy?

This is something mentioned in the "See also" of the wikipedia page for the axiom of determinacy, but when you click on it it takes you to the page for "Determinacy" and the section for ...
1
vote
1answer
22 views

Verifying Correlated Equilibria for a game of Chicken

I'm reading Computing Correlated Equilibria in Multi-Player Games (C.H. Papadimitriou, T. Roughgarden). Consider the following extracts While the following extract is from here, it is ...
2
votes
2answers
120 views

First mover advantage in a Stackelberg game

I am considering a simple game with two firms. Each firm faces the following demand function \begin{equation*} q_i(p_i,p_j)= a- b p_i + cp_j, \end{equation*} where $i,j\in \{1,2 \}$ and $i\neq j.$ ...
2
votes
1answer
52 views

7 hats, 6 prisoners

I came across this variant of the prisoner-hat problem the other day and couldn't seem to muster a proper solution: $6$ prisoners are on an island and are each assigned a hat numbered $1$ through ...
2
votes
1answer
98 views

Game theory: Finding Nash equilibrium in $3\times 3\times 3$ matrices

I tried to find how to solve $3\times 3\times 3$ matrix to find Nash equilibrium but I could not find anything on the web. Maybe I am searching with wrong keywords... I understand how to solve Nash ...
1
vote
0answers
18 views

Difference between Sequential and Weak Sequential Equilbria

This is in reference to the Game theoretic concepts as Nash equilibrium refinements. Sequential equilibrium are often defined as satisfying two conditions: consistency and sequential rationality. ...
0
votes
1answer
26 views

Recursive utilities in a repeated game

I am trying to set up utilities for an infinitely repeated game and I am having some trouble figuring out how to write the correct functional form. This game has a stochastic component where a ...
3
votes
0answers
65 views

Compute shooting targets for the gunmen

This is an extension of the well known "3 gunmen puzzle": N gunmen with hitting probabilities in (0,1] take turns to shoot at each other. Firing order is fixed (gunman 1 shoots first, then gunman ...
3
votes
1answer
33 views

Representations Verse Solution Concepts

In Game Theory, we generally refer to "normal form" and "extensive form" as representations. And, we generally describe "Nash Equilibrium," "strictly dominated strategies," "maxmin strategies," ...
2
votes
2answers
43 views

Can a modified $19\times19$ checkerboard be tiled with decominoes ($10\times1$ rectangles)

Consider a $19\times19$ checkerboard with the center square removed, the four corner squares removed, and with four extra squares-one above the center square of the top row, one below the bottom ...
1
vote
0answers
50 views

Nim game real life applications

I've learned how to prove and apply the Nim game strategy in discrete mathematics, but I was wondering if there is any real life examples and application for this theory. I searched online and didn't ...
2
votes
0answers
108 views

Game theory, Book by Tirole and Fudenberg, Never a weak best response,unclear example

In this book, I have the following problem: on page 446, there is a sentence: Note that $(0.9,0.9)$ is not removed by NWBR, as D is not dominated after C is deleted. I do not understand this "as". ...
2
votes
1answer
77 views

Pick a number that is better than your friends

Consider the following game. There are $n$ players, each one has to pick a (real) number $x$ between $0$ and $100$. There is one round to the game. The winner is the person whose number is closest ...
1
vote
1answer
69 views

A game with coin toss

So I have a game between two players, p1 and p2. Someone(nature?) tosses a biased coin with 80% chance on head. p1 observes the outcome of it and write on a piece of paper head/tail(not neccessarily ...
1
vote
0answers
19 views

does individually strategy proof implies coalitionally strategy proof?

Suppose $F$ is a social choice function \begin{equation*}F:N\rightarrow A\end{equation*} where $N=\{1,...,n\}$ is the set of agents and $A$ is a finite set of outcomes. suppose that $F$ is ...
0
votes
0answers
47 views

Finding an equilibrium to this game

So this question was given in an exam: One of Player 1 and Player 2 need to wake up in the morning to receive a package. Neither wants to wake up early and that is the cost to each player. Both the ...
0
votes
0answers
30 views

Game theory - coalition game question

The following is a question from a past exam that I am studying: For a 3-person game of perfect information. Let S denote the set {1,2,3}. First player A chooses i ϵ S. Then player B, knowing i ...
2
votes
1answer
71 views

Probability in the board game “Istanbul”

I tried this game yesterday with a couple of friends (really interesting, although I did not win, I would definitely recommend it) here is a small piece of the game: A player first calls out a ...
1
vote
1answer
46 views

Optimal strategy in chicken game

Consider a one-shot, simultaneous chicken game, as described here: https://en.wikipedia.org/wiki/Chicken_(game) Assume that I'm playing this game against a player that I consider to be of similar ...
1
vote
0answers
49 views

Replicator equation for mixed strategies?

The the replicator equation is usually defined for pure strategies. More specifically, the replicator eqn for $n$ strategies is given by: \begin{equation} \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} ...
3
votes
1answer
66 views

Algorithm for assigning users to “buckets” according to users' preferences and ranking

Suppose there is a set of $n$ users which must each be assigned to one, and only one, of $k$ mutually exclusive "buckets". However, the number of users allocated to the $i$-th bucket must be no lower ...
1
vote
0answers
58 views

Bayesian Equilibrium

We have to answer the following question, and I can make some progress on the first couple of parts but get stuck in finishing them off. The third part I'm not sure where to start! *Consider the ...
0
votes
0answers
44 views

How do I prove using strong form induction a statement regarding winning strategies in this coin game?

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins ...
0
votes
0answers
10 views

obtaining cases from the integral equation

I'm struggling with the recalculation of the formal model from the published article by Epstein and O'Halloran (1994), and I am failing miserably when it comes to understanding of their calculation, ...
2
votes
1answer
101 views

Bayesian game theory

We have to answer this question and I think I have done part (a) right but get stuck at part (b). Since $-0.5 \le \varepsilon_i \le 0.5 \ \forall i$, I seem to get a solution of the NE being TR, which ...
4
votes
1answer
95 views

Winning Strategy with Addition to X=0

Problem: Two players play the following game. Initially, X=0. The players take turns adding any number between 1 and 10 (inclusive) to X. The game ends when X reaches 100. The player who reaches 100 ...
0
votes
1answer
38 views

Expected value, discrete random variable,discount factor

This example is taken from HERE ,page 424: What is the expected value $X(v)$ of this series: $X(v)=E(\Sigma_{t=0}^{\infty}\delta^t p_t(v))$ where $p_t(v)\in[0,1]$ with $\delta\in(0,1)$? Are all data ...
1
vote
1answer
27 views

Disprove that the given strategy pair is a solution to the game.

Problem: For the following matrix game, prove or disprove that the given strategy pair is a solution to the game. \begin{align} A &= \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & ...
0
votes
0answers
19 views

Payoff Matrix/ How to fill positions in the matrix — Game Theory.

The Problem state: P1 and P2 each have three cards: a king, a queen, and a jack. They play their cards, one at a time, with the high card winning the trick (K>Q>J) and the playing of equal cards ...
2
votes
0answers
35 views

Why doesn't the frequency of a strategy reach zero under the replicator dynamics?

Background The replicator equation with $n$ strategies is given by the differential equation: \begin{equation} \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} a_{ij}x_{j} - \phi \right) \qquad i = 1, ...
0
votes
0answers
13 views

Information sets in Extensive Form Game with imperfect information

I have constructed an extensive form game with imperfect information given in the attached image. I am however a little uncertain as to whether my information sets are actually admissible if I, for ...
2
votes
1answer
19 views

When does a matrix game and the sign flipped matrix game have the same nash equilibria?

Given a game $G$, we can construct another $G'$, by a positive scaling i.e. $\lambda \in \mathbb{R}_{++}$, s.t. each entry of $A$ is scaled by $\lambda$ Obviously, $G$ and $G'$ have the same nash ...
0
votes
1answer
59 views

Mixed Nash equilibria in $n$-player games

I'm reading up on Game Theory. So far, I feel like I have a pretty good understanding on two-player games and their properties. Consider a two person game where the payoff matrices are $A_{m\times ...
0
votes
0answers
17 views

Subgame perfect nash equilibrium in a non-Prisoner Dilemma Game

working on this for hours but I can't find any solution yet ... I got a 3x3 matrix of a non-Prisoner dilemma game It looks like that:      C2      D2 ...
0
votes
0answers
58 views

How many distinct strict ordinal 2x2x2 games exist?

Consider the same type of strict ordinal games as described in How to simply show that there are "78 'strict ordinal' 2x2 game matrices" and add a third player with two strategies ...
0
votes
0answers
23 views

Sustaining cooperation

The question poses: Explain why better monitoring of treaty compliance can be more effective at sustaining cooperation I'm assuming this question is talking about one's reputation for example? If my ...
1
vote
1answer
27 views

Optimal point selection to maximize length of closest points interval

Consider the following game: there are $n$ players, who pick $x_i\in I = [0,1]$ in turns, $1\leq i\leq n$. For each selection $x = (x_1,\dots,x_n)\in I^n$, the player's $i$ reward is the length of the ...
1
vote
2answers
38 views

IRV failing monotonicity criterion

I am looking for the simplest possible example of instant runoff voting failing the monotonicity criterion. By “simplest possible” I mean the scenario with the fewest number of candidates $(3)$ and ...
0
votes
0answers
42 views

Combinatorial Allocation Problem

The problem I am trying to solve is that there are $m$ distinct items to sell through a combinatorial auction and bids have been received. But for any pairs of bids $b_i(X)$ and $b_i(Y)$, the subsets ...
1
vote
0answers
213 views

Game theory book by Tirole,Fudenberg, zero up to first order of $\epsilon$,equilibrium

In this book on Game Theory, on page 186,I do not understand the very end of the page: [T]he incentive to deviate$-$the left hand side of equation 5.18$-$ is $0$ in first order of $\epsilon$, so that ...