
New York Computer Science and Economics Day
Friday, October 15, 2010
NYCE 2010 is the third annual New York Computer Science and Economics Day. The goal of the meeting is to bring together researchers in the larger New York metropolitan area with interests in Computer Science, Economics, Marketing and Business and a common focus in understanding and developing the economics of internet activity. Examples of topics of interest include theoretical, modeling, algorithmic and empirical work on advertising and marketing based on search, user-generated content, or social networks, and other means of monetizing the internet.
Organizing Committee
Christian Borgs
Microsoft
Michael Kearns
University of Pennsylvania
Sebastien Lahaie
Yahoo
Vahab Mirrokni
Sponsors
Past NYCE Meetings
For a complete list of sponsors, please click the Sponsor tab.
Agenda
*Presentation times are subject to change.
Friday, October 15, 2010 | |
8:30 AM | Registration and Refreshments |
9:00 AM | Computational Aspects of Equilibria |
10:00 AM | Optimal Dynamic Mechanism Design with Minimal Information Disclosure |
10:40 AM | Break |
11:10 AM | Portfolios from Sorts |
12:10 PM | Lunch (on-site) |
1:50 PM | Rump Session Tanmoy Chakraborty (University of Pennsylvania), Market Making in Mean Reversion Price Models Xi Chen (Columbia University), A Complexity View of Markets with Social Influence Sanmay Das (Rensselaer Polytechnic Institute), Comparing Prediction Market Structures Bhaskar DasGupta (UIC), Stochastic Budget Optimization in Internet Advertising Vasilis Gkatzelis (New York University), Coordination Mechanisms for Weighted Sum of Completion Times in Machine Scheduling Gagan Goel (Google), Single-Parameter Combinatorial Auctions with Partially Public Valuations Sharad Goel (Yahoo! Research), Birds of a Feather Shop Together: Predicting Consumer Behavior with Social Networks Mohammad T. Irfan (Stony Brook University), Influence Games with Application to Identifying the Most Influential Nodes in Social Networks Beibei Li (NYU), Designing Ranking Systems for Hotels on Travel Search Engines by Mining User-Generated and Crowd-Sourced Content Azarakhsh Malekian (Northwestern University), Competitive Equilibrium for Unit Demand Buyers with Non-quasi-linear Utilities Soumya Sen (University of Pennsylvania), The Impact of Resource Reprovisioning on Network Infrastructure Choice Sven Seuken (Harvard University), Market Design meets User Interface Design |
2:50 PM | Break |
3:20 PM | Converting any Algorithm into an Incentive-Compatible Mechanism |
4:00 PM | Mechanism Design Double Feature |
5:00 PM | End of Program |
Speakers
Keynote Speakers
Robert Almgren, PhD
New York University and Quantitative Brokers
Hal Varian, PhD
University of California, Berkeley and Google
Mihalis Yannakakis, PhD
Columbia University
Speakers
Sham Kakade, PhD
University of Pennsylvania
Robert Kleinberg, PhD
Cornell University
Sponsors
Promotional Partners
Baruch College Financial Engineering Program
Abstracts
Computational Aspects of Equilibria
Mihalis Yannakakis, PhD, Columbia University
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; price equilibria in markets; optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysis of the evolution of various types of dynamic stochastic models. It is not known whether these problems can be solved in polynomial time. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles and the corresponding complexity classes that capture them; the effect on the complexity of the underlying computational framework; and the relationship with other open questions in computation.
Optimal Dynamic Mechanism Design with Minimal Information Disclosure
Sham Kakade, PhD, University of Pennsylvania
Consider the problem of profit maximization (i.e. revenue-optimal dynamic mechanism design) in settings where an item is repeatedly sold over time. A central issue is how can the seller incentivize a buyer to reveal her (dynamically evolving) private information so as to maximize revenue.
We provide a simple optimal dynamic mechanism for rather general settings. The mechanism optimally balances exploration and exploitation, taking incentives into account. Furthermore, while the (abstract) optimal "direct" mechanism may collect arbitrarily complicated private statistics about the buyer, we provide a simple implementation which is both revenue optimal and has desirable privacy preserving properties. We also discuss applications to online ad auctions.
Joint work with: Ilan Lobel & Hamid Nazerzadeh
Portfolios from Sorts
Robert Almgren, PhD, New York University and Quantitative Brokers
Modern portfolio theory, initially developed by Markowitz in 1952 and much extended, gives us a rich and powerful framework for generating optimal investment portfolios. The classic theory requires that we supply precise numerical values for the expected returns of each asset, and a complete covariance matrix. In practice, managers do not have a complete set of expected return values, but they may have qualitative information or beliefs regarding the expected *relative* performance of various assets or subsets of the investment universe.
We present a method for portfolio optimization based on replacing expected returns with ordering information, that is, beliefs about the relative performance of different assets or sectors. We give a simple and economically rational definition of optimal portfolios that extends Markowitz' mean variance optimality condition in a natural way; in particular, our construction allows full use of covariance information. The formulation we develop is very general and is easily extended to a variety of cases, for example assets are divided into multiple sectors or there are multiple sorting criteria available.
Converting any Algorithm into an Incentive-compatible Mechanism
Robert Kleinberg, PhD, Cornell University
Does algorithm design become harder in the presence of incentive constraints? The theory of algorithmic mechanism design is largely founded on the presumption that the answer is affirmative, a presumption that has been rigorously confirmed under various interpretations of the question. This is unfortunate, since it would be very convenient if there existed generic procedures to convert any algorithm into an incentive-compatible mechanism with little or no computational overhead.
In this talk I will identify two broad settings in which such generic procedures exist. First, I will present a reduction that removes the computational overhead of computing payments in truthful mechanisms: it transforms any monotone allocation function into a randomized, truthful-in-expectation mechanism that evaluates the allocation function only once. Second, I will present a polynomial-time reduction transforming an arbitrary algorithm into a Bayesian incentive-compatible mechanism, given a suitable amount of information about the type distributions of agents.
The first result is joint work with Moshe Babaioff and Alex Slivkins; the second result is joint work with Jason Hartline and Azarakhsh Malekian.
Mechanism Design Double Feature
Hal Varian, PhD, University of California, Berkeley and Google
Ad Auctions Without Position Normalizers: How to design an incentive compatible sponsored search auction without using information about position clickthrough rates.
Approximate Implementation of Envy-Free Outcomes: Some thoughts about incentive-compatible mechanisms that provide approximate implementations of certain envy-free outcomes. Examples include second-degree price discrimination and competitive equilibria.
Travel & Lodging
Our Location
The New York Academy of Sciences
7 World Trade Center
250 Greenwich Street, 40th floor
New York, NY 10007-2157
212.298.8600
Hotels Near 7 World Trade Center
Recommended partner hotel:
The New York Academy of Sciences is a part of the Club Quarters network . Please feel free to make accommodations with Club Quarters on-line to save significantly on hotel costs.
Club Quarters Reservation Password: NYAS
Club Quarters, World Trade Center
140 Washington Street
New York, NY 10006
Phone: (212) 577-1133
Located on the south side of the World Trade Center, opposite Memorial Plaza, Club Quarters, 140 Washington Street, is just a short walk to our location.
Other hotels located near 7 WTC:
212.945.0100 |
212.693.2001 |
212.385.4900 |
212.269.6400 |
212.742.0003 |
212.232.7700 |
212.747.1500 |
212.344.0800 |