Browsing by Author "Mavronicolas, Marios"
Now showing items 120 of 109

Book Chapter
Algorithmic Game Theory and Applications
Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Spirakis, Paul G. (John Wiley & Sons, Inc., 2007)Methods from game theory and mechanism design have been proven to be a powerful mathematical tool in order to understand, control, and efficiently design dynamic, complex networks, such as the Internet. Game theory provides ...

Article
Approximate Equilibria and Ball Fusion
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2003)We consider selfish routing over a network consisting of m parallel links through which n selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the ...

Article
Balancing networks: State of the art
Mavronicolas, Marios (1997)Balancing networks have recently been proposed by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 348358 as a new class of distributed, lowcontention data structures ...

Conference Object
A catalog of ∃ℝcomplete decision problems about Nash equilibria in multiplayer games
Bilò, Vittorio; Mavronicolas, Marios (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
A combinatorial characterization of properties preserved by antitokens
Busch, Costas; Demetriou, Neophytos; Herlihy, M.; Mavronicolas, Marios (2000)Balancing networks are highly distributed data structures used to solve multiprocessor synchronization problems. Typically, balancing networks are accessed by tokens, and the distribution of the tokens on the network’s ...

Article
A combinatorial treatment of balancing networks
Busch, Costas; Mavronicolas, Marios (1996)Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348358, May 1991), represent a new class of distributed, lowcontention data structures ...

Article
A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks
Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2004)Smart Dust is comprised of a vast number of ultrasmall fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that cooperate to accomplish a large sensing task. Smart ...

Article
A comparative study of protocols for efficient data propagation in smart dust networks
Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)Smart Dust is comprised of a vast number of ultrasmall fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that cooperate to accomplish a large sensing task. Smart ...

Article
The complexity of decision problems about nash equilibria in winlose 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
The complexity of equilibria for riskmodeling valuations
Mavronicolas, Marios; Monien, Burkhard (2016)Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than ...

Article
The complexity of pure equilibria in mixweighted congestion games on parallel links
Mavronicolas, Marios; Monien, Burkhard (2015)We revisit the simple class of weighted congestion games on parallel links [10], where each player has a nonnegative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. ...

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, ...

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
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 ...

Article
Computing on a partially eponymous ring
Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2006)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...

Article
Computing on a partially eponymous ring
Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2009)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...

Article
Conditional valueatrisk: Structure and complexity of equilibria
Mavronicolas, Marios; Monien, Burkhard (2017)Conditional ValueatRisk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain

Article
Congestion games with playerspecific constants
Mavronicolas, Marios; Milchtaich, I.; Monien, Burkhard; Tiemann, K. (2007)We consider a special case of weighted congestion games with playerspecific latency functions where each player uses for each particular resource a fixed (nondecreasing) delay function together with a playerspecific ...

Conference Object
Contention in balancing networks resolved
Hadjimitsis, Leonidas; Mavronicolas, Marios (ACM, 1998)Counting networks have been originally presented by Aspnes et al. as a new class of distributed/coordinated data structures suitable for solving many fundamental, multiprocessor coordination problems that can be expressed ...