Zobrazeno 1 - 10
of 128
pro vyhledávání: '"Hansen, Kristoffer Arnsfelt"'
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problems with polynomial-time verifiable solutions. In particular, we constru
Externí odkaz:
http://arxiv.org/abs/2312.01237
We study the classic problem of dividing a collection of indivisible resources in a fair and efficient manner among a set of agents having varied preferences. Pareto optimality is a standard notion of economic efficiency, which states that it should
Externí odkaz:
http://arxiv.org/abs/2307.12605
In this paper we study the computational complexity of computing an evolutionary stable strategy (ESS) in multi-player symmetric games. For two-player games, deciding existence of an ESS is complete for {\Sigma} 2 , the second level of the polynomial
Externí odkaz:
http://arxiv.org/abs/2203.07407
Publikováno v:
SIAM Journal on Computing, Special Issue FOCS 2021
We introduce a new technique for proving membership of problems in FIXP - the class capturing the complexity of computing a fixed-point of an algebraic circuit. Our technique constructs a "pseudogate" which can be used as a black box when building FI
Externí odkaz:
http://arxiv.org/abs/2111.06878
We study the computational complexity of computing or approximating a quasi-proper equilibrium for a given finite extensive form game of perfect recall. We show that the task of computing a symbolic quasi-proper equilibrium is $\mathrm{PPAD}$-complet
Externí odkaz:
http://arxiv.org/abs/2107.04300
In the consensus halving problem we are given n agents with valuations over the interval $[0,1]$. The goal is to divide the interval into at most $n+1$ pieces (by placing at most n cuts), which may be combined to give a partition of $[0,1]$ into two
Externí odkaz:
http://arxiv.org/abs/2103.04452
Publikováno v:
MFCS 2020, LIPIcs 170, 45:1--45:15
We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is Existential Theory of
Externí odkaz:
http://arxiv.org/abs/2006.08314
We study the computational complexity of decision problems about Nash equilibria in $m$-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or
Externí odkaz:
http://arxiv.org/abs/2001.05196
Publikováno v:
EPTCS 305, 2019, pp. 83-90
We give an example of a finite-state two-player turn-based stochastic game with safety objectives for both players which has no stationary Nash equilibrium. This answers an open question of Secchi and Sudderth.
Comment: In Proceedings GandALF 20
Comment: In Proceedings GandALF 20
Externí odkaz:
http://arxiv.org/abs/1903.11935