The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
141 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
439 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 ...
11
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
425 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
150 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
500 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
813 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
230 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 ...
2
votes
3answers
222 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
4
votes
1answer
173 views

How many different states of Nash equilibrium?

So there is this quite well known Prisoner's dilemma where two parties can both defect and cooperate (and get points based on their decisions). In my presently used example I take it that cooperating ...
2
votes
1answer
232 views

Optimal auction for risk-averse seller

Consider an auction of a single unit of indivisible good. There are $n$ buyers whose values of the object is drawn independently from the uniform distribution on $[0,1]$. The buyers have interim ...
10
votes
2answers
636 views

Is quantum game theory reducible to classical game theory?

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways: Superposed initial states, Quantum ...
16
votes
2answers
6k views

Lowest Unique Bid

Each of n players simultaneously choose a positive integer, and one of the players who chose [the least number of [the numbers chosen the fewest times of [the numbers chosen at least once]]] is ...
8
votes
3answers
276 views

Can we efficiently compute a third Nash Equilibrium, given two?

A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's ...
19
votes
5answers
587 views

$n$-in-a-row game on $\mathbb{R}^2$

For integers $n$ such that $\:3< n\:$,$\:$ what is known about the following 2-player game: Player_1 and Player_2 take turn choosing points on $\mathbb{R}^2$ that were not previously chosen, with ...
24
votes
6answers
3k views

I know that you know…

A bit unsure if the following vague question has enough mathematical content to be suitable upon here. In the case, please feel free to close it. In several circumstances of competition, a particular ...
10
votes
2answers
1k views

Is there an equivalent of Heisenberg's uncertainty principle in the decision sciences ?

From memories of a quantum mechanics class and Wikipedia: In quantum mechanics, the uncertainty principle is any of a variety of mathematical inequalities asserting a fundamental limit to the ...
0
votes
5answers
1k views

Nash Equilibrium of simple betting game [closed]

I'm trying to find the Nash Equilibrium of a simple betting game, and have come up with a very surprising result which I'd like to solicit comment on. The game is simple: Two players each receive a ...
2
votes
1answer
170 views

Non-Constant-Sum Blotto Game for Only 2 Players and 2 Battlefields

In the simplest asymmetric Colonel Blotto game with 2 players, dividing their given Ni soldiers (i=1,2) over 2 battlefields, what are their expected utilities, Ui (i.e., expected number of battlefield ...
0
votes
2answers
2k views

Game Theory: Is there a Mixed Strategy Nash Equilibrium?

The game looks like this: a b A [(-12, 1) (8, 8)] B [(15, 1), (8,-1)] (15, 1) and (8,8) are Nash Equlibria. However, could you still mix ...
9
votes
1answer
494 views

M-matrix plus S-matrix is P-matrix?

I am trying to prove that a mapping has a unique fixed-point by showing that its Jacobian is a P-matrix. In this particular case the Jacobian can be decomposed as the sum of two matrices and I would ...
10
votes
3answers
969 views

Nim game for odd number of stones

Consider the classical Nim game with total number of stones being odd. Then the first players wins, of course, what follows from the general description of winning positions. But is there some shorter ...
12
votes
2answers
745 views

An unfair game involving an odd number of pieces of chocolate

Two greedy chocolate eaters play the following game involving $n$ pieces of chocolate and an additional parameter $\alpha$ with initial value $1$: Each player eats either $\alpha$ pieces of chocolate ...
4
votes
0answers
156 views

Examples of functions from matrices to real numbers with certain properties

Let $M(\mathbb{R})$ be the set of all matrices (of any size) over $\mathbb{R}$. Let $v : M(\mathbb{R}) \rightarrow \mathbb{R}$ be a function which satisfies the following 5 properties: If ...
15
votes
1answer
528 views

The Chow & Robbins game ≈ 0.79295350640: improvements could come from simple statistics, or from a continuous version of the game

This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes ...
15
votes
2answers
4k views

Simple proof of the existence of Nash equilibria for 2-person games?

Is there a nice elementary proof of the existence of Nash equilibria for 2-person games? Here's the theorem I have in mind. Suppose $A$ and $B$ are $m \times n$ matrices of real numbers. Say a ...
2
votes
5answers
1k views

Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details. Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, ...
10
votes
12answers
4k views

Are there any interesting connections between Game Theory and Algebraic Topology?

I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? ...
2
votes
1answer
566 views

game theory - coin flipping question

Lets say 2 players A and B try to have the most money at the end after playing a casino game in which they have a $49\%$ chance to double a wager. Here are the rules to the bet between A and B: ...
49
votes
9answers
8k views

Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers. The ...
6
votes
1answer
619 views

Determinantal formula for the nullspace of a singular matrix

In June 2012, Bill Press and Freeman Dyson published a remarkable paper on the iterated prisoner's dilemma. A key step in their derivation is a simple fact from linear algebra that I feel I should ...
0
votes
2answers
216 views

Mysterious sentence in a paper: what's the ultimate distribution of pure strategies?

Does anybody know how to interpret the sentence: For any set $T$ of mixed strategies, let $D[T]$ denote the set of probability distributions over the elements of $T$, each expressed as vector, ...
7
votes
1answer
224 views

Optimum Tournament Strategy

Consider a symmetric N-player game in which all players partition one total unit of energy among individual games. The probability of winning each game is simply proportional to the spent energy ...
0
votes
0answers
588 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
5
votes
2answers
534 views

Gandhi's quote formalized [closed]

Hello, I hope this question is appropriate for Mathoverflow. Gandhi said, "Be the change that you wish to see in the world". I don't understand anything in Game/optimization theory (I don't know ...
0
votes
0answers
71 views

Computing maximum point for minimal function of a family of linear functions

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such ...
3
votes
2answers
328 views

Uniqueness of equilibrium from infinite strategies

I took the following game from the Peter Winkler collection (chapter "Games"): Two numbers are chosen independently at random from the uniform distribution on [0,1]. Player A then looks at the ...
1
vote
0answers
241 views

Allocation game optimal strategy

There are two players, Alice and Bob. There is an initial pool of 100 dollars. Alice proposes an allocation of the dollars (real numbers, not necessarily integers), and Bob can either accept or ...
5
votes
1answer
378 views

Resources-Aware Combinatorial Game Theory

First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter). Now the question: **is there such a thing as the study of ...
4
votes
1answer
266 views

Indeterminacy of long games

Hello, all, Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
4
votes
1answer
1k views

Finding the Nash Equilibrium of $0-1$ poker with one betting round

While working on a hobby project I encountered a difficult math problem. Or at least, difficult for me. Here is the problem: Given an $a > 0$, find all pairs of a value $λ \in [0,1]$ and a ...
14
votes
0answers
445 views

The multiplication game on the free group

Fix $W\subseteq\mathbb F_2$ and consider the following two-person game: Player 1 and Player 2 simultaneously choose $x$ and $y$ in $\mathbb F_2$. The first player wins, say one dollar, iff $xy\in W$. ...
9
votes
3answers
448 views

Representing a real number as the value of a countably infinite game

Is it true that for any real number $p$ between 0 and 1, there exist finite or infinite sequences $x_m$ and $y_n$ of positive real numbers, and a finite or infinite matrix of numbers $\varphi_{mn}$ ...
2
votes
3answers
1k views

Motivation for the Sprague-Grundy theorem

The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber. What does the equivalence relation thus defined tell us ...
5
votes
2answers
582 views

Pursuit-Evasion on a Manifold

I know pursuit-evasion has been studied in many contexts, including on a manifold (e.g., Melikyan, "Geometry of Pursuit-Evasion Games on Two-Dimensional Manifolds"), but I have not seen this version: ...
7
votes
1answer
442 views

Cake-cutting and amenable groups

I recently heard Alan Taylor speak about envy-free fair division and started wondering if questions like these make sense if we replace finitely additive measures with invariant means on amenable ...
6
votes
1answer
776 views

Drawing lines and removing squares - an Alice and Bob game

Thought about the following while in a Complex Analysis lecture: Let there be a $N \times N$ grid of squares and two players $A$ and $B$. First, $A$ needs to draw a line $l$ that needs to intersect ...
1
vote
0answers
807 views

What would be nice open problem in evolutionary game theory ? [closed]

Hello, i was trained as a biologist, but have taught myself mathematics to a level that is roughly equivalent to that of a masters degree in math. I decided to try do some phd-research in ...
2
votes
3answers
406 views

Why are Nash-Equilibria inside the Simplex S_n unique ?

Hello, i came across a remark that states that nash equilibria inside the simplex S_n are unique. Or stated differently: If there is more then one such equilibrium, then they have to lie on the ...
5
votes
1answer
524 views

Decay of Relative Growth in Conway's Game of Life

Intro The question is about Game of Life. Let us denote the set of points obtained from initial configuration $A$ after $m$ steps as $A(m)$ (we are only interested in finite initial configuration, ...