Search

Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced the whole of Life as we see it around us. There is a computational way to articulate the same amazement: "What algorithm could possibly achieve all this in a mere three and a half billion years?" In this paper we propose an answer: We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known in computer science to be surprisingly powerful and versatile. MWUA maximizes a tradeoff between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution.

Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range of public goods games have intractable equilibrium problems: The existence of pure Nash equilibria is NP-hard to decide, and mixed Nash equilibria are PPAD-hard to find. We define general utility public goods games, and prove a complexity dichotomy result for finding pure equilibria, and a PPAD-completeness proof for mixed Nash equilibria. Even in the divisible goods variant of the problem, where existence is easy to prove, finding the equilibrium is PPAD-complete. Finally, when the treewidth of the directed network is appropriately bounded, we prove that polynomial-time algorithms are possible. [ABSTRACT FROM AUTHOR]

We introduce a simple dynamic mechanism design problem in which the designer offers two items in two consecutive stages to a single buyer. The buyer's joint distribution of valuations for the two items is known, and the buyer knows the valuation for the current item, but not for the one in the future. The designer seeks to maximize expected revenue, and the mechanism must be deterministic, truthful, and ex-post individually rational. We show that finding the optimum deterministic mechanism in this situation — arguably one of the simplest meaningful dynamic mechanism design problems imaginable — is NP -hard. We also prove several positive results, including a polynomial-time linear programming-based algorithm for the revenue optimal randomized mechanism (even for many buyers and many stages). We prove strong separations in revenue between non-adaptive, adaptive, and randomized mechanisms, even when the valuations in the two stages are independent. [ABSTRACT FROM AUTHOR]

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as applicationspecific methods for computing multivariate expectations over product distributions. For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider. [ABSTRACT FROM AUTHOR]

We study a novel genre of optimization problems, which we call segmentation problems, motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several segments, so that the overall cost is optimized. We focus on two natural and interesting (but MAXSNP-complete) problems in this class, the HYPERCUBE SEGMENTATION PROBLEM and the CATALOG SEGMENTATION PROBLEM, and present approximation algorithms for them. We also present a general greedy scheme, which can be specialized to approximate any segmentation problem. [ABSTRACT FROM AUTHOR]

Presents information on the off-line version of the geometric Gallery Tour (GT) problem. Notations and preliminaries of the study; Solutions and extensions of the problem; How to design an on-line algorithm for finding an optimal route.

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics, and threshold phenomena. Recent work on heuristics and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and st-connectivity questions for the graph of solutions of Boolean formulas. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side—which includes but is not limited to all problems with polynomial-time algorithms for satisfiability—is in P for the st-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear; thus, diameter and complexity of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary. [ABSTRACT FROM AUTHOR]

Abstract: We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of any monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or “skyline”, queries [Kian-Lee Tan, Pin-Kwang Eng, Beng Chin Ooi, Efficient progressive skyline computation, in: VLDB, 2001, pp. 301–310; Wolf-Tilo Balke, Ulrich Güntzer, Jason Xin Zheng, Efficient distributed skylining for web information systems, in: EDBT, 2004. ]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions. [Copyright &y& Elsevier]

We prove complexity, approximability, and inapproximability results for the problem of finding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial algorithm that approximates the market equilibrium arbitrarily close when the number of goods is bounded and the utilities linear. We also show a communication complexity lower bound in a model appropriate for markets. Our result implies that the ideal informational economy of a market with divisible goods and unique optimal allocations is unattainable in general. [Copyright &y& Elsevier]

We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is an on-line algorithm, generalizing a well-known algorithm for finding a majority element, for identifying a set of at most 1/θ items that includes, possibly among others, all items with frequency greater than θ. [ABSTRACT FROM AUTHOR]

We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any ratio. In contrast, we give a dynamic programming algorithm which finds a subdivision into two parts with total perimeter at most that of the optimum bisection, such that the two parts have areas within epsilon of each other; the time is polynomial in the number of sides of the polygon, and 1/epsilon. When the polygon is convex, or if the parts are required to be connected, then the exact problem can be solved in quadratic time. [ABSTRACT FROM AUTHOR]

We present an extension of the Lin-Kernighan local search algorithm for the solution of the asymmetric traveling salesman problem. Computational results suggest that our heuristic is feasible for fairly large instances We also present some theoretical results which guided our design of the heuristic. [ABSTRACT FROM AUTHOR]

We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer's (or, in another version Kakutani's) fixed point theorem, the most sophisticated result in his era's topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of "the outcome of the game"—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. [ABSTRACT FROM AUTHOR]

In evolutionary biology, randomness has been perceived as a force that, in and of itself, is capable of inventing: mutation creates new genetic information at random across the genome which leads to phenotypic change, which is then subject to selection. However, in science in general and in computer science in particular, the widespread use of randomness takes a different form. Here, randomization allows for the breaking of pattern, as seen for example in its removal of biases (patterns) by random sampling or random assignment to conditions. Combined with various forms of evaluation, this breaking of pattern becomes an extraordinarily powerful tool, as also seen in many randomized algorithms in computer science. Here we show that this power of randomness is harnessed in nature by sex and recombination. In a finite population, and under the assumption of interactions between genetic variants, sex and recombination allow selection to test how well an allele will perform in a sample of combinations of interacting genetic partners drawn at random from all possible such combinations; consequently, even a small number of tests of genotypes such as takes place in a finite population favors alleles that will most likely perform well in a vast number of yet unrealized genetic combinations. This power of randomization is not manifest in asexual populations. [ABSTRACT FROM AUTHOR]

Abstract: In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Playing large games using simple strategies, in: EC, 2003], and no approximation better than is possible by any algorithm that examines equilibria involving fewer than strategies [Ingo Althöfer, On sparse approximations to randomized strategies and convex combinations, Linear Algebra and its Applications (1994) 199]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a -approximate Nash equilibrium in any 2-player game. For the more demanding notion of approximately well supported Nash equilibrium due to [Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, SIAM Journal on Computing (in press) Preliminary version appeared in STOC (2006)] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities or ), and that an approximation of is possible, contingent upon a graph-theoretic conjecture. Subsequent work extends the impossibility result of Ingo Althöfer’s paper, as mentioned above, to [Tomás Feder, Hamid Nazerzadeh, Amin Saberi, Approximating nash equilibria using small-support strategies, in: EC, 2007], making our -approximate Nash equilibrium algorithm optimal among the algorithms that only consider mixed strategies of sublogarithmic size support. Moreover, techniques similar to our techniques for approximately well supported Nash equilibria are used in [Spyros Kontogiannis, Paul G. Spirakis, Efficient algorithms for constant well supported approximate equilibria in bimatrix games, in: ICALP, 2007] for obtaining an efficient algorithm for 0.658-approximately well supported Nash equilibria, unconditionally. [Copyright &y& Elsevier]

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Scho¨ning (1999) proved that a close algorithm for k-SAT takes time (2−2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.).We describe a deterministic local search algorithm for k-SAT running in time (2−2/(k+1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms. [Copyright &y& Elsevier]