The game-theory tag has no usage guidance.

**16**

votes

**1**answer

858 views

### 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".
...

**1**

vote

**1**answer

66 views

### A bound on the number of bilinear functions needed in order to obtain the minmax

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$.
Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...

**-3**

votes

**1**answer

68 views

### Simple equation to distribute points in a game [closed]

I need to create a equation to distribute points for users in the following game:
There are x users that play a game.
If only one of them hit he gets max points.
If all of them hit each gets min ...

**2**

votes

**0**answers

79 views

### standard auction model

I'm not familiar enough with the auction theory to know where to look, but this seems close to what seems to be known as the "standard auction model".
Say an asset is up for auction.The true value of ...

**1**

vote

**0**answers

38 views

### Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...

**0**

votes

**0**answers

358 views

### On the Theory of Infinite Step Processes of Sequential Decision Making

On the border of Set Theory and Game Theory there is a broad class of Infinite Step Processes of Sequential Decision Making that can be characterized by the main following property: a Future ...

**11**

votes

**2**answers

350 views

### Pursuit-Evasion type game on graph (“Flyswatter game”)

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...

**3**

votes

**1**answer

191 views

### Minimal Birthdays

In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.
Suppose we define the quasi-birthday ...

**75**

votes

**53**answers

25k views

### Which popular games are the most mathematical?

I consider a game to be mathematical if there is interesting mathematics (to a mathematician) involved in
the game's structure,
optimal strategies,
practical strategies,
analysis of the game ...

**4**

votes

**1**answer

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

**1**

vote

**2**answers

605 views

### Simple(?) game theory

3 players are playing a game where they get to pick independently without knowing the other players picks one of 2 prizes (A,B) and the payout is (a,b) for the two prizes, divided by how many people ...

**12**

votes

**0**answers

153 views

### Is the game Hanabi NEXPTIME-complete?

The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards ...

**18**

votes

**4**answers

1k views

### Fairest way to choose gifts

Suppose that a parent brings home from a trip $2n$ gifts of roughly
equal value for his/her two children. The children get to choose one
at a time which gifts they want. What is the fairest way to do ...

**1**

vote

**1**answer

114 views

### Convergence to equilibrium via gradient descent

J. B. Rosen proved that in concave games of n players (which assumes that Cartesian product of strategy profiles is convex) if the game satisfies the condition of diagonally strictly concave then ...

**6**

votes

**0**answers

231 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**1**

vote

**0**answers

212 views

### Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...

**8**

votes

**1**answer

135 views

### Optimal strategy for game of 'online sorting' into a poset

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution:
Each turn, the RNG produces a number, and the player must assign that ...

**4**

votes

**0**answers

133 views

### Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...

**1**

vote

**1**answer

177 views

### Is regularity closed under products?

Let $G \colon [0,1] \to [0,1]$ be a differentiable cumulative distribution function (monotonically non-decreasing function with $G(0) = 0$ and $G(1) = 1$). We say that $G$ is regular if $$ x - ...

**0**

votes

**0**answers

98 views

### Maximizing Expected Utility

I am currently trying to solve a maximization problem given by
$\max_{f(x)} \int_0^1 \int_\mathbb{R} (c-y\cdot f(x)-d\cdot (x+f(x)-b)^2) \ h(x) \ dx \ dy$.
Or in other words, I have a utility ...

**193**

votes

**9**answers

17k views

### John Nash's Mathematical Legacy

It would seem that John Nash and his wife Alicia died tragically in a car accident on May 23, 2015 (reference). My condolences to his family and friends.
Maybe this is an appropriate time to ask a ...

**-2**

votes

**1**answer

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

**15**

votes

**4**answers

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

**1**

vote

**1**answer

181 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

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

**0**

votes

**1**answer

244 views

### Equilibrium of random zero-sum game,

Hi,
How to find, or at least express, the equilibrium of a zero-sum game with an $n*n$ payoff matrix (each player has $n$ strategies) and the payoff of the entry $(i,j)$ is $u(i,j)$. $u$ a random ...

**5**

votes

**1**answer

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

**13**

votes

**7**answers

1k views

### Finding the largest integer describable with a string of symbols of predefined length

(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at ...

**1**

vote

**0**answers

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

**3**

votes

**2**answers

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

**5**

votes

**0**answers

208 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

88 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

88 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

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

**4**

votes

**0**answers

245 views

### References for this game

I would like to know how the following game is known in the literature and, possibly, to have references for related papers.
Description of the game: Fix a space $X$ and two Borel probability ...

**3**

votes

**2**answers

294 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

62 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, ...

**4**

votes

**1**answer

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

**1**

vote

**0**answers

283 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

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

**16**

votes

**1**answer

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

**13**

votes

**4**answers

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

**10**

votes

**1**answer

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

**7**

votes

**2**answers

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

**9**

votes

**1**answer

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

**7**

votes

**1**answer

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

**5**

votes

**1**answer

120 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) ...

**10**

votes

**3**answers

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

**13**

votes

**1**answer

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

**0**

votes

**1**answer

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