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
25 views

Finding mixed strategies question

Suppose I have a payoff matrix where each of the two players has three pure strategies. For player two, one of his staegies is weakly dominated. If I am seeking the mixed Nash equilibrium, do I ...
0
votes
4answers
74 views

In a game of drawing straws, why are all turns equally good?

For example, there are 3 straws in a pile - 2 long and 1 short. The person who draws the shortest straw loses. When a straw is drawn, it is removed from the pile. Drawing first, second, or last all ...
1
vote
0answers
44 views

Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
0
votes
0answers
32 views

does the max-min inequality hold for constrained functions?

I would like to know if the max-min inequality holds for constrained functions (e.g. MILPs). my problem looks like: $$\min_{w \in W} \max_{q \in Q(w)} F(w,q) \ge ? \max_{q \in Q} \min_{w \in W} ...
1
vote
0answers
20 views

Game Theory Rulerette, Sprague-Grundy Theorem

Here is the question: Rulerette. Suppose in the game Ruler, we are not allowed to turn over just one coin. The rules are: Turn over any consecutive set of coins with at least two coins being ...
0
votes
0answers
31 views

Why is a weakly dominated strategy not played in a mixed strategy equilibrium mixture?

This question has been bugging me a lot. If you take this game, for example 1/2 | L | R U | 12,1 | 8,8 D | 15,1 | 8,-1 My instructor said the equilibrium to this is (D,L), even though (U,R) is a ...
1
vote
1answer
51 views

Some zero-sum game

Consider a game with the following payoff-matrix $\textbf{M}=\begin{array}{c|c c c c} \! & A & B & C & D \\ \hline A & 0 & 1 & -1 & 0 \\ B & -1 & 0 & 1 ...
0
votes
1answer
44 views

Maxmin and minmax strategies

I was solving for a stable equilibrium in the following 2 player zero sum game. I need to calculate the equilibrium using maxmin and minmax strategies. In this game they should come out to be ...
0
votes
2answers
15 views

A question about Game Theory Notation in symmetric Games

In Martin Osbourne and Ariel Rubenstien's book A Course In Game Theory (page 20) the authors say that a 2 person game is symmetric the A1 = A2 (both players have access to the same action set) and ...
0
votes
1answer
30 views

Verifying minimum of a function when second derivative is 0

I was solving for a stable equilibrium in a game. I calculated expected payoff of one of the players which came out to be the function $$E= -4pq + 0.1p + 0.2q + 0.7$$ where p is probability of an ...
1
vote
0answers
29 views

Blackjack Dice Probability - Odds of winning and where to stand

Hi I'm looking for help/advice in finding the solution to the following problem. Suppose I have a fair $101$ sided dice labelled $0$ to $100$, Your objective is to roll the dice any number of times ...
1
vote
1answer
34 views

Winner in this game with divisors

I was solving this SPOJ question, which is as below: N wooden pieces (marked with numbers 1 to N) are placed in a transparent bottle. On his turn the first player takes out some piece (numbered x) ...
1
vote
0answers
41 views

Name and related theory for game: “n-th Player to respond wins”

What is the classic name of the game "The N-th player to respond wins"? What are general strategies for the case when the number of total players is not known (or maybe there's only a prior on the ...
0
votes
1answer
56 views

Nash equilibrium for n players game

There is a question that I am trying to solve but I am not sure about my approach and is hoping I could get some help. Here is the question: There are $n$ companies sharing a water reservoir, let's ...
0
votes
1answer
22 views

Gaining intuition as to why maximal lotteries use randomness to break general ties

The maximal lottery is a voting system based on choosing an optimal candidate game-theoretically. If a winner isn't clear (there is no condorcet winner), then it will return probabilities as to which ...
5
votes
1answer
113 views

A coin tossing game with random probabilities

Let $p$ a random variable, uniformed distributed in $[0,1]$. Two player $A$ and $B$ play the following game: Starting from A, a player gets a random value $p(\omega)\in[0,1]$, and he has two choices: ...
1
vote
1answer
21 views

How to graph a rational reaction set?

In my game theory class, I am asked to graph the rational reaction set for the follow matrix: $\begin{bmatrix} (3,-1) &(-1,-4) \\ (-1,2) & (1,2) \end{bmatrix}$ I am not sure how to graph ...
0
votes
0answers
29 views

Uniqueness of saddle point solution to zero-sum game

Considering a two player zero-sum game, is a found saddle point solution unique? And if not, are there any conditions under which the saddle point solution is unique?
0
votes
0answers
10 views

Game theoretic expected utility function with two unknown parameters

I am working on a game theoretic model for my Master's thesis in Political Science, and I have calculated the following expected utility function for player $i$: ${EU}_{i} = 3-12{V}_{i}S$. Both ...
0
votes
1answer
40 views

Mechanism design with known utilities (game theory)

I'm trying to prove that in an n-party setting, where each party has a private value, the dominant strategy is always to reveal it. I'm assuming that parties only care about monetary payoffs and ...
0
votes
1answer
23 views

Does exchanging the rows or columns of a matrix game affect the outcome?

This is part of an assignment. I feel like this is a really trivial question or I'm missing some key idea. I'm asked whether exchanging the rows affects a matrix game. I believe it doesn't because the ...
1
vote
0answers
36 views

Optimizing generalized ternary search

There are $N$ socks numbered $1$ to $N$, one containing a gift. Dave needs to find the sock with the gift. He can ask some questions in order to find that sock: in each question, Dave chooses $2$ ...
1
vote
1answer
86 views

Game theory - Finding Nash Equilibria

i have to solve these questions. I already came up with a solution. Can anyone look over it and state their opinion? Many thanks in advance :) CHALLENGE I 1. Consider the following game between ...
3
votes
1answer
55 views

How to prove that the zero sum game's optimal (security) strategy do not change when payoff matrix increase by a constant factor

I am not sure how to construct a proof for something so obvious, can someone give me some pointers on proving the following Suppose a constant K is added to each element of a pay-off matrix ...
0
votes
2answers
43 views

Best Strategy in a Non-Cooperative Game of Perfect Information (Pure Strategies only)

Suppose there are two players in this game, and each player has $4$ dollars prior to making his move. Each player has as his strategy space the ability to submit an integer number of these $4$ initial ...
0
votes
1answer
32 views

Game Theory rationalizable strategies that are all the same

Suppose player 1 has strategies u, m, and d, and player 2 has strategies A, B, and C. The strategies A, B and C are all identical (payoff equivalent). Can any of them be eliminated using the ...
0
votes
2answers
70 views

Playing rock paper scissors over online chat.

Is there a way to play rock, paper and scissors fairly over internet chat? By this, I mean that both players cannot play their hands simultaneously, one of them has to go first and the second player ...
3
votes
1answer
66 views

What is the optimal losing move?

I had a hard time trying to find the best-suited stackexchange site to ask this question. I'm still not sure whether this is the right place, so please guide me to the right one if you think this is ...
2
votes
0answers
44 views

Optimal strategy to escape spotlight

Here is the setup. A prisoner is being held in the center a circular yard with radius $r$ and can run in any direction at some velocity $v$, there is a spotlight which illuminates a line on the circle ...
0
votes
0answers
26 views

One Million Proficiency Efficiency Calculations

I have been playing the "Million" game on my apple device after discovering it through the trending applications in the search function. After beating the game I began to wonder to myself if there was ...
0
votes
0answers
41 views

Find the mixed strategy Nash equilibria in the investment race

This is Exercise 35.2 in Rubinstein's "A Course in Game Theory". This problem is very difficult. The lecturer gave us the answer but it's very hard to understand. I paste the problem here: Two ...
0
votes
2answers
155 views

Is there any winning strategy? 2015 and Game with marbles!!!

Two players, Alex and Brad, take turns removing marbles from a jar which initially contains 2015 marbles. Assume that on each turn the number of marbles withdrawn is a power of two. If Alex has the ...
0
votes
0answers
28 views

Making sense of an Expected Utility of a Mixed-strategy Profile definition

I came across a definition of Expected Utility of a Mixed-strategy Profile in Brown's and Shoham's "Essentials of Game Theory: A Concise, Multidisciplinary Introduction" where: "Given a normal-form ...
1
vote
1answer
222 views

Maximize the Earning

There are two thieves with a total of 1 billion ($10^9$) dollars in a bank vault. Now they must decide how to divide the booty. But there is one problem: the thieves have only $M$ minutes to leave the ...
-1
votes
2answers
186 views

How to divide the money based on the below conditions? [closed]

Two cheeky thieves have collectively decided to rob a bank. They have carefully counted a total of exactly $100$ dollars in the bank vault. Now they must decide how to divide the booty. But there is ...
3
votes
1answer
42 views

Shapley values as a hash/compression of a game

Computing a Shapley value, we are mapping the set of coalition games on $N$ to a vector of $N$ elements: $$ \phi: \; \mathbb{R^{2^N}} \to \mathbb{R}^N $$ In a sense, this is compression, or more ...
3
votes
2answers
75 views

Multiplying Single Digit Numbers to Get Product >1000

This is yet another Alice and Bob problem. Alice and Bob are playing a game on a blackboard. Alice starts by writing the number $1$. Then, in alternating turns (starting with Bob), each player ...
1
vote
1answer
74 views

Good books to learn Combinatorial Game Theory? [duplicate]

I am currently doing my IB Diploma and we are supposed to make an extended essay on a subject of our choice- and i chose math. my research question is- "how to derive a perfect strategy to always win ...
1
vote
1answer
38 views

Game theory: solutions concepts if each player has different utility

Assuming, I have a network game (where the players are e.g. users in a network), how is it possible to model user-specific a-priori information (which results in different utility functions for each ...
1
vote
1answer
26 views

Question about usage of $\leq$ in definition of Nash equilibrium

Quick definition: Given $g$, a strategy N-tuple $u^* = (u_1^*,...,u^*_N)$ is said to be a Nash equilibrium if: $$J_i(u_i^*, u^*_{-i}) \leq J_i(u_i, u^*_{-i}), i \in N$$ where $J$ is ...
1
vote
1answer
62 views

What is the quickest way to find Nash equilibria in two player bimatrix game?

Suppose the cost/penalty matrix of a game is given as: $$M = \begin{bmatrix} (-5,-5) & (0,0) \\ (0,0) & (-3,-3) \end{bmatrix}$$ Then the game as two equilibria $(u_{11},u_{21})$ and ...
1
vote
1answer
33 views

Can someone please help me understand what a “player set” is in extensive form game

my text defines player set as: In N-player game $g$, each non-terminating node is partitioned into $N+1$ sets $g^0, ... g^N$. These are player sets. However it makes no attempt to identify ...
1
vote
1answer
29 views

Devising a method to arrive at a square only being able to move right and up

I was recently presented with a problem where I have a 10x10 grid and a marker that starts at position (1, 1). Two players are able to manipulate the marker by moving it as far right, or (exclusive) ...
0
votes
3answers
165 views

Reducing TIC-TAC TOE State Space by using Symmetry in Artificial Intelligence

Im learning Heuristics in AI.I see that for brute force search there are 9! states.But the textbook says that first 3 levels are reduced by symmetry.How does that work?
0
votes
1answer
26 views

A question in Osborne-Rubinstein A course in game theory,

I am having trouble with Rubinstein's electronic email game (proposition 83.1) in the textbook(first edition). My question: Line 7 starting from the "proof", "...player 2's expected payoff is at ...
4
votes
2answers
172 views

How many legal states of chess exists?

I have a fairly simple question. How many legal states of chess exists? "Legal" as in allowed by the rules and "state" as an unique configuration of the pieces. I'm not asking for the number of ...
0
votes
0answers
24 views

numerical solution for nash equillibrium

I have the following setup. $\pi_1=f_1(q,r)$ and $\pi_2=f_2(q,r)$ are the real valued payoff/profit functions of the two players. Player 1 gets to pick $q$ and player 2 gets to pick $r$. I also know ...
0
votes
0answers
45 views

Probabilities in this blackjack variation

Let's say I play blackjack (52 cards, figures count for 10, aces count for 1 or 11) and alone (no dealer). The cards I use for one particular game are always removed at the end of that game and won't ...
0
votes
0answers
93 views

“Composition” property in cooperative game theory?

I am trying to find a property which can help to analyse the composition of a cost/profit division and which allocation rules (e.g., Shapley value or nucleolus) would satisfy it. In short, the idea ...
6
votes
1answer
80 views

Tzaloa 2015 game problem (piles with $1,2,4 \dots 2^{19}$ coins each)

We have $20$ piles with $1,2,4,8\dots 2^{19}$ coins repectively and two players. In each turn a player must select five piles that have at least one coin and remove exactly one coin from each. Player ...