Computer Science Department
School of Computer Science, Carnegie Mellon University


Foundation of Machine Learning,
by the People, for the People

Nika Haghtalab

Ph.D. Thesis

August 2018


Keywords: Machine learning, Algorithmic economics, Theory of Computer Science, Mechanism design, Stackelberg Games, Auction Design, No-regret Learning, Collaborative learning, Learning from the crowd, Kidney Exchange

Typical analysis of machine learning algorithms considers their outcome in isolation from the effects that they may have on the process that generates the data or the entity that is interested in learning. However, current technological trends mean that people and organizations increasingly interact with learning systems, making it necessary to consider how these interactions change the nature and outcome of learning tasks.

The field of algorithmic game theory has been developed in response to the need for understanding interactions in large interactive systems in the presence of strategic entities, such as people. In many cases, however, algorithmic game theory requires an accurate model of people's behavior. In the applications of machine learning, however, much of this information is unavailable or evolving. So, in addition to the challenges involved in algorithmic game theory, there is a need to acquire the information without causing undesirable interactions.

In this thesis, we present a view of machine learning and algorithmic game theory that considers the interactions between machine learning systems and people. We explore four lines of research that account for these interactions: learning about people, where we learn optimal policies in game-theoretic settings, without an accurate behavioral model and in ever changing environments, by interacting with and learning about people's preferences; learning from people, where we manage people's expertise and resources in data-collection and machine learning; learning by people, where people can interact with each other and collaborate together to effectively learn related underlying concepts; and learning for people, where machine learning is used to benefit people and society, in particular, by creating models that are resilient to uncertainties in the environment.

Thesis Committee:
Avrim Blum (Co-Chair)
Ariel D. Procaccia (Co-Chair)
Maria-Florina Balcan
Tim Toughgarden (Stanford University)
Robert Schapire (Microsoft Research)

Srinivasan Seshan, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

300 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by