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
599 views

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 ...
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 ...
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 ...
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 ...
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. ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...