Abstract. A Nash equilibrium of a routing game is a stable state where no (randomizing) user could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst-case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev., 3 (2009), pp. 65–69], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst-case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links.

We study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. We show that a handful of such decision problems are Existential-R-complete; that is, they are exactly as hard as deciding the Existential Theory of the Reals.

[Schaefer and Stefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of EXISTS-R as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, given a 3-player game, whether or not it has a Nash equilibrium with no probability exceeding a given rational is EXISTS-R-complete. Four more decision problems about Nash equilibria for 3-player games were very recently shown EXISTS-R-complete via a chain of individual, problem-specific reductions in [Garg et al., Proceedings of ICALP 2015]; determining more such EXISTS-R-complete problems was posed there as an open problem. In this work, we deliver an extensive catalog of EXISTS-R-complete decision problems about Nash equilibria in 3-player games, thus resolving completely the open problem from [Garg et al., Proceedings of ICALP 2015]. Towards this end, we present a single and very simple, unifying reduction from the EXISTS-R-complete decision problem from [Schaefer and Stefankovic, Theory of Computing Systems, 2015] to (almost) all the decision problems about Nash equilibria that were before shown NP-complete for 2-player games in [Bilo and Mavronicolas, Proceedings of SAGT 2012; Conitzer and Sandholm, Games and Economic Behavior, 2008; Gilboa and Zemel, Games and Economic Behavior, 1989]. Encompassed in the catalog are the four decision problems shown EXISTS-R-complete in [Garg et al., Proceedings of ICALP 2015].

We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots only make local decisions. We use a state-machine representation to formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of fat robots. The main idea behind the algorithm is to enforce the robots to reach a configuration in which all the following hold:

A K-smoothing network is a distributed, low-contention data structure where tokens arrive arbitrarily on w input wires and reach w output wires via their completely asynchronous propagation through the network. The maximum discrepancy among the numbers of tokens arriving at the ouput wires, called smoothness, is at most K. It has been a longstanding open problem to construct a K-smoothing network with (i) optimal K, (ii) optimal Θ(lg w) depth (called smalldepth), (iii) no use of the AKS sorting network, and (iv) no reliance on global initialization. In this work, we present a very simple, randomized network which meets all four desiderata: • It is the cascade of a reasonably small number (about 150) of copies of the simple block network [6]; hence,

We revisit smoothing networks which are made up of balancers and wires. Tokens arrive arbitrarily on w input wires and propagate asynchronously through the network; each token gets service on the output wire it arrives at. The smoothness is the maximum discrepancy among the numbers of tokens arriving at the w output wires. We assume that balancers are oriented independently and uniformly at random. We present a collection of lower and upper bounds on smoothness, which are to some extent surprising:-The smoothness of a single block network is log log w + Θ(1) (with high probability), where the additive constant is between -2 and 4. This tight bound improves vastly over the upper bound of O(√log w) from Herlihy and Tirthapura, and it significantly improves our understanding of the smoothing properties of the block network. -Most significantly, the smoothness of the cascade of two block networks is no more than 16 (with high probability); this is the first known randomized network with so small depth (2 log w) and so good smoothness. The proof introduces some novel combinatorial and probabilistic structures and techniques which may be further applicable. This result demonstrates the full power of randomization in smoothing networks. -There is no randomized 1-smoothing network of width w and depth d that achieves 1-smoothness with probability better than d/w-1. In view of the deterministic 1-smoothing network from Klugerman and Plaxton, this result implies the first separation between deterministic and randomized smoothing networks, which demonstrates an unexpected limitation of randomization: it can get to constant smoothness very easily, but after that, the progress to 1-smoothing is very limited.

A packet-switching algorithm specifies the actions of the nodes in order to deliver packets in the network. A packet-switching algorithm is universal if it applies to any network topology and for any batch communication problem on the network. A long-standing open problem has concerned the existence of a universal packet-switching algorithm with near-optimal performance guarantees for the class of bufferless networks where the buffer size for packets in transit is zero. We give a positive answer to this question. In particular, we give a universal bufferless algorithm which is within a polylogarithmic factor from optimal for arbitrary batch problems: ${\cal T}=O\left({\cal T}^*\cdot \log^3(n+N)\right)$, where ${\cal T}$ is the packet delivery time of our algorithm, ${\cal T}^*$ is the optimal delivery time, n is the size of the network, and N is the number of packets. At the heart of our result is a new deterministic technique for constructing a universal bufferless algorithm by emulating a store-and-forward algorithm on a transformation of the network. The main idea is to replace packet buffering in the transformed network with packet circulation in regions of the original network. The cost of the emulation on the packet delivery time is proportional to the buffer sizes used by the store-and-forward algorithm. We obtain the advertised result by using a store-and-forward algorithm with logarithmic sized buffers. The resulting bufferless algorithm is constructive and can be implemented in a distributed way.

Two important performance parameters of distributed, rate-based flow control algorithms are their locality and convergence complexity. The former is characterized by the amount of global knowledge that is available to their scheduling mechanisms, while the latter is defined as the number of update operations performed on rates of individual sessions until max-min fairness is reached. Optimistic algorithms allow any session to intermediately receive a rate larger than its max-min fair rate; bottleneck algorithms finalize the rate of a session only if it is restricted by a certain, highly congested link of the network. In this work, we present a comprehensive collection of lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, bottleneck, rate-based flow control algorithms. Say that an algorithm is oblivious if its scheduling mechanism uses no information of either the session rates or the network topology. We present a novel, combinatorial construction of a capacitated network, which we use to establish a fundamental lower bound of $\frac{dn}{4} + \frac{n}{2}$ on the convergence complexity of any oblivious algorithm, where n is the number of sessions laid out on a network, and d, the session dependency, is a measure of topological dependencies among sessions. Moreover, we devise a novel simulation proof to establish that, perhaps surprisingly, the lower bound of $\frac{dn}{4} + \frac{n}{2}$ on convergence complexity still holds for any partially oblivious algorithm, in which the scheduling mechanism is allowed to use information about session rates, but is otherwise unaware of network topology. On the positive side, we prove that the lower bounds for oblivious and partially oblivious algorithms are both tight. We do so by presenting optimal oblivious algorithms, which converge after $\frac{dn}{2} + \frac{n}{2}$ update operations are performed in the worst case. To complete the picture, we show that linear convergence complexity can indeed be achieved if information about both session rates and network topology is available to schedulers. We present a counterexample, nonoblivious algorithm, which converges within an optimal number of n update operations. Our results imply a surprising convergence complexity collapse of oblivious and partially oblivious algorithms, and a convergence complexity separation between (partially) oblivious and nonoblivious algorithms for optimistic, bottleneck rate-based flow control.

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 correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash equilibrium with non-increased makespan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic Preflow-Push algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash equilibria.

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.

Article Sequentially consistent versus linearizable counting networks Share on Authors: Marios Mavronicolas Department of Computer Science and Engineering, University of Connecticut, Storrs, CT Department of Computer Science and Engineering, University of Connecticut, Storrs, CTView Profile , Michael Merritt AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ AT&T Labs - Research, 180 Park Avenue, Florham Park, NJView Profile , Gadi Taubenfeld The Open University, 16 Klausner St., Tel-Aviv 61392, Israel The Open University, 16 Klausner St., Tel-Aviv 61392, IsraelView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 133–142https://doi.org/10.1145/301308.301342Online:01 May 1999Publication History 5citation224DownloadsMetricsTotal Citations5Total Downloads224Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a combinatorial framework for the study of a natural class of distributed optimization problems that involve decision-making by a collection of n distributed agents in the presence of incomplete information; such problems were originally considered in a load balancing setting by Papadimitriou and Yannakakis (Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, pp. 61–64, August 1991). For any given decision protocol and assuming no communication among the agents, our framework allows to obtain a combinatorial inclusion-exclusion expression for the probability that no “overflow” occurs, called the winning probability, in terms of the volume of some simple combinatorial polytope.

Counting networks have been originally

No abstract available.

No abstract available.

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 suitable for solving many fundamental multi-processor coordination problems that can be expressed asbalancing problems. In this work, we present a mathematical study of the combinatorial structure of balancing networks, and a variety of its applications. Our study identifies important combinatorialtransfer parametersof balancing networks. In turn, necessary and sufficient combinatorial conditions are established, expressed in terms of transfer parameters, which precisely characterize many important and well studied classes of balancing networks such ascounting networksandsmoothing networks. We propose these combinatorial conditions to be “balancing analogs” of the well knownZero-One principleholding forsorting networks Within the combinatorial framework we develop, our first application is in deriving combinatorial conditions, involving the transfer parameters, which precisely delimit the boundary between counting networks and sorting networks.

No abstract available.

No abstract available.

No abstract available.

Article A combinatorial treatment of balancing networks Share on Authors: Costas Busch Department of Computer Science, University of Crete, Heraklion 71110, Greece and Institute of Computer Science, Foundation of Research and Technology, Heraklion 71110, Greece Department of Computer Science, University of Crete, Heraklion 71110, Greece and Institute of Computer Science, Foundation of Research and Technology, Heraklion 71110, GreeceView Profile , Marios Mavronicolas Institute of Computer Science, Foundation of Research and Technology, Greece and Department of Computer Science, University of Cyprus, Nicosia, Cyprus Institute of Computer Science, Foundation of Research and Technology, Greece and Department of Computer Science, University of Cyprus, Nicosia, CyprusView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 206–215https://doi.org/10.1145/197917.198092Online:14 August 1994Publication History 7citation146DownloadsMetricsTotal Citations7Total Downloads146Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The tick synchronization problem is defined and studied in the semisynchronous complete network with n processes. An algorithm for the tick synchronization problem enables each process to make an estimate of real time close enough to those of other processes. It is assumed that the (real) time for message delivery is at most d and the time between any two consecutive signs of any process is in the interval (c, 1), where 0>