# 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
Filter by
Sorted by
Tagged with
628 views

1 vote
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 ...
1 vote
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 vote
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 ...
1 vote
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 ...
1 vote
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
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?
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
89 views

### Is $AM = AM$?

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