Stack Exchange Network

Stack Exchange network consists of 175 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 study of competitive and non-competitive games, equilibrium concepts such as Nash equilibrium, and related subjects. Combinatorial games such as Nim are under [tag:combinatorial-game-theory], and algorithmic aspects (e.g. auctions) are under [tag:algorithmic-game-theory].

0
votes
0answers
8 views

Game Theory, formulating a payoff matrix

Rowena and Colin play a hide-and-seek game. Rowena hides in one of 3 locations, and then Colin searches them in some order. If he searches in order i, j, k then his search cost is ci, ci + cj or ci + ...
0
votes
0answers
6 views

Finding mixed strategy Nash Equilibrium in First Price Sealed Bid Auction with Complete Information

Let we think about $\textbf{First Price Sealed Bid Auction}$ in which bidder who offers highest bid wins the object. There are only two bidders in this auction for the simplicity, $I_1$ and $I_2$. ...
0
votes
0answers
44 views

Can an open source project be considered a cooperative game?

Quote from https://opensource.google.com/docs/why/#engineering-economics: While open source work may have benevolent results, it is not an act of charity. Releasing work as open source and the ...
-1
votes
0answers
16 views

Reference for EV/ betting game questions. [on hold]

Need some good material to practice questions on probabilistic games. Mainly questions on the lines of finding EV and deciding whether it's a fair bet or not, or how much should one bet.
0
votes
0answers
16 views

Week 1 Game Theory Example 7

Example 7. Verify that the strategies $y^{*}=(\frac{1}{2},\frac{1}{4},\frac{1}{4}),x^{*}=(\frac{1}{2},\frac{1}{4},\frac{1}{4})$ are optimal and $v=0$ is the value of the game $\overline{\Gamma}_{A}$ ...
-1
votes
1answer
41 views

Can a game theory strategy go in an endless loop?

Suppose there are two players in a game. Player A arrives at their best strategy by game theory but they also know that Player B knows about game theory, so Player B will also go with their best ...
0
votes
0answers
7 views

joint venture capital determination (game theory)

In a joint venture project, n≥2 partners are to determine the amount of capital y to be invested in the company. They use the following rule. Simultaneously, each partner i submits a real number si≥0. ...
0
votes
1answer
16 views

Is it possible to have one pure strategy and infinitely many mixed strategies?

I'm wondering if it is possible to construct a game in which there is one pure strategy and infinitely many mixed strategies? I don't believe this is true, since mixed strategies mix over pure ...
1
vote
0answers
12 views

In game theory, what is the difference between garden of Eden and winning positions?

Conversely, what is the difference between traps and losing positions? Also, what is the relation between the set of winning position and garden of Eden? (I'm guessing the latter is the subset of the ...
1
vote
0answers
125 views

Find the strategy to be left with legal moves

Two people are playing with $6$ piles of stones, $2$ piles each of similar type. The piles might be of different sizes. If a move consists of removing a particular type of pile completely and then ...
0
votes
1answer
14 views

Convex hull of sets in Minimax theorem

Suppose $X\subseteq\mathbb{R}^n$ is a convex and compact set, and $Y\subseteq\mathbb{R}^m$ is a nonconvex bounded set. Consider $$ \min_{x\in X}\max_{y\in Y}x^TAy. $$ Is this equivalent to $$ \min_{...
0
votes
0answers
20 views

Optimal moves for maximizing perimeter?

Herman and Alex play a game on a 5×5 board. On his turn, a player can claim any open square as his territory. Once all the squares are claimed, the winner is the player whose territory has the longer ...
0
votes
0answers
18 views

Splitting a game into $2$ separate games

I have a mathematical problem which I would be grateful if anyone can guide me through. I have a game with a utility function like ($f(x)+f(y)$- $x$ and $y$ are independent) which has got unique ...
1
vote
0answers
10 views

Commitment Games, Nash Equilibria and Subgame Perfect Nash Equilibria

Are all Nash equilibria found from the strategic form of a commitment game all subgame perfect Nash equilibria (SPNE)?
0
votes
1answer
32 views

Understand mixed strategy N.E

Problem: I'm calculating the mixed strategy N.E for the game $$ \vec g= \begin{bmatrix}(3,3)&(0,1)\\(1,0)&(2,2)\end{bmatrix} $$ for two players (player X plays in rows, player Y plays in ...
0
votes
0answers
9 views

Verification of solution: Picking points on the line to optimise probability of winning (Game Theory)

I remembered this interesting question about game theory from a job application, and would like to get some verification on the solution I came up with (since I didn't get to know if it was correct). ...
0
votes
0answers
20 views

Mixed Strategy Nash Equilibrium Verification

There are 2 players. Player 1 has an infinite set of pure strategies: $[0,2]$ and player 2 has 2 strategies: $L$ and $R$. The payoff to player 1 are $u_1(x,L)=x^2$ and $u_1(x,R)=-x$. The payoff to ...
0
votes
1answer
20 views

Who has a winning strategy in Choquet game on rational numbers?

I know that in a real-numbers-variant of Choquet game, the player aiming for non-empty intersection has a winning strategy. Is the same true for rational numbers?
0
votes
0answers
6 views

Is the outcome of level-k reasoning different from the one of IESDS?

Level-k reasoning is based on higher levels best replying to the strategies of lower level people while iterated elimination of strictly dominated strategies (IEDS) focuses on ruling out those ...
0
votes
0answers
39 views

What do we know about the set of all games having Nash equilibrium?

Let us denote $G$ set of all games (of some particular type), and then consider $N = \{ g \in G | \mbox{game $g$ admits (mixed) Nash equilibrium} \}$. I want to ask you for some good source ...
1
vote
0answers
43 views

Modelling congestion games in python without tons of for loop

In the bidirected triangle network as shown below, 4 agents $\{s1,s2,s3,s4\}$ have their own destination $\{t1,t2,t3,t4\}$. I am trying to model this problem with a python script without any game ...
2
votes
2answers
47 views

Optimal way to stack deck against adversarial opponent?

A two-player card game is played with a deck of cards numbered 1-52, which is shuffled and placed face down. Each player draws a card from the top of the deck, then both players reveal their cards and ...
7
votes
1answer
74 views

Optimal way to stack deck against uniformly random opponent?

A card game is played by splitting a face-down shuffled deck evenly between two players. The deck consists of cards numbered 1-52. Each player reveals the top card of their deck, and the player whose ...
5
votes
3answers
143 views

Two people take turns coloring a convex polyhedron

Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first ...
2
votes
2answers
50 views

Nim-game, how many winning moves?

Let us assume that we play a nim-game (last person who draws a card, wins) and are in a position $a_1, a_2$ (sizes of piles). Assume that we have nim-sum (NS) $a \neq 0$. How many moves are there? ...
2
votes
0answers
23 views

Find the position for your maximize chance for winning. [duplicate]

There is a long line of people waiting outside a theatre to buy tickets. The theatre owner comes out and announces that the first person to have a birthday same as someone standing anywhere before him ...
4
votes
0answers
27 views

Colouring a triangular lattice competitive game

Suppose we have an infinite triangular lattice. In a competitive 2-person game, the players take turns colouring one point of the lattice which had not yet been coloured. There are 5 colours available....
0
votes
0answers
31 views

Convex combination and zero sum game

Hello, I have some questions regarding zero sum games and linear programming. As you all can see, in Diagram 1, there is no pure Nash Equilibrium unless if we use mixed strategy for both players. I ...
0
votes
0answers
15 views

Reinforcement learning and Game Theory

I see very close relationship between reinforcement learning and game theory in terms of stats, actions and rewards. But I am not able to spot the differences in both methods, clearly. I have seen ...
0
votes
1answer
39 views

Amount of strategies in tic-tac-toe

So, I have this problem for my homework in which I'm asked to show that the amount of strategies for player number 1 in tic-tac-toe is between $$9*7^8*5^{48} \text{ and } 9*7^8*5^{48}*3^{192}$$ But I ...
0
votes
0answers
46 views

game theory (prisoner dilemma) applied to brexit

I'm not a mathematician, but I learned about the prisoner dilemma, one example of game theory, in the final chapters of the "Selfish gene". Now I found a video pretending to apply it to the brexit ...
0
votes
0answers
21 views

3 players game theory formulation

I really confused about the formal representation of three players game theory formulation. I read several references and find a big difference in these references. I want some help to write the right ...
0
votes
1answer
56 views

3x3 pay off matrix with no dominated strategy with nash eq

Create a $3x3$ pay off matrix that does not have any dominated strategy and has exactly two Nash equilibrium. No mixed-strategy is allowed. I have tried and made this $\begin{bmatrix} A &B ...
0
votes
0answers
50 views

First-Price, Sealed Bid Nash Equilibrium Uniform Valuations

I'm trying to solve the following exercise: Consider a sealed bid first price auction with $2$ players in which the valuation ($v$) of each of the players is best described by a uniform distribution ...
0
votes
0answers
29 views

Why is the Shapley Value a linear mapping? What about the Prenucleolus?

The following three axioms were used by Myerson (Theorem 9.3, page 438, 1980) to fully characterise the Shapley Value as the unique solution function $\phi:G(n)\to\mathbb{R}^n$ satisfying them (notice ...
0
votes
0answers
16 views

Why are mathematical programming problems with equilibrium constraints (MPEC) harder than solving the KKT conditions?

In optimization theory a complementarity problem is a problem, where the constraints include complementarity conditions, such as $$ u^{T}v=0, u_{i}, \geq 0, v_{i}\geq 0, u,v \in \mathbb{R}^{n}. $$ ...
0
votes
1answer
41 views

Nash Equilibrium Grandfather Problem

A grandfather is writing his will and must decide how much money he will leave to his three children: Sean, Tom, and Brad. The grandfather comes up with the following plan. Each of his children is ...
0
votes
1answer
39 views

Altruistic rational agent

is there an agent in Game Theory (or even AGT), which goal is to minimizes other's costs? I've seen some agents that I would call "socialist", which goal is to minimize the sum, but including their ...
0
votes
0answers
46 views

What is the Nash Equilibrium of the Dollar Auction?

The dollar auction is a type of auction in which players bid money for a dollar. Whoever bids the most pays what they bid and gets the dollar. Whoever bids the second most pays what they bid and get ...
0
votes
1answer
44 views

Representing beauty contest with $n$ players in normal form game

I have a beauty contest question in which players must guess a number between $0$ and $5$. The closest score to ($p\times\text{average score}$) wins. Winners take 1 and losers take 0, whilst players ...
2
votes
1answer
45 views

A game-theoretic chess puzzle — Proof verification

I recently came up with the following chess puzzle (which has almost nothing to do with one's Chess skills): Puzzle: Consider a variant of chess where black has to start with $1...e5$ regardless of ...
0
votes
0answers
22 views

Nash-equilibrium in mixed strategies with arbitrary payoff function

So I came across this question in an old exam from the lecture I'm currently studying for regarding nash-equilibria in mixed strategies, which for the life of me I cannot seem to be able to find an ...
0
votes
0answers
23 views

How are all kinds of equilibra in game theory connected to each other? (Please correct my summary)

I am a TA in a basic class on game theory in the economics department. I am ashamed to admit, but I do not entirely understand how all the different kinds of equilibria connected to each other. The ...
0
votes
0answers
32 views

How to divide people into groups to maximize happiness

I need to split about 100 people into n number of groups: There should be equal numbers of freshmen, sophomores, juniors and seniors in each group. There are certain preferences, such as the ...
1
vote
1answer
84 views

How to win in Battleship?

Battleship explained in wiki: (also Battleships or Sea Battle1) is a guessing game for two players. It is played on ruled grids (paper or board) on which each players fleet of ships (including ...
0
votes
1answer
15 views

Derive formula for Shapley value

I have an exercise for Shapley value. As I know how to calculate it, I have an 8-element set and it would be difficult to calculate it by hand. It is a network G(V, E), where V is the set of nodes ...
0
votes
0answers
10 views

Ex-ante expected utility in Bayesian games

I am reading the paper "Transition Models of Equilibrium Assessment in Bayesian Game" by Kiminao Kogiso, and I saw a quite new way to define the expected utility of a player in a Bayesian game. The ...
1
vote
1answer
40 views

is there a winning strategy, and if so what is it?

Player 1 and player 2 play a game which consists of a rectangular grid with 3 rows and 20 columns. During each players turn they can colour a square in the grid (either a 1 x 1, 2 x 2 or a 3 x 3 ...
0
votes
1answer
34 views

Given $\epsilon \in [0, 1]$, find an analytic solution to $\underset{x \in \Delta_k | x_1 \ge \epsilon}{\text{argmax}}\;x^Tb$.

Let $\epsilon \in [0, 1]$, $b \in \mathbb R^k$, and $\Delta_k := \{x \in \mathbb R^k | x \ge 0,\; 1^Tx = 1\}$ be the unit $(k-1)$-dimensional simplex with $k\ge 2$. Question Find a closed-form ...
1
vote
1answer
34 views

Does this game have a core?

I'm trying to find the core of this cooperative game: $N = \{1,2,3\}$ and $v(\{1\})=24$, $v(\{2\})=24$, $v(\{3\})=26$, $v(\{1,2\})=42$, $v(\{1,3\})=44$, $v(\{N\})=52$. My solution: $x_1 \ge 24$...