Location: We meet in the Gates 4B lobby, also known as the theory lounge.
Mailing List: thseminar@cs.stanford.edu. Email shaddin to sign up.
Contact: Shaddin Dughmi (shaddin at cs dot stanford dot edu)
Food: Wendy usually choses the food at her discretion. However, the speaker may suggest a preference to Wendy for the day of their talk ahead of time.
For previous quarter schedules see here.
We consider atomic congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non-cooperative and each wishes to follow strategies that minimize her own latency with no regard to the global optimum. In this talk, we discuss the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomic congestion games with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestion games by forcing players to follow strategies where the total latency suffered is within a factor of $2$ of the minimum possible; this result is tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs.
Boolean functions that only depend on a small but unknown subset of the variables (also known as juntas) play an important role in several areas such as learning theory, complexity theory, and social choice theory. In recent years, researchers have started to study algorithms that identify the relevant variables of such functions f from random examples (x,f(x)). In this talk, I will introduce a greedy algorithm for this learning task and present a characterization of the functions for which it is successful. This characterization is based on a property of the Fourier spectrum of the functions. If time permits, I will also talk about extensions to learning with noise in the variable and function values and present some open problems for the general junta learning problem.
In many real-world settings, strategic agents are instructed to follow best-reply or better-reply dynamics (economic markets, Internet protocols, etc.). Such settings give rise to many questions: Will these dynamics converge or go on indefinitely? Will they converge quickly? What happens in distributed and asynchronous settings in which communication between players may be delayed or lost? Is it in the best interest of the agents to follow such dynamics? We explore the answers to these questions in the context of two classes of games for which pure Nash equilbiria always exists: Potential games and dominance-solvable games. In particular, we characterize a subclass of games for which we prove that best-reply dynamics are not only guaranteed to converge in asynchronous settings, but are (ex-post-Nash) incentive-compatible. We provide several examples of such games: stable-roommates problems, network- routing games, first-price auctions, cost-sharing mechanisms, and congestion-control games.
Based on joint works with Noam Nisan, Michael Schapira and Aviv Zohar, and on discussions with Tim Roughgarden.
Counting might seem to be a simple task, but it is no longer simple when millions of quantities are counted at the same time, and when increments happen every few nano-seconds. These are the requirements of network per-flow counters, where each "flow", consisting of a stream of packets, is the quantity to be counted. There are two problems here: 1. Which counter should an incoming packet increment? There needs to be a perfect hash function, or a table that keeps track of flow-to-counter association and can be accessed within a few nano-seconds. 2. Fast memories are expensive. The millions of counters and the table mentioned in 1 will require an infeasible amount of fast memories. We present a counter architecture, called Counter Braids, inspired by sparse random-graph codes. Counter Braids solves both problems by "braiding" a hierarchy of counters with random graphs, hence compressing while counting. We prove that Counter Braids, with an optimal decoder, has an asymptotic compression rate matching the information theoretic lower bound. For implementation, we present a low-complexity, analyzable message passing decoding algorithm, which can recover flow sizes with vanishing error at link speed. The topic is thematically related to graphical models, sparse random graph codes and compressed sensing.
Joint work with: Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar and Abdul Kabbani
Web search engines perform two basic tasks: they acquire Web pages via crawling, and present lists of pages and advertisements in response to user search queries. Given the gigantic size of the Web these tasks can be viewed as constrained optimization problems. On the acquisition side the constraint is on the crawling resources, while on the presentation side, the constraint is on user attention: users cannot be expected to sift through large amounts of content. Furthermore, some parameters needed to solve these optimization problems may or may not be known leading to the offline and online versions of the problems. In this talk we will look at these optimization problems. In particular, we will focus on the online presentation of advertisements where the unknown parameters are the ad quality values. I will present a method of simultaneously estimating unknown parameters and exploiting current estimates. Our method extends and adapts well-known "Bandit" models from Machine Learning.
We describe a simple distributed algorithm for a class of convex optimization problems. The algorithm is based on the application of iterative gradient ascent to a suitable dual problem. It requires an approximate summation subroutine, and produces an approximate solution to the optimization problem.
This is joint work with Tim Roughgarden and Devavrat Shah.
We consider the problem of selecting individuals in the current population in Genetic Algorithms for crossover to find a solution of high fitness of a given combinatorial optimization problem. Many schemes has been considered in literature as possible selection strategies, such as Roulette-wheel selection, Windowing, Exponential reduction or Linear transformation. It is shown that if one wishes to maximize any linear function of the final state probabilities, e.g. the fitness of the best individual of the final population, then the best distribution for selecting individuals is each generation is a rectangular distribution over the individuals sorted by their fitness values.
Carbon nanotubes are a promising technology for producing more efficient circuits. Circuit design for carbon nanotube circuits presents different challenges from classical circuits, requiring different design techniques. In particular, carbon nanotubes may not assemble in the intended directions so circuits must be robust to certain types of errors. In this talk, we formulate an abstract model of carbon nanotube circuits and express several natural optimization problems. We show that these problems are hard to approximate in general and then present ways to produce large improvements for important classes of circuits such as XOR and plurality.
joint work with Anindya De and Ashish Goel