# Tagged Questions

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

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 ...
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 ...
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_{...
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, ...
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 ...
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 ...
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$, ...
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 ...
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 ...
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 ...
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 "...
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 ...
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? ...
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,...
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 ...
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 ...
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 ...
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 ...
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.$ ...
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$,...
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 ...
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. ...
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 ...
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 ...
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," "...
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 ...
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 ...
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". ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} a_{...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 \\...
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 ...
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: \dot x_{i} = x_{i} \left( \sum_{j=1}^{n} a_{ij}x_{j} - \phi \right) \qquad i = 1, \...
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 ...
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 ...