Questions tagged [game-theory]

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

Filter by
Sorted by
Tagged with
20 votes
0 answers
632 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 \...
user avatar
  • 2,279
16 votes
2 answers
9k 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 ...
user avatar
11 votes
2 answers
555 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 ...
user avatar
10 votes
3 answers
214 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 two-...
user avatar
8 votes
1 answer
312 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 ...
user avatar
8 votes
1 answer
1k 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 $3$ ...
user avatar
  • 339
8 votes
1 answer
1k views

What is the optimal algorithm for playing the hangman word game?

Suppose we are playing the game hangman. My opponent and I both have access to the dictionary during the game. My opponent picks a word from the dictionary with knowledge of the algorithm which I will ...
user avatar
7 votes
4 answers
855 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 ...
user avatar
  • 559
7 votes
3 answers
345 views

Why does Min-Max algorithm delays a good move indefinitely?

Consider a simple chess example: Q is white Queen. K, R is black King and black Rook respectively. A B 1 . Q 2 . . 3 K . 4 . . 5 . . 6 R . 7 . . 8 . R 1,2......
user avatar
  • 165
7 votes
1 answer
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 ...
user avatar
  • 723
7 votes
1 answer
770 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 ...
user avatar
7 votes
2 answers
216 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 ...
user avatar
7 votes
1 answer
240 views

Winning strategy for a given game on graphs

The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h_1$, then player 2 responds with a villain $v_1$ who has played in ...
user avatar
7 votes
1 answer
153 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 ...
user avatar
6 votes
1 answer
1k 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 ...
user avatar
6 votes
1 answer
550 views

Machine learning approach to auction game

I am newbie with machine learning. In order to learn more I decided to try solving a specific problem/game that I have in mind. The problem is the following: I have a list of $N$ items which are ...
user avatar
  • 161
5 votes
3 answers
455 views

How does "solving" a game like connect four or tic-tac-toe work?

To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all ...
user avatar
  • 279
5 votes
2 answers
227 views

Must the champion of an entire tournament beat the champion of a possible tournament among other players?

I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given ...
user avatar
5 votes
1 answer
3k 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 ...
user avatar
  • 970
5 votes
1 answer
195 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 ...
user avatar
  • 101
5 votes
1 answer
327 views

Analysis of komi values for increasing Go board sizes and agents strength

Komi is the additional number of points given to the non-starting player in the game of Go. For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it ...
user avatar
4 votes
3 answers
358 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 ...
user avatar
  • 1,016
4 votes
1 answer
907 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 ...
user avatar
  • 1,304
4 votes
2 answers
41 views

Determining the existence of a forced win vs determining the best outcome

A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position. Is this problem equivalent under polynomial-time reduction to ...
user avatar
4 votes
1 answer
107 views

Optimal strategy in repeated cake-cutting

Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob'...
user avatar
4 votes
1 answer
271 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.
user avatar
4 votes
1 answer
837 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 ...
user avatar
  • 3,149
4 votes
1 answer
80 views

Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions. More precisely, let us define the strategy of each player as a function mapping from every valuation that they ...
user avatar
4 votes
2 answers
336 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 ...
user avatar
  • 506
4 votes
1 answer
75 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 ...
user avatar
4 votes
1 answer
70 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 ...
user avatar
  • 2,238
3 votes
2 answers
948 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?
user avatar
  • 341
3 votes
3 answers
258 views

how does the shap algorithm work in polynomial time?

I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based ...
user avatar
  • 339
3 votes
2 answers
2k views

Number of winning combination in Nim

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are ...
user avatar
3 votes
1 answer
94 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 ...
user avatar
  • 494
3 votes
1 answer
209 views

Solving the 10 players duel game

Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game. Rules of the game: Players from #1 to #10 take turns to fire at each other. ...
user avatar
  • 135
3 votes
1 answer
664 views

Evaluation functions of Minimax algorithm

Let's say we have the following relationship between $f_1$ and $f_2$: $$f_2(s) = \sqrt{1 + f_1(s)}$$ And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to ...
user avatar
  • 645
3 votes
1 answer
3k views

Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one ...
user avatar
3 votes
1 answer
143 views

Analysis of the Banana Game

My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs. Game Description The banana game is played with a ...
user avatar
  • 133
3 votes
2 answers
18k 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 ...
user avatar
  • 355
3 votes
1 answer
439 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?
user avatar
  • 459
3 votes
1 answer
112 views

Thirty-one game. Prediction of the winner

I have a problem with creating an algorithm to predict a winner of thirty-one game. Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on ...
user avatar
3 votes
1 answer
70 views

Develop a winning strategy for a game

Okay so I've been going crazy about this problem I was given. It is as follows: Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed ...
user avatar
3 votes
1 answer
140 views

Understanding Incentive Compatibility of pooled Bitcoin Mining paper

I'm trying to understand the paper Incentive Compatibility of Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data Security – ...
user avatar
  • 222
3 votes
1 answer
160 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 ...
user avatar
  • 797
3 votes
1 answer
106 views

Winning move in graph based strategy game

I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
user avatar
3 votes
0 answers
132 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 ...
user avatar
  • 1,304
3 votes
0 answers
128 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 "...
user avatar
  • 216
3 votes
0 answers
80 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 ...
user avatar
  • 131
2 votes
1 answer
267 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 ...
user avatar