CAREER: Information Elicitation in Algorithmic Economics and Machine Learning

A wide variety of important problems, from designing self-driving cars to forecasting the spread of a disease, rely on making and evaluating predictions. These problems in turn rely on loss functions, which are mathematical tools to measure prediction (in)accuracy. Well-designed loss functions can guide both computers and humans in making accurate predictions.

In machine learning, a branch of artificial intelligence, computers make predictions by choosing the predictive model that best fits historical data, as judged by a loss function. Yet a general framework to design and analyze loss functions is lacking for many common machine learning tasks. In economics, an efficient information economy is crucial to facilitate the trade of data, predictions, and other information.

Unfortunately, current economic mechanisms fall short for settings involving competition and collaboration, which are vitally important to a healthy economy. This project will to address these shortcomings, by (a) developing a general framework to design and analyze loss functions in machine learning, and (b) designing collaborative and competitive mechanisms to facilitate markets for predictions, data, and beyond.

These results will impact a number of key economic sectors as our society continues to progress toward an information economy.

In supervised machine learning, algorithms employ surrogate loss functions, which are easier to optimize than the target loss but still solve the same problem. Despite their prevalence and importance, the literature lacks a general framework to systematically design and analyze surrogate losses. Such a framework is especially lacking in structured prediction settings, as in computer vision, natural language processing, and bioinformatics, where one tries to predict an object like a tree or sequence.

Using ideas from economics, the project will develop a new framework to study and design convex surrogate losses, with the potential for sharper and more general results. Using techniques from discrete convex geometry, this framework readily applies to polyhedral (piecewise linear convex) losses, a popular class in structured prediction. In algorithmic economics, information elicitation mechanisms, which exchange information for money, are a promising foundation for an information economy.

The project will study a variety of new mechanisms, and develop new analyses of existing mechanisms, to increase efficiency and incentive-compatibility. Among these settings are machine learning competitions, forecasting competitions, and a new mechanism to fund general collaborative projects. These settings address several central questions about multi-agent elicitation mechanisms, some of which have been open for over a decade.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.