• Conference Object  

      A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games 

      Bilò, Vittorio; Mavronicolas, Marios (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 

      Bilò, Vittorio; Mavronicolas, Marios (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 

      Bilò, Vittorio; Mavronicolas, Marios (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  

      Complexity of rational and irrational Nash equilibria 

      Bilò, Vittorio; Mavronicolas, Marios (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  

      Computing Nash equilibria for scheduling on restricted parallel links 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (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 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (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 

      Mavronicolas, Marios; Panagopoulou, P. N.; Spirakis, Paul G. (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 

      Feldmann, R.; Mavronicolas, Marios; Pieris, Andreas (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 graph-theoretic network security game 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (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, ...
    • Article  

      How many attackers can selfish defenders catch? 

      Mavronicolas, Marios; Monien, Burkhard; Lesta, Vicky Papadopoulou (2013)
      In a distributed system with attacks and defenses, both attackers and defenders are self-interested entities. We assume a reward-sharing scheme among interdependent defenders
    • Article  

      Nash equilibria for voronoi games on transitive graphs 

      Feldmann, R.; Mavronicolas, Marios; Monien, Burkhard (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 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (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 non-decreasing, non-constant ...
    • Article  

      Nash equilibria in discrete routing games with convex latency functions 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2004)
      We study Nash equilibria in a discrete routing game that combines features of the two most famous models for non-cooperative routing, the KP model [16] and the Wardrop model [27]. In our model, users share parallel links. ...
    • Article  

      Network game with attacker and protector entities 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2005)
      Consider an information network with harmful procedures called attackers (e.g., viruses)
    • Article  

      A network game with attackers and a defender 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2008)
      Consider an information network with threats called attackers
    • Article  

      A new model for selfish routing 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2008)
      In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, ...
    • Article  

      A new model for selfish routing 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2004)
      In this work, we introduce and study a new model for selfish routing over non-cooperative 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 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)
      In this work, we consider an interesting variant of the well-studied 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 

      Mavronicolas, Marios; Michael, Loizos; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (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 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Persiano, Giuseppe; Philippou, Anna; Spirakis, Paul G. (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 ...