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)

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
user avatar
  • 121
0 votes
0 answers
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 ...
user avatar
-4 votes
1 answer
73 views

Calculate card percentage return [closed]

No sorry this isn’t how things work around here
user avatar
  • 13
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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-...
user avatar
  • 101
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 29
3 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
2 votes
2 answers
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 (...
user avatar
  • 20.3k
0 votes
2 answers
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: ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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, ...
user avatar
  • 816
0 votes
0 answers
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 ...
user avatar
  • 113
1 vote
1 answer
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)$,...
user avatar
  • 1,902
0 votes
0 answers
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 ...
user avatar
  • 101
2 votes
1 answer
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 ...
user avatar
2 votes
3 answers
313 views

Is a zero-sum game always a two player game?

Can a zero-sum game involve more than 2 players? It does not seem to make sense to me, given that most books define a zero sum game as a game whereby the payoff matrices satisfy $$A + B = 0$$ Or $B = -...
user avatar
  • 5,156
0 votes
1 answer
190 views

Prove or disprove that there exists no more specific match-ups involving these 4 third-placed teams for the round of 16 other than

UEFA EURO 2020 has been just started, still with the format of 24 teams. The top 2 in each groups will proceed to the round of 16 along with the best of 4/6 third-placed finishers. Prove or disprove ...
user avatar
0 votes
0 answers
23 views

Individually Rational Definition

I noticed that in the book Algorithmic-game-theory(Noam Nisan), the definition of Individually Rational is "players always get nonnegative utility" in a mechanism. However, my instructor ...
user avatar
  • 402
0 votes
1 answer
59 views

Nash Equilibrium in two person game reduction

My game theory professor mentioned in class that finding a nash equilibrium in any two person game can be reduced to find a nash equilibrium in a symmetric two person game by constructing a symmetric ...
user avatar
  • 402
2 votes
0 answers
40 views

Equilibrium for Implicit Best Response Functions

I am dealing with a problem in economics, specifically game theory, where $n$ agents have a best response $x_i$ given by an implicit function, as described below. We have $ i \in \{ 1, 2, ..., n \}$, $...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
2 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 966
3 votes
1 answer
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 ...
user avatar
  • 228
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
  • 11
0 votes
1 answer
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....
user avatar
1 vote
0 answers
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 ...
user avatar
  • 79
2 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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"...
user avatar
  • 21
0 votes
1 answer
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 ...
user avatar
  • 161
1 vote
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 101
6 votes
4 answers
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 ...
user avatar
  • 4,061
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
2 answers
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, ...
user avatar
  • 399
1 vote
0 answers
23 views

No truthful, IR and deterministic online auction can obtain $(2-\epsilon)$-approximation for efficiency theorem proof is unclear to me

The theorem is from Algorithmic Game Theory Textbook by Nisan et al. available here on page 423 https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf To elaborate on the notation, $\...
user avatar
  • 305
0 votes
1 answer
35 views

Best choice in a two player games without dominant strategy

Let's assume A and B play a game in which A wants a high outcome while B wants a low outcome. A can choose top or bottom and B can choose left or right. Depending on their choices the outcome is $$\...
user avatar
  • 253
1 vote
2 answers
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.
user avatar
1 vote
1 answer
77 views

software graph theory for finding graph with girth 3

Is there any software for finding all graphs (edges and nodes) with girth(the girth of a graph is the length of a shortest cycle contained in the graph) three and diameter at least three? The ...
user avatar
  • 55
1 vote
0 answers
263 views

Confusion regarding ISD and IWD

Statement-1: If a game is ISD-solvable(Iterated strict dominance), then the security level of every player is the same as his utility in the ISD solution. Statement-2:IWD(Iterated weak dominance) is ...
user avatar

1
2 3 4 5 6