NSF Award Search: Award # 1101717 - ICES: Large: Collaborative Research: Towards Realistic Mechanisms: statistics, inference, and approximation in simple Bayes-Nash implementation

Award Abstract # 1101717

ICES: Large: Collaborative Research: Towards Realistic Mechanisms: statistics, inference, and approximation in simple Bayes-Nash implementation

NSF Org:	CCF Division of Computing and Communication Foundations
Recipient:	NORTHWESTERN UNIVERSITY
Initial Amendment Date:	July 8, 2011
Latest Amendment Date:	July 8, 2011
Award Number:	1101717
Award Instrument:	Standard Grant
Program Manager:	Tracy Kimbrel CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering
Start Date:	September 1, 2011
End Date:	August 31, 2016 (Estimated)
Total Intended Award Amount:	$333,327.00
Total Awarded Amount to Date:	$333,327.00
Funds Obligated to Date:	FY 2011 = $333,327.00
History of Investigator:	Jason Hartline (Principal Investigator) hartline@eecs.northwestern.edu
Recipient Sponsored Research Office:	Northwestern University 633 CLARK ST EVANSTON IL US 60208-0001 (312)503-7955
Sponsor Congressional District:	09
Primary Place of Performance:	Northwestern University 633 CLARK ST EVANSTON IL US 60208-0001
Primary Place of Performance Congressional District:	09
Unique Entity Identifier (UEI):	EXZVPWZBLUE8
Parent UEI:
NSF Program(s):	Inter Com Sci Econ Soc S (ICE)
Primary Program Source:	01001112DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s):	7924
Program Element Code(s):	805200
Award Agency Code:	4900
Fund Agency Code:	4900
Assistance Listing Number(s):	47.070

ABSTRACT

Mechanism design lays the economic foundations for the design and analysis of economic institutions, social and computer protocols, service provisioning, and other applications where participants may act selfishly in their own best interest. A common paradigm for real-world mechanism design is trial and error: a mechanism is proposed, it is executed, then changes are made to it based on its performance. In order to make these changes an econometric analysis must be undertaken, i.e., the participants' actions in the mechanism (assumed to be in equilibrium) must be reverse engineered to obtain the participants' preferences. Using these inferred preferences, potential changes to the mechanism can be evaluated and ranked. While mechanism design theory for the most part relies on knowledge of the market, real world mechanisms tend to do some market analysis on the fly. The PIs research will combine econometric inference with mechanism design theory to investigate the econometric properties of mechanisms and design mechanisms that are simultaneously good at market analysis and exploiting that information to attain an objective specified by the mechanism designer.

This research program will introduce econometric techniques to computer science and will bring together topics from computer science and economics that have yet to be studied together. For example, these issues are very important in practice, especially in the rapidly growing areas of sponsored search and targeted display advertising. Auction mechanisms have been deployed for pricing and placement of advertisements and a major challenge is in adjusting the mechanisms in response to past data.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Chawla and Hartline "Auctions with Unique Equilibrium" ACM Conference on Electronic Commerce , 2013

Chawla, Hartline, Nekipelov "A/B Testing of Auctions" ACM Conference of Electronic Commerce , 2016

Chawla, Hartline, Nekipelov "Mechanism Design for Data Science" ACM Conference on Electronic Commerce , 2014

J Hartline, V Syrgkanis, E Tardos "No-Regret Learning in Bayesian Games" Advances in Neural Information Processing Systems , 2015

S Alaei, J Hartline, R Niazadeh, E Pountourakis, Y Yuan "Optimal auctions vs. anonymous pricing" IEEE Symposium on Foundations of Computer Science , 2015

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

This project develops data-driven methods that enable a principal to adjust the parameters of an auction so as to optimize its performance, i.e., for "mechanism redesign". We study a paradigmatic family of auctions and develop a method for counterfactual inference that allows the equilibrium revenue or welfare of one auction in the family to be estimated from the equilibrium bids in another. One application of this method is a framework for A/B testing of auctions, a.k.a., randomized controlled trials, wherein an auctioneer can compare the revenue of auctions A and B. Another application is in instrumented optimization where we identify sufficient properties of an auction so that the revenue of any counterfactual auction can be estimated from equilibrium bids of the former; we then optimize revenue over auctions with these properties.

Intellectual Merit:

The main technical contribution of this work is a method for counterfactual revenue estimation: given two auctions we define an estimator for the equilibrium revenue of one from equilibrium bids of the other. Our estimator has a number of appealing properties that contrast with the standard econometric approach to inference in auctions. In the standard approach, first the value distribution is inferred from bids of the first auction using equilibrium analysis, and then the estimated value distribution is used to calculate the expected equilibrium revenue of the second auction. To infer the value distribution, the standard approach employs estimates of the derivative of the bid function via an estimator that typically must be tuned to trade-off bias and variance using assumptions on the bid distribution. In contrast, our method estimates revenue directly from the bids and our estimator requires no distribution dependent tuning. Our method is statistically efficient with estimation error proportional to one over the square root of the number of observed bids.

Broader Impact:

In 2015 the PIs organized the first Workshop on Algorithmic Game Theory and Data Science in conjunction with the ACM Conference on Economics and Computation (EC 2005), prominently featuring work on this project. The workshop received a huge amount of attention and has led to this area receiving a considerable amount of focus from researchers in the field.

Our results can be applied to problems in online market place design of, for example, Uber, Zillow, Booking.com, Google, etc. Results from this proposal have been presented to research groups at technology companies like these and have played an important role in collaboration with these companies.

Last Modified: 12/14/2016
Modified by: Jason D Hartline

Please report errors in award information by writing to: awardsearch@nsf.gov.

Success

Error