# Questions tagged [game-theory]

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

106 questions
Filter by
Sorted by
Tagged with
161 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 ...
18 views

### Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
244 views

### Why does Min-Max algorithm delays a good move indefinitely?

Consider a simple chess example: Q is white Queen. K, R is black King and black Rook respectively. A B 1 . Q 2 . . 3 K . 4 . . 5 . . 6 R . 7 . . 8 . R 1,2......
52 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 ...
139 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 ...
135 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 – ...
47 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.
392 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 ...
65 views

### Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions. More precisely, let us define the strategy of each player as a function mapping from every valuation that they ...
66 views

### Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?

The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and ...
22 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? ...
18 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 ...
297 views

### Metagame Paradox: what is wrong with this explanation?

Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post ...
13k views

### Nim game tree + minimax

Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player ...
66 views

### Is there any model of Game of Life compatible with hypercomputation?

I found a question in Mathematics Stack Exchange which asks a very similar question (https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
75 views

### Two Minimax AIs playing against each other

I am trying to have my Minimax AI chess players play against each other. I was a bit confused about an implementation detail. Let's call black my first minimax AI ...
66 views

### Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
38 views

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\... 2answers 135 views ### Must the champion of an entire tournament beat the champion of a possible tournament among other players? I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given ... 0answers 49 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 ... 4answers 577 views ### Why isn't chess an impartial game? In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions: (1) The game is finite; i.e. there is a ... 0answers 32 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 ... 2answers 86 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 ... 2answers 37 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 ... 1answer 205 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 ... 3answers 264 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 ... 1answer 268 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 ... 1answer 86 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'... 3answers 180 views ### Fair division of two-dimensional cake I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division). In contrast to the well-studied cake-division problem, land-division is two-... 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 ... 2answers 6k views ### Guessing the smallest unique positive integer Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the ... 0answers 262 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? 1answer 276 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 ... 1answer 1k 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 ... 1answer 99 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 ... 1answer 42 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). ... 0answers 479 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 ... 0answers 59 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 ... 1answer 60 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 ... 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 ... 2answers 288 views ### Adversarial Monte Carlo Tree Search Asymmetry Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth, growing promising subtrees more than non-promising ones. But in a 2-player adversarial game, when a win at one node is a ... 1answer 176 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 ... 1answer 59 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 ... 0answers 37 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 ... 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 ... 1answer 314 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? 1answer 73 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 ... 0answers 530 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 \...
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 ...