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

3
votes
0answers
75 views

Should I maximize points in the beginning of a long match?

I have a question that may really be about mathematical modelling as much as math itself, but I will try to give it a formulation suited for this site. Suppose that I am going to play some game, ...
1
vote
0answers
36 views

Finding an interval of solutions from a Game Theory problem

So I have this problem from Game Theory and I have most of the solution, but at the end it involves an algebraic inequality that seems un-solvable or at least not solvable within reason. So the ...
1
vote
1answer
55 views

Mixed strategy Nash equlibria (defending territory)

Hi I am trying to figure out the MSNE of this game. I am confused wether there are 2 MSNE or 3. Player 2 would put (1/2) on xx and yy and then player 1 would either put (1/4)on all or (1/2) on xxx ...
2
votes
0answers
80 views

How to find optimal strategies for infinite betting games?

Suppose we have a game structure of the following form: Game: You have an $n-$sided die. At any point in the game, there is a "value" associated to the rolls that have already occurred. You can ...
1
vote
1answer
70 views

Best response dynamics in Bertrand duopoly game

Question: Consider Bertrand's duopoly game in which the set of possible prices is discrete. Does the sequences of prices under best response dynamics converge to a Nash equilibrium when both prices ...
-2
votes
1answer
79 views

Puzzle: Players A,B,C,D are in a line

Players A,B,C,D stands in a line. Players A, D do not move. round 1: player B moves one distance closer to the midpoint of A,C round 2: player c moves one distance closer to the midpoint of B,D ...
1
vote
0answers
44 views

The value of a stochastic game

I understand why a stochastic game with discounted payoff has a value $v$ and optimal strategies over the set of stationary strategies. But why is $v$ also the game's value over the set of behavioral ...
1
vote
1answer
65 views

Are there any limit to the total amount of moves in chess? [closed]

Are there any limit to the total amount of possible moves before stalemate or checkmate in chess? If so, what is it and how do one prove that? EDIT: As I wrote in a comment below, stalemate is ...
3
votes
1answer
78 views

Why can a Nim sum be written as powers of 2?

I have this confusion. Why do we express a nim sum as powers of 2 and why do nim sums cancel in pairs of 2 only? For instance, let's take the nim game(6,10,15) Now clearly *6 = * $2^2$ + * $2^1$ *10 ...
1
vote
1answer
45 views

Can the price of anarchy be infinite?

It seems that the price of anarchy for a normal-form game can be infinite, or undefined, when the social welfare of the "worst" equilibrium is 0. For example, consider this game: \begin{matrix} ...
1
vote
1answer
40 views

Transience in a simple Markov chain

Consider the following simple game from a textbook called "Competitive Markov Processes" by Filar & Vrieze (Springer 1996). This is a two player game with two states. In the first state (the ...
0
votes
0answers
22 views

Not every correlated equilibrium is equivalent to a Nash equilibrium?

This is a statement made under Theorem 3.4.13 on page 84 in the book by Yoav Shoham and Kevin Leyton-Brown, Multiagent Systems. Could someone explain this to a lay-man and also elaborate on why they ...
0
votes
1answer
123 views

Nash equilibrium in first price auction

I'm trying to understand Exercise 18.2 from Martin J. Osborne and Ariel Rubinstein A Course in Game Theory about finding pure Nash equilibria in a first-price auction. There are n players, named ...
0
votes
1answer
50 views

Variant of The Price Is Right

Let there be four contestants in a game similar to "The Price Is Right". They simultaneously write down bids for an object they don't know, the bids can range from 1 to 1000 USD. The object's value ...
1
vote
2answers
56 views

Shapely's “Stochastic Games”: An upper bound on each player's gain

In a stochastic game the play proceeds by steps from position to position, according to transition probabilities controlled jointly by the two players. We shall assume a finite number, $N$, of ...
2
votes
3answers
183 views

Do you need to know how to play games to study game theory?

I was never good at card games, mainly because I never played them (rough childhood, another time another place). So you can imagine the fun time I spent in probability counting the likelihood in ...
1
vote
1answer
68 views

How to make sure Player 2 always wins in 23 NIM game?

Game begins with a pile of 23 toothpicks. Players take turns, withdrawing either 1, 2, 3 toothpicks at a time. The player to withdraw the last toothpick loses the game. We need to make player 2 to ...
3
votes
1answer
125 views

Donald Knuth's Nontransitive Bingo Cards

In Time Travel and Other Mathematical Bewilderments, Martin Gardner presents a set of four nontransitive bingo cards designed by Donald Knuth (pp. 61). The rules are that the first player to complete ...
0
votes
1answer
81 views

Finding sub-game perfect Nash equilibrium

So, for each $q\in\left[0,1\right]$, I would like to find all the sub-game perfect Nash equilibrium of this game. The game tree is as follows: Next, I split the problem into $4$ cases, ...
0
votes
0answers
32 views

Submodular function of 2 variables with specific properites

For an application in economics, I am looking for an example function with the following properties: Function of 2 variables on the unit interval, i.e., $f : [0,1]\times[0,1] \rightarrow ...
0
votes
0answers
43 views

Minimum coins to remove to ensure win

In nim game there are $N$ piles of coins, both players will take turns and pick at least one coin from one particular pile only, Alice starts the game first. A player loses when he/she cannot ...
2
votes
0answers
102 views

Is it possible to calculate the balanced cost of parameters' increase in card game? How?

I wonder if it's possible to calculate the balanced cost of parameters' increase for the card game. Game rules: Each player draw 7 cards at the beginning of the game and then one card each turn ...
1
vote
1answer
64 views

What kind of mathematics is required by game theory?

I want to learn about game theory, but I do not know if I have the necessary background to do so. What kind of mathematics does game theory involve the most? What are some of the things that an ...
0
votes
1answer
79 views

Odds of winning a two part drawing

There is a local drawing that involves being selected out of an estimated 6000 entries, and then correctly selecting 1 of 3 numbers in order to win. The numbers have are actually cards in a deck that ...
0
votes
2answers
38 views

Characterization of pre-orders

Let $X$ be an arbitrary set, and $\leq$ be a pre-order on $X$. Does there always exist $u:X\to \Bbb R$ such that $x'\leq x''$ iff $u(x') \leq u(x'')$? If this is not true in general, is that true ...
0
votes
1answer
42 views

Clarification of Game Theory Exercise

Look at the second exercise here: (open yale course on game theory) http://oyc.yale.edu/sites/default/files/problemset1_1.pdf Does anyone understand the meaning of this from question a) "What ...
1
vote
1answer
77 views

What is the total number of possible chess moves at White's second turn?

At White's first turn there are $20$ possible moves: each pawn can move forward one or two spaces, or a knight can jump over the pawns to one of two positions each. Some moves are of course likelier ...
2
votes
1answer
265 views

Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
0
votes
1answer
32 views

Coalition games

Let us define $\gamma([n],v)$ and $(\gamma'([n],v')$ as the two cooperative games in coalition form. Both games have the same set of players. Let this hold for every non-empty coalition $S$: $v(S) ...
3
votes
1answer
54 views

Can one player win more games while scoring fewer points over multiple trials a simple probabilistic game?

The Game Two players $P_{1}$ and $P_{2}$ will play the following game: Three non-negative numbers $a$, $b$, and $c$ will be selected at random from a distribution unknown to either player. The ...
2
votes
1answer
44 views

Expected revenue in first-price auction with budget constraint drawn uniformly between [0,1]

I am trying to understand an example from the article "Standard Auctions with Financially Constrained Bidders" Che & Gale (1998) - Review of Economic Studies. Two buyers each value an object at ...
0
votes
0answers
9 views

Where can i find good tutorials of the simplex algorithm,hungarian algorithm and lagrange optimization?

Where can i find good tutorials of the simplex algorithm,hungarian algorithm and lagrange optimization? My textbook is kind of vague and i would love to learn these fascinating algorithms as good as ...
2
votes
1answer
61 views

How do I show that this game played on a Markov chain has a unique Nash equilibrium?

There are $k$ stages in this game, and each stage is worth one unit of utility to a player (of which there are $n$). Each player $i$ finishes stages at a rate $\lambda_i$ (in a continuous time Markov ...
0
votes
1answer
75 views

Topology and Differential Games

I'm a engineer who is making research on differential games in multiagent control. I was reading a tutorial on differential games and the author advised to get the required math background from the ...
2
votes
2answers
200 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 ...
0
votes
1answer
25 views

Sub-game perfection when an agent is indifferent

If looking at one of the sub-games the player is indifferent between two actions. How does the backward induction work to recognize sub-game perfection? I.e., suppose player 3 has two action $A_3 = ...
1
vote
1answer
72 views

Winning or losing in chess - a question of combinatorics?

I have observed that every chess game can be assumed as a sequence of moves that lead either to win or to lose (in a few cases to a drawn game). It is very interesting to Count all the moves that are ...
2
votes
0answers
200 views

stable marriage algorithm problem

Better of the two Suppose that in the stable marriage problem with $n$ men and $n$ women, we have found two (possibly different) stable matchings $S$ and $T$. We will show how to combine $S$ and $T$ ...
0
votes
0answers
61 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
1
vote
1answer
39 views

Mixed Nash equilibrium in two players game three stategies

I have this problem about finding the mixed Nash equilibrium. The payoff matrix is the following A(p) B(q) C(1-p-q) A 4 0 0 B 0 4 0 C ...
0
votes
0answers
33 views

Does this payoff matrix correlate to the problem statement for the game?

The problem statement: Consider a two agent game in which the possible action for agents are C and D. The utilities and therefore preferences for agent $i$ among strategy choices are: $$ ...
0
votes
1answer
59 views

Game Theory - Contributing to a public good

I have attempted to answer the question but I think I am trying to answer it in a very difficult way as the algebra gets messy and confusing. If anyone could help me out it would be greatly ...
1
vote
1answer
75 views

Game Theory - n-player friends/enemies game

"Consider the following game with n players $\{1, . . . , n\}$. Each player is invited to two parties. All players like to party, but the parties are on the same day, so each player has to decide ...
2
votes
0answers
52 views

Showing $\frac{1+c}{a+b}\leq \varphi$, when $\frac{1}{1+b}\leq a\leq 1$, $\frac{c^2}{a+c}\leq b\leq 1$ and $0\leq c\leq 1$

The title pretty much says it all. Let $\varphi\triangleq\frac{1+\sqrt 5}{2}$ be the golden ratio. Let $a,b,c$ be some non-negative numbers such that: $\frac{1}{1+b}\leq a\leq 1$ ...
1
vote
1answer
53 views

Weakly acyclic games in game theory

I read that weakly acyclic games are more general than potential games. Potential games are said to have a finite improvement property where each player's payoff function is aligned with a potential ...
0
votes
1answer
371 views

Dominant-Strategy Equilibrium vs Nash Equilibrium

What's the difference between dominant-strategy solution and Nash Equilibrium? I could not tell the difference judging from the definitions. It would be appreciated if these concepts can be ...
0
votes
1answer
61 views

Who's winning this coin drawing game?

There are 2 piles of coins, each containing 2010 pieces. Two players A and B play a game taking turns (A plays first). In each turn the player on play has to take 1 or more coins from 1 pile or ...
1
vote
1answer
92 views

Pareto optimality - Game theory

Good morning, I have this game theory problem. Let's consider 5 farmers, each of them has 2 cows to put into the field. So every farmers can put 0,1 or 2 cows. I denote the three stategies by ...
1
vote
2answers
85 views

Single bid auction: calculating bid as function of winning probability

I'm simulating a auction game with sealed single bid, where each of the $n$ players has winning probability $p_i,i=1,...,n$, and their bids $b_i$ have to be calculated to meet the $p_i$. Supposing ...
0
votes
1answer
40 views

Reducing an I-optimal problem to a Pareto-optimal problem

Given a set $\textbf y\subset\mathbb R^2$, let $y = (y_1,y_2), y'=(y'_1,y'_2)\in\textbf y$ be elements of that set, let $\alpha_{min}\in\mathbb R$, $\alpha_{min}<1$, $\alpha_{max}\in\mathbb R$, ...