Questions tagged [game-theory]

The tag has no usage guidance.

52 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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$. ...
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 ...
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....
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-...
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 ...
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 ...
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 ...
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 ...
294 views

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