Arrow Research search

Author name cluster

Marios Mavronicolas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers
2 author rows

Possible papers

25

TCS Journal 2009 Journal Article

Preface

  • Paul G. Spirakis
  • Marios Mavronicolas
  • Spyros C. Kontogiannis
Details DOI

MFCS Conference 2008 Conference Paper

Voronoi Games on Cycle Graphs

  • Marios Mavronicolas
  • Burkhard Monien
  • Vicky G. Papadopoulou
  • Florian Schoppmann

Abstract In a Voronoi game, each of a finite number of players chooses a point in some metric space. The utility of a player is the total measure of all points that are closer to him than to any other player, where points equidistant to several players are split up evenly among the closest players. In a recent paper, Dürr and Thang (2007) considered discrete Voronoi games on graphs, with a particular focus on pure Nash equilibria. They also looked at Voronoi games on cycle graphs with n nodes and k players. In this paper, we prove a new characterization of all Nash equilibria for these games. We then use this result to establish that Nash equilibria exist if and only if \(k \leq \frac{2n}3\) or k ≥ n. Finally, we give exact bounds of \(\frac 94\) and 1 for the prices of anarchy and stability, respectively.

Details

MFCS Conference 2007 Conference Paper

Congestion Games with Player-Specific Constants

  • Marios Mavronicolas
  • Igal Milchtaich
  • Burkhard Monien
  • Karsten Tiemann

Abstract We consider a special case of weighted congestion games with player-specific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the player-specific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group. In this way, we obtain the class of weighted congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance weighted congestion games.

Details

MFCS Conference 2006 Conference Paper

The Price of Defense

  • Marios Mavronicolas
  • Loizos Michael
  • Vicky G. Papadopoulou
  • Anna Philippou
  • Paul G. Spirakis

Abstract We consider a strategic game with two classes of confronting randomized players on a graph G ( V, E ): ν attackers, each choosing vertices and wishing to minimize the probability of being caught, and a defender, who chooses edges and gains the expected number of attackers it catches. The Price of Defense is the worst-case ratio, over all Nash equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium. We provide a comprehensive collection of trade-offs between the Price of Defense and the computational efficiency of Nash equilibria. – Through reduction to a Two-Players, Constant-Sum Game, we prove that a Nash equilibrium can be computed in polynomial time. The reduction does not provide any apparent guarantees on the Price of Defense. – To obtain such, we analyze several structured Nash equilibria: – In a Matching Nash equilibrium, the support of the defender is an Edge Cover. We prove that they can be computed in polynomial time, and they incur a Price of Defense of α ( G ), the Independence Number of G. – In a Perfect Matching Nash equilibrium, the support of the defender is a Perfect Matching. We prove that they can be computed in polynomial time, and they incur a Price of Defense of \(\frac{|V|}{2}\). – In a Defender Uniform Nash equilibrium, the defender chooses uniformly each edge in its support. We prove that they incur a Price of Defense falling between those for Matching and Perfect Matching Nash Equilibria; however, it is \({\cal NP}\) -complete to decide their existence. – In an Attacker Symmetric and Uniform Nash equilibrium, all attackers have a common support on which each uses a uniform distribution. We prove that they can be computed in polynomial time and incur a Price of Defense of either \(\frac{|V|}{2}\) or α ( G ).

Details

MFCS Conference 2004 Conference Paper

The Price of Anarchy for Polynomial Social Cost

  • Martin Gairing
  • Thomas Lücking 0001
  • Marios Mavronicolas
  • Burkhard Monien

Abstract 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, while social cost is now the expectation of the sum, over all links, of a certain polynomial evaluated at the total latency incurred by all users choosing the link; we call it polynomial social cost. The polynomials that we consider have non-negative coefficients. We are interested in evaluating Nash equilibria in this model, and we use the Price of Anarchy as our evaluation measure. We prove the Fully Mixed Nash Equilibrium Conjecture for identical users and two links, and establish an approximate version of the conjecture for arbitrary many links. Moreover, we give upper bounds on the Price of Anarchy.

Details

MFCS Conference 2003 Conference Paper

Which Is the Worst-Case Nash Equilibrium?

  • Thomas Lücking 0001
  • Marios Mavronicolas
  • Burkhard Monien
  • Manuel Rode
  • Paul G. Spirakis
  • Imrich Vrto

Abstract A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such equilibria within the context of a certain game that models selfish routing for a set of n users each shipping its traffic over a network consisting of m parallel links. In particular, we are interested in identifying the worst-case Nash equilibrium – the one that maximizes social cost. Worst-case Nash equilibria were first introduced and studied in the pioneering work of Koutsoupias and Papadimitriou [9]. More specifically, we continue the study of the Conjecture of the Fully Mixed Nash Equilibrium, henceforth abbreviated as FMNE Conjecture, which asserts that the fully mixed Nash equilibrium, when existing, is the worst-case Nash equilibrium. (In the fully mixed Nash equilibrium, the mixed strategy of each user assigns (strictly) positive probability to every link.) We report substantial progress towards identifying the validity, methodologies to establish, and limitations of, the FMNE Conjecture.

Details