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

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
63 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
209 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
89 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
141 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
217 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
34 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
299 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
129 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
22 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 ...
1
vote
2answers
7k 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
24 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
84 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
148 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
331 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
85 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
137 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 ...
1
vote
1answer
49 views

Number of rounds to find out the winner in nondeterministic game

Imagine, I'm organizing competition for AI Yahtzee players (or some other game, poker, backgammon etc.). I want to find out who plays better: player A or player B. If they play just one game, winner ...
5
votes
1answer
449 views

Hackenbush game strategy for stalk

There are some piles of numbers. Numbers are divided in 2 groups, A and B. Player x plays with group A and player y plays with group B. x makes the move first. On each step a player chooses a pile and ...
0
votes
1answer
323 views

Game theory : A and B are playing divide the dollar

A and B are playing divide the dollar. Denote A’s strategy by a (the amount he claims) and B’s strategy by b. If they can agree on a division of the dollar (a + b ≤ 1) they walk away with the share ...
0
votes
1answer
48 views

In the game shown below what strategies can player 2 adopt in a subgame-perfect equilibrium?

What difference would it make to possible predictions of how rational states play this game if player 2 does not know player 1’s move when it chooses (i.e. node2 and node3 belong to the same ...
4
votes
2answers
470 views

3x3 Nash Equilibrium?

I'm trying to figure out a Nash Equilibrium for a 3x3 zero-sum game, and it's not following normal patterns (or I'm making a huge oversight, in which case I'll feel stupid!). Can anyone help me? The ...
0
votes
1answer
234 views

Prove the dominant strategy of Game Theory

A row $r$ of the payoff matrix is said to dominate a row $s$ if $a_{rj}\geq a_{sj}$ for all $j$ = 1,2,......,$n$. Similarly, a column $r$ of the payoff matrix is said to dominate a column $s$ if ...
1
vote
1answer
65 views

simultaneous probability elicitation from multiple agents without an exogenous banker

A proper scoring rule is a function $f:[0,1]\times\{0,1\}\to \Bbb R$ such that, if a subject will receive a reward of $f(x,0)$ for reporting his estimate of the likelihood of an event as $x$ if the ...
2
votes
2answers
133 views

Game Theory Problem with Dice

I need solution to this game theory problem. It seems impossible to me. Two players (1 and 2) play the following game. Player 1 must write the numbers from 1 to 18 on the sides of 3 dice without ...
2
votes
1answer
63 views

Is this a novel game theory measurement?

A measurement of skill versus chance in games. Overview I present here what I believe to be a novel approach to measuring the amount of skill versus luck in various types of games. The method gives ...
0
votes
0answers
30 views

Game in a joint-stock company

I would like to compare myself with you on work experience that I'm living these days: In a joint-stock company there are three teams of managers who manage all offices, each team has five directors, ...
2
votes
2answers
79 views

In the next matrix, why is (55,0) not a Nash Equilibrium?

My book says that the next matrix has no Nash Equilibriums. Still, Im a little confused about row 3, column 2. Reasoning from player 2's perspectivo, he could say "if player 1 chooses row 3, I Will ...
1
vote
1answer
50 views

Choosing strategies to maximize ones payoff and minimize others payoff

In game theory, the aim of every player is to pick strategies that maximizes their payoff. This is done irrespective of the payoff of others. But in real life competitions, there arises a secondary ...
7
votes
1answer
227 views

Man, Woman, Dog, seeking stable relationship.

There is a classic problem in combinatorics dealing with a stable pairing between a set of men and a set of women as spouses. (Gale-Shapely algorithm) ...
0
votes
1answer
42 views

probabilistic behaviour

I am trying to understand what 'probabilistic behaviour' in a 'deterministic model' means. I am reading this paper http://www.ulb.ac.be/sciences/use/publications/JLD/16.pdf but i find myself unable ...
0
votes
1answer
74 views

Proximal functions

I am a little bit new to proximal functions and I am currently stuck with the following problems How would I derive the prox function for the regularizer (h(x) function) : $\alpha\sum_{k+} $ and for ...
1
vote
2answers
57 views

Duals of Linear Programs

We are trying to find the dual of the following linear program. $$ \max_x \ ax_1 \ + x_2 $$ such that: $$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$ ...
0
votes
3answers
116 views

How to discourage contestants from entering a lottery twice?

Suppose you have a lottery. And you want to prevent participants from buying multiple tickets. What would be the best way to discourage this? For example, increasing the win-chance for all previously ...
0
votes
0answers
56 views

Teach Shubik Dollar Auction to 13 years olds

I am a former math student who got into teaching. I love game theory and since I have some spare time, I would like to play Shubik's Dollar Auction with my class of 13 year old children. For those of ...
4
votes
1answer
91 views

Nash Equilibrium of cheating a test($N$-player game)

Consider a classroom with $N$ students. All the students are taking a test. Each student has 2 strategies. They can either "cheat" or be "honest"(meaning they don't cheat). The payoffs are as follows ...
1
vote
2answers
74 views

Where's the Nash Equilibrium here? $ \begin{pmatrix} (2,-2) & (2,-2)\\ (1,-1) & (3, -3) \\ \end{pmatrix} $

I just opened a book on Game Theory, so I'm totally new to this. My book says that the only Nash Equilibrium in the example below is (2, -2) -first row, first column-, and I really don't see why... ...
0
votes
1answer
65 views

Finding Mixed Strategy Nash Equilibria

Okay, so I was working through this problem: Now, I understand the computations. What I don't understand is why the solution says that each player will play H with probability p=2/3. I would have ...
0
votes
0answers
43 views

Reference to mean field game theory

Can someone suggest a good reference to introductory mean field game theory? It would be good if it explains with examples. Thank you.
0
votes
1answer
92 views

Consider a game in which two players take turns removing any positive number of pebbles they want from one of two piles of pebbles.

Consider a game in which two players take turns removing any positive number of pebbles they want from one of two piles of pebbles. The player who removes the last pebble wins the game. Show that if ...
1
vote
1answer
210 views

Expected payment in second price seal-bid auction

Environment Suppose $n$ bidders participate in a second price sealed-bid auction, in which one object is being sold. Each bidder $i$ values the object at $v_i$, and each $v_i$ is independently and ...
1
vote
1answer
80 views

Game of Stones - Count the ways

We are given a number of piles of stones. and we can remove two stones , where both stones come from different piles. We do this until all the piles are finished or only one pile is left as we cannot ...