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

3
votes
1answer
20 views

Shapley values as a hash/compression of a game

Computing a Shapley value, we are mapping the set of coalition games on $N$ to a vector of $N$ elements: $$ \phi: \; \mathbb{R^{2^N}} \to \mathbb{R}^N $$ In a sense, this is compression, or more ...
3
votes
2answers
44 views

Multiplying Single Digit Numbers to Get Product >1000

This is yet another Alice and Bob problem. Alice and Bob are playing a game on a blackboard. Alice starts by writing the number $1$. Then, in alternating turns (starting with Bob), each player ...
1
vote
1answer
50 views

Good books to learn Combinatorial Game Theory?

I am currently doing my IB Diploma and we are supposed to make an extended essay on a subject of our choice- and i chose math. my research question is- "how to derive a perfect strategy to always win ...
1
vote
1answer
28 views

Game theory: solutions concepts if each player has different utility

Assuming, I have a network game (where the players are e.g. users in a network), how is it possible to model user-specific a-priori information (which results in different utility functions for each ...
1
vote
1answer
19 views

Question about usage of $\leq$ in definition of Nash equilibrium

Quick definition: Given $g$, a strategy N-tuple $u^* = (u_1^*,...,u^*_N)$ is said to be a Nash equilibrium if: $$J_i(u_i^*, u^*_{-i}) \leq J_i(u_i, u^*_{-i}), i \in N$$ where $J$ is ...
0
votes
1answer
24 views

What is the quickest way to find Nash equilibria in two player bimatrix game?

Suppose the cost/penalty matrix of a game is given as: $$M = \begin{bmatrix} (-5,-5) & (0,0) \\ (0,0) & (-3,-3) \end{bmatrix}$$ Then the game as two equilibria $(u_{11},u_{21})$ and ...
0
votes
0answers
32 views

In what ways would a course on convex optimization be useful in game theory?

From talking to several other people in the past, and referencing Quora, it seems that convex optimization is really a tiny subset of game theory in that it only models the behavior of one single ...
1
vote
1answer
23 views

Can someone please help me understand what a “player set” is in extensive form game

my text defines player set as: In N-player game $g$, each non-terminating node is partitioned into $N+1$ sets $g^0, ... g^N$. These are player sets. However it makes no attempt to identify ...
1
vote
1answer
24 views

Devising a method to arrive at a square only being able to move right and up

I was recently presented with a problem where I have a 10x10 grid and a marker that starts at position (1, 1). Two players are able to manipulate the marker by moving it as far right, or (exclusive) ...
0
votes
3answers
30 views

Reducing TIC-TAC TOE State Space by using Symmetry in Artificial Intelligence

Im learning Heuristics in AI.I see that for brute force search there are 9! states.But the textbook says that first 3 levels are reduced by symmetry.How does that work?
0
votes
1answer
11 views

A question in Osborne-Rubinstein A course in game theory,

I am having trouble with Rubinstein's electronic email game (proposition 83.1) in the textbook(first edition). My question: Line 7 starting from the "proof", "...player 2's expected payoff is at ...
3
votes
2answers
92 views

How many legal states of chess exists?

I have a fairly simple question. How many legal states of chess exists? "Legal" as in allowed by the rules and "state" as an unique configuration of the pieces. I'm not asking for the number of ...
0
votes
0answers
13 views

numerical solution for nash equillibrium

I have the following setup. $\pi_1=f_1(q,r)$ and $\pi_2=f_2(q,r)$ are the real valued payoff/profit functions of the two players. Player 1 gets to pick $q$ and player 2 gets to pick $r$. I also know ...
0
votes
0answers
33 views

Probabilities in this blackjack variation

Let's say I play blackjack (52 cards, figures count for 10, aces count for 1 or 11) and alone (no dealer). The cards I use for one particular game are always removed at the end of that game and won't ...
0
votes
0answers
41 views

“Composition” property in cooperative game theory?

I am trying to find a property which can help to analyse the composition of a cost/profit division and which allocation rules (e.g., Shapley value or nucleolus) would satisfy it. In short, the idea ...
6
votes
1answer
64 views

Tzaloa 2015 game problem (piles with $1,2,4 \dots 2^{19}$ coins each)

We have $20$ piles with $1,2,4,8\dots 2^{19}$ coins repectively and two players. In each turn a player must select five piles that have at least one coin and remove exactly one coin from each. Player ...
0
votes
1answer
39 views

Why does the 1st player in this subset take-away game always have a winning strategy?

This is a HW problem of mine that I cannot, for the life of me, figure out. There is a take-away game where there are a number of elements A, and the person that wins is that last person to remove a ...
0
votes
1answer
23 views

Nash equilibrium for two players game.

Consider a game for two players, say "Player A" and "Player B". The two sets of strategies are denoted by $A$ and $B$, available to the players. Consider a symmetric situation where the players have ...
2
votes
0answers
72 views

Expected travel of random walk in arbitrary game with multiple payouts

As explained here, the average distance or 'travel' of a random walk with $N$ coin tosses approaches: $$\sqrt{\dfrac{2N}{\pi}}$$ What a beautiful result - who would've thought Pi was involved! ...
0
votes
1answer
23 views

When solving a system of equations for a game theory question, can the solutions be negative?

I have a homework question on solving a game matrix geometrically. $m =$ $\begin{bmatrix}1 & 11\\7 & 2\end{bmatrix}$ (after adding the constant $k$ to ensure it's a positive matrix) The ...
0
votes
1answer
41 views

Find a Nash equilibrium solver

The solvers I know so far are designed only to allow payoffs as given numbers. But is there a solver allowing users to type payoffs as variables?
0
votes
0answers
74 views

Finding Nash equilibrium in game with random event at event tree?

I have posted a question about finding the NE of sequential game with imperfect information. It is lucky that the game can solve could be dealt with could be dealt with by a simpler argument. Here is ...
2
votes
0answers
56 views

A fashion victim puzzle

Consider $n \in \mathbb{N}$ fashion-sensitive kids, each wearing a T-shirt; for simplicity, kid $i \in \{1, \ldots, n\}$ initially wears shirt $i$. Tastes over the shirts are summarized in an $n ...
-3
votes
1answer
49 views

How to find the Nash equilibrium or subgame perfect equilibirum in a sequential game with imperfect information? [closed]

I have a problem with the sequential game with random event at the event tree. The model of the game as follows: Player = $\{A,B\}$ Pure strategy of player $A: A1, A2, A3$ For each strategy of ...
0
votes
1answer
27 views

IESDS and Nash Equilibrium - same solution [closed]

Applying the Iterated Elimination of Strictly Dominated Strategies (IESDS) to a game resulted with the same solution of the Nash Equilibrium. What does this imply? Actually that specific "quadrant" ...
0
votes
1answer
56 views

English translation of von Neumann's “Zur Theorie der Gesellschaftsspiele”, 1928

Some colleagues and I are reading various classic papers. We would like to read von Neumann's "Zur Theorie der Gesellschaftsspiele", 1928, but do not read German. Do you know of an English ...
3
votes
2answers
64 views

System of Differential Equations- Asymmetric First-Price Auction

I am working on a problem in my Auction Theory textbook regarding a two-player asymmetric first price auction. Assume the bidders are risk neutral. The problem statement is as follows: ...
6
votes
0answers
162 views

Cutting a Banach-Tarski Cake

I was reading a cake-cutting problem here (not really related, so I won't link to it), and for some reason, this variation occurred to me. I have no idea whether this problem is even well-formed: ...
3
votes
1answer
59 views

A deadly game of two werewolves and two townsfolk

This question was closed due to lack of own effort shown. Because I like the game of werewolf (a.k.a. Mafia) and thought it was a nice idea to pose a simplified version of it as a game-theoretic ...
1
vote
1answer
47 views

What is the mixed strategy equilibrium bid, if any, for complete information auction games with minimum bid?

Consider the following complete-information, auction game. There are two players $i=1,2$. Each bids simultaneously a value $b_i\in[0,\infty)$. The payoff function is symmetric: $$ \pi_i ...
2
votes
1answer
50 views

Mixed strategy problem - game theory

I have a basic doubt in a question of game theory. Assume that in a $2$ player game the mixed strategy profile $((a,b,0),(c,d,0))$ is a mixed strategy NE. Does the indifference condition in a mixed ...
0
votes
0answers
18 views

super-additive, sub-additive, and shapely value limitations?

I am working on the coalition formation. Most of the scientist used concept of shapely value for distributing the utility among the members of coalition. Up to my understanding, shapely value is good ...
10
votes
2answers
553 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
1
vote
0answers
31 views

Expectation of a continuous function

Can someone help with the following? I have a continuous function $g: A_i \times A_{-i} \to \mathbb{R}^k$, and a probability measure $\mu \in \Delta(A_{-i})$. We can let $A_i=\mathbb{R}^n$ and ...
0
votes
1answer
65 views

Is this a game theory problem or optimization problem?

Consider a problem that looks for a $x$ that can make the following problem into some equilibrium state (similar to an equilibrium solution to a min-max problem in game theory) $$ \max_x f(x)$$ $$ ...
0
votes
1answer
16 views

imperfect information in extensive form

Hi I'm trying to understand how to convert into extensive form this imperfect information game. consider the second graph of this example taken from example of imperfect information game in extensive ...
1
vote
1answer
41 views

Is my cake split envy-free (and coalition-resistant)?

I once read that splitting a cake in 4 parts envy-free is notoriouse difficult. Not to mention splitting it with 5 or more people. Methods involve arbitrarily long recursions and cake split onto ...
1
vote
0answers
23 views

Example of infinite game without any Nash equiblibria

I have to find an example of a game that does not admit (mixed strategy) Nash equilibria. Consider a game in normal form. Let $N=\{1,2\}$ be set of players and $S_i=\mathbb{R}$ a set of possible ...
-1
votes
1answer
50 views

Facing problem to compute ShapleyValues [closed]

I am facing problem to compute the ShapleyValues. Suppose there are 5 people in a city. First person has 10 dollars, 2nd person has 6 dollars, 3rd person has 11 dollars, 4th person has 12 dollars and ...
1
vote
1answer
65 views

Expected Utility Method and a Repeated Game Solution

I am trying to replicate Bruce B. de Mesquita's (BDM) results on political game theory for prediction. Based on where actors stand on issues, their capabilities, salience, BDM's method attempts to ...
2
votes
2answers
38 views

A game with no pure or mixed strategy equilibrium?

I'm trying to find any and all pure or mixed strategy Nash equilibria for the game $$\begin{array}{|c|c|c|c|}\hline & L & C & R \\ \hline T & (6,2) & (0,6) & (4,4) \\ \hline ...
1
vote
1answer
41 views

Dual Core in Cooperative Game Theory

I'm a bit confused over if the dual core of a game is the same as the core of the original game. Definition of dual game: $$ v^*(S) = v(N) - v( N \setminus S ), \forall~ S \subseteq N.\, $$ I then ...
3
votes
1answer
30 views

Proof that $\min_{b\in B} u(a,b)\leq \min_{b\in B}\max_{a\in A}u(a,b)$

So I have two finite sets $A,B$ and $u:A\times B\rightarrow \mathbb{R}$ a utility function. I am asked to give a certain proof but I don't need help with the whole thing, I just need help figuring ...
1
vote
1answer
25 views

Game Theory (continuous utility, pure strategy)

I have a game in which two players, 1 and 2, choose a non-negative real number level of effort $e_1,e_2$ respectively. Their cost for this choice is $ce_i$ for $i=1,2$ where $c>0$ is the same for ...
3
votes
0answers
57 views

Auction Design : Multiple lots, one win max per bidder, not regret

This is a real life game theory problem. I have to organize an auction. There is a finite number of lots, which are not equivalent. There is a finite number of bidders; the number of bidders is ...
1
vote
1answer
60 views

Can a transitive relation be represented by a utility function?

I am currently studying for my Game Theory exam and came across a question that seems pretty basic but somehow can't wrap my head around. So if you could share some insight with me, that would be ...
4
votes
1answer
98 views

Have I Found an Error in “Game Theory” by Hans Peters?

I am reading the book Game Theory: A Multileveled Approach Second Edition by Hans Peters. It appears to be the most recent copy. I've search here and on Google for a list of known errors in the book, ...
0
votes
1answer
34 views

Can a game with a pure strategy Nash equilibrium also have mixed strategy equilibria? [closed]

I have questions: If zero-sum game has pure strategy Nash equilibrium (saddle point), can it have also mixed strategy equilibria? What if game is not zero-sum?
3
votes
3answers
130 views

Playing Odd-Even Cricket, is there a perfect strategy

This is a simple two-player game. One if the people is picked to 'bat'. Both players simultaneous choose a number from 1 to 6. (When playing against a person, you use your hands to show the number). ...
3
votes
1answer
51 views

An inequality relating to moves to P-positions in Nim

I have been researching this variant of Nim. I have been unable to prove the following claim. What is annoying is that I feel I am missing something really obvious. Does anyone have any ideas on how ...