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

0
votes
2answers
652 views

Solving a 2*3 game with graphical method in game theory

Solve the following game. $$ \begin{pmatrix} 1 & 2& 3 \\ 4 & 2 & 1 \\ \end{pmatrix} $$ Since this is a $2\times3$ matrix I used the graphical method ...
1
vote
1answer
77 views

Finding values such that the game is strictly determinable

Please help me to solve these two problems. Q1)Find the range of values of p and q that will make the entry (2,2) a saddle point of the game. $$ \begin{pmatrix} &player B\\ ...
3
votes
2answers
146 views

Game involving tiling a 1 by n board with 1 x 2 tiles?

Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins. Which player ...
1
vote
2answers
56 views

extensive and strategic game

definitions of extensive and strategic (normal) games are very different. Here is the question, what would you call a game which is extensive but in each step strategic. For instance at each step ...
1
vote
0answers
45 views

Monte-Carlo tree search convergence proof

I have been doing some reading about Monte-Carlo tree search for games, recently. The Wikipedia article mentions that the algorithm converges to the minimax evaluation for finite zero-sum two-player ...
3
votes
0answers
184 views

Is there any hope to solve the game chess?

I heard about an estimate how many legal positions there are in a chess game. There are roughly ${10}^{40}$. Is it realistic that this amound of positions can be checked in the near future ? Or is ...
11
votes
2answers
283 views

Optimal Strategy for Bar Dice

This game is played in bars in Wisconsin, USA, but I'm sure variations are played many places around the world. The game has practical value, since once mathematicians figure out the best strategy, ...
1
vote
1answer
104 views

An unusual notation in game theory

As a game theorist, I have come across this notation previously but never found it disturbing. However, in the game theory book by Myerson, this notation is taken to its limits, and I think that it ...
6
votes
2answers
600 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
1answer
55 views

Prove that in an impartial Game, the P-Positions all have Sprague-Grundy Value =0

I'm looking at some work with Combinatorial Game Theory and I have currently got: (P-Position is previous player win, N-Position is next player win) Every Terminal Position is a P-Position, For ...
0
votes
1answer
29 views

Probability - choosing best strategy

Am I going about this problem the right way? In a certain game a participant is allowed three attempts to score a hit. In three attempts he must alternate which hand he uses: thus he has two ...
3
votes
1answer
227 views

Game Theory Voting

I am having some difficulty in solving the following problem. I was wondering whether someone would be kind enough to sketch a solution or even better to solve the whole game. Thanks Suppose that ...
1
vote
1answer
73 views

Interesting riddle game question?

I have a row of case values with a total of 100 difference cases. I play a game with someone else and I get to go first. Each player takes turns taking a case from either end of the row. All values ...
1
vote
2answers
85 views

Second-Price Sealed-Bid Auction

Consider 2 individuals who are interested in one indivisible object. Each player $i$ has a valuation $v_i > 0$ for the object. Assume $v_1 \geq v_2$. In this scenario, each player submits a bid ...
1
vote
0answers
127 views

Make the maximum sum in a interval.

Two players $A$ and $B$ are playing a game with array $A$ of $N$ elements in which each player chooses an array interval with maximum sum. The other simultaneously chooses another interval in the same ...
1
vote
1answer
133 views

K piles stone game

Their are k piles with total n stones in some order where each pile can have stones greater or equal to zero.Two player A and B plays a game in which player A cant see the configuration of piles but ...
1
vote
1answer
59 views

Finding social cost in game theory paper

From theorem 3 in http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf Let $w_1$,$w_2$ = 1. I have interpreted the above paper as saying that the social cost is the same thing as the expected cost ...
1
vote
1answer
41 views

Flipping the Grid

Suppose a grid of size N * M is having only 1 and 0. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Following steps can be called as a single move. Select two integers ...
2
votes
1answer
36 views

Categorization of PBE refinements into forward/backward looking?

I have recently come across the term forward / backward looking refinement of a Perfect Bayesian Equilibrium. I am, however, unsure about the meaning of this term, and unable to find any information ...
1
vote
0answers
131 views

Subgame Perfect Nash Equilibrium Problem

Suppose that there are two incumbent icecream vendors, but that there is a possibility of entry of a third vendor. Specifically, at any location on the beach a third vendor can, after observing the ...
3
votes
1answer
40 views

Centipede game of 2 students

PROBLEM We have two students who both begin with 1 point, their utility is equal to the number of points they have. Student $1$ has the first turn, he can decide to end the game and both students ...
0
votes
1answer
421 views

Ice cream vendor problem

PROBLEM This is a question considering game theory. Assume there is a beach with $n$ ice cream vendors on it who position themselves along the beach. For an arbitrary $n$, find a candidate Nash ...
2
votes
1answer
85 views

Coin game strategy [closed]

PROBLEM Suppose two players play a coin game. They both have a coin and can choose themselves what the probability is that they will play head $H$. So for player $i$, the chance he gets head is ...
3
votes
1answer
54 views

Static game question

GAME PROBLEM At a tv game show, two players are handed six cards each. Each of the six cards shows a number, and both players have the same cards. The six numbers are $0,0,3,0,15$. The game is as ...
5
votes
1answer
117 views

How to split the difference in game theory?

There are two parties in talks to settle a law suit. The expected value of going to court for the plaintiff is $\$3,155$ The expected value of going to court for the defendant is $-\$10,244$ The ...
2
votes
1answer
79 views

Finitely repeated games

Consider the following matrix game: \begin{matrix} & L &M&R \\ T&8,8 & 0,9 & 0,0 \\ C&9,0 & 0,0 & 3,1 \\ B&0,0 & 1,3 & 3,3 \end{matrix} For ...
0
votes
0answers
29 views

How do we calculate the revenues for VCG in the following Sponsored Search Auction problem?

There are 3 slots a,b and c with click-through rates of 10, 6 and 4 respectively. There are three advertisers x,y and z with the gain-per-click of each advertiser being 7,6 and 1 respectively. How do ...
1
vote
0answers
64 views

Proving lower bounds from algorithmic game theory paper (specifically, price of anarchy is lower bounded by 3/2 for $m$ links)

This question is similar to Understanding proofs from paper on Game Theory (Price of Anarchy) This question is about the same proof: proving the lower bound that the price of anarchy (sometimes ...
0
votes
1answer
218 views

Question related to the General equilibrium in exchange economies

I need some help in solving this question: Consider the following two-person, two-good economy. Persons $A$ and $B$ each consume two goods xylophones $(x)$ and yams $(y)$. Person $A$ enters the world ...
2
votes
1answer
92 views

Generalized Mechanism Design, Stanley Reiter diagram and Vickrey Auction

I am trying to learn this new topic, Mechanism Design and stumbled upon the "Stanley Reiter" diagram (see the top-right side on the page). I have also learned that the Second Price Sealed Bid ...
7
votes
1answer
143 views

Two people are looking for each other. Is it faster for both to actively search, or for one to search while the other stays still?

Choose among two actors randomly and place the chosen actor at the origin. Place the other actor in the unit circle uniformly at random. Both actors move at the same speed. Both actors are said to ...
1
vote
1answer
231 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? ...
2
votes
0answers
50 views

Optimally Efficient Tournament Strategies

Consider a fair symmetric game between two players that always results in exactly one of the players winning, i.e. there are no ties. When two players $P$ and $Q$ play each other, $P$ wins with a ...
1
vote
2answers
36 views

Calculate the Ranks of Candidates based on Votes and Total Candidates

What is the formula to calculate the rank of each candidate when I have the total candidates and votes secured by each? I've managed the percentage part, but calculating the rank has me stuck. Id be ...
2
votes
1answer
352 views

questions on information set definition

The definition of "information set" is An information set is a set of decision nodes, all belonging to the same player, over which that player cannot distinguish. ...
1
vote
2answers
138 views

Problem regarding filling squares inside a $n\times n$ grid.

Assuming a $n\times n$ square grid, what is the most number of squares that can be filled in such that there are no completed rows, columns, or diagonals? Is there a formula to calculate this? ...
1
vote
0answers
22 views

Game with no Right option is an integer

Lessons in Play, Chapter 5, number 15. Prove that if G either has no right options (Or no left options), then G is an integer.
0
votes
0answers
27 views

Hackenbush value Proof

Essentially there are two ways to assign values to a hackenbush game. If all edges in the string are Left's, the value is clearly an integer equal to the number of edges. Otherwise, Left's edges ...
0
votes
1answer
66 views

Optimal social cost = 1 … Game Theory paper

Say you have $n = m$ identical links, where each agent $i$ has a unit of traffic to push from source to sink, that is, $w_i = 1$. I've seen it stated, but not shown, that the optimal solution has ...
2
votes
2answers
8k 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 ...
1
vote
0answers
25 views

Playing Connect 6?

Say I'm playing Connect 6, a variation of Connect 4, and I get to go first. For a $n \times n$ board, which position should I place my chip on to maximize my odds of winning? Note than unlike Connect ...
0
votes
1answer
85 views

Partisan/Partial Game Theory

There are enough resources available on the internet regarding "impartial" game theory. But I cannot seem to find much information regarding "partial" game theory. Can someone name some such resources ...
2
votes
1answer
156 views

Placing K knights in an nxn board such that no two attack each other

This is a problem from spoj A and B are playing a very interesting variant of the ancient Indian game 'shatranj(also known as chess)' on a 'maidaan'(chessboard) n×n in size. They take turns ...
1
vote
0answers
37 views

Is there a textbook treatment of Ky Fan's minimax theorem and its generalizations?

Theorem 2 in Ky Fan(1952) is a powerful tool in zero-sum games, which states: Let $X$ be a compact Hausdorff space and $Y$ an arbitary set (not topologized). Let $f$ be a real-valued function on ...
0
votes
0answers
22 views

social optimum bounds … game theory

opt $\geq \frac{max_i w_i}{max_js_j}$ The social optimum is always bigger than or equal to the max weight/max speed. This is supposed to be easy to see, but I don't see it. Taken from around ...
12
votes
3answers
556 views

Formula for picking time closest to (but after) target

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win ($+1$), if not, you lose ...
2
votes
2answers
334 views

What is worth of a stalk in red-blue Hackenbush??

I was studying about Red-Blue hackenbush from this link http://www.link.cs.cmu.edu/15859-s11/notes/Hackenbush.pdf http://math.ucsd.edu/~wgarner/math168a/blueredhackenbush.htm this url shows a ...
2
votes
1answer
3k views

pure strategy vs mixed strategy

Apparently, I'm not understanding this simple concept. What are the differences between the two? Can a person have multiple pure strategies that change throughout the game?
1
vote
1answer
87 views

Understanding proofs from paper on Game Theory (Price of Anarchy)

I'm trying to distill the arguments in the paper "Worst-Case Equilibria" (http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf). But there are some things I do not understand and would appreciate ...
2
votes
1answer
140 views

Question on the equivalence of behaviour strategy and mixed strategy for a player with a single information set

Prove that if a player in an extensive-form game has only one information set, then his set of mixed strategies equals his set of behavior strategies. This is the exercise $6.4$ on page $246$ in ...