The tag has no usage guidance.

learn more… | top users | synonyms

7
votes
0answers
113 views

Variants of the Angel problem

The original Angel problem, first proposed by Conway, Berlekamp, and Guy has two players: the devil and the angel. The angel is placed at the origin of an infinite $2$-D chessboard. The angel's ...
4
votes
0answers
111 views

Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
0
votes
0answers
47 views

Factorization (separation?) of n-player game into p-player game and (n-p)-player game

When is an n-player game factorizable (separable?) into a p-player game and an (n-p)-player game? Apologies if this is known among game theorists already - but it leads to further questions, ...
5
votes
1answer
145 views

Existence of mixed Nash equilibria for compact strategy spaces

In Peleg (1969) it is shown that a game with finite strategy spaces and continuous utilities has a mixed Nash equilibrium for any cardinality of players. Is the same true if the strategy spaces are ...
2
votes
0answers
33 views

How to model how players affect each others in a cooperative game?

The Shapley value is a very useful concept to evaluate the importance/contribution of a player based on how he affects different possible coalitions. Now based on this information, is it possible to ...
1
vote
0answers
54 views

Game Theory Cake Cutting [closed]

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 ...
4
votes
1answer
261 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 ...
1
vote
1answer
150 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 1/...
-5
votes
1answer
106 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 = \#\{...
8
votes
1answer
298 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 ...
3
votes
2answers
348 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) ...
3
votes
1answer
182 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 ...
-2
votes
1answer
34 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 ...
1
vote
1answer
104 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 ...
4
votes
1answer
116 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
0answers
45 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
392 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
396 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 ...
12
votes
0answers
193 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 ...
3
votes
1answer
200 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 ...
1
vote
0answers
254 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 ...
1
vote
1answer
145 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 ...
8
votes
1answer
147 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
147 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 ...
6
votes
0answers
261 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 ...
0
votes
0answers
129 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 ...
1
vote
1answer
180 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 - \frac{1-...
198
votes
9answers
18k 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
188 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
1answer
184 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
124 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 $n$,...
15
votes
4answers
572 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
1answer
124 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
0answers
129 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
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
107 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
170 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
2answers
304 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: $$\Delta([n])=\{x\in[0,...
2
votes
1answer
68 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
0answers
290 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
117 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
801 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
2answers
369 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 ...
8
votes
2answers
200 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 - ...
14
votes
4answers
997 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
1answer
385 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
1answer
511 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
3answers
325 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
1answer
124 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) ...