Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [game-theory]

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

1
vote
0answers
25 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
27 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.
0
votes
0answers
10 views

game theory: application to simulataneous hidden and numerous auctions

Context: 5 people have each 100$ (that are bound to be bet). The one with the max points wins the game. There are 3 objects; one is worth 2 points, the other 3 points and the last 4 points. The ...
2
votes
2answers
74 views

How to express the existence of winning strategy of the starter of a game in temporal logic?

Consider a two-player game. A winning strategy of a player is a strategy following which the player can always beat his opponent, no matter how his opponent responds. A game can be unfolded to a ...
4
votes
2answers
31 views

Determining the existence of a forced win vs determining the best outcome

A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position. Is this problem equivalent under polynomial-time reduction to ...
4
votes
3answers
138 views

How does “solving” a game like connect four or tic-tac-toe work?

To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all ...
4
votes
1answer
75 views

Optimal strategy in repeated cake-cutting

Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob'...
2
votes
0answers
40 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
1answer
87 views

Variant of nim game with particular rules

Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the ...
0
votes
0answers
151 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
1answer
147 views

Utilization of static evaluation functions in chess

Disclaimer: I'm very new to computer science & game programming I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just ...
2
votes
1answer
354 views

Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one ...
3
votes
1answer
80 views

Analysis of the Banana Game

My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs. Game Description The banana game is played with a ...
0
votes
1answer
37 views

Probability that a leaf with 1 will be selected in game tree evaluation

I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar). ...
0
votes
0answers
247 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
54 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 ...
-1
votes
1answer
36 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 ...
1
vote
0answers
23 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 ...
0
votes
1answer
133 views

Game of Nim (Find winning states in large range)

If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively I know that the solution of (winning) iff x^2x^3x != 0 but if x can be in the range from 1 to 2^61 so How many ...
1
vote
1answer
49 views

Develop a winning strategy for a game

Okay so I've been going crazy about this problem I was given. It is as follows: Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed ...
2
votes
0answers
26 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 ...
5
votes
1answer
147 views

Analysis of komi values for increasing Go board sizes and agents strength

Komi is the additional number of points given to the non-starting player in the game of Go. For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it ...
0
votes
0answers
18 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 ...
5
votes
1answer
294 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 ...
0
votes
1answer
65 views

Algorithm to find the optimal strategy to feed your cousin (Long question)

I have a programming problem, instead of describing the whole domain it's easier for me to create an analogy. The numbers I use in this example are completely arbitrary. Your cousin is coming over ...
3
votes
1answer
108 views

Understanding Incentive Compatibility of pooled Bitcoin Mining paper

I'm trying to understand the paper Incentive Compatibility of Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data Security – ...
1
vote
1answer
263 views

How are the 1s and 0s derived by the minimax algorithm for the game called “nim”?

I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim: There is a statement in the book that explains the numbers but it's still not clear to me, In ...
2
votes
0answers
111 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 ...
2
votes
0answers
53 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 ...
3
votes
1answer
130 views

Solving the 10 players duel game

Players #1 to #10 with hit probabilities $0.1,0.2,...,0.9,1$ (which are common knowledge) take part in a shooting game. Rules of the game: Players from #1 to #10 take turns to fire at each other. ...
1
vote
0answers
27 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
1answer
628 views

Representation of 8-Puzzle for (A*) Search Algorithm in C

I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C. https://en....
3
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 ...
0
votes
1answer
354 views

A nim game variant with pass move

This variant is almost similar to the normal nim game which states - Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the ...
2
votes
1answer
128 views

Nim Games: Is it possible to reduce following using Grundy Number?

Following is the problem from a finished programming contest. Two players try to create a number, DesiredTotal, by adding numbers from 1 to N. The first to cross the number is the winner. The ...
2
votes
1answer
129 views

Complexity of parity game solving compared to PLS, PPA, and PPAD

Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or ...
1
vote
0answers
30 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?
3
votes
1answer
436 views

Evaluation functions of Minimax algorithm

Let's say we have the following relationship between $f_1$ and $f_2$: $$f_2(s) = \sqrt{1 + f_1(s)}$$ And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to ...
4
votes
2answers
1k views

Number of winning combination in Nim

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are ...
0
votes
1answer
75 views

Computing losing positions in modified Wythoff's game efficiently

Wythoff's game is as follows: there are two players $A$ and $B$ ( $A$ being the first player ) and there are $2$ piles of stones. When his turn a player can remove one or more stones from anyone pile ...
2
votes
1answer
269 views

Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
4
votes
1answer
52 views

In Minimax, how should we handle draws?

A player playing the Minimax strategy should choose moves which minimise their maximum loss. What should happen when draws can happen? Should we class the draw as a win because we aren't losing? Or ...
3
votes
1answer
615 views

Winning strategy of Nim game when picking from multiple piles is allowed

I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in ...
3
votes
0answers
97 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
vote
1answer
120 views

Metaheuristic for NP-complete problem without exact algorithms other than brute-force

Computing Pure Nash Equilibria (PNE) is a Game Theory related problem. Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.). I want to design a metaheuristic ...
0
votes
0answers
167 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 ...
3
votes
1answer
513 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
3
votes
0answers
93 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
1answer
270 views

Induction proof of alpha-beta search

Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?
1
vote
0answers
38 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 ...