# Questions tagged [game-theory]

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

144 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 11
1 vote
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, ...
• 111
1 vote
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 ...
• 11
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 ...
• 41
1 vote
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 (...
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 ...
66 views

• 154
1 vote
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 ...
• 11
1 vote
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 (...
• 11
1 vote
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....
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 ...
• 21
1 vote
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 ...
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 ...
• 13
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 ...
1 vote
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 ...
• 239
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 ...
1 vote
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 ...
• 113
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 ...
• 1
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 ...
• 109
1 vote
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 ...
1 vote
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 (...
• 111
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 ...
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 ...
• 369
1 vote
131 views

• 101
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 ...
• 394
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? ...
1 vote
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 ...
• 111
1 vote
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 ...
• 211
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-...