^November December – 2006 ^January

The emergence of the Internet has initiated a radical shift of focus of our thinking about computational networked systems. While traditional system design assumes that all participants behave according to the intentions of the system designers, in reality, computer networks are built, operated and used by multiple users with diverse sets of interests. Hence, Internet protocols must be explicitly designed to work with interacting strategic individuals. Recently, there has been a growing interest in using tools from game theory and mechanism design to tackle incentive-related problems in these complex environments. In the first part of the talk, I will give an overview of the field, and demonstrate the inherent tension between individual rationality and collective welfare in computer networks through prime examples from my research. In the second part of the talk, I will concentrate on the inefficiency that is incurred due to users' selfishness in network routing, network formation and multicast transmission. In contrast to the common measure of "price of anarchy", which quantifies the loss incurred due to both selfishness and lack of coordination, we isolate the inefficiency originated from selfishness from that originated from lack of coordination. We show that coordination among selfish users can significantly improve the efficiency of the studied applications.

Topological persistence measures the "persistence" of topological features, such as connected components, tunnels and cavities, within the sublevel sets, ${x: f(x) < c}$, of a scalar field. The topological persistence of a feature is stable under small perturbations of the scalar field. Interval persistence is a generalization of topological persistence which better represents topological features in level sets, ${x: f(x) = c}$, gives a fuller matching of critical values, and is the appropriate setting for a stability theorem for critical points under small perturbations of scalar fields.

I will give an introduction to topological persistence and then discuss interval persistence, its relationship to topological persistence, and stability and matching of critical points under interval persistence. Joint work with Dr. Tamal Dey and Dr. Yusu Wang from The Ohio State University. Dr. Rephael Wenger is an associate professor in the Department of Computer Science and Engineering at The Ohio State University. He works on computational geometry, geometric algorithms and geometric modelling, particularly as they apply to graphics, visualization and biomedical image processing.

Issues on the border of Computer Science and Economics have drawn much recent research attention, mostly motivated by the Internet, where selfish agents interact in computational settings. I discuss various issues on this borderline, and in particular the problem of market design under computational constraints and in the presence of selfish agents with private preferences. To overcome strategic behavior, the predominant approach in the literature is to construct dominant strategy truthful mechanisms, but unfortunately not every approximation algorithm can be used for such a construction. In this talk I present a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any approximation algorithm to a dominant-strategy ascending mechanism. I also show how approximation can be achieved when agents do not have dominant strategies, using our new notion of "Algorithmic Implementation in Undominated Strategies". These results are taken from a joint research with Ron Lavi and Elan Pavlov.

During the last two years, I took part in a project at NASA Ames Research Center that attempts to improve the technology used to do activity planning for the Mars Exploration Rovers, and rovers for future NASA missions. The Mars rovers are autonomous vehicles that roam around the surface of Mars looking for interseting data. They can take pictures and perform various experiments. They have to operate autonomously for long strecthes at a time. These rovers are considered a great success story, but they are actually idle a great portion of the time. In this talk I'll explain the problems with current technology used to select their plans, and the work we did on devising planning algorithms that can come up with much better plans. This is joint work with a large group at NASA headed by Nicolaus Meuleau.