# Questions tagged [game-theory]

The game-theory tag has no usage guidance.

52
questions with no upvoted or accepted answers

**19**

votes

**0**answers

517 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$. ...

**11**

votes

**0**answers

401 views

### Generalization of Penney's game (Penney's paradox)

The standard Penney's game is played by two players. Player $A$ chooses a sequence of $k>2$ bits and $B$ (seeing $A$'s selection) chooses a different sequence of $k$ bits. A fair coin is flipped ...

**10**

votes

**0**answers

267 views

### $L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan

There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....

**10**

votes

**0**answers

3k views

### Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog

I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao http://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-...

**7**

votes

**0**answers

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

**6**

votes

**0**answers

80 views

### Pursuit-evasion with many slow pursuers

Question: Suppose that intelligent pursuers with speed $v<1$ are randomly scattered on the plane with area density $1/r$ ($r>0$ is distance from the origin). If you start at the origin ...

**6**

votes

**0**answers

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

**6**

votes

**0**answers

889 views

### Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined terminating sequence. What is the probability that the number is a multiple of some $k$.
For example, the terminating ...

**6**

votes

**0**answers

294 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 \...

**5**

votes

**0**answers

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

**5**

votes

**0**answers

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

**4**

votes

**0**answers

117 views

### What are some interesting examples of cooperative games that can be naturally generalised to a stochastic version of it?

In classical, deterministic cooperative game theory, there are $N$ players that can form $2^{N}$ coalitions. Each of these coalitions is assigned a value by means of the characteristic function $v ( \...

**4**

votes

**0**answers

193 views

### Game theory of writing multiple choice tests

Here is a model which seems pretty close to my experience of writing multiple choice tests.
Let's view the answer $t$ to each question as a binary string in $S:=\{ 0,1 \}^k$, all equally likely. The ...

**4**

votes

**0**answers

137 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 \...

**4**

votes

**0**answers

190 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 $\mathbf{a}...

**3**

votes

**0**answers

50 views

### Random Two-Player Asymmetric Game

About half a year ago I asked a question on MSE about a random two player game. At the time, the question received some attention and some progress was made, but was not resolved completely. I have ...

**3**

votes

**0**answers

84 views

### General way to find Nash equilibrium in continuous game

I'm really interesting how to find Nash equilibrium in a continuous game with two players in the general case.
Let's consider a game with continuous utility functions $F_1, F_2 : [0, 1] \times [0, 1]...

**3**

votes

**0**answers

146 views

### Reference Request: A Set-Valued Minimax Theorem?

Suppose that $\mathcal{C}$ and $\mathcal{D}$ are subsets of $L^2(X,\Sigma,\mu)\cap L^{\infty}(X,\Sigma,\mu)$, where $\mu$ is a finite-measure on $(X,\Sigma)$. Let $F:L^2(X,\Sigma,\mu)\times L^2(X,\...

**3**

votes

**0**answers

133 views

### final coalgebra of the 𝓟${_{<κ}}$(A×X) endo-functor in $Set^*$?

In the paper Coalgebraic Games and Strategies F. Honsell, M. Lenisa, and R. Redamalla use the functor $F_A$(X) = ${\mathscr{P}_{<κ}}$(A×X) to define games coalgebraically. This is a functor from ...

**3**

votes

**0**answers

98 views

### Piece rank probability in this Stratego-like game

There's this game in a 9x8 board where 2 players take turns moving pieces. The players have pieces ranked 1-21. Players can't see the opponent's pieces' ranks, just positions. Pieces landing on the ...

**3**

votes

**0**answers

77 views

### Equilibrium Strategy for half-street [0,1] Poker game, no-limit (from The Mathematics of Poker)

I have been trying to understand Example 14.3 from p154 of Bill Chen's and Jerrod Ankenman's book The Mathematics of Poker without much success. In this section they are analyzing what they refer to ...

**3**

votes

**0**answers

273 views

### What is the value of this simple game with primes?

Consider the following game. Alice selects an integer $n$ from $[1,b]$, while Bob selects an integer $m$ from $(a,b]$ (for concreteness, you may choose $a=10^{10}$ and $b=10^{1000}$). Alice wins if $m-...

**3**

votes

**0**answers

73 views

### Selecting the best choice for the smallest single appearing natural number

Assume we have $n$ players (each knows the number of competitors). Each has to chose a natural number and the player that has selected the smallest number, that appears uniquely, is going to win (if ...

**3**

votes

**0**answers

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

**2**

votes

**0**answers

54 views

### Extension of Standard English Peg Solitaire

An entire analysis of standard English Peg Solitaire has been given. See
Berlekamp, E. R.; Conway, J. H.; Guy, R. K. (2001) [1981], Winning Ways for your Mathematical Plays (paperback) (2nd ed.), A ...

**2**

votes

**0**answers

242 views

### How to promote a blog?

Math behind might be interesting.
Quite recent bloggingg activity might have interesting math model.
The point is that bloggers compete for subscribers and at the same time
cooperate gaining ...

**2**

votes

**0**answers

91 views

### Difficulty of 3-color forest Hackenbush

"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...

**2**

votes

**0**answers

62 views

### Forgetful Determinacy and Gale-Stewart theorem

I have been studying a 1969 article by Rabin that proofs his apparently very influential Tree Theorem (that says the monadic second-order theory of 2 successors, S2S, is decidable).
To give a bit of ...

**2**

votes

**0**answers

118 views

### Cooperation in asymmetric Prisoners Dilemma

There are 2 players, each can choose 2 actions, a or b. The payoffs in each case are given by rules
Actions (a,a) -> payoffs (3,4)
Actions (a,b) -> payoffs (0,5)
Actions (b,a) -> payoffs (4,0)
...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

60 views

### What is the Bruss-Yor concept of no information?

A few years ago, a question related to a paper of Thomas Bruss and Marc Yor on the so-called last arrival problem received some attention on this forum.
What I'd like to know now is:
What are the ...

**1**

vote

**0**answers

76 views

### Zero-sum games where getting information helps the opponent more

You may know of the paper on the "Memory" game - sometimes the best strategy is turning known cards (here: https://www.math.kth.se/xComb/x1.pdf). Here is a simpler toy example: You and your opponent ...

**1**

vote

**0**answers

68 views

### How does one reconcile a formula for the Shapley value for a coalition with the one given in a relatively old paper?

This is a cross-post from this question on MSE.
In the Wikipedia article on the Shapley value (here), a formula is given that generalises the notion of the Shapley value from an individual player to ...

**1**

vote

**0**answers

33 views

### rank-choice shared-resource fair-division

I'm looking for an algorithm or a paper that solves a problem with a particular set of properties.
Imagine you have some number of rooms and some greater number of people. Each person should be ...

**1**

vote

**0**answers

163 views

### A universal framework for Game Theory?

Ever since the seminal work of Von Neumann and Morgestern Game Theory has grown into a formidable sector of pure and applied mathematics.
There are all sorts of games: perfect information, ...

**1**

vote

**0**answers

136 views

### How to find the equilibrium of the following stochastic game (numerically)

I build up a stochastic game with two groups of players (Group A and Group B) and within each group, the players can have two labels as H and L (label of each player may change from period to period). ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

343 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, ...

**0**

votes

**0**answers

18 views

### Being sparse with information in an impartial game - is this game known?

You might known the thesis of Alfthan where he showed that in the game of Memory, your best move may contain turning a card that is known anyway.
I came up with a game to model the effect (denying ...

**0**

votes

**0**answers

38 views

### Two players choosing one of three numbers

$A$ and $B$ play the following game. Initially, for positive integer $n$, each player takes turns choosing one of three numbers:
$1$
the number of digits of $n$
the sum of the digits of $...

**0**

votes

**1**answer

100 views

### A game theory problem mixed strategy over a continuous set

I have two players $A$ and $B$, the action of $A$ is $x_A\geq 0$ and the action of $B$ is $x_B\geq 0$. Let $c_0\in(0,1)$, $c_3>0$ and $c_2>c_1>0$ be constants. The payoff functions of $A$ and ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

75 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 that:...

**0**

votes

**0**answers

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