# Questions tagged [game-theory]

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

102 questions
Filter by
Sorted by
Tagged with
299 views

### Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
56 views

### In Minimax, how should we handle draws?

A player playing the Minimax strategy should choose moves which minimise their maximum loss. What should happen when draws can happen? Should we class the draw as a win because we aren't losing? Or ...
772 views

### Winning strategy of Nim game when picking from multiple piles is allowed

I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in ...
110 views

### How are benchmarks created?

Computing equilibria in games and the complexity thereof is imho still quite a young field in which a lot of work still is to be done (especially the former). GAMUT (2004) is a very nice "suite of ...
125 views

### Metaheuristic for NP-complete problem without exact algorithms other than brute-force

Computing Pure Nash Equilibria (PNE) is a Game Theory related problem. Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.). I want to design a metaheuristic ...
213 views

### A 9 token game of Nim tree construction

Trying to construct the full tree for a 9 game token of Nim and am slightly confused. I don't understand how two players, min and max, will make their pick. For example, max picks first and can only ...
662 views

### Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
101 views

### What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called "...
299 views

### Induction proof of alpha-beta search

Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?
39 views

### Voronoi game in discrete space

Here i want to discuss about Linear Voronoi game. The game consists of two players, and a finite set of users placed along a line. Each player has 2m facilities, where m>0 is a fixed integer. The ...
94 views

### that there would be no perfect strategy for poker

In my opinion, every imperfect information game where there is the possibility of bluffing lacks a perfect (or winning) strategy, for the simple reason that knowing your opponent's strategy will let ...
60 views

### Why is Game Theory used to explain implementations of 3GPP D2D communication?

My question is about D2D as it relates to 3GPP (release 13+, I believe). All I have read on the subject uses Game Theory as a mechanism to explain usage. Why would authors use Game Theory for ...
539 views

### Why isn't chess an impartial game?

In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions: (1) The game is finite; i.e. there is a ...
77 views

### Is $AM = AM[2]$?

Any $k$ round AM can be reduced just two rounds whereby Arthus just does the $k$ coin tosses and passes on the information to Merlin. Merlin sees all the coin toss results and computes everything ...
276 views

### Adversarial Monte Carlo Tree Search Asymmetry

Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth, growing promising subtrees more than non-promising ones. But in a 2-player adversarial game, when a win at one node is a ...
76 views

### Stable matching of producers, consumers and objects

Has the following version of the stable matching problem been studied? There are $k$ types of objects. There are $n$ producers, each of whom can produce a single object of any type, and has a ...
67 views

### Is it possible to make excluded search with for loop in Java? [closed]

I am trying to calculate all pure strategy Nash equilibrium in a mxn game. It requires to check all pure strategy pairs (m.n pairs). Suppose player 1 has m strategies. Algorithm should start with the ...
2k 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 the ...
1k 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 depth-...
244 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 (...
317 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 ...
294 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 ...
1k views

### Dynamic subtraction game

I came across the following dynamic subtraction game: There is one pile of n chips. The ﬁrst player to move may remove as many chips as desired, at least one chip but not the whole pile. ...
476 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 ...
2k 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 ...
810 views

### Solve parity game in polynomial time?

Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
278 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 ...
124 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 ...
1k 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 ...
6k 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 ...
545 views

67 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 ...
204 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 ...
12k 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 ...
171 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 ...