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

1
vote
0answers
49 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 ...
12
votes
3answers
589 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
498 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 ...
3
votes
1answer
11k 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
103 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
215 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
54 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
545 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
931 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
69 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
772 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
357 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
68 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
276 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
94 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 ...
2
votes
2answers
97 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
66 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
366 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
44 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
180 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
66 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$$ ...
1
vote
3answers
133 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 ...
4
votes
1answer
154 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
84 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
89 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
1answer
121 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
436 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
87 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 ...
3
votes
2answers
132 views

Simple game-theoretical problem

I have a confusion regarding the following problem: Suppose there are three players, and each of them has to pick a number out of $1,2$ or $3$. If there is a player who picked a unique number ...
2
votes
1answer
946 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
0
votes
1answer
44 views

How does prior round knowledge affect 2-round voting?

Consider a simple 2-round voting scheme where the 1st round is a decision between two choices $A$ and $B$, and the second round is a decision between the winner of the 1st round and an existing choice ...
1
vote
1answer
108 views

A game theory question about tiles, part 2

A recent question asked about the following game: There are six tiles, face down. Three are type A and three are type B. Each player turns over three tiles, and wins if they match. Otherwise, they ...
0
votes
1answer
86 views

A game theory question about tiles

So if there are two players playing a tile game where there are two sets of matching tiles $a_1, a_2, a_3$ and $b_1, b_2, b_3$, what would the optimal strategy be to maximize winning probability? Go ...
3
votes
1answer
566 views

About game theory for high school students

I am a mathematician with a background in analysis who is teaching at a local high school in his spare time. There is some room for extra curricular math subjects and I want to use it for game ...
1
vote
2answers
66 views

Game with two players and 120 points in total

Assume the following game: The game has two players $P_{1}$ and $P_{2}$ and 15 rounds in which they play against each other. Each round gives an amount of points equal to its number, i.e. the ...
1
vote
1answer
137 views

How to calculate a Nash equilibrium strategy for toy games quickly?

Given the game of Kuhn poker or Rock-Paper-Scissors, why is it hard to calculate the solution to it? From my very limited understanding, it seems that to solve it you need to employ the counterfactual ...
1
vote
1answer
131 views

Two traders don't trust each other; what transactional equation optimises reward and minimises risk?

Years ago while on a Wikipedia browsing binge, I read a maths article about how two (or more) mistrusting parties can reach an transactional equilibrium, but I've wracked my brain and I can't remember ...
1
vote
1answer
65 views

Games with known outcome but unknown strategy

Is there any two-player game for which it is known that a particular player (not just one of the two players) has a winning strategy but no such strategy is known explicitly? I see that it ...
3
votes
1answer
103 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
0
votes
1answer
243 views

Solving a linear programming problem: Are my formulations correct?

QUESTION J (PTY) LTD is a fertilizer manufacturing enterprise that produces two types of fertilizers, namely white and gray. The white fertilizer is for crops like maize, sorghum, etc while the gray ...
2
votes
2answers
87 views

A Recurrence Equation From a Game

$a_n=a_{n-1}(a_{n}-a_{n-2}+1)$ The above equation is defined in $[0,m]$ st. $a_{0}=0$ and $a_m=1$. It turned up as I was trying to analyze a simple richman game. I have managed to solve the equation ...
0
votes
4answers
272 views

Recommended math background for game theory

I recently got interested in some game theory applications to poker. I want to try some of them out programmatically, but a lot of the math is a bit confusing. I learn math on my own fairly quick and ...
2
votes
1answer
85 views

Game Probability Problem

Consider a game played by two people $X_1$ and $X_2$. Against the general population, $X_1$ wins with probability $0.51$ and $X_2$ wins with probability $0.49$. We have no knowledge of the ...
0
votes
3answers
112 views

solutions poker texas hold'em

Is there any equation that characterizes the poker game in terms of variables such as the strength of the hand, the amount of betting money in the pot, etc? Is there any solution that says what the ...
0
votes
1answer
78 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
109
votes
1answer
4k views

Identification of a curious function

During computation of some Shapley values (details below), I encountered the following function: $$ f\left(\sum_{k \geq 0} 2^{-p_k}\right) = \sum_{k \geq 0} \frac{1}{(p_k+1)\binom{p_k}{k}}, $$ where ...
12
votes
2answers
749 views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
1
vote
1answer
80 views

What is the relative strength of each of the players in this game?

This is a real life problem. A group of people meet once a week to play a game between two teams. Each round 2 people are randomly appointed captains. Each captain takes turns picking people to be on ...
9
votes
2answers
1k views

Determine the winner of a tic tac toe board with a single matrix expression?

Assume a tic-tac-toe board's state is stored in a matrix. $$ S=\begin{bmatrix} -1 & 0 & 1 \\ 1 & -1 & 0 \\ 1 & 0 & -1 \\ \end{bmatrix} $$ Here, $X$ is mapped to $1$, $O$ is ...
0
votes
1answer
84 views

What is a sample space supposed to be?

In this paper, Robert Aumann claim that(page 508): But as shown at the bottom of page 520, all these sample spaces don't admit uncountable independent random variables. What's the implication of ...