Questions tagged [gt.game-theory]
Theoretical question related to Computer Science and Game Theory
114 questions
2
votes
0
answers
37
views
Complexity of deciding whether a given payoff vector can be achieved by some mixed strategy profile in a normal form game
Note that this mixed strategy profile does not need to be a Nash equilibrium. I'm mostly looking for references, as I assume the answer is known, but my searches have only found results about Nash ...
7
votes
1
answer
177
views
Given a 2-player zero-sum game in EFG, find a pure Nash equilibrium (given that one exists)
Say we want to find a pure Nash equilibrium of a 2-player zero-sum (2P0S) game. A pure equilibrium does not exist for all games, so let's consider the setting where we are promised that such an ...
- 256
1
vote
1
answer
78
views
Sequential Two-player Game related to "Bandit Detection"
Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x_t$ which is represented by a ...
- 13
0
votes
0
answers
70
views
Undecidability of games with limited hidden state
Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable.
Question:...
- 2,742
1
vote
0
answers
97
views
Do game semantics for logic have Curry-Howard-like correspondence with game semantics for programming languages?
Both for logic and PLs do have notion of game semantics. Both are defined by two-player dialogue game, but players are different. In first case it is game between Verifyer and Falsifyer and in second ...
- 315
4
votes
0
answers
140
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 101
2
votes
1
answer
146
views
Approximating the utilitarian welfare minus a constant
Assume we have $n$ agents and $m$ indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.
Denote the set of allocations by $\mathcal{A}$ and the ...
- 101
3
votes
1
answer
249
views
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.
For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:
It is ...
- 33
0
votes
1
answer
233
views
What Complexity Class is this? Is this already known?
Let's call this the Path Game.
For this example, lets imagine a 16x16 grid:
Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
- 21
2
votes
2
answers
580
views
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$The question that I am wondering in this post is if there is any intuition to ...
- 125
3
votes
0
answers
53
views
Online assignment lower bound results
I am reading the following paper which presents a $(1-\epsilon)$-competitive online algorithm for the MaxMin (similar to the makespan) problem, defined as follows:
a set of requests are arriving in an ...
- 31
1
vote
1
answer
188
views
Can theoretical computer science be combined with mechanism and information design and applications in financial markets
I am considering to take a position as a phd student in a computer science department. I am a mathematician with a master degree in finance and my research interests are mainly focused in game theory. ...
- 11
-1
votes
1
answer
134
views
Algorithm for finding traffic equilibrium
I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
9
votes
0
answers
161
views
"Looking for help understanding a proof by Gossner (1998)."
Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
- 209
1
vote
0
answers
77
views
Algorithmic game theory with decentralized mechanism of exchanging information
An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical ...
- 209
1
vote
1
answer
66
views
How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$
Consider a bimatrix game problem with matrix $A$ and $B$. The definition of the value $v = [v_1, v_2]$ of the Nash equilibrium $(x, y)$ are as follows,
$$v_1 = x^TAy,$$
$$v_2 = x^TBy.$$
The situation ...
- 141
0
votes
0
answers
135
views
Is this "choose and switch" game just 2SAT in disguise?
Suppose you have $n$ switches lined up on a wall, labeled left to right from $1$ to $n$. The switches are either on or off.
You get a list of $q$ choices that must be made. A choice consist of two ...
- 137
3
votes
1
answer
220
views
Algorithm to find $n$ player nash equilibrium
This is the question asked 10 years before.
Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years?
The game dealing ...
- 141
0
votes
1
answer
175
views
Application of Yao's Minmax Principle for Adaptive Randomized Algorithms
Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for ...
- 171
11
votes
0
answers
206
views
Is 4-in-a-row PSPACE-complete?
This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
- 682
11
votes
1
answer
715
views
The theoretical complexity of Go - The state of the art
What are the latest advances in theoretical complexity of Go?
I know some early works about the complexity of Go:
"Go is polynomial-space hard" proved that Go is PSPACE-hard.
"Ladders are PSPACE-...
- 421
13
votes
3
answers
1k
views
A game on several graphs
Consider the following game on a directed weighted graph $G$ with a chip at some node.
All nodes of $G$ are marked by A or B.
There are two players Alice and Bob. The goal of Alice (Bob) is to ...
- 2,023
8
votes
1
answer
377
views
Winning strategy in the game of triplets
The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements.
Two players take turns picking elements from $X$ until all elements are ...
- 2,314
10
votes
1
answer
516
views
What is the complexity of this game?
This is a generalization of my previous question.
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
- 2,023
5
votes
0
answers
823
views
Games on Turing machines that are AH-hard
I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
- 1,046
10
votes
1
answer
420
views
Is this game EXPSPACE-complete?
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be ...
- 2,023
1
vote
0
answers
89
views
Nim-game variant - weird ending condition
the game is structured like this:
two players
the players alternate moves
4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$
at each move, the player can either remove one or two elements from ...
10
votes
1
answer
280
views
Equilibrium in a Halting Game
Consider the following 2-player game:
Nature randomly picks a program
Each player plays a number in [0, infinity] inclusive in response to nature's move
Take the minimum of the players’ numbers, and ...
- 103
3
votes
0
answers
56
views
Correlated random models of game trees
Say we want to understand a game tree search algorithm in a theoretical context. Thus, we want a parameterized family of problem instances, separate from actual games such as a chess, so that ...
- 3,313
3
votes
2
answers
727
views
Can generalized twenty questions be solved by a greedy algorithm?
The game of twenty questions can be generalized in the following way.
Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ is ...
- 247
1
vote
0
answers
52
views
Circuit games in extensive form with imperfect information
Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with ...
- 2,181
2
votes
0
answers
216
views
Two-player zero-sum games in extensive form represented as directed acyclic graphs
The following is a way to represent two-player zero-sum games in extensive form. Consider a directed acyclic graph $G$ where each non-terminal vertex is one of 3 types: player 1 vertex, player 2 ...
- 2,181
2
votes
1
answer
178
views
Maximum stable matching/allocation
I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed ...
- 119
1
vote
1
answer
194
views
The logic in derivation of virtual welfare
I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment ...
- 191
6
votes
1
answer
204
views
On bandwidth of graphs
I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance.
I could only find research related to computing the bandwidth, ...
- 9,018
1
vote
1
answer
754
views
Minmax vs Maxmin
I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to ...
- 113
-4
votes
1
answer
159
views
Understanding Prisoner's dilemma [closed]
Imagine two prisoners held in separate cells, interrogated simultaneously, and offered deals (lighter jail sentences) for betraying their fellow criminal. They can "cooperate" (with the other prisoner)...
- 95
16
votes
0
answers
546
views
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of ...
- 6,051
7
votes
3
answers
2k
views
What is the application of combinatorial game theory
I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
- 153
0
votes
0
answers
304
views
Finding an equivalent NP-complete instance for this game-theory problem
I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
- 139
4
votes
1
answer
211
views
Stackelberg solution to $n$-player Hotelling's game on a segment
Suppose that several agents need to place points (one per
agent) on the interval $[0,1]$. An agent's goal is to maximize the
volume of the Voronoi cell that contains his point. When $n$ agents must
...
- 10.6k
5
votes
0
answers
214
views
Applications of Combinatorial Games in Computational Biology
I'm looking for general references in the literature about applications of games algorithmics in computational biology.
Q1. What are the notable cases of computational-biology or bioinformatics ...
- 650
2
votes
0
answers
105
views
What mathematical models can analyze and optimize such message passing system?
I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message ...
- 121
3
votes
1
answer
879
views
Is there a tool for finding Nash equilibria in parametric games?
There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix.
Such tools are Game Theory Explorer and Gambit.
However, as ...
- 9,508
14
votes
1
answer
254
views
Computationally bounded version of Nash equilibrium?
I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.
Imagine some kind of two-player perfect information game which is ...
- 7,620
2
votes
1
answer
470
views
How to prove the existence of a pure Nash equilibrium?
I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I ...
- 23
11
votes
3
answers
954
views
Implementation of surreal numbers for games
There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
- 9,018
-2
votes
1
answer
345
views
Iterated Prisoner's Dilemma Algorithms
While reading a post on Scott Aaronson's blog about Eigenmorality, I ran across the idea of the iterated prisoner's dilemma tournament. I've studied some TCS on my own, but had never really thought ...
user1338
1
vote
1
answer
126
views
Generalized Secretary Optimization Problem
In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates. I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar ...
- 1,099
9
votes
1
answer
321
views
Secretary hiring game
This is an extension of the classical secretary problem.
In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is.
W.l.o.g, we assume ...
- 9,508