Game Theory

Classically in economics, the study of how information influences strategic interactions has been largely descriptive. Much of the recent work in my group examines the associated prescriptive question, which is becoming increasingly important in today’s information economy: what information should a system designer make available to agents so that they can collectively make good decisions? This task is referred to as persuasion or information structure design.

This type of research holds special promise in the field of transportation as global optimizations, though not always locally advantageous, are necessary to improve overall traffic flow.

Our research lays the groundwork for an algorithmic theory of persuasion, building on top of a recent flurry of work on persuasion in the economics community. In [1], I proved that optimal persuasion is computationally intractable in the generic case of two competing agents and a public communication channel. This explains the lack of an economic characterization of optimal policies. In [2], we showed how to circumvent this impossibility in multi-agent settings which are “smooth”. Somewhat surprisingly, we showed in [3] that optimal persuasion admits computationally efficient, instructive, and near-optimal policies when there is only one decision-making agent. In [4], we show a similar positive result when there are multiple agents with binary actions, no inter-agent externalities, and the system designer can communicate privately with each of the agents. I also recently wrote a survey [5] on the topic.

Being that algorithmic persuasion is coming into its own as a field, we believe the time is ripe for a killer application of our models and algorithms. One promising application is traffic management. In an ongoing collaboration with IMSC, and working with the LA Metro, we are exploring the use of algorithmic persuasion as a tool for traffic management in Los Angeles. Persuasion algorithms would be informed by real-time traffic sensors and historical traffic data, and would be integrated into a GPS navigation app.

Related Publications

[1] On the Hardness of Signaling. Shaddin Dughmi. FOCS 2014.
[2] Mixture Selection, Mechanism Design, and Signaling. Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, and Shang-Hua Teng. FOCS 2015.
[3] Algorithmic Bayesian Persuasion. Shaddin Dughmi and Haifeng Xu. STOC 2016.
[4] Algorithmic Persuasion with no Externalities. Shaddin Dughmi and Haifeng Xu. EC 2017.
[5] Algorithmic Information Structure Design: A Survey. Shaddin Dughmi. SIGecom Exchanges, 2017.