New York Computer Science and Economics Day

New York Computer Science and Economics Day

Friday, October 15, 2010

The New York Academy of Sciences

Presented By

 

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

Google

Sponsors

    Gold Sponsors



Past NYCE Meetings

NYCE Day 2009
NYCE Day 2008

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
Mihalis Yannakakis, PhD, Columbia University

10:00 AM

Optimal Dynamic Mechanism Design with Minimal Information Disclosure
Sham Kakade, PhD, University of Pennsylvania

10:40 AM

Break

11:10 AM

Portfolios from Sorts
Robert Almgren, PhD, New York University and Quantitative Brokers

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
Robert Kleinberg, PhD, Cornell University

4:00 PM

Mechanism Design Double Feature
Hal Varian, PhD, University of California, Berkeley and Google

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

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

Click here for directions.

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:

Embassy Suites Hotel

      212.945.0100

Millenium Hilton

212.693.2001

Marriott Financial Center

212.385.4900

Club Quarters, Wall Street

212.269.6400

Eurostars Wall Street Hotel

212.742.0003

Wall Street District Hotel

212.232.7700

Wall Street Inn

212.747.1500

Ritz-Carlton New York, Battery Park

212.344.0800