February 2, 2006 - "Games, Networks, and Algorithms"
Christos Papadimitriou
Abstract
The Internet is the first computational artifact that was not designed, but emerged from the interaction of many agents. As a result, it is the first subject in Computer Science that must be approached with the same puzzled humility with which other sciences approach the universe, the cell, the brain, the market. Since the Internet is both the result and the theater of the interaction of selfish agents, mathematical economics should be relevant to its study. Conversely, the Internet has enabled new kinds of interactions and markets, and in this sense it is a challenge to that field. In recent years we have seen an increasingly active interface, motivated and informed by the advent of the Internet, between the theory of games on the one hand, the theory of algorithms and complexity on the other, and both with networking. Even though this corpus of research is already quite extensive and diverse, one can identify in it at least three important themes: Understanding the computational complexity of the fundamental computational problems associated with games, such as finding Nash and other equilibria; this quest is arguably of fundamental value to game theory, and not just the result of the professional bias of a few computer scientists. There is also the field of algorithmic mechanism design, striving to devise computationally efficient methods for designing games whose equilibria are precisely the socially desirable outcomes (for example, that the person who has the highest personal appreciation for the item being auctioned actually wins the auction). Finally we have an ever-expanding family of problems collectively given the playful name "the price of anarchy," studying how much worse a system emerging from the spontaneous interaction of a group of selfish agents can be when compared with the ideal optimum design. This talk will review recent results and open problems in these areas.
March 29, 2006 - "Art|Sci: Between Blue Skies and Sobering Facts"
Victoria Vesna
Abstract
Victoria Vesna will present a few recent art | science collaborations that address nanotechnology dreams and nightmares, environmental effects on mental health and water as a source of life and reflection of our collective (un)conciousness. Working in between the amazing potential and fast pace changes of new sciences and technologies and the realities of our collective existence, she will discuss the challenges one faces when creating art in the world today.
June 8, 2006 - "Economics of Combinatorial Auctions"
Paul Milgrom
Abstract
Advances in computing technology have made it increasingly feasible to operate resource allocation mechanisms that entail solving combinatorial optimization problems. The so-called "pivot mechanism" is an auction procedure that has the desirable properties of selecting outcomes that are efficient according to the bidders' reported information and making it a dominant strategy for bidders to report their information truthfully. This lecture will describe the disadvantages of the pivot mechanism and highlight alternative designs that may perform better in practice.
August 3, 2006 - "Diffusion and Cascading Behavior in Complex Networks"
Jon Kleinberg
Abstract
The flow of information through a large social network can be thought of as unfolding with the dynamics of an epidemic: as individuals become aware of new ideas, technologies, fads, rumors, or gossip, they have the potential to pass them on to their friends and colleagues, causing the resulting behavior to cascade through the network. We will consider a collection of models for such phenomena proposed in the mathematical social sciences, as well as recent algorithmic work on the problem by computer scientists. Building on this, we discuss the implications of cascading behavior in a number of on-line settings, including the diffusion of topics among bloggers, the effect of ``word of mouth'' in the promotion of new products, and the influence of social networks in the growth of on-line communities.
October 5, 2006 - "Behavioral Graph Coloring"
Michael Kearns
Abstract
The pioneering work of Travers and Milgram in 1969 established the now-familiar folklore of "six degrees" of separation in natural social networks. More recently, researchers including Jon Kleinberg and Duncan Watts have explored the algorithmic aspects of how messages are forwarded in such networks. Perhaps the computer science view of this fascinating line of thought can be best summarized as follows: Using relatively local information, distributed human organizations can compute good approximations to the all-pairs shortest paths problem. What other sorts of distributed optimization problems can humans networks solve?
In this talk, he will describe the preliminary but thought-provoking findings of a series of behavioral experiments we have been performing at Penn. Human subjects attempt to perform distributed graph coloring using a system that controls network structure, information conditions, incentives, and a variety of other variables of interest. The experiments shed early light on whether such problems can be solved by human networks, under what conditions, and on what algorithms they seem to adopt.
December 12, 2006 - "Information Retrieval in Context"
Sue Dumais
Abstract
Most information retrieval technologies are designed to facilitate information discovery. However, much knowledge work involves finding and re-using previously seen information in the context of ongoing work activities. An overview of techniques that people currently use to support re-access will be presented, and usage experiences with the "Stuff I've Seen" desktop search prototype that provides unified access to a wide range of heterogeneous information that a person has previously encountered (email, web pages, files, news, appointments) will be summarized. Key finding include the importance of time and people as retrieval cues, and the importance of metadata in supporting interactive retrieval. Alternative presentation techniques that leverage rich contextual cues such as timelines and memory landmarks are promising alternatives to the long ranked lists of search results that we are all familiar with. Richer personalized and contextualized information retrieval capabilities can also supported using this infrastructure.
Big Thinkers Archives
2008 Calendar of Events
2007 Calendar of Events
Video