The study of competitive and non-competitive games, equilibrium concepts such as Nash equilibrium, and related subjects. Combinatorial games such as Nim are under (combinatorial-game-theory), and algorithmic aspects (e.g. auctions) are under (algorithmic-game-theory).

learn more… | top users | synonyms

1
vote
1answer
35 views

game theory question

For a non-cooperative bimatrix game the feasible set is $$\{(u,v)=(\mathbf{p}^TA \mathbf{q},\mathbf{p}^TB \mathbf{q}):p \in X^*, q \in Y^*\}$$ graph the non-cooperative feasible set for the Battle ...
2
votes
1answer
60 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
1
vote
2answers
26 views

Game Theory: Can someone explain the notation used in the definition of “best response”

I am reading a paper which states that that the best response correspondence of a player is mapping: $B_i(s_{-i}): S_{-i} \Rightarrow S_i$ such that $B_i(s_{-i}) \in arg\ max_{s_i \in S_i} ...
4
votes
1answer
749 views

The Notion Of Degenerate Two Player Game

I try to get the intuitive understanding of the notion "degenerate two player game". Definition. A two-player game is called non degenerate if no mixed strategy of support size $k$ has more than $k$ ...
0
votes
0answers
23 views

Support lemma - Game theory

Let α be $a$ mixed strategy profile, $a_i ∈ supp(\alpha _i), a_i \notin B_i(\alpha _{−i}), a_i' ∈ B_i(\alpha _{−i})$ and $a_i'$ defined by $\alpha_i'(a_i)=0$, $\alpha_i'(a_i')=\alpha _i ...
2
votes
1answer
38 views

Is my answer correct? (Devious auction game)

(Taken from here) The question was A man is auctioning a real $20\$$ bill. There are a vast number of bidders. A person may make as many bids as he wants. The starting bid is $5\$$. No $2$ ...
1
vote
1answer
402 views

Reduce the payoff matrix using (weakly) dominated strategies

Below is the payoff matrix of a game. Use the principle of elimination of (weakly) dominated strategies to simplify the payoff matrix. What is the optimal solution of the game for the row player? ...
1
vote
1answer
23 views

Nash equlibrium game theory

Given the following game: Find nash equilibrium (NE) Find subgame perfect nash equilibrium. Main problem i have is with converting this to normal form of the game (because this is i think ...
0
votes
0answers
17 views

A min-max problem and convex optimization problem.

Let $x^*$ a solution of the convex programming problem $$ \begin{array}{rl} \max & f_0(x)&\\ \mbox{s.t.} & g(x)\leq 0 \end{array} $$ where $f_0:\mathbb{R}^n\to \mathbb{R}$ and the ...
-1
votes
1answer
35 views

Mixed strategy nash equilbrium

In a mixed strategy Nash equilibrium it is always the case that: a) for each player, each pure strategy that is played with negative probability yields the same expected payoff as the equilibrium ...
7
votes
0answers
52 views

Diagonal-free Sudoku grid

I have a Sudoku grid with the property that diagonally adjacent elements are distinct (it is also a torus under the same property). The grid offers new and exciting logical possibilites. My question ...
0
votes
0answers
12 views

How to calculate effect of different variables/parameters on a quantity?

I am developing a game for iOS. In the game I have around eight different parameters that directly affect the score of the player. We can say that these eight variables decide the difficulty of the ...
-2
votes
1answer
26 views

(Won/loss, game) Does anyone know how to do the question below? [closed]

Can anyone please explain me how to answer this question, using a table? Consider the following two person game: A natural number n represents the position in the game. When it in a players ...
0
votes
0answers
7 views

Prove that a directed tree does not have a path from a descendant to its parent

Prove: Let T = (V, E) be a directed tree. If v is a vertex of V and u is a descendant of v, then there is no path from u to v. My idea is that if u is a descendant of v, then there exist a path from ...
2
votes
1answer
58 views

Price of anarchy for selfish routing games with polynomial latency functions

I have a question regarding selfish routing games. For the case where we have affine latency functions I was able to calculate a worst case price of anarchy (PoA) of $4/3$. However, now assume $L_d$ ...
1
vote
1answer
42 views

What is the name of this kind of games?

In game theory, suppose we have a set of players $\mathcal{N}=\{1, 2, \ldots, n\}$, a set of actions $\mathcal{A}_i$ of player $i\in\mathcal{N}$, and a payoff function $u_i$ of player ...
1
vote
0answers
63 views

The best strategy to increase StackExchange Reputation [closed]

I do not have a lot of background in game theory, but I am curious how would one formally pose the title problem and mathematically describe possible strategies. Are the problems of this type best ...
8
votes
3answers
3k views

Deal or No Deal: Monty Hall?

This question was inspired by another question posted today: Monty Hall Problem Extended. So I thought that the comments an answers brought up a great point about increasing the doors to 100 or ...
1
vote
2answers
336 views

Dominant Strategy in Table Games

I have some basic background in game theory, but still there are exist simple questions that I cannot answer for sure. Whether Tic-Tac-Toe game has a dominant strategy? May be only one of the ...
0
votes
1answer
43 views

binomial distributions and their transforming (6.37-6.39)

I'm lost and frustrated. I don't know how the author (Karl Sigmund; The Calculus of Selfishness) transforms 6.37 in the book pages imaged below: $$ P_y = \sigma w^{N-1} + ...
2
votes
1answer
42 views

Subgame perfect Nash equilibrium & perfect Bayesian Nash equilibrium - Game theory

For a week or so I have been struggling with the topics around the concept of subgame perfect Nash equilibrium (SPNE) and the perfect Bayesian Nash equilibrium (BNE). Namely: Is it possible to apply ...
0
votes
1answer
39 views

Game with matches. Very interesting mathematical problem.

Suppose you have a set of matches. You arrange them in 9 rows such that the first row has one match the second two matches the third three and so on until the ninth row which has nine matches. There ...
5
votes
3answers
21k views

How to compute ALL Nash equilibria in an example of a 3x3 matrix

I am trying to understand how to compute all Nash equilibria in a 2 player game, but I fail when there are more than 2 possible options to play. Could somebody explain to me how to calculate a matrix ...
0
votes
1answer
508 views

Game Theory. Repeated Games. Strategy set.

I'm reading the book "Strategic games" by Krzysztof R. Apt. I have a question about the strategies in Prisoner Dilemma repeated game. On page 63 there is expression: "In the first round each player ...
2
votes
1answer
58 views

move a cuboid from start to destination

Consider the field with infinitely many boxes, "S" means start, "D" destination, and I already found a way to move a $1\times 2\times 4$-cuboid (as you can see on the right at this picture) from the ...
0
votes
1answer
50 views

Game theory question- no idea how to proceed

A monopolist sells two products, X and Y . There are three consumers with asymmetric preferences. Each consumer buys either one unit of a product or does not buy the product at all. The per-unit ...
0
votes
1answer
70 views

Gambling to pay off debt?

Someone told me something interesting today. They said they were going to take their bonus check from work, to the casino because they have "better odds" of paying off more debt then if they would ...
0
votes
0answers
20 views

A minimum settlement for a bargaining problem

Question: Alpha and Beta are 2 companies. Now Alpha thinks that Beta has violated Alpha's trademark. Beta denies that. Now, Alpha is threatening to go to the court and claim 5,000,000 EUR from Beta ...
0
votes
1answer
38 views

Game theory question- boxes

There are two players 1 and 2, and the game begins with player 1 selecting one of the boxes marked 1 to 16. Following such a selection, the selected box, as well as all boxes in the square of which ...
1
vote
1answer
66 views

Brouwer's fixed point continuous function

Can anyone point me out the continuous functions without brouwer fixed point's for the following sets $$A = \{x \in \mathbb{R}^2 | x_1,x_2 \geq 0 \text{ and }x_1^2+x_2^2 = 1 \}$$ $$B = \{x \in ...
0
votes
0answers
19 views

Mixed Strategy Nash Equilibrium in this game?

L (q) R (1-q) l (p) [(2, 1), (0, 1)] r (1-p) [(-1, 0), (1,7)] I'm having a lot of trouble understanding what the mixed strategy nash equilibrium is ...
1
vote
1answer
14 views

Algorithms for computing Nash equilibria

Excuse me, since I am modeling a situation into a nonzero-sum n-player non-cooperative game. I wonder if there is any algorithm for computing its Nash equilibria?
0
votes
1answer
34 views

What is a two person constant sum game?

I read that a two-person constant-sum game is a two-player game in which, for any choice of both players strategies, the row player's reward and the column player's reward add up to a constant value ...
1
vote
1answer
28 views

How much is it worth to participate in a second price auction?

You have a valuation for an object (say $v_a$), which you don't know yet but you know is distributed U[0,1]. You will be competing in a second price auction against a completely identical guy as you, ...
1
vote
3answers
37 views

Looking for the function of x for a line that approaches, but never reaches 100

I'm looking for the function of x for a line that intersects at (0,0) and (100,80), and as x goes off into infinity, the line approaches, but never touches 100. See image attached. I am writing a ...
0
votes
1answer
29 views

Mixed strategy Nash Equilibrium

How do I solve this problem by using mixed strategy Nash equilibrium? \begin{pmatrix} (2,0)& (1,1)&(4,2)\\ (3,4)&(1,2)&(2,3)\\ (1,3)&(0,2)&(3,0) \end{pmatrix} I tried to ...
2
votes
2answers
117 views

Splitting the dollar Nash equilibrium

I'm working on a game theory problem I can't seem to figure out. Players 1 and 2 are bargaining over how to split $\$10$. Each player names an amount $s_i$, between 0 and 10 for herself. These ...
1
vote
1answer
21 views

A proof related to diameter of a simplex S

Question: Prove that the diameter $\mathcal p(S)$ of a simplex $\mathcal S$ equals the greatest Eucledian distance between two vectors in the simplex. My opinion: We all know what every vector in the ...
1
vote
0answers
21 views

Has two player five-card draw poker been solved?

I know that some other types of Poker have recently been solved with computers but has five-card draw poker been solved and if so, is there any place for mathematical analysses in the game? I need to ...
2
votes
0answers
50 views

Cournot competition: profit maximizer vs. market share maximizer

Today during an informal conversation with an established business researcher, I learned such a fact: In the classical Cournot competition model, if one player is a profit-maximizer, the other ...
4
votes
1answer
82 views

Do you need true randomness to beat the two-envelope game?

A well-known (non-)paradox in probability involves a two-envelope game played between two players, $A$ and $B$: $A$ selects two distinct (real) numbers, $x$ and $y$, writing each one down on a card ...
1
vote
1answer
25 views

Probability of number of drawing cards in a scenario being equal to that in another scenario

I came across the following question in a book:- $Q.$ Cards are drawn one by one at random from a well shuffled pack of $52$ cards. $(a)$Find the probability that exactly $n$ cards are drawn before ...
5
votes
2answers
383 views

Bounded sequence with divergent Cesaro means

Is there a bounded real-valued sequence with divergent Cesaro means (i.e. not Cesaro summable)? More specifically, is there a bounded sequence $\{w_k\}\in l^\infty$ such that ...
2
votes
0answers
29 views

Minimum number of steps to guess an item in a database given a liar

Let's say I have a database of $N\times N$ size ($N$ rows and $N$ columns). My friend wants me to guess the location of an item. We start by binary guess, meaning I ask him if it is in upper half and ...
1
vote
0answers
214 views

Proof that $12$ in a row tic-tac-toe is a tie game?

How can be it proved that tic-tac-toe on an infinite grid (winning with $12$ in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)? There is a hint: to ...
2
votes
0answers
24 views

Finding the core of a coalition game

I need to find the core of a 3-player coalition game graphically, given that $v(\phi)=0$, $v(1) = 9, v(2)=8, v(3) = 9, v({1,2}) = 14, v({1,3})=15, v({2,3}) = 13, v({1,2,3}) = 21$ So I'm following the ...
436
votes
25answers
54k views

Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an ...
3
votes
1answer
1k views

Mixed Strategy Nash Equilibrium of Rock Paper Scissors with 3 players?

It seems like most game theory tutorials focus on 2-player games and often algorithms for finding Nash equilibria break down with 3+ players. So here is a simple question: Is ...
4
votes
0answers
61 views

Wizard against two dwarfs: guess the whole function

An evil wizard plays the following game with two dwarfs $A$ and $B$: he thinks of a function $f:\mathbb{R}\to\mathbb{R}$ (which is not required to have any regularity properties, such as ...
0
votes
0answers
20 views

Unfair coin tossing game,target,optimal fixed investment,

Suppose the player has capital 1\$. He chooses a number $f\in[0,1]$.He tosses an unfair coin repeatedly, which wins for him, with probability $p$, a gain $q\times f \times$ current capital \$,where ...