Questions tagged [game-theory]
Theory of dynamic processes with several competing actors that try to achieve some goal in a strategic way.
34
questions with no upvoted or accepted answers
17
votes
0answers
522 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 \...
6
votes
1answer
377 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 ...
3
votes
0answers
110 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 ...
3
votes
0answers
101 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 "...
3
votes
0answers
73 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 ...
2
votes
0answers
18 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? ...
2
votes
0answers
48 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 ...
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
0answers
35 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 ...
2
votes
0answers
27 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 ...
2
votes
0answers
2k 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 ...
2
votes
0answers
1k 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 ...
1
vote
0answers
31 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\...
1
vote
0answers
30 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
42 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.
1
vote
0answers
24 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
vote
0answers
128 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 ...
1
vote
0answers
55 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 ...
1
vote
0answers
33 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. ...
1
vote
0answers
32 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?
1
vote
0answers
39 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 ...
1
vote
0answers
60 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 ...
1
vote
0answers
76 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 ...
1
vote
0answers
476 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 ...
0
votes
0answers
17 views
How to determine the complexity of a mixed strategy NASH equilibrium problem
How to determine a complete-information mixed strategy NASH equilibrium problem with finite numbers of players and strategies? That is, there exists a payoff matrix which shows all the relation among ...
0
votes
1answer
55 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 ...
0
votes
0answers
255 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
0answers
410 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
56 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 ...
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 ...
0
votes
0answers
214 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
0answers
77 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 ...
0
votes
0answers
62 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 ...
-1
votes
1answer
54 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 ...
