Skip to main content

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
0 answers
19 views

Multiplayer one-round one-move voronoi game on graphs

I'm trying to solve a variant of Voronoi Game. Given a Graph $G=(V, E)$, with uniform distance $d(E)=1$, a subset of the vertices $\hat{V} \subseteq V$ are vertices of interests. $k$ players take ...
z.x.99's user avatar
  • 11
1 vote
0 answers
19 views

Examples of challenging general-sum matrix games

Solving $N$-player general sum matrix games is known to be PPAD-complete, and even for two players algorithms such as Lemke-Howson can take exponential time in the worst case. On the other hand, ...
ntrstd11's user avatar
  • 111
1 vote
0 answers
24 views

Stable Flow Problem with one sided preferences

I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
Finn's user avatar
  • 11
4 votes
0 answers
207 views

Game of permutations as a minimization problem

Consider the following "game". There is an ant on a strip of length N. The ant can perform the following actions: move left, move right, and paint the cell he is on with white or black. The ...
TRP's user avatar
  • 41
1 vote
0 answers
56 views

Which good should I split?

One classic fair division allocation problem is to allocate indivisible goods among agents with respect to envy freeness (no agent envies another agent). In my settings, all the goods are divisible (...
Samuel Bismuth's user avatar
0 votes
1 answer
176 views

BFS on a graph and BFS on a tree

I found the following question in my book and I have no clue on what the answer should be: What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate ...
Robert's user avatar
  • 1
0 votes
0 answers
66 views

Envy-Free Allocation is NP-Hard

If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
Doc Stories's user avatar
0 votes
1 answer
34 views

"Succinct circuit representation" on Turing machines?

The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and &...
Loic Stoic's user avatar
1 vote
1 answer
92 views

Another Game Theory Problem

We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
Identicon's user avatar
1 vote
1 answer
54 views

Possible to solve a combinatorial game with integer programming?

I recently had the idea that it would be neat if it were possible to make a SAT solver play combinatorial games. To start, I'm trying a relatively simple case of solving single-stack Misère Nim ...
Exalted Toast's user avatar
1 vote
0 answers
54 views

How to find optimizers with computer in this kind of minimax problem [closed]

I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (...
mathworker21's user avatar
1 vote
0 answers
43 views

Long and short memory in reinforcement learning Connect 4 AI

I'm writing an AI based on reinforcement learning to play Connect 4. That's my second bot and attempt to RNN and AI (first was copy a code of snake RNN AI from youtube) and I'm looking for some ...
Saguro's user avatar
  • 11
1 vote
0 answers
64 views

Are there computational complexity results for generative adversarial networks?

First time posting on here; if this question is too rough I would appreciate if you could point me to a stackexchange forum where this question may be a better fit. Generative adversarial networks (...
infobox's user avatar
  • 11
1 vote
0 answers
36 views

External regret algorithms playing dominated strategies

Edit 3/14 to refer to textbook question: I am trying to understand the concept of external regret better, and am working through the Nisan et al. (eds.) Algorithmic Game Theory book (https://www.cs....
Andreas Haupt's user avatar
2 votes
0 answers
36 views

Partition columns into m groups to maximize absolute value sums

The Task You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
k-0348's user avatar
  • 21
1 vote
0 answers
166 views

What algorithm is best for resource gathering in an RTS game in quickest time?

Though the concept can be for many RTS games but lets use the specific system of 'age of empires'. For simplicity one resource will be considered. Food. So in the game there are villagers who gather ...
Uchiha Madara's user avatar
0 votes
0 answers
113 views

Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
Manny's user avatar
  • 13
4 votes
1 answer
212 views

How to find an algorithm to calculate the best move for this 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 ...
joaoroque's user avatar
1 vote
1 answer
118 views

Complexity of LTL realizability of safety games with Next operator only

It is known that the computational complexity of deciding whether an LTL specification is realizable in a safety game is 2EXP-complete (that is, you receive an LTL formula, where some variables belong ...
Noel Arteche's user avatar
0 votes
0 answers
20 views

Game Theory Schulz Method

Hey I was wondering I did all the 3 neccessary things so Head to Head comparision, Diagraph and the Head to Head Strength Comparision with the help of the Diagraph. In first method there is no ...
dxxd01's user avatar
  • 1
1 vote
1 answer
47 views

Find optimal play by optimizing orders of each player alternatingly

A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
Qurious Cube's user avatar
-1 votes
1 answer
453 views

Finding an Algorithm for the HAPPY-CAT problem

I'm trying to develop an the algorithm for the problem: The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a ...
EpRa's user avatar
  • 1
3 votes
1 answer
3k views

Algorithm for winning solitaire

Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves? Description of ...
Maxim's user avatar
  • 109
1 vote
0 answers
33 views

Reliability of information on large social networks like Wikipedia [closed]

I was going through the playlist of an online course on Social Network Analysis offered by the Indian Institute of Technology (Madras), when I came across the claim that "when a lot of people get ...
Ishan Kashyap Hazarika's user avatar
1 vote
0 answers
242 views

Equally optimal nodes during minimax with alpha-beta pruning

Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
jth's user avatar
  • 111
0 votes
1 answer
117 views

The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
Powerful blaster's user avatar
3 votes
3 answers
553 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 ...
ihadanny's user avatar
  • 369
1 vote
1 answer
131 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] + \...
Cam's user avatar
  • 121
1 vote
1 answer
28 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. ...
Jake's user avatar
  • 3,800
9 votes
1 answer
5k 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 ...
zfj3ub94rf576hc4eegm's user avatar
1 vote
0 answers
319 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 ...
Math-E-Mad-X's user avatar
2 votes
2 answers
111 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 ...
ZeroMaxinumXZ's user avatar
-2 votes
2 answers
79 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 ...
Jamal B.'s user avatar
2 votes
1 answer
35 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 ...
Ernie's user avatar
  • 53
0 votes
1 answer
54 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. ...
asde's user avatar
  • 11
1 vote
0 answers
253 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 ...
Zyx's user avatar
  • 145
3 votes
1 answer
134 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 ...
DonVitoMarco's user avatar
-1 votes
2 answers
999 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....
Sandeep's user avatar
  • 47
7 votes
1 answer
292 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 ...
Dennis Lewis's user avatar
2 votes
0 answers
387 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 ?
math_coder's user avatar
2 votes
1 answer
580 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 ...
user avatar
7 votes
3 answers
509 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......
Raj's user avatar
  • 175
0 votes
0 answers
58 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 ...
m00s3's user avatar
  • 101
0 votes
2 answers
149 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 ...
olinarr's user avatar
  • 394
2 votes
0 answers
103 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? ...
stupsisenior's user avatar
1 vote
1 answer
911 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 ...
ESDAIRIM's user avatar
  • 111
1 vote
1 answer
533 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 ...
namesake22's user avatar
0 votes
2 answers
123 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-...
user180164's user avatar
2 votes
1 answer
183 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 ...
Manoharsinh Rana's user avatar
4 votes
1 answer
82 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 ...
afreelunch's user avatar