The game-theory tag has no wiki summary.

**-2**

votes

**1**answer

73 views

### How can we solve the TSP problem using game theory? [closed]

Is there a known way to model the traveling salesman problem (TSP) using non-cooperative game theory?
I only found in the internet cooperative game theory. Why there is no work that solves the TSP ...

**1**

vote

**1**answer

164 views

### Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...

**4**

votes

**0**answers

75 views

### Analysis of Nim-Like Game? [closed]

There are a finite number of heaps, each with a finite number of counters. Two players take turns; on each move, they may remove exactly one counter from any heap, and also, if the heap is of size ...

**15**

votes

**4**answers

522 views

### Fair cake-cutting between groups

The cake-cutting game is usually played between individuals. What if we try to play it between groups?
A certain land has to be divided between two states. There are $n$ citizens in each state. ...

**5**

votes

**1**answer

91 views

### Anything known about the Grundy Ordinal of Sylver's Coinage

Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:
The two players take turns naming positive integers that are not the
...

**1**

vote

**0**answers

89 views

### Convergence proof for fictitious play!

In "Fictitious play property for games with identical interests" by D. Monderer and L.S. Shapley, the convergence of fictitious play to a Nash equilibrium is proved for a potential game with players ...

**5**

votes

**0**answers

203 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**2**

votes

**0**answers

79 views

### On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...

**1**

vote

**0**answers

62 views

### optimal strategies for 2-player zero-sum games of perfect information

I asked essentially this on math.SE slightly more than
3 days ago, and it hasn't received any answer there.
Do finite-state 2-player zero-sum games of perfect information with only win-draw-loss ...

**3**

votes

**0**answers

122 views

### What mathematical models can analyze and optimize systems based on gossip?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as people gossiping about stuff.
System description:
We have a ...

**3**

votes

**2**answers

273 views

### (linear algebra) - Can a symmetric equilibrium achive higher social-welfare than some equilibrium with the same support?

EDIT: rewritting the question to linear algebra to make it more accessible.
Denote by $\Delta([n])$ the set of all probability distributions over $\{1,2,\ldots,n\}$, that is:
...

**2**

votes

**1**answer

60 views

### Is there always a symmetric “subset equilibrium” for an equilibrium in a symmetric game?

Consider a 2-player symmetric game given by a payoff matrix $A\in [0,1]^{n,n}$ for the row player (i.e. the column player matrix is $A^t$).
Let $s=<s_1,s_2>$ be a (possibly mixed-strategies, ...

**1**

vote

**0**answers

266 views

### What is known about multiplayer poker with flop?

I am interested in the following simplified version of poker.
Each player gets a card (for example, either A or B).
Then they bet knowing their own cards (for example, the pot initially has 1 euro, ...

**2**

votes

**1**answer

100 views

### How to find equilibrium of the following game?

I'm looking at the following game:
2 symmetric players $\{A,B\}$, each choose a number $x_a,x_b\in [0,1]$.
The utility of player $A$ is:
$$U_A = \
\begin{cases} p\cdot x_a &\mbox{if } x_a> ...

**15**

votes

**1**answer

744 views

### Removing pawns - the game

Here is a simple game I've invented (if the idea is not fresh, then please let me know):
The game is played on a board.
The board has some (finite) number of lines drawn on it.
A pawn is placed on ...

**3**

votes

**2**answers

330 views

### Graph game minimum vertex degree

Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):
BR claims an unclaimed edge from $E$, adds it ...

**7**

votes

**2**answers

191 views

### Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...

**13**

votes

**4**answers

877 views

### Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game

The game
Lucy has $2n$ distinct white colored balls numbered $1$ through $2n$. Lucy picks $n$ different balls in any way Lucy likes, and paint them red. Lucy then giftwrap all the balls so that it is ...

**9**

votes

**1**answer

301 views

### Guessing the larger integer: A game-theoretic twist

The starting point for this question is the old chestnut, already discussed on MO, about a game show on which the host has chosen two distinct integers and the contestant gets to reveal one of them at ...

**6**

votes

**1**answer

400 views

### Explicit examples of undetermined games

Suppose we have a game between two players in which they take alternating turns. The game can have finite length, length $\omega$ or any transfinite number of steps (however, I'm not concerning games ...

**10**

votes

**3**answers

274 views

### Limiting probabilities for two-player game drawing random uniform numbers

Consider this simple 2-person game I just made up:
Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. ...

**5**

votes

**1**answer

114 views

### What is the (mixed strategies) equilibrium of this game?

Given a weight vector $w\in [0,1]^d$ such that $\sum w_i=1$, the game goes as follows:
Two players, $X,Y$ choose strategies $x,y\in [0,1]^d$ such that $\sum x_i = \sum y_i = 1$.
The utility (profit) ...

**13**

votes

**1**answer

366 views

### Stromquist's 3 knives procedure

(copied from math.SE)
BACKGROUND: A cake has to be divided among 3 people with possibly different tastes, such that each person receives a single connected piece, and no person prefers another ...

**10**

votes

**1**answer

277 views

### Game on the tree [closed]

There's a problem from programming competition which already finished:
http://codeforces.com/contest/458/problem/F
Two weeks already passed but still nobody solved it yet - in fact you can see here ...

**-1**

votes

**1**answer

688 views

### Maximal score for the 2048 game [duplicate]

t's been weeks (months?) since the 2048 game--by Gabriele Cirulli--took Internet by storm. I have an explicit integer $X$ which is greater or equal than any score of this game. Possibly my $X$ is the ...

**44**

votes

**5**answers

3k views

### Escape the zombie apocalypse

Consider zombies placed uniformly at random over $\mathbb{R}^2$ with asymptotic density $\mu$ zombies/area. You are placed at a random point and can move with speed $1$. Zombies move with speed $v\leq ...

**2**

votes

**0**answers

92 views

### Mean Capture time for the Rabbit-Hunter paper by Peres et al [closed]

I am a non-math student. I am trying to read the paper "Hunter, Cauchy Rabbit, and Optimal Kakeya Sets" by Yuval Peres et al.
Link - http://arxiv.org/abs/1207.6389
In his video based on the paper - ...

**3**

votes

**1**answer

239 views

### All solutions to a set of integral equations

I would like a better understanding of the set of pairs $(f_1,f_2)$ of functions $[0,1] \times [0,1] \to [0,1]$ which satisfy the following conditions:
For all $y \in [0,1]$, $f_1(x,y) \geq ...

**2**

votes

**1**answer

118 views

### QBF of exponential length?

We consider a slightly extended version of a nondeterministic finite automaton, call it a "propositional nondeterministic finite automaton". It is defined as follows. Consider a fixed propositional ...

**4**

votes

**1**answer

487 views

### Did Nash prove that every game or every symmetric game has a symmetric equilibrium?

Most references seem to state that Nash showed every symmetric game has a symmetric equilibrium point, but as far as I can tell from Nash's paper, he actually showed the much more general statement ...

**41**

votes

**5**answers

8k views

### Why was John Nash's 1950 Game Theory paper such a big deal?

I'm trying to understand why John Nash's 1950 2-page paper that was published in PNAS was such a big deal. Unless I'm mistaken, the 1928 paper by John von Neumann demonstrated that all n-player ...

**0**

votes

**0**answers

192 views

### Game Theory - need references on analysis of particular game

My hobby AI research have led me to a thorethical game of particular design. As design is pretty simple, I was sure that such game has well-known name. But my question on math.stackexchange, where I ...

**16**

votes

**1**answer

714 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**4**

votes

**1**answer

268 views

### Nash Equilibrium in general graphical game

Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.

**16**

votes

**6**answers

1k views

### Is a fair lottery possible?

I'm trying to come up with a scheme for a lottery where each individual has roughly the same chance of becoming the winner, regardless of the number of tickets one holds. So no individual should have ...

**1**

vote

**1**answer

140 views

### Optimum control of a probabilistic automaton

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to ...

**4**

votes

**0**answers

415 views

### Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.
For example, the terminating sequence could be ...

**17**

votes

**1**answer

612 views

### A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...

**6**

votes

**0**answers

227 views

### Identification of a curious function

The following question was asked on math.stackexchange, but there were no replies.
During computation of some Shapley values (details below), I encountered the following function:
$$
f\left(\sum_{k ...

**2**

votes

**3**answers

211 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 ...

**4**

votes

**1**answer

172 views

### How many different states of Nash equilibrium?

So there is this quite well known Prisoner's dilemma where two parties can both defect and cooperate (and get points based on their decisions). In my presently used example I take it that cooperating ...

**2**

votes

**1**answer

218 views

### Optimal auction for risk-averse seller

Consider an auction of a single unit of indivisible good. There are $n$ buyers whose values of the object is drawn independently from the uniform distribution on $[0,1]$. The buyers have interim ...

**10**

votes

**2**answers

608 views

### Is quantum game theory reducible to classical game theory?

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:
Superposed initial states,
Quantum ...

**5**

votes

**1**answer

492 views

### What can be done with computability logic that previous logic systems can't?

I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics.
What I'm seeking to know is:
Can computability logic ...

**-1**

votes

**1**answer

149 views

### To what equal constant in the Gibbs lemma

The Gibbs lemma is broadly used in games theory and in mathematical economics (optimal distributions of resourses, Cournot competition e.t.c.). Here it is:
Lemma (Gibbs). $f_1,f_2,\ldots,f_n$ be ...

**2**

votes

**1**answer

169 views

### Non-Constant-Sum Blotto Game for Only 2 Players and 2 Battlefields

In the simplest asymmetric Colonel Blotto game with 2 players, dividing their given Ni soldiers (i=1,2) over 2 battlefields, what are their expected utilities, Ui (i.e., expected number of battlefield ...

**10**

votes

**2**answers

1k views

### Is there an equivalent of Heisenberg's uncertainty principle in the decision sciences ?

From memories of a quantum mechanics class and Wikipedia:
In quantum mechanics, the uncertainty principle is any of a variety of mathematical inequalities asserting a fundamental limit to the ...

**9**

votes

**1**answer

479 views

### M-matrix plus S-matrix is P-matrix?

I am trying to prove that a mapping has a unique fixed-point by showing that its Jacobian is a P-matrix. In this particular case the Jacobian can be decomposed as the sum of two matrices and I would ...

**19**

votes

**5**answers

585 views

### $n$-in-a-row game on $\mathbb{R}^2$

For integers $n$ such that $\:3< n\:$,$\:$ what is known about the following 2-player game:
Player_1 and Player_2 take turn choosing points on $\mathbb{R}^2$ that were not previously chosen, with ...

**4**

votes

**0**answers

153 views

### Examples of functions from matrices to real numbers with certain properties

Let $M(\mathbb{R})$ be the set of all matrices (of any size) over $\mathbb{R}$. Let $v : M(\mathbb{R}) \rightarrow \mathbb{R}$ be a function which satisfies the following 5 properties:
If ...