# Questions tagged [algorithmic-game-theory]

Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. (Def: http://en.m.wikipedia.org/wiki/Algorithmic_game_theory)

257 questions
Filter by
Sorted by
Tagged with
35 views

### correct terminology for "dead-end game"

Apologies if this question has an obvious answer! My research is in pure math, but I've started to think about some applied problems that are similar to this game. The player arranges numbers 1-19 ...
19 views

### Why Nash or correlated equilibrium require complete information?

In games of complete information, there are common solution concepts such as Nash equilibrium and correlated equilibrium. The idea is that each player is playing a best response. My question is - Why ...
73 views

### Calculate card percentage return [closed]

No sorry this isn’t how things work around here
28 views

### What are the chances of drawing different mana producing sources in magic the gathering on your first turn. (assuming your the second player)

There are a number of assumptions in the given scenario - The first assumption is that the player is using a $60$ card deck. The deck contains a ratio of $24:60$ lands so $24$ lands total. They are ...
1 vote
52 views

### How many different ways can you solve the cracker barrel peg game? And is there an optimal starting arrangement of pegs?

The cracker barrel peg game is a strategical table game that is mockingly cocky with its confidence that the player won't win. Let me explain... Here is the game set up: The game itself is a ...
28 views

### Assigning a value based on win probability

I have a roster of entities which may compete in a competition that involves randomness . Generally if two entities directly compete and would have a win-loss-draw of about 50% (determined using monte-...
1 vote
46 views

### Two players with two piles of weights remove weights from each pile in their turn

Player one has weights 2,4,6,8,…,2022 in a pile. Player two has weights 1,3,5,7,…,2021. Player 1 starts the game and remove weights from her pile, one by one (in any order she likes),until her pile ...
35 views

### Prove existence of Correlated Equilibrium

How can I prove that every finite game has at least one Correlated Equilibrium? I know there is the idea that it has already been shown that every finite game has a Nash equilibrium and then from ...
93 views

### How to find winning Strategy for 4 celled animals of Harary's generalized tic tac toe

A polyomino is a structure made of unit squares joined along their sides. A single square is called a monomino. Two make a domino. Three join in two different ways to make two trominoes. Let's call ...
1 vote
273 views

### Calculating the correlated equilibrium of a $3\times 3$ normal form game using MatLab

Apologies if there is anything wrong with my formatting, this is my first post. I'm trying to use the linprog function in MatLab to calculate the correlated equilibrium in a normal form game ...
36 views

### Complexity of a reaching-a-node 2 player graph game

The game: There is an undirected simple graph with some special, winning nodes, and 2 players, who take turns. Player one (Seeker) moves on the graph (sits on a node, and moves along an edge), and ...
47 views

### Counting game strategy

Assume two players play against each other, and assume the initial number the game start with is 1. Each turn a player can add 1 or add 2 or multiply by 2. Goal: The winner is the player who reaches ...
1 vote
36 views

### Weighted Nim with Stacks and each player picks from opposite sides

There n stacks of coins. Each stack contains $k_i$ coins and the coins in a particular stack have distinct values. In each turn, you get to pick one coin from the top of any stack, and your opponent ...
51 views

### Intuition to move-optimality in Sokoban

The puzzle game of Sokoban has been fascinating to me since I was a child. It is played on a rectangular grid. Each square may be empty ( ) or contain a wall (...
66 views

### Most profitable multi unit open auction design

Imagine a seller have 300 apples to sell Bidders can offer their budget to buy apples. Bidders can buy multiple apples. Apple price must be same for everyone. Bidders can put bids like this: Karen: ...
1 vote
48 views

### Strategy for combinatorics game?

Let $m, n > 2$ be fixed integers. $A$ thinks of $n$ not necessarily distinct integers, $x_1, x_2, ..., x_n$, such that $1 \le x_i \le m$ for all $1 \le i \le n$. For each query, $B$ chooses and ...
58 views

### Analysis into noughts and crosses strategy

I was reading this paper that analyses some strategies of the game dots and boxes. To understand this concept I tried to apply some of the techniques used in the paper to other games such as noughts ...
201 views

### Stone game with two players, where one player can't choose from the pile which was choosen in previous turn.

Alice is playing a game with his friend, Bob. There are n piles of stones, the $i-th$ pile initially has $a_i$ stones. Alice and Bob will take alternating turns, with Alice going first. In each turn, ...
36 views

### Best strategy for idle games in a time range

I was wondering about IDLE games, and was trying to develop the best strategy for a specific time range. What is an IDLE game? There are several different building tiers. You begin with one free ...
1 vote
101 views

### Proof explaination: Every VCG mechanism is an incentive compatible mechanism

The following is taken from these lecture notes. Definition: A Groves mechanism is a mechanism $(f, p_1, \cdots, p_n)$ in a quasilinear environment in which: $f(b) \in argmax_{s \in S} \sum_i b_i(s)$,...
33 views

### Team Balancing / Score Normalisation for gamification

This is the first time I post in Mathematics as I'm normally in programing. But for this question, I think I can get better help here. I'm trying to create a gamification system where different teams ...
110 views

### Operate an aviation network without condition: Each city has a direct flight to 3 other cities; There is always a flight visiting all cities once each

Problem. A country has $10$ cities. Operate an aviation network within $2$ following conditions: a. Each city has a direct flight to exactly $3$ other cities. b. From a beginning city, there is always ...
313 views

1 vote
122 views

### How many proposals does it take for the boy-oriented Gale-Shapley to terminate when all boys have identical preferences?

In this Stable Marriage problem all boys have identical preferences. I was wondering how many proposals would it take to terminate this boy-orientated GS. (By boy-orientated I mean the boys are ...
27 views

### Need an analysis of the "generalized" Prisoners dilemma

Here is a scenario: Suppose that two persons (A and B) have an experiment that must be completed in either city X or city Y. If city X is chosen, A and B will pay \$2 and \$5 respectively for travel ...
1 vote
86 views

### What is the simplest and most intuitive way of computing the mixed strategy of a matrix game?

I have learned how to compute the mixed Nash equilibrium (NE) of a game many times, however, whenever I am faced with a matrix, I just cannot recall the exact way/logic of going about computing it. I ...
77 views

### Shapley Value for Voters in Electoral College

Consider (a simplified version of) the USA electoral college. Each state has millions of voters and tens of electors. The candidate with the most electors wins and each state allocates electors ...
362 views

### Is it true that a mixed Nash equilibrium cannot be strict?

A Nash equilibrium $y = (y_i, y_{-i}) \in \Delta$ is said to be strict if for all players $i$, $$u(y_i; y_{-i}) \geq u(x_i; y_{-i}), \forall x_i, y_i \neq x_i$$ Is it true that no mixed equilibrium ...
24 views

### Two players game, problem

I have this type of problem: two boys have to divide 10 playstation games. The strategy is that first one choose a game, then the second another and so on, by having a common goal to be both "the ...
22 views

### Part of game theory to check

I want to model this problem: I have two captains that have to choose between other people to built two different teams, obviously both prefer to choose firstly their "friends". Which part ...
32 views

### Possible error in textbook about weakly dominated strategy of a simple game

This is from Jurgen Weibull's textbook on game theory, page 10, where an example is introduced. The author claims that the player's third strategy is not weakly dominated by other two pure strategies....
1 vote
35 views

### Nash single equilibrium with potential method

I am learning about selfish routing in game theory from Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory. Cambridge University Press (2007) TL;DR I am struggling to solve exercise 18.4 ...
91 views

### About general strategies for game-problems: Adding 31 from numbers on a regular calculator

I am new to game related problems so, in particular, I'm starting with symmetry game problems. In this case, I was trying to solve the following problem: Two players, A and B, use a special ...
1 vote
31 views

### How can I find the optimal strategy

Imagine the following game A and B play against each other. Player A chooses a number X between 1 and N. And player B should guess the number X asking the question "Is it true that X >= K"...
42 views

### Dyadic product of two Boolean matrices

I'm currently working in game theory, and have the following equilibrium $\begin{bmatrix}1&0&1\end{bmatrix}$. I'd like to show the trivial equilibrium which results from this is given by the ...
1 vote
74 views

### Does there exist a matrix game with more than three players?

Im reading a textbook on game theory and the last example in the book is a three player game, where the first and second players choose left/right and the third player chooses up/down. Similar to the ...
1 vote
19 views

### Find converging subsequences in a metric space

Let $(X,d)$ be a metric space and $\{x_n\}_n$ a sequence. I'm looking for an algorithm that takes $x\in X$ as an input and gives a $y\in X$ as an output, with this property: if $\{x_n\}_n$ admits some ...
224 views

### Why can't you lose a chess game in which you can make $2$ legal moves at once?

So here is the Problem :- Consider a normal chess game in an $8*8$ chessboard such that every player makes $2$ legal moves at once alternatively . Now imagine that you was asked to play with Magnus ...
1 vote
76 views

### Doubts on a game that two players take turns to take an element and xor it to their sums.

This is originally a question from https://codeforces.com/contest/1383/problem/B, but this is more of a math problem than an algorithmic one, so I decided to post here. There is a game where two ...
1 vote
62 views

### Coin Tossing Game Optimal Stragegy [closed]

A and B are playing coin toss game with a fair coin as a team, both of them have to be correct in a game to be able to gain one point, no communications will be allowed after the game starts. Assuming ...
1 vote
343 views

### Good examples of zero-sum perfect information game?

I am trying to come up with some good examples of zero-sum perfect information games. What I have on the list are: Tic-Tac-Toe Connect $4$ Chess Any thing more? One more question, for Connect4, ...
1 vote
23 views

1 vote
1k views

### Game theory:- value of a game?

I haven't found any suitable explanation or even definition for this concept. What is the value of game in game theory? Can anybody explain me with an example.
1 vote