TGIF: Michael Albert on “From Dynamic Pricing to Dynamic Stackelberg Games: Going Beyond the No Learning Theorem”

From Dynamic Pricing to Dynamic Stackelberg Games: Going Beyond the No Learning Theorem

Abstract:

In this work, we study dynamic Stackelberg games, i.e. games in which a leader and a follower repeatedly interact, where the follower’s type is unknown and the follower is non-myopic. A natural question to ask is, can the leader learn the optimal strategy against the unknown follower through these repeated interactions? The No Learning Theorem from dynamic pricing, a particular type of dynamic Stackelberg game, would suggest that the leader cannot learn effectively from the follower. In contrast, we demonstrate, for the first time, that in general dynamic Stackelberg games, the leader can improve her utility through learning in repeated play. We also provide an algorithm based on a novel and compact mixed-integer linear program for finding the leader’s optimal dynamic policy. We also show that this dynamic policy continues to be nearly optimal even when allowing for the leader to have a larger strategy space, specifically if we permit communication between the leader and follower. Finally, we develop an algorithm to compute a Markovian policy for the leader that approximates the optimal policy while allowing for more efficient computation. Through simulations, we examine the efficiency, compared to static policies, and the runtime of the proposed algorithms.

Why is this work important for Data Science in Business?

Often, we are not merely analyzing data, we are also eliciting data from individuals. These individuals (or agents) may have strategic reasons to misrepresent their data. This puts a bound on both the kinds of things that we can learn from these strategic agents and the way in which we can use this data. The goal of this work is to, by examining some of the near hardest settings, develop tools to create strategies that achieve effective learning. While the tools presented are limited to relatively narrowly defined problems and computationally restricted to relatively small instances, we hope that they are a starting point to developing effective heuristics to learn effectively in these settings.

Questions for the audience:

In your work, is data generated by strategic agents? If so, what are the incentives of the data generators? 
While we assume very strong strategic agents that behave perfectly rationally in this work, how might we exploit boundedly rational agents or behavioral biases to learn effectively? 
For agents that are not behaving strategically, do potential consumers of their data have an ethical obligation to behave as if they are? I.e. should we restrict our use of data to settings and applications under which a strategic agent would rationally allow us to learn effectively?

Think-Grapple-Innovate-Friday Series

Many of the most exciting advances in data science and machine learning are driven by solving problems in the business world, particularly at companies like Google/Alphabet, Amazon, and OpenAI. To bring together researchers from a variety of schools and disciplines to share research on these topics, the DCADS Collaboratory is restarting its TGIF (Think-Grapple-Innovate-Fridays) seminar series, featuring speakers from the Darden School of Business, the School of Data Science, and beyond. The aim is to provide a hub for people to recognize shared interests, offer a multi-disciplinary and constructive perspective on scholarly work, and build the capacity at UVA to engage with cutting edge developments that have important ramifications for business, data science, and society as a whole. TGIF is sponsored by the Collaboratory for Applied Data Science in Business.  

Michael Albert

Assistant Professor Michael Albert teaches Quantitative Analysis courses in Darden’s MBA program, and he has joint appointments in Systems Engineering and Computer Science in the School of Engineering and Applied Sciences (SEAS) at UVA. His research focuses on combining machine learning and algorithmic techniques to automate the design of markets. His work has appeared in leading artificial intelligence and machine learning venues such as the Association for the Advancement of Artificial Intelligence (AAAI) and the International Joint Conference on Artificial Intelligence (IJCAI).

Prior to joining Darden in 2018, Albert received his Ph.D. in financial economics at Duke University’s Fuqua School of Business. He has also worked as a visiting assistant professor of finance at the Ohio State University, as a postdoctoral researcher at the Learning Agents Research Group at the University of Texas at Austin under Peter Stone, and as a postdoctoral researcher in the artificial intelligence group headed by Vincent Conitzer at Duke University.