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
0 votes
1 answer
25 views

Confused about symmetric game theory utility

I imagine this is a stupid question and I'm missing something obvious, but I can't really make heads or tails of this and seem to be unable to find good resources online, so here goes. I'm working ...
Musaeus's user avatar
1 vote
0 answers
17 views

Greedy and Randomized-Greedy Algorithms

I am studying Algorithmic Game Theory and am totally new to the topic, but wanted to clarify some items (apologies for the length beforehand). My book of reference is link. On the topic of External ...
Kai's user avatar
  • 43
0 votes
1 answer
51 views

Impossible Rubik's cube position (2 corners swapped!) [closed]

Left side, white up, Red, green, white corner swapped with Red, blue, white corner Right side, white up, Red, blue, white corner swapped with Red, green, white corner Right, Down, Back view of cube. ...
A.V. Anderson's user avatar
2 votes
1 answer
59 views

Find minimum sum of distance to all points in a vector, using an accumulator?

This is question will be about the theorem behind an efficient algorithm, which has been used in LeetCode problem 3086. Let me start by exposing the problem in a friendly way: You are a bus driver who ...
Murilo Perrone's user avatar
0 votes
0 answers
10 views

multiple minimax solutions in zero-sum games

recently learned the minimax theorem for zero-sum games, and had a clarification on it. The minimax solution gives the value for the game V, and is also a Nash Equilibria. So, does that mean that all ...
APerson's user avatar
  • 85
3 votes
1 answer
115 views

Find two coins of weight a, among n coins, where n-2 coins are coins of weight b

Task: Among the n coins there are exactly 2 coins of weight a, and exactly $n − 2$ coins of weight $b, a < b$. It is allowed to compare the weight of any two coins in one turn (there are three ...
Peter Griffin's user avatar
0 votes
0 answers
34 views

Looking for forced cycles (or proof of nonexistence thereof) in this game

Consider a game played on a board with $2$ rows and $n$ columns (with $n$ being arbitrarily large but finite). Each player controls a single color of pieces, and they take turns moving them according ...
Michał Zapała's user avatar
0 votes
0 answers
26 views

Dominant strategy sets?

In a normal form game $(N, A_i, u_i)$, consider a proper set $B_i \subseteq A_i$. This set satisfies the condition that for every action $a_i \in A_i$, there exists an action $a_i' \in B_i$ such that $...
bruno mazorra's user avatar
3 votes
0 answers
78 views

A strategy for number-guessing game

Let player A and player B are playing number-guessing game, which is: Player A draws one natural number $X$ in $1,2,\cdots,N$ at random. Player B guesses a number $Y$ in $1,2,\cdots, N$. Player A ...
mathhello's user avatar
  • 918
0 votes
0 answers
43 views

How to move marbles between tubes with the least amount of work

Consider the following problem which I give a "physical" marbles/tubes description of -- the formal description is easy to obtain from this "physical" description. Moving marbles ...
user918212's user avatar
0 votes
0 answers
32 views

Fair choice allocation using Edmonds Karp, adding group choices

I have an algorithm that uses Edmonds-Karp algorithm to distribute users into groups in a fair manner given a rating for their choice of groups. Currently a given graph for two users ($u1$, $u2$) and ...
Lucy Kalwa's user avatar
4 votes
0 answers
133 views

Books on chess mathematics [closed]

My question is whether there are some books on chess mathematics with theorems and their proofs concerning winning strategies for classes of initial positions. Despite there being a lot of books on ...
Bertrand Haskell's user avatar
0 votes
1 answer
72 views

Combinatorics and game of bingo

2000 dots on placed on a circle and may be colored either black or grey. If we see 2 black dots next to each other then we say bingo. if we see 2 grey dots are two apart (i.e. one black dot or one ...
Mathronza's user avatar
  • 164
1 vote
1 answer
50 views

On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty.

On a table there are $N$ stacks (numbered 1 to $N$). Stack $i$ contains $i$ tokens ($1≤i≤N$). During a move, a set of stacks can be chosen, and the same number of chips can be drawn from each stack ...
John's user avatar
  • 11
3 votes
1 answer
97 views

How do I find Nash Equilibria if I have Payoff functions instead of Payoff Matrix in MATLAB?

I am trying to implement the noncooperative game theory in my problem, where I framed two objective functions $J_1$ and $J_2$ for maximizing the power. I plotted the $ P_1$ and $P_2$ in MATLAB as ...
aman2909's user avatar
-1 votes
1 answer
84 views

How does this 2D6 probability math make sense? [closed]

I have a question about understanding the math to a previous question I had posed (answered successfully). Link at the bottom. The question is how does it make sense that rolling a 2D6 Die consisting ...
Keith Plunske's user avatar
2 votes
1 answer
112 views

Optimal strategy in number guessing game?

Consider the following game. Two players each create a passcode using the digits 0-9 four times with repetition allowed. The two take turns asking a yes or no question about the opponent's passcode. ...
jv3984's user avatar
  • 21
0 votes
0 answers
9 views

Intransitivity of Bounded Dominance For Full-Knowledge Two-Player Alternating Finite Deterministic Games?

Background A full-knowledge, two-player, alternating, finite, deterministic game is modeled by a tree T with labeled leaves and no infinite branches. The game starts at the root of the tree (level 0). ...
James's user avatar
  • 101
0 votes
0 answers
42 views

Prove: Priority Mechanism for Pairwise Kidney Exchange is DSIC (Dominant Strategy Incentive Compatible).

Priority Algorithm I need to prove the theorem below in detail for the priority algorithm, which is an algorithm for the third step of the initial pairwise kidney exchange algorithm. I just need an ...
Defne's user avatar
  • 1
0 votes
0 answers
78 views

Minimax algorithm with very large number of nodes and low depth

I have a minimax tree as follows: The number of branches can get extremely large (C(k,n)*C(n,j) to be specific), even though the depth is constant and very low. Is there any way to tackle this ...
madetolast's user avatar
0 votes
1 answer
47 views

Minesweeper sparsity and information processing

I've noticed while playing Minesweeper that when I have too few bombs, I get very easy to play games. In other words, I get games that can be solved with very simple algorithms. When I play games with ...
Joemoor94's user avatar
1 vote
1 answer
61 views

As $w$ tends to infinity what value does the game converge to?

I am not sure whether I have attempted this question right So we have a matrix $$\begin{matrix} 1 & 4 \\ 5 & w\\ \end{matrix} $$ What value does the game converge to as w goes to $-{\infty}$ ...
AKR's user avatar
  • 11
2 votes
1 answer
168 views

Why restricted removal Nim games with 1 pile has pattern (cycle in states)?

I working on solution of NIM-like game, where players take from one piece from 1 to k and players can't repeat previous turn (only the opponent's previous move). Total n stones in beginning. Winner is ...
student's user avatar
  • 21
2 votes
0 answers
29 views

Stationary Flock Logic

I'm trying to simulate a tabletop skirmish game and thus creating units that "stick together" meaning they move like a swarm and occupy the smallest space possible when idle (they have base ...
Carlo Moretti's user avatar
2 votes
0 answers
73 views

Find if a XOR game collapses to a certain state regardless of the input [duplicate]

A state is a binary sequence made up of 4 bits. Initially, there's a random and unknown state. You can choose to XOR the state with any other state. Then, the state is randomly permuted in a circular ...
No One's user avatar
  • 61
1 vote
1 answer
52 views

Maximize sum of all scores in tournament game

There are $2^{n}$ teams. There is only one person in each team at first. Every teams' score is $0$ at first. They play a tournament game. If team $A$ and team $B$ fights, team that has more team ...
tneserp's user avatar
  • 23
0 votes
0 answers
25 views

Combinations: Matching players in a tournament based on their preferred opponent.

I am working on an algorithm but I don’t know what I don’t know to start research. Let’s say I have 20 players in a tournament. Every round, each player will challenge another player to a match. ...
Jarett Duker's user avatar
1 vote
1 answer
155 views

Can a game of chess go on forever?

Is there non-terminating game of chess? I ran into this problem while designing a machine learning model to estimate the probability that a given chess player wins. If we ignore the 50-move-rule and ...
Dylan Rollins's user avatar
3 votes
3 answers
2k views

20-sided dice 100 rounds game

In a game there is a 20-sided die. At the start of the game it is on the table and the 1 face is facing upright. In each of the 100 rounds you have 2 options: you can either roll the dice or you can ...
SilverLight's user avatar
5 votes
2 answers
255 views

Boxes and dice game

You have $9$ boxes numbered $1$ through $9$ and then you have two $6$-sided dice. Each turn you roll the two dice and deduct the sum of the dice from the boxes by removing the number itself or any ...
Computers's user avatar
  • 313
5 votes
1 answer
243 views

Paint a cube by rolling it (Puzzle Algorithm)

I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is: You have a grid of 16 squares, six of which are blue; on one square rests a cube. ...
Zingerella's user avatar
0 votes
1 answer
92 views

Propability of an event when this event happens the chance decreases but when it doesn't happen chance increases.

A bit of story I've returned to Black Desert after a long time and now, as I've learned some math in my free time so... I'm wondering about some stuff from math point of view. Like how many Items and ...
SL07's user avatar
  • 13
3 votes
1 answer
237 views

Algorithms for computing pure strategy Nash equilibria

I'm looking through many sources, such as this one that mention algorithms, and time complexity of finding mixed strategy Nash equilibria. But is there any algorithm for finding pure strategy Nash ...
wavosa's user avatar
  • 167
0 votes
1 answer
319 views

Nash equilibria problem [closed]

I have a problem to solve the next exercise. Two players call a number from 1 to 100. The winnings are distributed as follows: players always receive no more than 100 rubles in total, the most greedy ...
Anton S's user avatar
  • 19
1 vote
1 answer
54 views

Utility function in graphical game theory

I'm reading a bit about Graphical Game Theory, but do not really understand the utility function the model uses. I'm going to consider a game like matching pennies, but with 3 players: Alice, Bob, and ...
Loic Stoic's user avatar
1 vote
1 answer
36 views

A formula for speed in a game about hiking. The variables include weather, weight of equipment, quality-score of equipment, etc [closed]

excited to post here for the first time... I am creating a game about hiking a (never ending) mountain. The game isn't a "runner." Instead it is strategic, where the player chooses their ...
Jack Burger's user avatar
1 vote
1 answer
150 views

Any tips or idea how to play this combinatorial game?

There is this puzzle called Chomp. You can play and read about it here if you don't know it: https://www.math.ucla.edu/~tom/Games/chomp.html It is well-known that Chomp has a winning strategy for the ...
MR_BD's user avatar
  • 5,942
1 vote
1 answer
97 views

Nash equilibrium in insurance pricing

The insurance market is considered to be a competitive market, so in order to study competition to determine a competitive premium, game theory seems to be a useful tool for studying those situations. ...
mus's user avatar
  • 11
2 votes
0 answers
62 views

Estimating NE for continuous, zero-sum games.

I am interested in estimating Nash Equilibria to symmetric, continuous two-player games of the following form. Let : $x_1$ - Player A's action $x_2$ - Player B's action where $x_1$, $x_2$ $\in [0,1]$ (...
Lostsomewhere's user avatar
0 votes
1 answer
95 views

Deducing hidden die [closed]

A dice deduction game uses a set of $N$ $(N-1)$-sided fair dice. For the $n$-th die in the set, if $n<N$, the face that shows $n$ pips is replaced with a blank. For $n=N$, all faces stays as it is. ...
mudiwii's user avatar
1 vote
0 answers
30 views

Hungarian algorithm for multiple items auction with unit demand; How to get market clearing prices?

The well known "Hungarian Algorithm" is capable of finding a matching in a weighted bipartite graph with minimal (respectively maximal) weight, and therefore can be used to find an optimal ...
Marten's user avatar
  • 11
2 votes
0 answers
44 views

Position compensation after rotation

I am working in a game. I have a spaceship which can accelerate in any direction and can rotate around any axis (in 3D space). I want to have all other bodies in the world remain in exactly the same ...
huhyuh's user avatar
  • 21
2 votes
0 answers
65 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 ...
L.C. Ruth's user avatar
  • 131
0 votes
0 answers
57 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 ...
roy aber's user avatar
-4 votes
1 answer
111 views

Guessing Game in two 6 sided Dice [closed]

DIE DESCRIPTION There is a $12$-sided Die with each face numbered as integer from $1$ to $12$. The die is loaded! $40\%$ of rolls are of face $12$. While $60\%$ of rolls are of any other integer from $...
Theo's user avatar
  • 13
0 votes
1 answer
34 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 ...
millgod27's user avatar
5 votes
2 answers
8k 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 ...
Madisen Werdell's user avatar
0 votes
0 answers
33 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-...
TinBane's user avatar
  • 101
0 votes
0 answers
53 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 ...
sakri monder's user avatar
0 votes
0 answers
101 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 ...
binaryBigInt's user avatar

1
2 3 4 5 6