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].
2,810
questions
2
votes
1answer
56 views
Game theory problem bishop on chessboard
Can anybody help me with this Game theory problem? It was presented in our "Game Theory" class which just started this trimester. So far we have only learned that one needs to look for a ...
1
vote
0answers
15 views
Best way to Play 20 questions
You and I are going to play a game. To start off with I play a measurable function $f_1$ and you respond with a real number $y_1$ (possibly infinite). We repeat this some number $N$ of times, to ...
0
votes
0answers
23 views
Prove that no stable matching mechanism exists for which truth-telling is a dominant strategy for every agent.
I have a question concerting Stable Marriage where the mechanism designer knows every agent finds all candidates acceptable.So the only way for an agent to misreport is to permute his or her ...
-1
votes
0answers
78 views
Determine all number of marbles for which the first player wins
Consider the two-player game that consists of a single bowl of $n$ marbles. The players alternate turns. During each turn, a player can remove $2^k$ marbles, for any $k \ge 0$ of his or her choice. ...
1
vote
1answer
23 views
Strategy for second-price auction with multiples
Suppose there is an auction website. The rules are that the winner pays second-highest bid, and if a bid is made with less than 3 minutes left on the timer, the timer is reset to 3 minutes.
A seller ...
0
votes
1answer
47 views
Calculating mixed strategy of $3 \times 3$ game
The Question
We consider the following zero-sum strategic game in matrix form
\begin{array}{c|lcr}
& \text{A} & \text{B} & \text{C} \\
\hline
A & 0 & +\epsilon & -\delta \\
B ...
4
votes
0answers
89 views
+100
Game theory, probability and snooker
I have a question that is very simple to understand and very complex to answer.
If a snooker player could elect to forego potting a coloured ball (typically worth a handful of points) and instead move ...
0
votes
1answer
32 views
Creating the Liar's Paradox with one truth and one lie (that aren't meta).
Some friends were playing a game where you say 1 truth and 1 lie about yourself, and the others have to guess which is which.
Just for fun, I was wondering if there was a reasonable way to give 2 ...
3
votes
0answers
44 views
Winning strategy of this Nim Game Variation?
In the Nim variation I'm looking at, two players alternate turns removing stones from N piles. The special condition is that each time a player removes k stones, k must be a multiple of the last k. ...
2
votes
0answers
38 views
Approaching “How much would you pay to play this game”-type game of chance questions
It appears that a somewhat common interview question for quantitative jobs involves asking the interviewee to submit a maximum price he would be willing to pay to play a game of chance. This question ...
1
vote
1answer
50 views
Game Theory: draw sets using a program?
I am asked to draw two different sets, S1 and S2 using a program to determine if the sets are equal. But for starters, I don't know how am I supposed to "draw" a set with a program and I ...
1
vote
0answers
48 views
Does Nash Theorem imply Zermelo's Theorem?
In 2-Player zero-sum game with every information open and no probabilistic strategy required, Nash Theorem states that one of the players has a strategy, in which the player can maintain a situation ...
-1
votes
1answer
39 views
When do games end up at a pure strategy equilibrium?
All the materials on Game Theory I have been digging so far only explain about definitions of Pure/Mix Strategies Equilibria and how to find them. However, I am really wondering under which specific ...
1
vote
1answer
27 views
What is a matrix of tuples?
Consider the prisoner's dilemma, in this game, you have a matrix,
$$A = \begin{bmatrix} (2,2) & (0,5) \\ (5,0) & (1,1) \end{bmatrix}$$
(or something like this)
But what is this object exactly?
...
1
vote
0answers
34 views
Pure and mixed strategy equlibrium
I am studying Game Theory and have problems with solving the questions regarding the game down below:
Consider $v_1 > v_2 > v_3 > 0$ and the following pay off matrix
$$
\begin{pmatrix}
A/B &...
0
votes
0answers
19 views
Shapley Assumption of Cooperation, and Interpretation
How strong is the assumption that players all cooperate? Are Shapley values still meaningful if some players have a negative effect on the reward?
I ask because a consultant is using Shapley values to ...
0
votes
0answers
47 views
How to bet having an $x> 1/2$ probability of winning
In a certain game, I have an $x> 1/2$ probability of winning. I have $y$ dollars at the start. I want to know what percentage $z$ of $y$ I should bet so that $y$ grows as much as possible with the ...
0
votes
0answers
17 views
Slope of virtual valuation function
I have the function $\frac{1-F(R)}{f(R)}$, where $F$ is the cdf, and $f$ is the pdf, of $v\sim[\underline{v},\bar{v}]\ni R.$ In order for this function to be monotonically decreasing in $R$, is it ...
0
votes
0answers
9 views
Ways to find all Weak Perfect Bayesian equilibria.
I've read lectures about W.P.B.E. There was a task to find W.P.B.E. in the case at page 27. According to lectures, there is at least one equilibrium. But how can we find all others? I hope there is a ...
0
votes
0answers
14 views
saddle point of a min-max problem over convex compact polytopes
In my optimisation notes, I have come across how one may "compute a Nash equilibrium in a two-player zero sum game by finding a saddle point of a min-max problem over convex compact polytopes&...
-3
votes
0answers
18 views
Potential Function in Game Theory
Please assist with this question.
Consider the following game:
game picture here
Is it potential game? If so, fill up potential function table bellow, else prove it.
This is the answer we received ...
0
votes
0answers
30 views
In a game, how do 2 factors interact when both influence your likelihood of a win?
Suppose a game exists such that the stronger of the 2 players is 60% likely to win and the taller of the 2 is 70% likely to win. In this world, height and strength are completely independent of each ...
0
votes
2answers
24 views
Good General Strategy For Solving For The Core In A Coalitional Game?
Does anyone have a good general approach to solving for the core of a coalitional game (or finding that there is no core)?
0
votes
1answer
32 views
Computing the Shapley Value for this two-player game
It is well known that the Shapley Value for any player $i\in N$ in any game $v:2^N\to\mathbb{R}$ is defined by the following formula:
\begin{gather}
S_i(\nu)=\sum_{S\subseteq N\backslash\{i\}}\frac{|S|...
3
votes
1answer
90 views
Improving description of vector systems and aggregation rules for social sciences
I am working on a simple individual based model that aggregates information. I am not a mathematician, but I would like to be as precise as possible with the terminology used to describe the system ...
1
vote
1answer
24 views
What exactly is a “successor” in the Extended Gale-Shapley algorithm?
Background
In the main Gale-Shapley algorithm, a Stable Matching (if one exists) within the conventional Stable Marriage Problem is achieved as follows:
...
0
votes
0answers
15 views
For every game, is there a formula $f(G)$ which takes the game state $G$ as input and whose output can be interpreted as draw/win/lose?
For the tic-tac-toe example, we may set the game state after a move by each player (X and O played), or equivalently before the move of the first player:
$M$ = \begin{bmatrix}M_{11}&M_{12}&M_{...
0
votes
1answer
30 views
Can we find Nash Equilibrium payoffs in degenerate games
In a 2 person, constant sum game, all NE strategies have identical payoff, the 'value' of the game. Typically this is calculated by first calculating one NE strategy.
In many algorithms for ...
2
votes
1answer
53 views
Coin toss game for choosing two numbers a,b and other player predicting the greater among the two. Find winning strategy
$\textit{Question:}$
Given a coin with probability p of landing heads after being flipped, pick two numbers
a, b such that a $\neq$ b, and associate “heads” to one of them and “tails” to the other. ...
0
votes
1answer
40 views
Nash Equilibrium - El Farol Bar Problem
Statement of the problem, from Wikipedia:
Every Thursday night, a fixed population want to go have fun at the El Farol Bar, unless it's too crowded.
If less than 60% of the population go to the bar, ...
0
votes
3answers
44 views
Expected average gain from implementing a policy via majority vote
Suppose a country with $n$ citizens decides whether to implement a new policy. The value of implementing that policy for each individual citizen is known only to them and is uniformly distributed on $[...
0
votes
0answers
49 views
Optimal strategy and expectation for dice game
I have a question about a popular dice 'slot' game in Belgium. A couple different casinos seem to be calling it "Mystery Box". I'll do my best to describe the rules...
The game board is made ...
0
votes
1answer
29 views
Find all equilibria of this zero sum game
We have to find the equilibria of the zero sum game specified by the following matrix:
\begin{matrix}
\\ & A & B & C
\\ T &-2 & 10 & 4
\\ M & 7 & 8 & 7
\\ B &...
1
vote
2answers
42 views
Proof of separating hyperplane theorem using minimax theorem for zero sum games
Let $x_1,\ldots,x_M\in\mathbb{R}^N$. Let $P \equiv conv \{x_1,\ldots,x_M\}$ denote the convex hull of these points. Using the Minimax Theorem prove that for all $y\in\mathbb{R}^N \setminus P$ there ...
1
vote
1answer
38 views
What is the name of a game in which if you both choose the same, you will lose, otherwise, one will win?
I am familiar with games like Prisoners Dilemma and Chicken game. However, I could not find out the name of this specific game that I believe should have interesting properties. This game has this ...
2
votes
0answers
18 views
When is Counterfactual Regret Minimization appropriate?
I must be missing something fundamental here.
In a 'stacked normal form 2 person zero-sum game' we can solve for the NE strategies and payoffs recursively. If we have access to the full tree we can ...
1
vote
1answer
13 views
Question about proper subgames in game theory.
Consider the following game presented as a tree.
As we can see there are $3$ players and the question is to find all N.E and all S.P.N.E. But I have a doubt about one thing. As we can see, if the ...
1
vote
1answer
17 views
Difference between simultaneous and ordered N.E. in the problem.
Consider the following game. There are two players and one of them could be in two states:
$A$ with probability $p$ and $B$ with probability $1 - p$. Both players actions are $1, 2,$ and to not ...
1
vote
1answer
33 views
Balancing a dice game - probability question
I am currently developing a TTRPG game system, and I am trying to determine the probability of success in various situations to see how balanced it might be.
The system is fairly simple, you roll a ...
4
votes
1answer
109 views
Winning strategy for the second player?
Suppose our two player game consists of them constructing a binary sequence (0’s and 1’s) by taking alternate turns choosing to write either zero or one at each turn, and thereby extending the ...
0
votes
1answer
48 views
Rock/Paper/Scissors strategy when opponent is restricted to only one choice (i.e. (0,0,1))?
Trying to help my college kid with a probability problem, but sad to say I can't figure it out! Is there a simple explanation?
What is the probability you win in a game of r/p/s.
I think this one is ...
0
votes
0answers
31 views
Game theory and Quantal response equilibrium
I am going to study about quantal response equilibrium while going through the topic I realised I need to have a proper understanding of the game theory first (superficial understanding won't be ...
0
votes
1answer
36 views
Lasker Nim, Sprague-Grundy Function Proof
It's been stated that the Sprague-Grundy function of Leskar's Nim is as follows:
$g (4k + 1) = 4k + 1\\ g (4k + 2) = 4k + 2\\ g (4k + 3) = 4k + 4\\ g (4k + 4) = 4k + 3$
The strategy to prove this ...
1
vote
1answer
28 views
Finding optimal strategies of matrix game
So I'm trying to wrap my head around the basics of game theory, and would like to know if I argue correctly:
Say I have the game
$$
A = \begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & -1 & 2 ...
1
vote
1answer
24 views
Expected winnings in a game with buckets of prizes
Imagine a game where there are $3$ buckets ($1$, $2$, and $3$) full of an unlimited amount of prizes. You choose a bucket at random and pull out a prize - the prize you pull out has a chance of having ...
-2
votes
1answer
50 views
Peer rated - relative ordering of people based on IQ
I am trying to develop a peer rated IQ network which can be implemented in the real world. To summarise the problem statement, consider an ecosystem of 100 people. The aim is to rank the 100 people in ...
2
votes
0answers
31 views
$(0,1)$-normalization of cooperative games
I'm currently doing some exercises on cooperative games. To be honest I can't really find any examples of (0-1)-normalization of games. Consider the game with $N=\lbrace I,II,III \rbrace$ and ...
0
votes
0answers
13 views
Subadditive cooperative game definition
Cooperative game is a pair $\left< N,\nu\right>$ where $N$ is a set of players and $\nu:2^N\rightarrow \mathbb{R}$ is a function satifying $\nu(\emptyset)=0$. I found this article where the ...
0
votes
0answers
23 views
Auctioneer have preferences over bidders
I have a problem in which an agent (call this agent A) have a predefined preferences over a set of agents (something like the value of friendship). consider the agent A may not know all agents. The ...
1
vote
1answer
18 views
Would Nash equilibrium in a game when only pure strategies are allowed be also a Nash equilibrium in a game when mixed strategies are allowed as well? [closed]
Would Nash equilibrium in a game when only pure strategies are allowed be also a Nash equilibrium in a game when mixed strategies are allowed as well?
