Search

We study online competitive algorithms for the line chasing problem in Euclidean spaces Rd, where the input consists of an initial point P0 and a sequence of lines X1,X2,...,Xm, revealed one at a time. At each step t, when the line Xt is revealed, the algorithm must determine a point Pt ∈ Xt. An online algorithm is called c-competitive if for any input sequence the path P0, P1, ..., Pm it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets Xt are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of √2 ≈ 1.412 for convex body chasing in 2 dimensions.

The Nash equilibrium as a prediction myopically ignores the possibility that deviating from the equilibrium could lead to an avalanche of beneficial changes by other agents. We consider a non-myopic version of Cournot competition, where each firm selects either profit maximization (as in the classical model) or revenue maximization (by masquerading as a firm with zero production costs). We consider many non-identical firms with linear demand functions and show existence of pure Nash equilibria, that simple dynamics will produce such an equilibrium, and that some natural dynamics converge within linear time. Furthermore, we compare the outcome of the non-myopic Cournot competition with that of the standard Cournot competition. Prices in the non-myopic game are lower and the firms, in total, produce more and have a lower aggregate utility. We also briefly consider a non-myopic version of Bertrand competition, and find that prices increase relative to the classical model. © 2013 Elsevier Inc.

This paper introduces a coalgebraic foundation for coinductive types, interpreted as sets of values and extended with set theoretic union. We give a sound and complete characterization of semantic subtyping in terms of inclusion of maximal traces. Further, we provide a technique for reducing subtyping to inclusion between sets of finite traces, based on approximation. We obtain inclusion of tree languages as a sound and complete method to show semantic subtyping of recursive types with basic types, product and union, interpreted coinductively.

We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair. We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness. A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness Θ( ˜ √ d) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Ω(log1/3 (d)) to Ω(log d). We also show that the competitive ratio of global random greedy against adaptive adversaries is Ω(d).

International audience; The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-hard cases, for example, on grid graphs and chordal graphs.

We study the mechanism design version of the unrelated machines scheduling problem, which is at the core of Algorithmic Game Theory and was first proposed and studied in a seminal paper of Nisan and Ronen. We give an improved lower bound of 1+φ≈2.618 on the approximation ratio of deterministic truthful mechanisms for the makespan. The proof is based on a recursive preprocessing argument which yields a strictly increasing series of new lower bounds for each fixed number of machines n≥4. © 2012 Springer Science+Business Media, LLC.

We study, from the perspective of competitive analysis, the trade-off between communication cost and delay cost, or simply the send-or-wait dilemma on a hierarchical rooted tree. The problem is an abstraction of the message aggregation problem on communication networks and an organizational problem in network hierarchies. We consider the most natural variant of the problem, the distributed asynchronous regime, and give tight (within a small additive constant) upper and lower bounds on the competitive ratio of the optimization problem. We also consider the centralized version of the problem, in which there is a central entity which remains updated about any incoming messages to the network and which can control the internal delivery of messages in the network. For the centralized setting, we combine a natural rent-tobuy strategy with prediction techniques to achieve the first constant competitive ratio algorithm for any non-trivial class of network topologies. © 2011 The Author(s).

We study time-dependent strategies for playing congestion games. The players can time their participation in the game with the hope that fewer players will compete for the same resources. We study two models: the boat model, in which the latency of a player is influenced only by the players that start at the same time, and the conveyor belt model in which the latency of a player is affected by the players that share the system, even if they started earlier or later; unlike standard congestion games, in these games the order of the edges in the paths affect the latency of the players. We characterize the symmetric Nash equilibria of the games with affine latencies of networks of parallel links in the boat model and we bound their price of anarchy and stability. For the conveyor belt model, we characterize the symmetric Nash equilibria of two players on parallel links. We also show that the games of the boat model are themselves congestion games. The same is true for the games of two players for the conveyor belt model; however, for this model the games of three or more players are not in general congestion games and may not have pure equilibria. © 2012 Springer-Verlag Berlin Heidelberg.

We study online profit-maximizing auctions for digital goods with adversarial bid selection and uniformly random arrivals. Our goal is to design auctions that are constant competitive with ; in this sense our model lies at the intersection of prior-free mechanism design and secretary problems. We first give a generic reduction that transforms any offline auction to an online one, with only a loss of a factor of 2 in the competitive ratio; we then present some natural auctions, both randomized and deterministic, and study their competitive ratio; our analysis reveals some interesting connections of one of these auctions with RSOP, which we further investigate in our final section. © 2010 Springer-Verlag.

We introduce the notion of coordination mechanisms to improve the performance in systems with independent selfish and non-colluding agents. The quality of a coordination mechanism is measured by its price of anarchy - the worst-case performance of a Nash equilibrium over the (centrally controlled) social optimum. We give upper and lower bounds for the price of anarchy for selfish task allocation and congestion games. © Springer-Verlag Berlin Heidelberg 2004.

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to 1+ √2 for 3 or more machines. © 2008 Springer Science+Business Media, LLC.

We consider the problem of maintaining a fixed number k of items observed over a data stream, so as to optimize the maximum value over a fixed number n of recent observations. Unlike previous approaches, we use the competitive analysis framework and compare the performance of the online streaming algorithm against an optimal adversary that knows the entire sequence in advance. We consider the problem of maximizing the aggregate max, i.e., the sum of the values of the largest items in the algorithm's memory over the entire sequence. For this problem, we prove an asymptotically tight competitive ratio, achieved by a simple heuristic, called partition-greedy, that performs stream updates efficiently and has almost optimal performance. In contrast, we prove that the problem of maximizing, for every time t, the value maintained by the online algorithm in memory, is considerably harder: in particular, we show a tight competitive ratio that depends on the maximum value of the stream. We further prove negative results for the closely related problem of maintaining the aggregate minimum and for the generalized version of the aggregate max problem in which every item comes with an individual window. © 2009 Springer Berlin Heidelberg.

The k-server problem is perhaps the most influential online problem: natural, crisp, with a surprising technical depth that manifests the richness of competitive analysis. The k-server conjecture, which was posed more than two decades ago when the problem was first studied within the competitive analysis framework, is still open and has been a major driving force for the development of the area online algorithms. This article surveys some major results for the k-server problem. © 2009 Elsevier Inc. All rights reserved.

In a system where noncooperative agents share a common resource, we propose the price of anarchy, which is the ratio between the worst possible Nash equilibrium and the social optimum, as a measure of the effectiveness of the system. Deriving upper and lower bounds for this ratio in a model where several agents share a very simple network leads to some interesting mathematics, results, and open problems.22The conference version of this work [Koutsoupias and Papadimitriou (1999) [17]] appeared a decade ago and it has been followed by a large amount of work on the concept of the price of anarchy (as witnessed by the extensive coverage in Nisan et al. (2007) [9]). In this journal version we tried to keep as much as possible the text of the original paper. There are, though, important changes because results that were substantially improved in the meantime are omitted. The other notable change is that here we use the term "price of anarchy" instead of the original term "coordination ratio". The use of the latter term faded away in the literature, being replaced by the term "price of anarchy" which was first introduced in Papadimitriou (2001) [18]. © 2009 Elsevier Inc. All rights reserved.

We study the mechanism design problem for scheduling unrelated machines and we completely characterize the decisive truthful mechanisms for two players when the domain contains both positive and negative values. We show that the class of truthful mechanisms is very limited: A decisive truthful mechanism partitions the tasks into groups so that tasks in each group are allocated independently of the other groups. Tasks in a group of size at least two are allocated by an affine minimizer and tasks in singleton groups by a task-independent mechanism. This characterization is about all truthful mechanisms, including those with unbounded approximation ratio. A direct consequence of this approach is that the approximation ratio of mechanisms for two players is 2, even for two tasks. In fact, it follows that for two players, VCG is the unique algorithm with optimal approximation 2. © 2008 Springer-Verlag Berlin Heidelberg.

We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in a seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound 1+φ ≈ 2.618 is a step towards the final resolution of this important problem. © Springer-Verlag Berlin Heidelberg 2007.

Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to design deterministic and randomized approximation algorithms. The mechanism design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the mechanism design version of the fractional variant of this problem. We give lower bounds for any fractional truthful mechanism. Our lower bounds also hold for any (randomized) mechanism for the integral case. In the positive direction, we propose a truthful mechanism that achieves approximation 3/2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For n machines, our mechanism achieves an approximation ratio of n+1/2. Motivated by the fact that all the known deterministic and randomized mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the task-independent algorithms. We give a lower bound of n+1/2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms. © 2010 ACM.

We present a simple model in which the worldwide web (www) is created by the interaction of selfish agents, namely document authors, users, and search engines. We show experimentally that power law statistics emerge very naturally in this context, and that the efficiency of the system has certain monotonicity properties. © Springer-Verlag Berlin Heidelberg 2005.

We study the online matching problem when the metric space is a single straight line. For this case, the offline matching problem is trivial but the online problem has been open and the best known competitive ratio was the trivial Θ(n) where n is the number of requests. It was conjectured that the generalized Work Function Algorithm has constant competitive ratio for this problem. We show that it is in fact Ω(log n) and O(n), and make some progress towards proving a better upper bound by establishing some structural properties of the solutions. Our technique for the upper bound doesn't use a potential function but it reallocates the online cost in a way that the comparison with the offline cost becomes more direct. © Springer-Verlag 2004.

The k-server problem is one of the most fundamental online problems. The problem is to schedule k mobile servers to visit a sequence of points in a metric space with minimum total mileage. The k-server conjecture of Manasse, McGeogh, and Sleator states that there exists a k-competitive online algorithm. The conjecture has been open for over 15 years. The top candidate online algorithm for settling this conjecture is the work function algorithm (WFA) which was shown to have competitive ratio at most 2k-1. In this paper, we lend support to the conjecture that WFA is in fact k-competitive by proving that it achieves this ratio in several special metric spaces: the line, the star, and all metric spaces with k+2 points. © 2004 Elsevier B.V. All rights reserved.

We study several interesting variants of the k-server problem. In the CNN problem, one server services requests in the Euclidean plane. The difference from the k-server problem is that the server does not have to move to a request, but it has only to move to a point that lies in the same horizontal or vertical line with the request. This, for example, models the problem faced by a crew of a Certain News Network trying to shoot scenes on the streets of Manhattan from a distance; for any event at an intersection, the crew has only to be on a matching street or avenue. The CNN problem contains as special cases two important problems: the BRIDGE problem, also known as the cow-path problem, and the weighted 2-server problem in which the 2 servers may have different speeds. We show that any deterministic online algorithm has competitive ratio at least 6+17. We also show that some successful algorithms for the k-server problem fail to be competitive. In particular, no memoryless randomized algorithm can be competitive. We also consider another variant of the k-server problem, in which servers can move simultaneously, and we wish to minimize the time spent waiting for service. This is equivalent to the regular k-server problem under the L∞ norm for movement costs. We give a 12k(k+1) upper bound for the competitive ratio on trees. © 2004 Elsevier B.V. All rights reserved.

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 expected latency through each link is at most a constant multiple of the optimum maximum latency had global regulation been available. For the case of uniform links it is known that all Nash equilibria belong to this class of strategies. We are interested in bounding the coordination ratio (or price of anarchy) of these strategies defined as the worst-case ratio of the maximum (over all links) expected latency over the optimum maximum latency. The load balancing aspect of the problem immediately implies a lower bound ω (ln m/ln ln m) of the coordination ratio. We give a tight (up to a multiplicative constant) upper bound. To show the upper bound, we analyze a variant of the classical balls and bins problem, in which balls with arbitrary weights are placed into bins according to arbitrary probability distributions. At the heart of our approach is a new probabilistic tool that we call ball fusion; this tool is used to reduce the variant of the problem where balls bear weights to the classical version (with no weights). Ball fusion applies to more general settings such as links with arbitrary capacities and other latency functions.

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 its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its 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 Nash equilibrium, constructing a Nash equilibrium with given support characteristics, constructing the worst Nash equilibrium (the one with maximum social cost), constructing the best Nash equilibrium (the one with minimum social cost), or computing the social cost of a (given) Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results (both as NP-hardness and #P-completeness 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. © 2002 Springer-Verlag Berlin Heidelberg.

We develop a general duality-theory framework for revenue maximization in additive Bayesian auctions. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. We demonstrate the power of the framework by applying it to a multiple-good monopoly setting where the buyer has uniformly distributed valuations for the items, the canonical long-standing open problem in the area. We propose a deterministic selling mechanism called Straight-Jacket Auction (SJA) which we prove to be exactly optimal for up to 6 items, and conjecture its optimality for any number of goods. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal mechanism itself; as a result, SJA is defined by natural geometric constraints.