Marios Mavronicolas

AAMAS Conference 2026 Conference Paper

Complexity of (Non-)Convergence in Iterative Voting

• Paul W. Goldberg
• Marios Mavronicolas
• Tomasz Was

Iterative voting is a well-studied model of repeated decision-making, introduced in 2010 by Meir et al. [19], where strategic voters may repeatedly revise their votes, given information about other voters’ interim votes, before convergence to a stable state where no voter has an incentive to revise. Despite considerable previous convergence and non-convergence results for iterative voting under various voting rules and information and behavioral assumptions in the last 15 years, the computational complexity of detecting convergence and non-convergence has not been explored before. In this work, we present the first such complexity results. Specifically, we establish, as our main results, the NP-completeness of the following two decision problems about plurality elections when an arbitrary group of voters can revise their votes as long as the updates are direct and beneficial for each member of the group: • Does a given election converge to a strong Nash equilibrium within at most ℓ revision steps? We exhibit instances where a strong Nash equilibrium does exist but is unreachable by any number of such steps. • Does a given election create voting cycles of ℓ revision steps? We also prove general results for Pareto efficient voting rules. Specifically, for two voters and three candidates, if in each step a single voter updates their vote using the natural TB heuristic [16], then for every Pareto-efficient voting rule there is no cycle of length more than two. In contrast, when both voters update their votes using the same heuristic simultaneously, and we have𝑚 ≥ 3 candidates, every rule satisfying a slight refinement of Pareto efficiency can end up in a cycle of length𝑚.

TCS Journal 2025 Journal Article

The contest game for crowdsourcing reviews

• Vittorio Bilò
• Marios Mavronicolas
• Paul G. Spirakis

We consider a contest game with discrete strategies, modelling a contest where reviews for a proposal are crowdsourced from n players. Player i has a skill s i, strategically chooses a quality q ∈ { 1, 2, …, Q } for her review and pays an effort f q ≥ 0, strictly increasing with q. Under voluntary participation, a player may opt to not write a review, paying zero effort; mandatory participation excludes this option. For her effort, she is awarded a payment per her payment function, which is either player-invariant, like, e. g. , the popular proportional allocation, or player-specific; it is oblivious when it does not depend on the loads on other qualities. The utility to player i is the difference between her payment and her cost, calculated by a skill-effort function Λ ( s i, f q ). Skills may vary for arbitrary players; when players are anonymous, s i = 1 for each player i. In a pure Nash equilibrium, no player could increase her utility by unilaterally switching to another quality. We show the following results about the (in)existence and the computation of a pure Nash equilibrium: • A contest game with arbitrary players and player-invariant and oblivious payments is an unweighted congestion game with player-specific constants on parallel links [42]; so it has a generalized ordinal potential, the Finite Improvement Property (FIP) and a pure Nash equilibrium, which can be computed in PLS. However, under the assumption that the payment function is monotonically nonincreasing, a pure Nash equilibrium can be computed efficiently by resorting to [44, Theorem 2]. In contrast, a pure Nash equilibrium might not exist for (i) anonymous players and player-invariant but not oblivious payments, (ii) arbitrary players and proportionally allocated payments, and (iii) anonymous players and player-specific and oblivious payments; in the latter case, it is NP -hard to decide existence even if players are anonymous. These counterexamples prove the tightness of our existence result and suggest that the decision and search problems for a pure Nash equilibrium are computationally hard. • Under some mild assumptions on the efforts, the contest game with anonymous players and proportional allocation has at least one Nash equilibrium. For arbitrary players, we identify a simple condition involving both skills and efforts that suffices for the existence of a pure Nash equilibrium in the special case where the skill-effort function has the product form Λ ( s i, f q ) = s i f q. In both cases the pure Nash equilibrium is simple and computable in constant time. • Under the assumption that costs are player-consistent, there is a polynomial-time Θ ( n Q ) algorithm to decide the existence and compute a pure Nash equilibrium for constant Q, for the case of arbitrary players and player-invariant payments; so the computational problem is XP -tractable with respect to the parameter Q. Player-consistent costs means that all players are incurred the same relative costs for a given pair of qualities. The computed equilibrium is contiguous by design: players with higher skills are contiguously assigned to lower qualities. Our results indicate that the decision and search problems for pure Nash equilibria are likely to be computationally hard even in the simplest case, but can be made easy even in the hardest case by adopting simple assumptions on efforts, payments or costs, no matter whether participation is mandatory or voluntary.

TCS Journal 2021 Journal Article

The complexity of ( E + Var )-equilibria, ESR -equilibria, and SuperE -equilibria for 2-players games with few cost values

• Chryssis Georgiou
• Marios Mavronicolas
• Burkhard Monien

We consider 2-players minimization games with very few cost values. Players are risk-averse and play mixed strategies. The players care about minimizing some function other than expectation or minimizing expectation with additional properties: Expectation plus Variance (E+Var), or Extended Sharpe Ratio (ESR), or Expectation (E) with the additional property that Variance is zero ( Var = 0 ). These give rise to ( E + Var )-equilibria, to ESR -equilibria, and to SuperE-equilibria, respectively: in an ( E + Var ) -equilibrium, no player could unilaterally reduce her ( E + Var )-cost; in an ESR -equilibrium, no player could unilaterally reduce her ESR -cost; in a SuperE-equilibrium, Var =0 and no player could unilaterally reduce her E-cost. We show two complexity results: • Deciding the existence of an ( E + R )-equilibrium is strongly NP -hard for 3-values games, where R is a general risk valuation, assuming that E + R is strictly quasiconcave and satisfies certain technical properties. N P -hardness is inherited to E + Var and to ESR, shown to have the properties. • Deciding the existence of a SuperE-equilibrium is strongly NP -hard for 3-values games, but computing one is in P for 2-values games. These results identify a complexity separation between 2-values and 3-values games. We also identify certain combinatorial properties of ( E + Var ) -equilibria for 2-values games.

TCS Journal 2020 Journal Article

Conditional Value-at-Risk: Structure and complexity of equilibria

• Marios Mavronicolas
• Burkhard Monien

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; α ∈ ( 0, 1 ) is the confidence level. In this work, we study the strategic equilibria for an economic system modeled as a game, where risk-averse players seek to minimize the Conditional Value-at-Risk of their costs. Concretely, in a CVaR α -equilibrium, the mixed strategy of each player is a best-response. We establish two significant properties of CVaR α at equilibrium: (1) The Optimal-Value property: For any best-response of a player, each mixed strategy in the support gives the same cost to the player. This follows directly from the concavity of CVaR α in the involved probabilities, which we establish. (2) The Crawford property: For every α, there is a 2-player game with no CVaR α -equilibrium. The property is established using the Optimal-Value property and a new functional property of CVaR α, called Weak-Equilibrium-for- VaR α, we establish. On top of these properties, we show, as one of our two main results, that deciding the existence of a CVaR α -equilibrium is strongly NP -hard even for 2-player games. As our other main result, we show the strong NP -hardness of deciding the existence of a V -equilibrium, over 2-player minimization games, for any valuation V with the Optimal-Value and the Crawford properties. This result has a rich potential since we prove that the very significant and broad class of strictly quasiconcave valuations has the Optimal-Value property.

TCS Journal 2016 Journal Article

The complexity of equilibria for risk-modeling valuations

• Marios Mavronicolas
• Burkhard Monien

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 expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V = E + R of expectation E and a risk valuation R of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V -equilibrium, no player could unilaterally reduce her cost. Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E -strict concavity and observe that every E -strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem: • Two strategies: Deciding the existence of a V -equilibrium is strongly NP -hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1) Var (variance), or (2) SD (standard deviation), or (3) a concave linear sum of even moments of small order. • Two players: Deciding the existence of a V -equilibrium is strongly NP -hard when choosing R as (1) γ ⋅ Var, or (2) γ ⋅ SD, where γ > 0 is the risk-coefficient, or choosing V as (3) a convex combination of E + γ ⋅ Var and the concave ν-valuation ν − 1 ( E ( ν ( ⋅ ) ) ), where ν ( x ) = x r, with r ≥ 2. This is a concrete consequence of a general strong NP -hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.

TCS Journal 2010 Journal Article

An efficient counting network

• Costas Busch
• Marios Mavronicolas

We present a novel counting network construction, where the number of input wires w is smaller than or equal to the number of output wires t. The depth of our network is Θ ( lg 2 w ), which depends only on w. In contrast, the amortized contention of the network depends on the number of concurrent processes n and the parameters w and t. This offers more flexibility than all previously known networks, with the same number w of input and output wires, whose contention depends only on two parameters, w and n. In case n > w lg w, by choosing t > w lg w the contention of our network is O ( n lg w / w ), which improves by a logarithmic factor of w over all previously known networks with w wires.

TCS Journal 2009 Journal Article

Computing on a partially eponymous ring

• Marios Mavronicolas
• Loizos Michael
• Paul Spirakis

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 identical (as in the anonymous model) nor necessarily unique (as in the eponymous model). In a decision problem formalized as a relation, processors receive inputs and seek to reach outputs respecting the relation. We focus on the partially eponymous ring, and we shall consider the computation of circularly symmetric relations on it. We consider sets of rings where all rings in the set have the same multiset of identity multiplicities. • We distinguish between solvability and computability: in solvability, processors are required to always reach outputs respecting the relation; in computability, they must do so whenever this is possible, and must otherwise report impossibility. – We present a topological characterization of solvability for a relation on a set of rings, which can be expressed as an efficiently checkable, number-theoretic predicate. – We present a universal distributed algorithm for computing a relation on a set of rings; it runs any distributed algorithm for constructing views, followed by local steps. • We derive, as our main result, a universal upper bound on the message complexity to compute a relation on a set of rings; this bound demonstrates a graceful degradation with the Least Minimum Base, a parameter indicating the degree of least possible eponymity for a set of rings. Thereafter, we identify two cases where a relation can be computed on a set of rings, with rings of size n, with an efficient number of O ( n ⋅ lg n ) messages.

TCS Journal 2009 Journal Article

Preface

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

TCS Journal 2009 Journal Article

Preface

• Marios Mavronicolas

TCS Journal 2009 Journal Article

The structure and complexity of Nash equilibria for a selfish routing game

• Dimitris Fotakis
• Spyros Kontogiannis
• Elias Koutsoupias
• Marios Mavronicolas
• Paul Spirakis

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.

TCS Journal 2008 Journal Article

A new model for selfish routing

• Thomas Lücking
• Marios Mavronicolas
• Burkhard Monien
• Manuel Rode

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 KP model [E. Koutsoupias, C. H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404–413] and the W model [J. G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the of the Institute of Civil Engineers 1 (Pt. II) (1952) 325–378]. In the hybrid model, each of n users is using a mixed strategy to ship its unsplittable traffic over a network consisting of m parallel links. In a Nash equilibrium, no user can unilaterally improve its Expected Individual Cost. To evaluate Nash equilibria, we introduce Quadratic Social Cost as the sum of the expectations of the latencies, incurred by the squares of the accumulated traffic. This modeling is unlike the KP model, where Social Cost [E. Koutsoupias, C. H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404–413] is the expectation of the maximum latency incurred by the accumulated traffic; but it is like the W model since the Quadratic Social Cost can be expressed as a weighted sum of Expected Individual Costs. We use the Quadratic Social Cost to define Quadratic Coordination Ratio. Here are our main findings: • Quadratic Social Cost can be computed in polynomial time. This is unlike the # P -completeness [D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, P. Spirakis, The structure and complexity of Nash equilibria for a selfish routing game, in: P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, R. Conejo (Eds.), Proceedings of the 29th International Colloquium on Automata, Languages and Programming, in: Lecture Notes in Computer Science, vol. 2380, Springer-Verlag, 2002, pp. 123–134] of computing Social Cost for the KP model. • For the case of identical users and identical links, the fully mixed Nash equilibrium [M. Mavronicolas, P. Spirakis, The price of selfish routing, Algorithmica 48 (1) (2007) 91–126], where each user assigns positive probability to every link, maximizes Quadratic Social Cost. • As our main result, we present a comprehensive collection of tight, constant (that is, independent of m and n ), strictly less than 2, lower and upper bounds on the Quadratic Coordination Ratio for several, interesting special cases. Some of the bounds stand in contrast to corresponding super-constant bounds on the Coordination Ratio previously shown in [A. Czumaj, B. Vöcking, Tight bounds for worst-case equilibria, ACM Transactions on Algorithms 3 (1) (2007); E. Koutsoupias, M. Mavronicolas, P. Spirakis, Approximate equilibria and ball fusion, Theory of Computing Systems 36 (6) (2003) 683–693; E. Koutsoupias, C. H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404–413; M. Mavronicolas, P. Spirakis, The price of selfish routing, Algorithmica 48 (1) (2007) 91–126] for the KP model.

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.

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.

TCS Journal 2007 Journal Article

The increase of the instability of networks due to Quasi-Static link capacities

• Dimitrios Koukopoulos
• Marios Mavronicolas
• Paul Spirakis

In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C > 1 under a ( w, ρ ) -adversary. We obtain the following results: • Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention–resolution results in instability at rates ρ > 2 − 1 and for large enough values of C. • The combination of dynamically changing link capacities with compositions of contention–resolution protocols on network queues suffices for similar instability bounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates ρ > 2 − 1 for large enough values of C. • The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instability bounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.

TCS Journal 2006 Journal Article

The price of anarchy for polynomial social cost

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

In this work, we consider an interesting variant of the well studied KP model for selfish routing on parallel links, which reflects some influence from the much older Wardrop model [J. G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. of Civil Eng. Part II 1 (1956) 325–378]. In the new model, user traffics are still unsplittable and links are identical. Social cost is now the expectation of the sum, over all links, of latency costs; each latency cost is modeled as a certain polynomial latency cost function evaluated at the latency incurred by all users choosing the link. The resulting social cost is called polynomial social cost, or monomial social cost when the latency cost function is a monomial. All considered polynomials are of degree d, where d ⩾ 2, and have non-negative coefficients. We are interested in evaluating Nash equilibria in this model, and we use the monomial price of anarchy (MPoA) and the polynomial price of anarchy (PPoA) as our evaluation measures. Through establishing some remarkable relations of these costs and measures to some classical combinatorial numbers such as the Stirling numbers of the second kind and the Bell numbers, we obtain a multitude of results: • For the special case of identical users: ∘ The fully mixed Nash equilibrium, where all probabilities are strictly positive, maximizes polynomial social cost. ∘ The MPoA is no more than B d, the Bell number of order d. This immediately implies that the PPoA is no more than ∑ 1 ⩽ t ⩽ d B t. For the special case of two links, the MPoA is no more than 2 d - 2 ( 1 + ( 1 / n ) d - 1 ), and this bound is tight for n = 2. • The MPoA is exactly ( ( 2 d - 1 ) d / ( d - 1 ) ( 2 d - 2 ) d - 1 ) ( ( d - 1 ) / d ) d for pure Nash equilibria. This immediately implies that the PPoA is no more than ∑ 2 ⩽ t ⩽ d ( ( 2 t - 1 ) t / ( t - 1 ) ( 2 t - 2 ) t - 1 ) ( ( t - 1 ) / t ) t.

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

TCS Journal 2005 Journal Article

Game Theory Meets Theoretical Computer Science

• Samson Abramsky
• Marios Mavronicolas

TCS Journal 2005 Journal Article

The cost of concurrent, low-contention Read&Modify&Write

• Costas Busch
• Marios Mavronicolas
• Paul Spirakis

This work addresses the possibility or impossibility, and the corresponding costs, of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system. A natural class of monotone RMW operations associated with monotone groups, a certain class of algebraic groups introduced here, is considered. The popular Fetch&Add and Fetch&Multiply operations are examples from the class. A Monotone Linearizability Lemma is proved and employed as a chief combinatorial instrument in this work; it establishes inherent ordering constraints of linearizability for a certain class of executions of any distributed system implementing a monotone RMW operation. The end results of this work specifically apply to implementations of (monotone) RMW operations that are based on switching networks, a recent class of concurrent, low-contention data structures that generalize counting networks (J. ACM 41(5) (1994) 1020–1048) (which implemented the traditional Fetch&Increment operation). These results are negative; they are shown through the Monotone Linearizability Lemma. In particular, the first lower bounds on size (the number of switches in the network) for any (non-trivial) switching network implementing a monotone RMW operation are derived. It is proven that if the network incurs low contention, then its size must be infinite, no matter whether the number of states of each switch is finite or infinite. Since Fetch&Increment is implementable with counting networks of finite-size (J. ACM 41(5) (1994) 1020–1048), these lower bounds imply a space complexity separation between Fetch&Increment and any monotone RMW operation in the model of switching networks. The presented lower bounds provide a mathematical explanation for the observed inability of researchers over the last thirteen years to extend counting networks, while keeping their finite-size, high-concurrency and low-contention, in order to perform tasks more complex than Fetch&Increment but yet as simple as Fetch&Add.

STOC Conference 2004 Conference Paper

Computing Nash equilibria for scheduling on restricted parallel links

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

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.

TCS Journal 2003 Journal Article

Trade-off results for connection management

• Marios Mavronicolas
• Nikos Papadakis

A connection management protocol establishes and handles a connection between two hosts across a wide-area network to allow reliable message delivery. We continue the previous work of Kleinberg et al. (Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems, January (1995), pp. 258–267) to study the precise impact of the level of synchrony provided by the processors’ clocks on the performance of connection management protocols, under common assumptions on the pattern of failures of the network and the host nodes. Two basic timing models are assumed: clocks that exhibit a certain kind of a drift from the rate of real time, and clocks that display a pattern of synchronization to real time. We consider networks that can duplicate and reorder messages, and nodes that can crash. We are interested in simultaneously optimizing the following performance parameters: the message delivery time, which is the time required to deliver a message, and the quiescence time, which is the time that elapses between periods of quiescence, in which the receiving host deletes all earlier connection records and returns to an initial state. We establish natural trade-offs between message delivery time and quiescence time, in the form of tight lower and upper bounds, for each combination of the timing models and failure types. Several of our trade-off results significantly improve upon or extend previous ones shown by Kleinberg et al.

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.

TCS Journal 2002 Journal Article

Threshold counters with increments and decrements

• Costas Busch
• Neophytos Demetriou
• Maurice Herlihy
• Marios Mavronicolas

A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value ⌊v/w⌋, where v is the current counter value and w is a fixed constant. Thus, the Read operation returns the “approximate” value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a Decrement operation that changes the counter value from v to v−1.

STOC Conference 2001 Conference Paper

The price of selfish routing

• Marios Mavronicolas
• Paul G. Spirakis

We study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links . We assume a collection of n network users , each employing a mixed strategy which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum expected latency over all links is minimized. We consider both uniform and non-uniform link capacities.

TCS Journal 1999 Journal Article

Foreword

• Marios Mavronicolas

TCS Journal 1999 Journal Article

Linearizable read/write objects

• Marios Mavronicolas
• Dan Roth

We study the cost of using message passing to implement linearizable read/write objects for shared-memory multiprocessors under various assumptions on the available timing information. We take as cost measures the worst-case response times for performing read and write operations in distributed implementations of virtual shared memory consisting of such objects, and the sum of these response times. It is assumed that processes have clocks that run at the same rate as real time and are within δ of each other, for some known precision constant δ ⩾ 0. All messages incur a delay in the range [d−u, d] for some known constants u and d, 0 ⩽ u ⩽ d. For the perfect clocks model, where clocks are perfectly synchronized, i. e. , δ = 0, and every message incurs a delay of exactly d, we present a linearizable implementation which achieves worst-case response times for read and write operations of βd and (1 − β)d, respectively; β is a trade-off parameter, 0 ⩽ β ⩽ 1, which may be tuned to account for the relative frequencies of read and write operations. This implementation is optimal with respect to the sum of the worst-case response times for read and write operations. We next turn to the approximately synchronized clocks model, where clocks are only approximately synchronized, i. e. , β > 0, and message delays can vary, i. e. , u > 0. Our first major result is the first known linearizable implementation for this model which achieves worst-case response times of less than βd + 3u + min {δ, u} + ε, and (l − β)d + 3u for read and write operations, respectively, under a mild restriction on the trade-off parameter β, 0 ⩽ β < 1− u d; ε is any arbitrary constant such that 0 ⩽ ε ⩽ min {2u, d − u}. This implementation employs a novel use of approximately synchronized clocks in order to utilize the lower bound on message delay time and achieve bounds on worst-case response times that depend on the message delay uncertainty u. For a wide range of values of u, these bounds improve upon previously known ones for implementations that supports consistency conditions even weaker than linearizability. Our next major result is a lower bound of d + min {δ, u} 2 on the sum of the worst-case response times for read and write operations, for the approximately synchronized clocks model. This bound applies to linearizable implementations possessing some natural symmetry properties; the bound is shown using the technique of “shifting” executions. Corresponding lower bounds, but with no symmetry assumptions, are shown on the individual worst-case response times for read and write operations. Our bounds for the approximately synchronized clocks model extend naturally to the imperfect clocks model, where clocks may be arbitrarily far from each other, i. e. , δ = ∞.