The game-theory tag has no usage guidance.

**1**

vote

**1**answer

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

**7**

votes

**1**answer

264 views

### What does “game theory” cover and how should it be called?

There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things:
Combinatorial game theory dealing with certain ...

**4**

votes

**1**answer

255 views

### Time-efficient way of calculating the least number of 1s in a representation of $n$ using only the operations $+,!$

This was inspired by the following paper:
J. Arias de Reyna, J. van de Lune, "How many $1$s are needed?" revisited, arXiv link.
It might help explain my question better, because my question is ...

**79**

votes

**53**answers

26k 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 ...

**1**

vote

**1**answer

148 views

### Averaged geometric series with floor function

Given a value $p\in[0,1]$ (a probability of occurrence), I would like to bound the following expression:
$$ s\frac{1-(1-p)^{k+1}}{p(k+1)} + (1-s)\frac{1-(1-p)^{k}}{pk},\ \ \ \text{where $k=\lfloor ...

**-5**

votes

**1**answer

100 views

### What means the expression “#{…}”? [closed]

I was reading the definition of a congestion game in the theory of games. Then I read the following expression:
"For each element $e$ and a vector of strategies $(P_1,P_2,...,P_n)$, a load $x_e = ...

**3**

votes

**2**answers

317 views

### Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...

**17**

votes

**2**answers

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

**-2**

votes

**1**answer

32 views

### how to resolve the infinite nesting of interactive POMDP

I am reading papers about I-POMDP. I cant understand the finitely nested I-POMDPs given in these papers.
The belief update of the algorithm has a problem that agents' belief updates mutually depend ...

**3**

votes

**1**answer

162 views

### What's the best betting strategy to double money if we have $\delta$ advantage?

Suppose that I am very skilled in a gambling game, and any day that I bet $x$, I get back $2x$ with probability $\frac 12+\delta$ (and nothing with probability $\frac 12-\delta$). My goal is to double ...

**4**

votes

**1**answer

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

**-3**

votes

**1**answer

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

**1**

vote

**0**answers

39 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

372 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

375 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

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

**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

615 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

171 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

130 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

248 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

231 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

145 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

139 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

179 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

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

**197**

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

156 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

566 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

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

**5**

votes

**0**answers

119 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

246 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

121 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

2k 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

126 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

366 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

211 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

103 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

164 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

247 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

300 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

64 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

674 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

287 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

115 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

793 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

919 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

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