0
votes
5answers
93 views

Some examples of applications of Game Theory

I'm approaching my junior year of HS now, and I'm looking for a good science fair project to do. I love mathematics, so I decided to a category of mathematics that can help base logical conclusions to ...
2
votes
1answer
47 views

Game theory: Mixed Strategies and Nash Equilibrium

So I've recently become interested in game theory, and I've visited this site to help me understand what exactly game theory is and the applications of it. In the lesson, they use an example of ...
0
votes
0answers
17 views

Can we prove constructively that $\epsilon$-equilibrium converges to (mixed strategy) Nash equilibrium?

We know that by using standard classical mathematics, $\epsilon$-equilibrium does converge to exact (mixed strategy) Nash equilibrium as $\epsilon$ becomes smaller. My question is, can we prove this ...
11
votes
4answers
166 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
1
vote
2answers
87 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
0
votes
1answer
33 views

The potential function of Prisoner's Dilemma

As in the famous example of "Prisoner's Dilemma" like this If the potential function is defined as: (V(q,q), V(q,c), V(c,q), V(c,c)) q = quiet, c = confess, V is the potential. So should the order ...
0
votes
0answers
20 views

de Bono's L-game modification

I am trying to find out if a simple modification od de Bono's L-game is still infinite if two players are perfect. Modified rule is that there no neutral pieces but, there is one piece for each player ...
1
vote
1answer
107 views

Optimal strategy for dominoes game

Here is the basic principle of the game I'm trying to find an optimal strategy for: Two players (say P and Q) are given a 2x3 grid and a domino. Then P chooses one way of positioning the domino on ...
4
votes
1answer
67 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
0
votes
1answer
103 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. ...
1
vote
1answer
98 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) = ...
4
votes
1answer
135 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 ...
2
votes
1answer
148 views

Largest white rectangle on board

Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those ...
4
votes
1answer
76 views

How to design a cost sharing auction format for collective bidding?

Problem goes like this: There's one resource which can only be utilized by a single set of agents $A_i$ (at any one time) out of $n$ predefined (disjoint) sets of agents. Each agent wants to use the ...
2
votes
1answer
73 views

the proof of Arrow's Theorem

I read Philip J. Reny's paper (Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach) What I cannot understand is step 5 of the proof of arrow's theorem. I think figure 4 is a ...
1
vote
2answers
55 views

extensive and strategic game

definitions of extensive and strategic (normal) games are very different. Here is the question, what would you call a game which is extensive but in each step strategic. For instance at each step ...
2
votes
1answer
296 views

questions on information set definition

The definition of "information set" is An information set is a set of decision nodes, all belonging to the same player, over which that player cannot distinguish. ...
0
votes
1answer
84 views

Partisan/Partial Game Theory

There are enough resources available on the internet regarding "impartial" game theory. But I cannot seem to find much information regarding "partial" game theory. Can someone name some such resources ...
2
votes
1answer
518 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
0
votes
1answer
62 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
42
votes
2answers
2k views

A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe

Consider a 9 by 9 matrix that consists of 9 block matrices of 3 by 3. Let each 3 by 3 block be a game of tic-tac-toe. For each game, label the 9 cells of the game from 1-9 with order from left to ...
1
vote
1answer
99 views

Two Player Game Useless Strategy

Let's consider the variant of dominated strategy which is the pure strategy that is not a best response to any mixed strategy of the opponent (two player game). Intuitively it sounds like more ...
2
votes
0answers
281 views

Is quantum game theory reducible to classical game theory? [closed]

Modnote: This question was manually migrated (closed and crossposted) to MathOverflow by request of the OP. Quantum game theory is an extension of classical game theory to the quantum domain. It ...
1
vote
0answers
99 views

Stable Matching Optimal Strategy Existence

There is a famous stable marriage problem. It's well known that the standard algorithm for stable marriage problem proposed by Shapley and Gale is man-optimal, men get a best according to their ...
3
votes
0answers
101 views

Unexpected hanging paradox maxmin strategies

I have a question about strategies of the players of Unexpected hanging paradox (I am very sorry for a long topic, topic exist already for a while, during this time I try to develop idea how to solve ...
3
votes
1answer
323 views

Converting a game in extensive form to normal form

I have some difficulties in representing the following game in the standard form. Game: two players game is represented as a game tree (in extensive form), a game tree is a full binary tree, both ...
5
votes
0answers
228 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
2
votes
1answer
126 views

Games for which the Lemke-Howson algorithm provides incomplete results

I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria ...
4
votes
0answers
90 views

Understanding Blackwell's Approachability Theorem

I'm not super solid on my linear algebra, so I am getting lost in the discussions of halfspaces. Can someone give me an intuitive explanation (possibly with a concrete toy problem) of Blackwell's ...
0
votes
0answers
309 views

Solutions to Nisan's Algorithmic Game Theory Exercises?

I am reading Nisan's "Algorithmic Game Theory". Does anybody know if you can find (part of) the solutions to the exercises online? I would like to double-check my answers. Thanks in advance!
5
votes
2answers
499 views

Game theory Computing pure Nash equilibrium probability

We have a $2$-player game and each player has $n$ strategies. The payoffs for each player are in range $\left[0,1\right]$ and are selected at random. Show that the probability that this random game ...
4
votes
1answer
733 views

Analytically solving (calculating Nash equilibrium for) 3-player extensive form games

Let's say we extend the popular half-street Kuhn poker variant to 3 players. The rules would be as follows: ...
1
vote
1answer
51 views

Game theory multiple cooperative adversaries

Are there any papers talking about games with multiple cooperative adversaries? I do research in computer science, and I am interested in this type of game. I am really not that knowledgeable in game ...
2
votes
1answer
74 views

Rough mixed strategy approximation in large zero-sum game

I have a pretty large two-player zero-sum game in which each agent must choose between many actions. I am seeking an algorithm to approximate a mixed strategy for each player. Algorithmic simplicity ...