Tutorial given at the 17th ACM conference on Economics and Computation (EC '16), July 25th 2016. Organizers: Rafael Frongillo (CU Boulder) and Bo Waggoner (Harvard --> UPenn -> MSR NY -> CU Boulder) See our original proposal here. Part 1: Foundations of elicitationAbstract: Elicitation is the study of contracts to exchange information for money. For example, how can you incentivize an agent to truthfully report a probability distribution for a future event? We'll cover the beautiful theory of proper scoring rules, based on properties of convex functions and Bregman divergences, their applications in algorithmic game theory, and connections to mechanism design. We will then give the basics of property elicitation, where one is interested in a statistic (e.g. the mean, variance, mode) of an agent's belief.Part 2: Connections to machine learningAbstract: How does the loss function determine the model selected by regression? We'll place this question in the context of elicitation, where loss functions correspond to scoring rules. The convexity-based paradigm from Part 1 applies here, and in particular we will explore property elicitation in this context. We'll conclude with more advanced topics such as elicitation complexity, which asks the number of parameters needed to elicit a given statistic, and survey open problems in the field.References Proper scoring rules(1950) Glenn W. Brier. Verification of forecasts expressed in terms of probability. Monthly Weather Review. (1952) I. J. Good. Rational Decisions. Journal of the Royal Statistical Society. (1956) John McCarthy. Measures of the value of information. PNAS. (1971) Leonard J. Savage. Elicitation of personal probabilities and expectations. (2007) Tilman Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. AGT applications list(peer prediction) Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback. Management Science, 2005. (and a large follow-up literature) (complexity) Pablo Daniel Azar and Silvio Micali. Rational proofs. STOC, 2012. (prediction markets) Robin Hanson. Combinatorial information market design. Information Systems Frontiers, 2003. (and a large literature) General TruthfulnessRafael M. Frongillo and Ian A. Kash. General truthfulness characterizations via convex analysis. WINE, 2014. Multiple Choice / Finite Properties(2009) Nicolas Lambert and Yoav Shoham. Eliciting truthful answers to multiple-choice questions. EC. (2014) Rafael M. Frongillo and Ian A. Kash. General truthfulness characterizations via convex analysis. WINE. See also: (1987) Franz Aurenhammer. A criterion for the affine equivalence of cell complexes in R^d and convex polyhedra in r^(d+1). Discrete & Computational Geometry. (1987) Franz Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM Journal on Computing. Linear Properties (Expectations)(2015) Rafael M. Frongillo and Ian A. Kash. Vector-valued property elicitation. COLT. Continuous one-dimensional properties(2008) Nicolas S. Lambert, David M. Pennock, and Yoav Shoham. Eliciting properties of probability distributions. EC. Indirect Elicitation(2008) Nicolas S. Lambert, David M. Pennock, and Yoav Shoham. Eliciting properties of probability distributions. EC.(2015) Tobias Fissler, Johanna F. Ziegel. Higher order elicitability and Osband's principle. preprint. (2015) Rafael M. Frongillo and Ian A. Kash. Vector-valued property elicitation. COLT. Risk measures(1999) Philippe Artzner, F. Delbain, JM Eber, and D. Heath. Coherent measures of risk. Mathematical finance. (2014) R. T. Rockafeller, J. O. Royset, S. I. Miranda. Superquantile regression with applications to buffered reliability, uncertainty quantification, and conditional value-at-risk. European Journal of Operations Resarch. (2015) Tobias Fissler, Johanna F. Ziegel. Higher order elicitability and Osband's principle. Machine Learning(2006) Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, Classification, and Risk Bounds. Journal of the American Statistical Association. (2015) Arpit Agarwal and Shivani Agarwal. On consistent surrogate risk minimization and property elicitation. COLT. |