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.

This is a free event. Advance registration is strongly encouraged. Details

Organizers

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

Schedule

8:30 AM – Registration Check-in and Coffee
9:00 AM – Constantinos Daskalakis, Microsoft Research
10:00 AM – Asim Ansari, Columbia University
11:00 AM – Coffee Break
11:30 AM – Susan Athey, Harvard University
12:30 PM – Lunch (On Own)
2:30 PM – Rump Session –
Christina Aperjis, Nikolay Archak,
Jacomo Corbo, Gagan Goel,
Aaron Jaggard, Sampath Kannan,
Sebastian Lehaie, Lingfang Ivy Li,
Evdokia Nikolova, Zhengzheng Pan and
Vytautas Valancius
3:30 PM – Coffee Break
4:00 PM – Tuomas Sandholm, Carnegie Mellon University
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.