Questions tagged [game-theory]

The tag has no usage guidance.

56 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
21
votes
0answers
549 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$. ...
14
votes
0answers
448 views

Identification of a curious function

The following question was asked on MSE but there were no replies. During computation of some Shapley values (details below), I encountered the following function: $$ f\left(\sum_{k \geq 0} 2^{-p_k}\...
12
votes
0answers
659 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
0answers
275 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
0answers
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-...
9
votes
0answers
188 views

Can Alice ever fare the worst in this variant of the truel game?

In the well known classic three way duel puzzle, 3 players Alice, Bob and Carol take turns to shoot each other until only one survives. In his/her turn, a player can either choose to shoot or pass$^{1}...
8
votes
0answers
128 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 ...
7
votes
0answers
395 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
0answers
668 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
0answers
998 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 ...
5
votes
0answers
254 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
0answers
229 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
1answer
171 views

Do random asymmetric games have more complicated strategies than random symmetric games?

Let $\Delta \subset \mathbb R^n$ be the locus of vectors whose entries are nonnegative and sum to $1$. For $M$ an $n\times n$ matrix over $\mathbb R$, let $x_M \in \Delta$ be the vector $x$ that ...
4
votes
0answers
140 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
0answers
197 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
0answers
142 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
0answers
199 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
0answers
60 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
0answers
113 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
0answers
141 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
0answers
132 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
0answers
135 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
0answers
278 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
0answers
159 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 ...
3
votes
0answers
76 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
0answers
55 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 ...
3
votes
0answers
311 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
0answers
103 views

Existence and uniqueness of solution of a nonlinear system

I need a proof of the following result to calculate a Nash equilibrium in the Showcase Showdown game. For all $n>1$, the system of equations $$\left\{ \begin{aligned} (1+e^{x}(-1+x))^{n-2}&=\...
2
votes
0answers
128 views

Finding an optimal strategy for a combinatorial sequential game

We are given a set $\{p_1, p_2, \ldots, p_n\}$ of players and a set of $\{\ell_1, \ell_2, \ldots, \ell_n\}$ of locations, where $n\in\mathbb{N}$. Each location can be either free or occupied, and each ...
2
votes
0answers
69 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
0answers
151 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,\...
2
votes
0answers
262 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
0answers
89 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
0answers
165 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
0answers
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
0answers
354 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
0answers
103 views

Nim variant with minimum number of objects?

I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...
1
vote
0answers
36 views

Suggestions for two-choice game played in ladder graph

I was just working on counting all the possible Nash Equilibrium solutions for a two-choice game played on a ladder graph (I got my results and all that for a generic number of players). And I was ...
1
vote
0answers
45 views

Maschler's bargaining set-an incomplete step in a proof

I have a problem with the concept of the bargaining set which is given below in some detail. Let $N=\{1,\ldots,n\}$ be a set of players and $v:2^N\to \mathbb{R}$ a superadditive game (meaning $S,T \...
1
vote
0answers
71 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
0answers
85 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
0answers
81 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
0answers
34 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
0answers
205 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
0answers
150 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
0answers
76 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
0answers
509 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
0answers
219 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
0answers
347 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
0answers
215 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 ...