Questions tagged [game-theory]

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

41 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20
votes
0answers
599 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
541 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
1answer
94 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 ...
3
votes
0answers
121 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
122 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
78 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
1answer
384 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 ...
2
votes
0answers
64 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
52 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
45 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
43 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
29 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
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 ...
2
votes
0answers
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 ...
1
vote
0answers
30 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 (...
1
vote
0answers
58 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 ...
1
vote
0answers
44 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
63 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
36 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
0answers
30 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
171 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
60 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
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. ...
1
vote
0answers
35 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
41 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
62 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
81 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
489 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
15 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 ...
0
votes
1answer
63 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 ...
0
votes
2answers
57 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 ...
0
votes
0answers
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 ...
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
0answers
758 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
66 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
301 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
86 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
66 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
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 ...