Browsing by Subject "Nash equilibria"
Now showing items 120 of 26

Conference Object
A catalog of ∃ℝcomplete decision problems about Nash equilibria in multiplayer games
(Schloss Dagstuhl LeibnizZentrum 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 winlose games
(2012)We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist

Article
Complexity of rational and irrational Nash equilibria
(2011)We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, ...

Article
Complexity of rational and irrational nash equilibria
(2014)We introduce two new natural decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ...

Article
Computing Nash equilibria for scheduling on restricted parallel links
(2010)We consider the problem of routing nusers on m parallel links under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. So, this problem is equivalent to the ...

Conference Object
Computing Nash equilibria for scheduling on restricted parallel links
(2004)We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the ...

Article
Cost sharing mechanisms for fair pricing of resource usage
(2008)We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand

Article
Facets of the fully mixed Nash equilibrium conjecture
(2010)In this work, we continue the study of the many facets of the Fully Mixed Nash Equilibrium Conjecture, henceforth abbreviated as the FMNE Conjecture, in selfish routing for the special case of n identical users over two ...

Article
A graphtheoretic 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 noncooperative multiplayer game on a graph, ...

Article
How many attackers can selfish defenders catch?
(2013)In a distributed system with attacks and defenses, both attackers and defenders are selfinterested entities. We assume a rewardsharing scheme among interdependent defenders

Article
Nash equilibria for voronoi games on transitive graphs
(2009)In a Voronoi game, each of κ≥2 players chooses a vertex in a graph G=〈V(G), E(G)〉. The utility of a player measures her Voronoi cell: the set of vertices that are closest to her chosen vertex than to that of another player. ...

Article
Nash equilibria in discrete routing games with convex latency functions
(2004)We study Nash equilibria in a discrete routing game that combines features of the two most famous models for noncooperative routing, the KP model [16] and the Wardrop model [27]. In our model, users share parallel links. ...

Article
Nash equilibria in discrete routing games with convex latency functions
(2008)In a discrete routing game, each of n selfish users employs a mixed strategy to ship her (unsplittable) traffic over m parallel links. The (expected) latency on a link is determined by an arbitrary nondecreasing, nonconstant ...

Article
Network game with attacker and protector entities
(2005)Consider an information network with harmful procedures called attackers (e.g., viruses)

Article
A network game with attackers and a defender
(2008)Consider an information network with threats called attackers

Article
A new model for selfish routing
(2008)In this work, we introduce and study a new, potentially rich model for selfish routing over noncooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, ...

Article
A new model for selfish routing
(2004)In this work, we introduce and study a new model for selfish routing over noncooperative networks that combines features from the two such best studied models, namely the KP model and the Wardrop model in an interesting ...

Article
The price of anarchy for polynomial social cost
(2004)In this work, we consider an interesting variant of the wellstudied KP model [18] for selfish routing that reflects some influence from the much older Wardrop model [31]. In the new model, user traffics are still unsplittable, ...

Article
The price of defense
(2006)We consider a strategic game with two classes of confronting randomized players on a graph G(V, E): v attackers, each choosing vertices and wishing to minimize the probability of being caught, and a defender, who chooses ...

Article
The price of defense and fractional matchings
(2006)Consider a network vulnerable to security attacks and equipped with defense mechanisms. How much is the loss in the provided security guarantees due to the selfish nature of attacks and defenses? The Price of Defense was ...