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

0
votes
0answers
33 views

A Dual Matching Market In the Roommate Problem

I am working on developing some new mechanism related to the Roommate Problem, which is a problem where given a set of $n$ agents, each agent can establish preferences on the other $n-1$ agents in the ...
1
vote
1answer
23 views

Re-implementing Matching Pennies

I'm a little confused on a problem from my game theory course. I am reviewing the standard ``matching pennies'' game where player $1$ wins $1$ and player $2$ loses $1$ if the their two pennies match ...
5
votes
1answer
73 views

How can I find the Nash-equilibrium of the following zero sum game?

I want to find the Nash-equilibrium of the following zero sum game. $$A=\begin{bmatrix}0&2&-1\\-2&0&3\\1&-3&0\end{bmatrix}$$ I used the Minimax Theorem. $$min_{x \in X} max_{...
2
votes
1answer
37 views

Strategies on a symmetric chess play

The idea is that the difficulty of the game of chess is derived primarily from the asymmetry between the king and queen. all other chess pieces are arranged symmetrically and can move symmetrically, ...
0
votes
1answer
67 views

Paradox of Random Natural Numbers

I've got a question about a game taken from a book called Rachunek prawdopodobieństwa dla (prawie) każdego by Jacek Jakubowski and Rafał Sztencel. Adam and Bolek have a machine that generates a pair ...
1
vote
1answer
43 views

Mixed Strategy Equilibrium of a Game

I am having some problems with an exercise that showed up in my game theory course. Consider the two player game where each player bids a non-negative integer multiple of five cents. The highest ...
2
votes
1answer
615 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
28 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
31 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
37 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
56 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
27 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
85 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 so,...
3
votes
2answers
57 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
257 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
73 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
23 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
142 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
54 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 $7$,...
2
votes
1answer
109 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
27 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
66 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
53 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
112 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
78 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
75 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
20 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
32 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
79 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
57 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 ...
2
votes
0answers
51 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} a_{...
3
votes
1answer
75 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
63 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
11 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
106 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 ...
5
votes
1answer
97 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
39 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 & 2 \\...
0
votes
0answers
23 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
37 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
15 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
63 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
18 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  ...