Decoding Decisions: Game Theory, Menus, and the Power of Learning

Imagine you’re in charge of security at a wildlife preserve in Africa, trying to protect a dwindling population of black rhinos against illegal hunting. With a limited budget, you don’t have enough rangers to effectively patrol a vast area. What can you do? 

The answer, according to Darden Professor Michael Albert, lies in game theory.  

Defining Game Theory 

Simply put, game theory is a branch of mathematics that studies how various parties, called “players,” behave in strategic situations — that is, when they make decisions based on how they think others will make decisions. The assumption is that players are rational — always angling to pursue their best interests — which means their behavior can be predicted.  

A “game” refers to a mathematical model used to analyze strategic interactions between players, such as individuals, organizations, or even nations, depending on the context. 

In the context of wildlife protection, notes Albert, the idea is that you, the defender, have some resources to protect some targets from the attacker.  

“You’ve got to set up some kind of strategy to stop the attacker,” he says. “You’ve got to figure out where to send your park rangers to catch the poachers and deter them. But you don’t know what the value of different targets to the attacker might be. You don’t necessarily know where poachers want to strike.” 

Albert’s research focuses on combining machine learning and algorithmic techniques to automate the design of markets. He says that in real-world scenarios, you could model the problem as a Stackelberg security game. In game theory, a Stackelberg security game provides a framework for analyzing strategic interactions between defenders and attackers in dynamic and uncertain environments. This can help inform decision-making and resource allocation in security operations. 

Some national parks are using advanced technologies that combine machine learning and game theory to intelligently deploy limited resources to protect endangered wildlife. Based on data from past attacks, machine-learning algorithms can learn the poachers’ behavior and predict where they are likely to strike. And a game-theory model can create randomized patrol routes that are unpredictable to the poachers. 

Originally developed to solve economic problems, game theory is a powerful tool with applications across many fields. It provides insights into diverse areas, from contract design and pricing strategies in business to election systems and military buildup in political science.  

Dealing with Information Asymmetry 

Just as the poachers have confidential information they don’t want to reveal to park rangers, parties interacting in a variety of contexts will often have inside information about themselves that the other side is not privy to.  

According to Albert, information asymmetry is a challenge in many economic interactions. Consider the case of health insurance. Individuals seeking insurance will often have private information about their health status that the insurance company doesn’t. Similarly, in hiring and compensation decisions, job candidates know their work ethic and the employer doesn’t.  

“In many situations,” says Albert, “decision-makers would like to access information known by others. For example, as a seller, I’d like to know some things about a customer to personalize pricing. As an employer, I’d like to know your work ethic. But I can’t ask you directly because you have good reasons for not disclosing this information. So an immediate way to gain insights about customers or employees is to observe their actions.” 

Learning Private Information Through Interactions 

The principal-agent problem, a simple, classic model in game theory, provides a useful framework. According to Albert, learning from interactions involving a single principal (such as a seller) who acts first and then an agent (such as a customer) who responds, has sparked considerable interest in computer-science literature.  

In a recent paper, “Learning in Online Principal-Agent Interactions: The Power of Menus,” coauthored with the University of Chicago’s Minbiao Han and Haifeng Xu and published in Proceedings of the AAAI Conference on Artificial Intelligence, Albert explores a learning challenge in online principal-agent problems during which the principal learns the agent’s private information from the agent’s revealed preferences in historical interactions. The paper focuses on pricing, Stackelberg security games, and contract-design problems.  

The Power of Menus 

Let’s examine pricing and consider how an online retailer could determine a customer’s value for a particular product through interactions.  

“Each time you visit my website, I could display an ad offering to sell you a product at a discounted price and see if you'll buy it,” says Albert. “Each interaction provides valuable information. By adjusting the price over time, I can zero in on your value for this product. This is one way of revealing information — giving you a single choice.” 

Albert suggests that there are more efficient ways to learn. Instead of providing a customer with only one option per interaction, a retailer can offer a menu of choices. For example, when you visit Verizon’s website, says Albert, you see a variety of phones with different features and price points. “The phones are set up in such a way,” says Albert, “that your choice tells Verizon something about your value for phones in general. Because you’re making a choice that has many pieces involved, it gives Verizon valuable information about you as a customer.” 

Albert’s research aims to determine the best way to set up such menus, whether online or in brick-and-mortar stores. He wants to develop specific strategies and algorithmic ways to determine whether learning is possible. “In some situations,” says Albert, “there’s no menu that will tell me anything significant. So what are the conditions under which a menu is going to be effective, what is that menu, and how can I learn the most from a single interaction?” 

Albert’s paper is intended for an academic  technical audience for whom its findings will be most relevant. It addresses a common problem in online interactions between a principal and an agent, where the principal needs to learn the agent’s private information over time. Typically, in such scenarios, the principal observes the agent's actions and infers their preferences from those actions. 

The existing research in computer science focuses on scenarios where the principal can only pick one strategy to interact with the agent in each round, and then learn from the agent's response. Albert and his coauthors, however, explore a scenario in which the principal offers the agent a menu of strategies to choose from.  

The paper provides a thorough investigation of several online principal-agent problem settings, such as pricing and contract design. It introduces algorithms — tailored to those problem settings — that shed light on the learning complexities of the problems, which the technical academic audience might find particularly interesting.