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].

learn more… | top users | synonyms

2
votes
2answers
675 views

Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
0
votes
1answer
46 views

What number of robbers, under the model of the prisoner's dilemma, would be optimal?

The prisoner's dilemma is defined as "Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of speaking to or exchanging messages with ...
14
votes
3answers
8k views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go. A suitably robust argument that establishes what is statistically the best strategy will be accepted.] Here's my description of the game: There's a $4\times 4$ ...
0
votes
1answer
123 views

Finding Nash Equilibria of a finte game of 2 players.

In a finite game, suppose player 1 has strategies $\{\alpha_1,\alpha_2\}$ and player 2 $\{\beta_1,\beta_2\}$ with payoffs as below. \begin{array}{c|c|c} &\beta_1&\beta_2\\ \hline\\ ...
1
vote
1answer
83 views

How to 'show your work' with game theoretic notation

Everything I've read on game theory seems to describe the game in notation and solves it in natural language. How do you work with notation in game theory? Could you recommend a straight-forward ...
0
votes
0answers
117 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
0
votes
1answer
354 views

Game Theory - trying to find game name by description

My hobby AI research have led me to a thorethical game of particular design. As design is pretty simple, I'm almost sure that such game has well-known name and tons of research already done around it. ...
4
votes
3answers
382 views

How to denote this in game theoretic notation

I'm writing a paper that demonstrates that linguists can use the concepts in game theory to infer what interlocutors naturally infer when the literal meaning of their utterances doesn't ostensibly ...
1
vote
1answer
201 views

Game Theory - Nash equilibrium question

Consider a game in which 2 players transmit packets in a network with a selected power $x ∈ [1, A]$ and $y∈ [1, A]$, respectively. The utility of the players can be expressed as: $$u_{i} (x,y) = ...
2
votes
2answers
350 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
1
vote
1answer
124 views

Determining Grundy Numbers for an inverted takeaway game

Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers. Rules: The game consists ...
4
votes
1answer
574 views

Game Theory/Bayesian approach to a bluffing game

Two players play the following card game with a deck consisting of (A,2,3,4,5). A dollar is placed in the pot by some third party, and player 1 is dealt a card. If it is an A, he has a winning card, ...
0
votes
2answers
125 views

Solution to $n$ by $n$ game of lights out

How can I solve an $n$ by $n$ game of Lights Out?
1
vote
1answer
81 views

Subscript before a function symbol?

Does anyone know what the subscript before the function means? $$ _pf_p $$ It's part of a definition for selfish routing in networks: Let $N = (V,E)$ be the network, which is a directed graph. ...
-1
votes
1answer
237 views

Game theory, gambling odds

I'm looking for mathematics around such game: Two games: 50%, max bet: 155000, price x1.96 0.0015%, max bet: 5, price x64224.3 Let, I will place 155,000 for 50% ...
5
votes
1answer
212 views

Topological games

I have seen in a few abstracts, as this for instance: A survey of topological games the remark that the subject Topological games has applications in other fields of mathematics. I am familiar with ...
1
vote
1answer
114 views

Game Of Strings

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a ...
3
votes
2answers
309 views

Finding optimal thresholds for “guess if number is highest” game

Consider the following game: five numbers are chosen randomly in the interval [0..1] with uniform distribution. The player is shown each number in turn and asked if it is the highest. The game ...
6
votes
0answers
116 views

Apple game question

Player A and Player B play a game. On the middle of the table there is a pot full of $N$ apples of different weights. Player A starts first and chooses an apple and starts eating it. Losing no time ...
0
votes
2answers
216 views

Game Theory: players' gender convention?

What is the Game Theory convention of using gender terms (male/female) for the players? I found only one reference suggesting that odd-numbered players are male and even-numbered players are female. ...
1
vote
1answer
92 views

Fair three-way sandwich division

This question discusses fair three-way sandwich division. Mentoined solutions include the Selfridge–Conway discrete procedure and the moving-knife procedure. I posed the question to the guys at the ...
3
votes
2answers
511 views

Existence of Saddle Point of a Matrix (Shapley's Theorem)

A $m\times n$ matrix $M=(a_{ij})_{m\times n}$ with real entries is said to have a pure saddle point at $(i_0,j_0)$ if $\min_j \max_i (a_{ij}) = \max_j \min_i (a_{ij}) = a_{i_0j_0}$. Here the notation ...
1
vote
1answer
46 views

Prove $f(x,y) > g(x,y)$ for all $x,y \in [0,1]$

I'm trying to prove the following: $$ 4xy + 4(1-x)(1-y) < \max\{8xy,8(1-x)(1-y),3\} \qquad \forall x,y \in [0,1] $$ In the language from the class, I'm trying to show that: $m_2 < ...
0
votes
1answer
217 views

Special Counterexample to Kakutani's Fixed-Point Theorem

For reference, here is the statement of Kakutani's fixed point theorem. Let $X$ be a compact, convex subset of $\mathbb{R}^n$ and let $f:X\to \mathcal{P}(X)$ be a set-valued function such that $f(x)$ ...
2
votes
1answer
136 views

Card game: How much will you pay to gamble?

You turn over the cards 2 at a time, if they are both red, you keep the cards, if they are both black I keep the cards. If one is red and the other is black then neither you nor I get a card. If you ...
3
votes
1answer
219 views

Brouwer's fixed point theorem

Theorem: If $f:D^n\rightarrow D^n$ is continuous then there is $x \in D^n$ such that $f(x)=x$. To prove the theorem we assume that $f$ is cts but has no fixed point, that is $f(x)\neq x$ for all ...
1
vote
1answer
73 views

Coin based subtraction game

I'm having a problem in Game Theory where I am trying to understand how a subtraction game can be interpreted by a coin based game. From my book: The problem I'm having is if I have 9 coins and the ...
1
vote
1answer
181 views

Explanation of basic definitions in game theory.

In the article entitled Non-Cooperative Game written by Nash in 1951, he discussed about the symmetries of games. Due to my lack of basic knowledge in permutations and symmetries, I looked up some ...
1
vote
0answers
50 views

On a certain type of card game

Suppose two players are playing a card game, which is described as follow. Each player is allowed to construct their own decks of exactly $n$ cards with an additional repeatable card, where each ...
1
vote
2answers
203 views

Why should a GE fail to exist in non-convex sets?

In an exchange economy with $2$ goods and $m$ identical Households where each household has utility function $u(x_1, x_2)$, together with positive endowments. If preferences are not convex, then why a ...
4
votes
1answer
423 views

A game of Chess - Ideal Solution

I am a student of physics. I have learnt some basic group theory, and I am wondering if there is any ideal solution for a given Chess game (like solving Rubik's cube). I know the no. of permutations ...
1
vote
0answers
33 views

Prove that the partial derivatives of $(y-g_i+a\sum^n_{j=1} g_j)$ are positive

I have a function: $$\pi_i^1=y-g_i+a\sum^n_{j=1}g_j,$$ where 0 < a<1< na, and I need to prove this: $$\frac{\partial(\sum^n_{i=1}\pi^1_i)}{\partial g_i}=-1+na>0.$$ I am not very ...
7
votes
1answer
613 views

Monkey typing ABRACADABRA and gamblers

Problem: A monkey is sitting at a typewriter, typing a letter (A-Z) independently and with uniform distribution each minute. What is the expected amount of time that passes before ABRACADABRA is ...
0
votes
1answer
54 views

A little question about the existence theorem of Nash equilibrium in game theory

Recently when I started reading Nash's paper, I found a little question about the linearity of payoff functions. Is it an assumption? Or did I miss some idea about the payoff function and its ...
1
vote
1answer
66 views

Questions about Auctions

I am having a hard time figuring out a problem. In a first price auction with a reserve price R and values of the bidders are U[0,1], how do we find expected revenue given the strategy of both of them ...
3
votes
1answer
113 views

Deriving statistical distributions from games

The normal distribution can be derived from basic principles and calculus The Normal Distribution: A derivation from basic principles. Are there other distributions that can be derived like this from ...
2
votes
2answers
129 views

A Special Type Of Guess The Number Game

There is Guess Number game like this: In this game, the player must find a hidden positive number by at most $T$ guesses (or turns). The parameter $T$ together with a health parameter $H$ is ...
5
votes
2answers
110 views

Can you incentivise competitors to handicap accurately, and also try to win?

A problem I ran into for real. A group of friends of widely differing abilities wants to hold a handicap cycling race, so that if everyone does about as well as expected, there would be a perfect dead ...
4
votes
1answer
162 views

What is a good strategy for this dice game? [duplicate]

I learned the following dice game from another forum. It was not solved there. The dice game is as follows. You start tossing six dice. After each toss you must put aside at least one of the dice ...
0
votes
1answer
110 views

How to recognize a proper sub game

The extensive form game in both diagrams appears the same, why the difference in the number of subgames?
21
votes
6answers
8k views

Help: rules of a game whose details I don't remember!

In a probability course, a game was introduced which a logical approach won't yield a strategy for winning, but a probabilistic one will. My problem is that I don't remember the details (the rules of ...
0
votes
2answers
60 views

Help me come up with a function

I have some numbers and corresponding numbers: 0 = 0 1 = 0 2 = 1 3 = 0 4 = 2 5 = 1 6 = 3 7 = 0 8 = 4 9 = 2 10 = 5 11 = 1 12 = 6 13 = 3 14 = 7 15 = 0 16 = 8 17 = 4 ...
2
votes
2answers
256 views

Expected value and optimal strategy for red/blue game

Firstly please excuse my ignorance if I'm posting this to the wrong exchange site. If this doesn't belong here let me know and I'll move it. Now as for my question, today during a short course that I ...
2
votes
0answers
71 views

Why is the feasible set of utility values (in bargaining problem) convex?

Let $S := \{x \in \Bbb{R}^n \mid x \ge 0, \sum_{i=1}^n x_i = 1\}$ be the set of mixed strategies. For a bimatrix game with pay-off matrices $A$, $B$ we denote $C := \{ (u, v) \mid \exists (x,y)\in ...
3
votes
0answers
88 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
0
votes
1answer
69 views

About mixed strategy Nash Equilibrium

Does a payoff matrix like $$\begin{array}{c|cc} &B& B&\\ \hline A& (0,1)& (1,1)\\ A& (1,1)& (0,1) \end{array}$$ has infinite number of mixed-strategy Nash ...
1
vote
2answers
109 views

Game theory reference for a beginner

I need to use game theory to model interaction in a network. What are some books or lectures that a beginner in game theory could use to understand the theory well?
0
votes
1answer
45 views

calculate win chance and win or not

I've got a logical problem with my mathematics skills. so far, I have to calculate a prizing system to say "you won" or "you lose". here my way until now: u = max. users p = prizes w = winchance in ...
2
votes
1answer
222 views

Game theory: proof V is convex and compact

Consider a non-cooperative game $(N,S_i,u_i)$. $\bullet \ N = \{1,...,n\}$ is the set of players. $\bullet$ For every player $i$, the set $S_i$ is the finite set of pure strategies. $\bullet$ For ...
1
vote
1answer
87 views

Implications of axioms of expected utility theory

Axioms for Expected Utility: Let $\succ $ be a binary relation on $X$. A1. $\succ $ is asymmetric and negatively transitive. A2. Independence of Irrelevant Alternatives: If $p,q,r \in X$ and if ...