Theory of dynamic processes with several competing actors that try to achieve some goal in a strategic way.

learn more… | top users | synonyms

1
vote
1answer
93 views

How to implement the regret matching algorithm?

My question is the following: How to calculate the regret in practice? I am trying to implement the regret matching algorithm but I do not understand how to do it. First, I have $n$ players with ...
-1
votes
1answer
201 views

Where is the recursion, in the minimax-decision algorithm?

The below is from an article titled: Minimax: Recursive Implementation To be a recursive function, you need to call yourself. What part of this pseudo code is calling itself? How does ...
1
vote
1answer
39 views

How do I compute this non terminal positions evaluation, for tic-tac-toe?

Looking at this solution on page 3 but having trouble understanding the evaluation function specifically. For non terminal positions, we use a linear evaluation function defined as Eval ...
2
votes
1answer
116 views

Optimizing resource management game (similar to Farmville) [closed]

Given a fully deterministic single player resource management game with a pre-known finite number of turns and reasonably simple rules (eg, Farmville, if it were single player, deterministic, and ...
3
votes
2answers
131 views

Metagame Paradox: what is wrong with this explanation?

Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post ...
1
vote
1answer
1k views

Mastermind (board game) - Five-guess algorithm

The algorithm (from here) - Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb. Remove all possibilities from S that would not give the same ...
1
vote
1answer
287 views

Dynamic subtraction game

I came across the following dynamic subtraction game: There is one pile of n chips. The first player to move may remove as many chips as desired, at least one chip but not the whole pile. ...
1
vote
0answers
204 views

Modification of Nim Game Winning Strategy

Here is the variation: We have some P piles of numbers,each having some pi numbers , and in each turn a player may choose a pile, and then a number from the chosen pile. All the numbers greater than ...
1
vote
0answers
203 views

Complexity of Alpha-Beta pruning with optimal move ordering

I originally read that Alpha-Beta pruning has time complexity of $O(b\ ^{m/2}\ )$ with perfect ordering (where b = branching factor, m = maximum ply depth) but have recently come across claims that ...
8
votes
1answer
209 views

High maths for game theory

I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky. But I find it hard to understand the ...
0
votes
0answers
47 views

Reference introductory books or articles to Game Semantics

Where can I find introductory books, articles, notes or slides on Game Semantics? I have searched a lot on the internet but I'm not satisfied by the material I found. It either is too informal, or it ...
2
votes
0answers
217 views

In what ways can we distinguish between a human and bot behavior?

Updated based on comments: In what ways can we distinguish a human being doing certain activities online and a bot programmed to do similar activities, say checking email, downloading some music ...
6
votes
1answer
494 views

Guessing the smallest unique positive integer

Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the ...
1
vote
1answer
151 views

Nash Equilibrium of 2-players game

I have a rather interesting exercise in Game Theory. Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 ...
3
votes
0answers
56 views

Online algorithm for planning

Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A ...
1
vote
1answer
112 views

$\epsilon$ - Nash Equilibrium exceeds Nash Equilibrium

I wonder if there exists a game in which $\epsilon$ - Nash equilibrium leads to a much higher payoff than any other Nash equilibrium. Show, for every $\epsilon$ > 0, a two player game where there is ...
2
votes
0answers
132 views

Nash equilibria in 3-player game with symmetry

Consider 3-player game. Players $x,y,z$, each player has two strategies. $x$: $x_1$ and $x_2$, $y$: $y_1$ and $y_2$, $z:z_1$ and $z_2$. The outcome of the game are represented by the labels of the ...
4
votes
1answer
308 views

Finding a winning strategy for toads and frogs

Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm ...
0
votes
0answers
49 views

Nash Equilibrium in Tree of Bounded Degree

I have an exercise which I can't solve. Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
5
votes
0answers
67 views

'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game: Intance of 'Stones' game is: finite set $X$ relation $R \subseteq X^3$ set $Y \subseteq X$ and ...
2
votes
0answers
388 views

Toads and frogs game algorithm

I am looking for an algorithm (or hint where to start), for Toads and Frogs Game. What I am interested in is not how to solve the problem (it's NP-hard), but how to plan one player's moves. I.e. how ...
3
votes
1answer
129 views

Difference between Dominant strategy and Winning Strategy

I am a little bit confused by the definition of dominant strategy and winning strategy, what's the difference between them. Following are the definitions taken from wikipedia, below every definition ...
9
votes
2answers
248 views

Fair cake-cutting when players join late

The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide ...
9
votes
2answers
130 views

Fair division of two-dimensional cake

I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division). In contrast to the well-studied cake-division problem, land-division is ...
2
votes
1answer
167 views

Poker with Bluffing (game theory)

I'm doing a self-study of Game Theory Evolving by Gintis, and am stuck on problem 4.16 "Poker with Bluffing". The first question asks "Show that Ollie has 64 pure strategies and Stan has 8 pure ...
1
vote
3answers
166 views

Is this NIM game tree correct?

I have an assignment to construct a game of Nim (a game in which two players must divide a pile of tokens into two unequal sizes; 6 can be divided into 2 & 4 but not 3 & 3). I was provided a ...
4
votes
1answer
64 views

Minimal-envy land division

There is a land divided to $D$ districts. There are $C$ citizens. We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district. Each citizen ...
10
votes
0answers
257 views

Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 ...
4
votes
1answer
57 views

Congestion Game with Varying Price

I molded my problem as the following game (it is a congestion game with varying price): $N$ players share resources $E$, $S_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is ...
7
votes
2answers
186 views

Is it more effective to vote for a woman?

A certain political party wants to encourage women to participate in their primary elections, so they decide, that the 4th position is reserved for a woman. That is, if there is no woman in the top 4 ...
1
vote
1answer
2k views

Nim game tree + minimax

Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player ...
1
vote
1answer
124 views

Expected gain of a game of chance with differently-priced tokens

Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular ...
7
votes
1answer
131 views

voting scheme for peaceful coexistence

Many areas in the world suffer from conflicts between two groups (usually ethnic or religious). For the purpose of this question, I assume that most people of both sides want to live in peace, but ...
7
votes
1answer
217 views

Alpha-Beta Pruning with simultaneous moves?

I have a game I'm building some ai for that has 2 players making simultaneous moves. In this game there is exactly one move where, if they both make it at the same time, the outcome is different than ...
4
votes
1answer
134 views

Mixed-strategy Nash equilibria

Is the following statement always true: if there is a mixed-strategy Nash equilibria then it is unique. I know that there can be several pure strategy Nash equilibrias.
7
votes
1answer
386 views

What use are the minimum values on minimax trees?

Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning): When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node ...