Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [game-theory]

The tag has no usage guidance.

0
votes
0answers
27 views

Research or a project in the field of game theory

I am a freshman in college, trying to major in Computer Science and Mathematics. In our college, we get this grant through which we can get involved in research with the professors. The professor I am ...
3
votes
0answers
124 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 ...
0
votes
1answer
53 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 ...
1
vote
0answers
119 views

How often do random games of go end in illegal moves?

Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...
1
vote
0answers
64 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 ...
3
votes
2answers
123 views

Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...
19
votes
3answers
719 views

What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?

Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ...
3
votes
1answer
63 views

Optimal Strategies for a “Blind” Graph Coloring Game

By the "blind" graph coloring game I denote the following problem, which is played by two players: player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that player has ...
2
votes
0answers
74 views

A community effort: equilibrium in quitting games [closed]

This thread is in the spirit of the polymath project: a combined effort of the community to solve a difficult open problem. It is an activity of the European Network for Game Theory whose goal is to ...
-1
votes
1answer
165 views

Matrix Tic Tac Toe

So we have a 3x3 matrix and two players, a player that only puts in ones and a player that only puts in zeros. A coin flip is used to decide which player goes first. The first move is always to fill ...
2
votes
2answers
64 views

Strong Nash Equilibria in repeated games

Suppose we have a simultaneous game, that has a strong Nash equilibrium (SNA), i.e. a weak Pareto efficient Nash equilibrium (no deviation of any subset of player brings a benefit to them). Now ...
3
votes
0answers
85 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 ...
11
votes
0answers
281 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 ...
13
votes
2answers
2k views

Who first chose the names Alice and Bob for players A and B? [closed]

Who first chose the names Alice and Bob for the players (or observers) A and B?
23
votes
1answer
1k views

Forcing and Family Contentions: Who wins the disputes?

The famous game-theoretic couple, Alice & Bob, live in the set-theoretic universe, $V$, a model of $ZFC$. Just like many other couples they sometimes argue over a statement, $\sigma$, expressible ...
3
votes
0answers
53 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 ...
11
votes
3answers
926 views

Cops, Robbers and Cardinals: The Infinite Manhunt

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob ...
2
votes
1answer
28 views

On the limit of assessments that are not sequentially rational

I have asked this question in Mathematics StackExchange, but there is no response yet. I've just realized that here is the right forum for asking research level questions... :'( In game theory, in ...
2
votes
0answers
233 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 ...
1
vote
1answer
65 views

Effective way to find Nash equilibrium

Is there any good algorithm for finding Nash equilibrium point, for one and repeated game theory? Thansk a lot for giving me some guidance.
27
votes
4answers
3k views

Alice and Bob playing on a circle

I want to solve this problem: Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move: Alice takes ...
18
votes
1answer
427 views

Who wins the Rubik's cube game?

This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier). Solver and Spoiler take turns making 90 degree twists (starting with Solver). ...
3
votes
1answer
147 views

Algorithms for Fixing Sudokus

Suppose someone got stuck solving a Sudoku and asks you to figure out, what went wrong. Unfortunately that person only sends you a copy of the instance, where you neither see which of the numbers ...
3
votes
1answer
218 views

How to prove that $a + b + 4 \sqrt{1 + a^{2} + b^{2}} \leq 4 \sqrt{a^{2} + b^{2}} + \sqrt{1+b^{2}} + \sqrt{1+a^{2}} + 2 $ for all $a, b > 0$?

I'd like to prove the following: $$ a + b + 4 \sqrt{1 + a^{2} + b^{2}} \leq 4 \sqrt{a^{2} + b^{2}} + \sqrt{1+b^{2}} + \sqrt{1+a^{2}} + 2 $$ for all $a, b \in \mathbb{R}_{>0}$. Question: is ...
0
votes
1answer
62 views

What are some relatively unknown solution concepts in cooperative game theory that are useful in a specific context?

In cooperative game theory, the payoffs for the grand coalition can be distributed in a number of ways. Each of those ways is a solution concept. Well-known examples of solution concepts include the ...
3
votes
0answers
264 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-...
4
votes
0answers
109 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
128 views

During the game of war, if you could order the cards in your deck of 26, what strategy should you employ? [closed]

During the game of war, if you could order the cards in your deck of 26, what strategy should you employ? Assume Player 2 has a random ordering of 26 cards and is not allowed to change the order in ...
10
votes
2answers
217 views

For which number of pairs is it an advantage to start in memory

Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned ...
66
votes
23answers
17k views

Which popular games have been studied mathematically?

I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with ...
1
vote
0answers
56 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 ...
17
votes
5answers
864 views

When is a game tree the game tree of a board game?

This question arises from what I find interesting in the recently asked question What is a chess piece mathematically? My answer to that question was that mathematically, game pieces are in general ...
9
votes
1answer
222 views

Ordered Nim game

Consider the following variant of Nim: There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$. A move consists of removing a positive ...
3
votes
1answer
348 views

If non-empty player has a winning strategy in Banach-Mazur game BM(X), then it also has in BM(Y)?

Let $f:X\rightarrow Y$ be a continuous, open, surjection function and second player (non-empty) has a winning strategy (not important which one, say for simplicity stationery st.) in $BM(X)$. Then can ...
1
vote
1answer
129 views

Completely mixed Nash equilibrium points

Must an isolated completely mixed Nash equilibrium (i.e., all strategies for all players receive positive weight) be essential? (By essential, I mean the equilibrium z of the game G that for every ...
1
vote
0answers
32 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 ...
8
votes
1answer
381 views

Who wins infinite Hex?

In this game, you start with a square. Alice tries to connect the top side to the bottom side, and Bob tries to connect the left side to the right side, like in Hex. Unlike in Hex, Alice and Bob use ...
3
votes
2answers
195 views

Study of Hex on the Torus

Hex is usually played on a parallelogram shaped board. What if you play it on a Torus? One thing I notice is that the idea of connecting opposite sides doesn't make much sense anymore, since a torus ...
7
votes
1answer
356 views

A game-theoretical question in a political economy model

My research question in a dynamic model of political competition boils down to the following conjecture. I am confident that it holds (all simulations work), but I have not been able to prove it yet. ...
3
votes
1answer
50 views

Relationship between the core of the quotient game of a convex game G and the projection of the core of G onto the a priori coalitions?

I am applying cooperative game theory to the question of how the structure of a value chain affects the distribution of profits among the contributing firms. I am struggling with the following. Let $...
3
votes
1answer
159 views

Is there a moving knife procedure for envy-free cake cutting with connected pieces?

In the wikipedia page on envy-free cake cutting, continuous "moving knife" algorithms for envy free cake cutting to connected pieces is only mentioned for up to 4 players. As the wikipedia article ...
2
votes
2answers
115 views

Theoretical analysis for repeated trust game

I am studying trust game (Berg, 1995). There are 2 players in this game: A and B. A moves first. A sends an amount between 0 and 10 to B. The amount is tripled in B's side. B sends back an amount ...
4
votes
1answer
144 views

Game theoretic aspects of Wang tiles?

Wang tiles are interesting in that they can simulate Turing machines. My question is whether anyone has studied their game theoretic properties? In particular, we could imagine a game in which you ...
12
votes
2answers
1k views

Should you bet in poker against Darth Vader?

This is a theoretical question about poker-type games. I'm not going to specify the rules. You can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a number ...
7
votes
2answers
312 views

Does the optimal strategy converge in poker if the SPR tends to infinity?

This a a theoretical question about poker type games. I'm sure I don't have to explain the rules - you can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a ...
-1
votes
1answer
54 views

Minimax solution but game has no value

Fix convex sets $\Delta,\Pi$ and let $r: \Pi \times \Delta \in [0,\infty]$ be linear (i.e., concave and convex) in its first parameter for every fixed second parameter. I'm looking for a situation ...
8
votes
1answer
1k views

Stable marriage with contracts: is it known?

Consider the following generalization of the classical Stable Marriage Problem. The rough idea is that instead of merely specifying who marries whom, a matching now chooses a set of "marriage ...
2
votes
0answers
81 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 ...
6
votes
4answers
1k views

Pure Mathematical Applications of Advanced Game Theory?

Games appear in pure mathematics, for example, Ehrenfeucht–Fraïssé game (in mathematical logic) and Banach–Mazur game (in topology). But the Game Theory behind those applications is not so deep, and ...
2
votes
0answers
48 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 ...