Questions tagged [game-theory]

The tag has no usage guidance.

52 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
0answers
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
0answers
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
0answers
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
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-...
7
votes
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
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
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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 ...