New York Computer Science and Economics Day (NYCE)

NYCE 2008 is the first annual NY Computer Science and Economics day held at The New York Academy of Sciences.

The goal of the meeting is to bring together researchers in the larger NY metropolitan area with interests in computer science, economics, marketing, and business, and a common focus in understanding and developing the economics of Internet activity.

Organizers

• Anindya Ghose (NYU Stern)
• S. Muthu Muthukrishnan (Google, Inc.)
• David Pennock (Yahoo, Inc.)
• Sergei Vassilvitskii (Yahoo, Inc.)

Agenda

Abstracts

The Complexity of Nash Equilibria in Large Games
Constantinos Daskalakis, Microsoft Research

The Nash equilibrium is one of Game Theory's most important notions of equilibrium. But, how credible would it be as a framework for behavior prediction in large games, e.g., the Internet, if there were no dynamics by which the game play could converge to such an equilibrium, within a non-prohibitively large number of iterations? Motivated by this question we study the computational complexity of the Nash equilibrium.

We show first that finding a Nash equilibrium is an intractable problem, which makes it unlikely that there are efficient dynamics for it. Since by Nash's theorem an equilibrium is guaranteed to exist, the Nash equilibrium belongs to the class of problems in NP which always have a solution, and previous work establishes that such problems are unlikely to be NP-complete. We show instead that the problem is as hard as any fixed-point computation problem in a precise technical sense, which is motivated by simplicial algorithms for the computation of fixed points.

In view of this hardness result, we discuss algorithms for computing approximate Nash equilibria and provide efficient algorithms for a large class of multi-player games, called anonymous, in which the players' utilities, although potentially different, do not differentiate among the identities of the other players. Examples of such games arise in congestion, social interactions, and certain auction settings.
(Based on joint work with Christos Papadimitriou and partially Paul Goldberg)

Modeling Multiple Relationships in Online Social Networks
Asim Ansari, Columbia University

Companies are increasingly becoming interested in harnessing the potential of online social networks for marketing purposes. The availability of data from online networks has renewed the interest in modeling the antecedents and consequences of relationship formation within such social networks. Social networks comprise of individuals or firms that are connected to each other via many distinct relationships. These relationships can differ along multiple dimensions, and a proper understanding of the nature of these connections is an important early step toward the effective use of social networks by marketers. In this paper we propose an integrated modeling framework for simultaneously modeling multiple relationships of different types. Our modeling approach accommodates both the directionality and intensity of network connections and in particular, we show how sparse network connections can be accommodated when modeling weighted relationships. The simultaneous analysis of multiple relationships allows one to understand whether these relationships share common determinants and whether actors in the network share similar roles across the relationships. We develop a hierarchical Bayesian framework based on MCMC methods for model inference and then analyze data from an online social network of music artists. In our application we model friendship, communication and music download relationships among these artists.

Market Design in Theory and Practice: Auctions for Sponsored Links in Online Advertising
Susan Athey, Harvard University

The revenue generated by advertising provides incentives for online publishers to create high-quality content. The problem of allocating advertisements to online page views is extraordinarily complex. On search engines, millions of unique phrases are entered by users each month, and hundreds of thousands of advertisers would like to place advertisements there. As with the Yellow Pages, advertisements are an important source of information for consumers. Over the past ten years, the market for search advertising evolved into a real-time auction that shares some features with an "ideal" auction that theory predicts would be effective. The design of the auction affects the quality of matching of advertisements to consumers, the search costs expended by consumers, the profit to the advertisers, and the extraction of revenue by the search engine. Over time, search engines have become increasingly sophisticated in pricing, and the design has become increasingly complex, with real-world experiences confirming existing theory and motivating new theory. A vibrant cross-disciplinary subfield surrounding the design of these auctions has emerged, combining theory, empirical analysis, field experiments, and the design of algorithms.

Expressiveness in Mechanisms and its Relation to Efficiency: Our Experience from $40 Billion of Combinatorial Multi-Attribute Auctions, and Recent Theory
Tuomas Sandholm, Carnegie Mellon University

A recent trend (especially in electronic commerce) is higher levels of expressiveness in the mechanisms that mediate interactions such as auctions, exchanges, catalog offers, voting systems, matching of peers, and so on. Participants can express their preferences in drastically greater detail than ever before. In many cases this trend is fueled by modern algorithms for winner determination that can handle the richer inputs.  But is more expressiveness always a good thing? What forms of expressiveness should be offered?

In this talk, I will first report on our experience from over $40 billion of combinatorial multi-attribute sourcing auctions. Then, I will present recent theory that ties the expressiveness of a mechanism to an upper bound on efficiency in a domain-independent way in private-information settings. Time permitting, I will also discuss theory and experiments on applying expressiveness to ad auctions, such as sponsored search and real-time banner ad auctions with temporal span and complex preferences.