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
1
vote
0answers
3 views

In counterfactual regret minimization, why are additions to regret weighted by reach probability?

I'm reading the algorithm on page 12 of An Introduction to Counterfactual Regret Minimization. On lines 25 and 26, we accumulate new values into $r_i$ and $s_i$: $25.\space \space r_I[a] ← r_I[a] + \...
1
vote
1answer
20 views

linear time nash equilibirum aproximations for two player zero sum games

I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
0
votes
0answers
14 views

Why do agents always employ the same algorithm when playing a congestion game?

I've been conducting research into congestion games and have come across many papers that study the effects on the outcome of a game played by agents employing a particular algorithm e.g. seeing how ...
5
votes
1answer
186 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 ...
1
vote
0answers
35 views

The opposite of a Tit-for-Tat strategy

The tit-for-tat strategy is a well-known strategy that can be applied, for example, in the Iterated Prisoner's Dilemma (IPD). Roughly, the idea is that you always repeat what the opponent did in the ...
2
votes
2answers
48 views

Zero-Sum Games and Halting Problem

Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to ...
0
votes
1answer
44 views

Trust in online platforms dealing with virtual goods

I am implementing an online platform, where third-parties sell virtual goods to clients on a subscription basis. Let's take for example ebooks as a virtual good in this case. How can the third-parties ...
2
votes
1answer
27 views

Recover a matrix with minimum number of queries

Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob ...
0
votes
1answer
47 views

Expected number of coins

Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob. ...
1
vote
0answers
25 views

Is this a valid heuristic for Dots and Boxes to reduce the branching factor of the search tree?

I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits ...
3
votes
1answer
71 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 ...
-1
votes
1answer
204 views

A single heap nim game

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game. A set P = {p1,p2,…,pk} determines the allowed moves....
1
vote
0answers
42 views

Is Dots and Boxes complementary to the game of Go?

I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go. Here's a ...
7
votes
1answer
186 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 ...
2
votes
0answers
153 views

Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
2
votes
1answer
295 views

What is the best solving algorithm for a game with stacks?

Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose ...
6
votes
3answers
256 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......
0
votes
0answers
56 views

How do evaluation functions influence the optimal sequence of moves?

Assume you have a game tree and the features $(f_1, f_2, f_3,\ldots,f_n )$ that describe the state of the game at any node. Also assume that you are using depth-limited minimax and always expand up to ...
0
votes
2answers
80 views

Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?

The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and ...
2
votes
0answers
41 views

Marriage Problem: Is both sided stable matching strongly pareto optimal?

According to this problem: Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium? Is the both sided stable matching strongly pareto optimal for both sides? ...
1
vote
1answer
292 views

Is there any algorithm so it can solve stable marriage problem with incomplete preference lists

I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed ...
1
vote
1answer
175 views

Two Minimax AIs playing against each other

I am trying to have my Minimax AI chess players play against each other. I was a bit confused about an implementation detail. Let's call black my first minimax AI ...
0
votes
2answers
80 views

Is there any model of Game of Life compatible with hypercomputation?

I found a question in Mathematics Stack Exchange which asks a very similar question (https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
2
votes
1answer
90 views

Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
4
votes
1answer
73 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 ...
1
vote
0answers
52 views

Game Theory: Using a convex hull algorithm to map out Pareto outcomes

I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this: Strategy profile $\mathbf{s}$ Pareto dominates strategy $\mathbf{s}'$ if for all $i\in\...
5
votes
2answers
186 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 ...
2
votes
0answers
49 views

Can Pareto Optimality be compared to Nash Equilibrium?

Given a state $s$, and a value function $v^i$ that determines the expected payoff for the i-th agent in that state, can the two definitions below, one of Nash equilibrium and another of Pareto ...
1
vote
0answers
33 views

Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous ...
1
vote
1answer
67 views

Transformation of a Product Buchi Game to a Parity Game

Is there anyway to express a Product Buchi game as a parity game? There is no stochasticity in my original turn-based game and a Deterministic Buchi Automaton is constructed for LTL specifications.
2
votes
2answers
92 views

How to express the existence of winning strategy of the starter of a game in temporal logic?

Consider a two-player game. A winning strategy of a player is a strategy following which the player can always beat his opponent, no matter how his opponent responds. A game can be unfolded to a ...
4
votes
2answers
39 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 ...
4
votes
3answers
353 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 ...
4
votes
1answer
91 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'...
2
votes
0answers
44 views

Agreeing on a Time in a Trustless Network

Imagine a chord-like network $N$. each machine $m \in N$ is directly connected to $N_m \subset N$. Without relying on official timeservers, I want all machines to synchronize to some time with ...
2
votes
1answer
315 views

Variant of nim game with particular rules

Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the ...
0
votes
0answers
279 views

What is the best heuristic function for evaluating the state in game of sprouts?

We are developing game of sprouts bot using min-max algorithm. We need a good heuristic function for evaluating the state of the game/player. Can someone please suggest?
0
votes
1answer
327 views

Utilization of static evaluation functions in chess

Disclaimer: I'm very new to computer science & game programming I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just ...
3
votes
1answer
2k 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 ...
3
votes
1answer
115 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 ...
0
votes
1answer
47 views

Probability that a leaf with 1 will be selected in game tree evaluation

I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar). ...
0
votes
0answers
691 views

Board Game algorithms

I have to find an evaluation function in which we evaluate the state of the game in each round. The game is like " roborally " , it is 2 player-Game in which there are a board and cards ...
0
votes
0answers
65 views

Simultaneously optimal strategies for both players in zero-sum games

Given a matrix $A \in \mathbb{R}^{m \times n}$ that describes a zero-sum game. What are necessary and sufficient conditions for cases in which the k-th pure strategy of the row-player and the l-th ...
-1
votes
1answer
62 views

Are dynamic and agent-based network formation models exclusive groups?

I am studying network formation models and I have seen the separation of those models into two groups (wikipedia): Agent-based models: Aka game-theory based models. This distinction makes sense to ...
1
vote
0answers
26 views

how to use the solution of mean payoff game to arrive at winning regions of parity game?

The 7th chapter (7.3 section) of "Automata Logics and Infinite Games" by Erich Gradel, Wolfgang Thomas, Thomas Wilke gives a way to convert max parity game to mean payoff game. I do not understand ...
0
votes
1answer
217 views

Game of Nim (Find winning states in large range)

If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively I know that the solution of (winning) iff x^2x^3x != 0 but if x can be in the range from 1 to 2^61 so How many ...
3
votes
1answer
64 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 ...
2
votes
0answers
42 views

Is this modified version of Nim solvable?

In the regular version of the game Nim, you have $n$ piles of stones, and you may remove one or more stones from a single pile in your turn. A modification I thought of involves the concept of piles ...
5
votes
1answer
248 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 ...
0
votes
0answers
20 views

Degrees of Separation Minimization & Pathfinding Elimination Strategy for Large Networks

Assume you have a graph/network N; Boundary Conditions: each vertex/node $n \in N$ can support a maximum number of $e_{max}$ connections Nodes can join and leave the graph. Each node $n$ has an ...