The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
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 ...
-5
votes
0answers
58 views

Better chances on a gambling game [closed]

I'm working on a program that I hope it will help me to get better chances on a gambling game. I have a very large database of numbers how occur in this game and my program pass through those numbers ...
-2
votes
1answer
70 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
519 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
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 ...
70
votes
52answers
20k 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
0answers
74 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
233 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
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 ...
13
votes
7answers
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
0answers
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 ...
3
votes
2answers
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 ...
5
votes
0answers
202 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
78 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
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
0answers
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 ...
4
votes
0answers
241 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
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
1answer
58 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
483 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
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
1answer
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
1answer
742 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
874 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
1answer
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 ...
7
votes
2answers
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 - ...
9
votes
1answer
299 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
1answer
398 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
1answer
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) ...
10
votes
3answers
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. ...
13
votes
1answer
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 ...
-1
votes
1answer
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
5answers
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
0answers
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 - ...
17
votes
1answer
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 ...
2
votes
1answer
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 ...
41
votes
5answers
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
0answers
191 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
1answer
711 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". ...
0
votes
0answers
417 views

Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...
4
votes
1answer
267 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
6answers
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
1answer
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 ...
0
votes
2answers
416 views

Generalized Sprague-Grundy Theorem

Hey, I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
10
votes
9answers
3k views

a mathematically rigorous introduction to game theory

I am looking for the best book that contains a mathematically rigorous introduction to game theory. I am a group theorist who has taken a recent interest in game theory, but I'm not sure of the best ...
4
votes
0answers
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 ...
-1
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
757 views

Algorithm on winning strategy of Winner (Simplified card game)

Here's an introduction to the ordinary Winner (card game): http://en.wikipedia.org/wiki/Winner_(card_game) I'm thinking about a simplification of the game. ** I've copied this problem to cstheory ...
6
votes
0answers
225 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 ...