Questions tagged [game-theory]
Theory of dynamic processes with several competing actors that try to achieve some goal in a strategic way.
44
questions with no upvoted or accepted answers
20
votes
0
answers
628
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 \...
- 2,279
6
votes
1
answer
549
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 ...
- 161
3
votes
1
answer
104
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 ...
- 31
3
votes
0
answers
127
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 ...
- 1,304
3
votes
0
answers
127
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 "...
- 216
3
votes
0
answers
79
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 ...
- 131
2
votes
0
answers
33
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
2
votes
1
answer
445
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 ...
user102382
2
votes
0
answers
66
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? ...
- 21
2
votes
0
answers
54
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 ...
- 121
2
votes
0
answers
46
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 ...
- 21
2
votes
0
answers
45
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 ...
- 21
2
votes
0
answers
30
views
Terminology for non-game theoretic techniques
When solving an adversarial problem there are two basic approaches: one that takes into account the thinking process of both sides, and as opposed to that the non-psychological computations.
For ...
- 658
2
votes
0
answers
3k
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 ...
- 253
2
votes
0
answers
2k
views
Nash equilibria in 3-player game with symmetry
Consider 3-player game.
Players $x,y,z$, each player has two strategies. $x$: $x_1$ and $x_2$, $y$: $y_1$ and $y_2$, $z:z_1$ and $z_2$.
The outcome of the game are represented by the labels of the ...
- 21
1
vote
0
answers
28
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....
1
vote
0
answers
41
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 ...
1
vote
0
answers
62
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 (...
- 11
1
vote
0
answers
91
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 ...
- 73
1
vote
0
answers
81
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 ...
- 145
1
vote
0
answers
73
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\...
- 111
1
vote
0
answers
37
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 ...
- 11
1
vote
0
answers
32
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 ...
- 1,239
1
vote
0
answers
192
views
Algorithm for calculating the Grundy value of a green-hackenbush graph
I need an algorithm to convert a green hackenbush graph to it's equivalent tree so that I can find the Grundy value of the Graph using colon principle.
I thought of finding the bridges in the given ...
- 151
1
vote
0
answers
61
views
An impartial game of snake
There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game.
The game proceeds as follows -
Both ...
- 151
1
vote
0
answers
37
views
Is a rational game playing agent still rational when not staying off terminal states when it looses in all child states?
I am working on a programming assignment to implement a Minimax algorithm and heuristic for the game Lines of Action.
The rules are pretty simple, each player alternates turns moving a single piece. ...
- 343
1
vote
0
answers
36
views
Parity games and acceptance conditions of automata on infinite words
I would like to understand the ideas behind parity games and their winning conditions. Where do they come from?
- 61
1
vote
0
answers
42
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 ...
- 11
1
vote
0
answers
63
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 ...
- 111
1
vote
0
answers
85
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 ...
- 5,674
1
vote
0
answers
492
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 ...
- 253
0
votes
0
answers
58
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
0
votes
0
answers
17
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
0
votes
1
answer
163
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
0
votes
2
answers
65
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 ...
- 1
0
votes
0
answers
57
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 ...
- 1
0
votes
0
answers
286
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
0
answers
791
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 ...
- 319
0
votes
0
answers
71
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 ...
- 57
0
votes
0
answers
21
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 ...
- 241
0
votes
0
answers
345
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 ...
0
votes
0
answers
89
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 ...
- 1,085
0
votes
0
answers
78
views
Nash Equilibrium in Tree of Bounded Degree
I have an exercise which I can't solve.
Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
- 3,149
-1
votes
1
answer
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 ...
