The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
43 views

Game Theory Cake Cutting

I'm familiar with Game Theory concepts (I took one course at College, but it was rather superficial), but my mathematical skills aren't at the best level though. However, I'd like to hear from more ...
1
vote
1answer
85 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
1answer
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
1answer
258 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
53answers
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
1answer
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
1answer
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
2answers
318 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
2answers
936 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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
2answers
376 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
1answer
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
1answer
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
2answers
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
0answers
172 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
4answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
117 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
9answers
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
1answer
157 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
4answers
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
1answer
183 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
0answers
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
1answer
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
1answer
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
7answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
677 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
0answers
288 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
1answer
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
1answer
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
4answers
922 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 ...