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
1answer
25 views

Do all equilibria in 2 player zero sum games have the same distribution over outcomes

I know that in a 2 player zero sum game all equilibria give each player the same expected value, but is it the case that they also induce the exact same distribution over payoffs? Or might there be ...
0
votes
0answers
10 views

How to Find Symmetric Equilibrium Bidding Strategy in Mixed Auction?

N-bidders take part in a mixed auction (mix of first- and second-price auctions). The highest bidder (bidder 'i') wins and pays a*b_i + (1-a)*(max b_j) ('i' is not equal to 'j'), where 'a' is fixed ...
2
votes
3answers
103 views

Chess and mathematics

I have to choose a research-like project to follow the next year. Because I'm a chess enthusiast, I was thinking of trying to tackle an (open) problem related to chess, and relevant to mathematics. ...
1
vote
0answers
41 views

Uniqueness of solution for a system of differential equations

A friend of mine working on Auction Theory needs to establish uniqueness of solution (up to initial and boundary conditions) of a system of differential equations of the form $$ ...
7
votes
1answer
120 views

All games determined + ZF inconsistent

Let $A$ be a nonempty set, $T\subset A^\mathbb{N}$ a nonempty pruned tree and $X\subset [T]$. The game $G_{A}(T,X)$ is played as follows: Player I and Player II take turns playing $a_{0},a_{1},\dots$ ...
2
votes
0answers
30 views

Who has a winning strategy in “knight” and why?

Perhaps, this game is already known, but I did not find anything about it, I call it "knight". The rules : Player 1 chooses the starting square of a knight on a normal 8x8 - chessboard. The ...
1
vote
1answer
50 views

Subtraction Game

I recently read about the Nim Subtraction Game. I have a variant, Suppose you have N stones and two players Alice and Bob, who can choose to pick either 1 stones or K stones. If Alice plays first when ...
1
vote
1answer
56 views

Economic Applications of Game Theory

I'm currently looking at this course in economic game theory. However, when attempting this example: In this question you are asked to price a simplified version of mortgage-backed securities. ...
0
votes
0answers
51 views

I'm looking for a formula to be applied on a game

I've been working on a game and I need to implement a feature, but I still haven't found a good formula for it. The problem is the following: Each team has X points, and all teams are able to ...
0
votes
1answer
33 views

Generalized Tournament Model

Consider an $n$-player simultaneous game ($n\geq2$). Each player $i$ chooses a costly bid, $q_i\in R_+$. There are $p<n$ prizes to be awarded to the $p$ bidders with the highest bids. Bids are ...
1
vote
1answer
48 views

Minimum excluded ordinal

I'm trying to understand some concepts of game theory. So far I've understood how the game of nim works, at least the most basic form: as long as the current game has value > 0 the current player can ...
2
votes
2answers
52 views

Computer software for solving mixed strategy Nash equilibrium

Is there any computer software available for solving for mixed strategy Nash equilibria for two players given each player's payoff matrix?
1
vote
1answer
41 views

In Courty and Li (2000) “Sequential Screening”, what justifies the last equation in Lemma 3.2?

Regarding the article "Sequential Screening," in Review of Economic Studies, 2000 by Courty and Li: In Lemma 3.2, the last equality states that ...
1
vote
1answer
51 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
8
votes
1answer
141 views

The Goblin Game

Goblin Game is a Magic: the Gathering card. The full text of the spell is: Each player hides at least one item, then all players reveal them simultaneously. Each player loses life equal to the ...
1
vote
1answer
60 views

Finding cut-off point for utility function

OK, so apologies for the easy question, but I'm new to this! This is somewhere between elementary algebra, and beginner's game theory. The question comes from a paper I read here (see p. 193): ...
3
votes
2answers
68 views

State-Space Complexity of RISK board game

I want to calculate the (state-space) complexity of the RISK board game. Online I found a thesis that outlines that complexity (page 34). Here is the summary: Let M denote the maximum number of ...
1
vote
2answers
104 views

What is the probability of going bankrupt in roulette?

Imagine that the bank has the money $M_1$ and the player has the money $M_2$. The rules are the following: You win with a chance of $\frac{17}{36}$ and lose with $\frac{19}{36}$ each round. Now you ...
0
votes
5answers
94 views

Some examples of applications of Game Theory

I'm approaching my junior year of HS now, and I'm looking for a good science fair project to do. I love mathematics, so I decided to a category of mathematics that can help base logical conclusions to ...
0
votes
1answer
33 views

Number of ways in a Nim game such that First Player always wins

Given $n$ piles of coins in a Nim game, how do I find the number of ways of making the first move under optimal play such that Player 1 always wins?
0
votes
1answer
33 views

Board Game Markov Process - Transient Probabilities

I need to write an essay on the Game of Life board game, and so I studied up on Markov Chains to help me calculate the probabilities and average payoffs for the spaces; however I'm not sure whether ...
2
votes
1answer
47 views

Game theory: Mixed Strategies and Nash Equilibrium

So I've recently become interested in game theory, and I've visited this site to help me understand what exactly game theory is and the applications of it. In the lesson, they use an example of ...
-1
votes
1answer
180 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
11
votes
5answers
414 views

The Price is Right optimal play

The following situation happened on the Price is Right and I was curious about the optimal response. The rules are: A contestant rolls a wheel with 5 cent increments from 5 - 100 (20 numbers total). A ...
1
vote
0answers
12 views

Distribution of coalition cost among coalition members (game theory) on the basis of contribution in coalition

Does any one know or point out the method or technique used for the distribution of the coalition cost among the coalition members depending upon their contributions in the coalition. In other words, ...
1
vote
1answer
27 views

The strategies yielding a zero-sum game's value

Let $m, n \in \mathbb{N}_1 := \{1, 2, \dots\}$ and let $\mathbf{A} \in \mathbb{R}_{m \times n}$ be a real, $m \times n$ matrix. Denote by $\Gamma$ the two-players, zero-sum game, whose payoff matrix ...
0
votes
3answers
41 views

How do we reduce a matrix in game theory?

Here we have $$\left[\begin{array}{}8 &3 &0 &5\\ 0 & 4& 4& 1\end{array}\right]$$ and I heard col2 $$\left[\begin{array}{}3\\4\end{array}\right]$$ is dominated by col3 ...
46
votes
8answers
11k views

Why do people lose in chess?

Zermelo's Theorem, when applied to chess, states: "either white can force a win, or black can force a win, or both sides can force at least a draw [1]" I do not get this. How can it be proven? ...
4
votes
2answers
511 views

John Nash's Hex proof

I am reading a book on Combinatorial Game Theory that describes a proof by John Nash that Hex is a 'first player' win, but I find the proof very confusing. This proof uses a strategy-stealing ...
0
votes
1answer
42 views

Prove that a Modified Cantor Distribution is Atomic.

Consider a measurable space $\{\mathcal{I},\mathcal{B}\}$, where $\mathcal{I} = [0,1]$ and $\mathcal{B}$ are the Borel sets on $\mathcal{I}$. And also, denote $\mathcal{C}$ as the cantor set on ...
2
votes
2answers
72 views

Is the Nash Equilibrium example in a “Beautiful Mind” accurate?

I was wondering if the Nash Equilibrium example shown in the movie A Beautiful Mind is accurate? and if not, what's wrong with it? Thanks
1
vote
0answers
50 views

Game Theory - Bayes Rule, Sequential Game

I am trying to solve the following model, but I get a few weird results. Sorry if it is too long... Nature moves first and with probability $p$ assigns player's 1 type to be High ($1-p$ for Low) ...
1
vote
1answer
55 views

Finding mixed nash equlibrium

In the following game I found one pure nash equilibrium: $(R, r)$: $\begin{array}{r|ccc} A\backslash B & l & m & r\\ \hline L & (-10, 4) & (10, 0) & (-1, -1)\\ M & (0, 10) ...
1
vote
2answers
41 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
0
votes
1answer
38 views

Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
0
votes
1answer
71 views

Can We Tell Which of These Strategies are Dominated?

This is the strategic form for a zero-sum game; it reflects player 1's expectations. I need to reduce this strategic form from 4x4 to 2x2 by eliminating the dominated strategies. All the examples ...
3
votes
1answer
18 views

Combination of supermodular and submodular functions

Suppose the production function $v(x,y)$ is increasing and submodular in both arguments, and the production function $c(x,y)$ is increasing and supermodular in both arguments ($x,y \geq 0$). Is the ...
1
vote
1answer
49 views

What is the difference between reinforcement learning, trial and error, and fictitious play?

I have three question about three algorithms. I have a game with $n$ players. The action space of player $i$ is given by $\mathcal{A}_i=\{a_1, a_2, \cdots, a_m\}=\mathcal{A}$. The joint action space ...
9
votes
1answer
146 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
1
vote
4answers
52 views

Nash Equilibrium and Limits in Game Theory

I am sure the solution to this is easy, but I can't work it out. Suppose we have an extremely simple game: There is only 1 player, who announces a number in the set [0,1]. His payoff is equal to his ...
4
votes
1answer
50 views

Expected revenue obtained by the Vickery auction with reserve price $1/2$

I would like to prove that the expected revenue of the Vickery auction with reserve price $1/2$ is $5/12$ when there are one item and two bidders the distribution of valuations are uniformly between ...
1
vote
1answer
54 views

How to calculate the expected utility for $3$ player game?

I do not understand how to calculate the expected utility of $3$ or more players game. For a $2$ player game, it is easy. Suppose I have two action $\{A, B\}$ and my opponent has two action $\{C, ...
4
votes
1answer
97 views

Prevent Alice from building a tower of height k

Alice and Bob take turns playing the tower of babel game, with Alice starting. In this game Alice has $m$ parcels of land. In each of Alice's turns she receives $n$ blocks and decides to distribute ...
4
votes
0answers
97 views

Saddle Points on Matrices

Let $n$, $m$ be positive integers. Suppose that $A$ is a $2$ x $n$ or an $m$ x $2$ matrix and that it has a saddle point. Show that among the saddle points of $A$ there exists at least one which ...
0
votes
1answer
27 views

Maximum payoff for safe bet

I'm having a hard time choosing a good strategy for this problem: assume that you have $m$ money that you can bet on $n$ mutually exclusive outcomes, all with unknown probabilities, and that each ...
2
votes
0answers
24 views

VCG - plynomial time algorithm when bidders are unit demand

Is there a polynomial time algorithm to run a VCG when bidders are unit-demand? I though to look at the Bipartite graph when the left side is the bidders the right is the items and the edges are the ...
0
votes
0answers
17 views

Can we prove constructively that $\epsilon$-equilibrium converges to (mixed strategy) Nash equilibrium?

We know that by using standard classical mathematics, $\epsilon$-equilibrium does converge to exact (mixed strategy) Nash equilibrium as $\epsilon$ becomes smaller. My question is, can we prove this ...
0
votes
0answers
30 views

Matrix Saddle Points and Dominance

I was teaching myself about dominance relations and saddle points after a friend of mine started discussing it with me and how it can be used in games. I wanted to know how to prove a problem like ...
3
votes
1answer
35 views

Computing a revenue for VCG auction

I would like your help with the following question regarding computing a revenue for a seller of an VCG (vickrey clarke groves) auction, I'm really new to this auctions\game theory so I'd really ...
0
votes
3answers
37 views

Definitions of noncooperative and cooperative games.

These days I have read many descriptions of a noncooperative game like the one below. A noncooperative game is a game in which players are unable to make enforceable contracts outside of the ...