Browsing by Subject "NP Complete"
Now showing items 1-5 of 5
-
Conference Object
A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016)[Schaefer and Štefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of ∃ℝ as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, ...
-
Article
The complexity of decision problems about nash equilibria in win-lose games
(2012)We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist
-
Article
The complexity of pure equilibria in mix-weighted congestion games on parallel links
(2015)We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. ...
-
Article
A graph-theoretic network security game
(2008)Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, ...
-
Conference Object
Towards feasible implementations of low-latency multi-writer atomic registers
(2011)This work explores implementations of multi-writer/multi-reader (MWMR) atomic registers in asynchronous, crash-prone, message-passing systems with the focus on low latency and computational feasibility. The efficiency of ...