Browsing by Author "Mavronicolas, Marios"
Now showing items 1-20 of 111
-
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. 348-358 as a new class of distributed, low-contention data structures ...
-
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
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. 348-358, May 1991), represent a new class of distributed, low-contention 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 ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate 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 ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
-
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
The complexity of equilibria for risk-modeling 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 mix-weighted 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 non-negative 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 (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
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
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
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
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
Conditional Value-at-Risk: Structure and complexity of equilibria
Mavronicolas, Marios; Monien, Burkhard (2020)Conditional Value-at-Risk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain
-
Article
Conditional value-at-risk: Structure and complexity of equilibria
Mavronicolas, Marios; Monien, Burkhard (2017)Conditional Value-at-Risk, 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 player-specific constants
Mavronicolas, Marios; Milchtaich, I.; Monien, Burkhard; Tiemann, K. (2007)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 ...