Research Interests

I'm interested in the problems at the intersection of artificial intelligence and game theory, and particularly auction theory. I focus on auctions where reporting truthfully is not the rational thing for an agent to do. One case of this is deliberative agents, agents must pay some (computational) cost to discover what the truth is. In this case, I study what rational agents will do in standard auctions, and what auctioneers can do to give agents the incentive to acquire information. Another case is position auctions, such as those used to sell keyword advertising on major search-engines. I'm working on computational methods for finding Nash equilibria of these auctions, and studying the economic outcomes of those equilibria.

 Education

 Other training

 Appointments

 Other Employment

 Publications: Competitive Refereed Conferences

• L. Elisa Celis, Anna R. Karlin, Kevin Leyton-Brown, C. Thach Nguyen, David R. M. Thompson. “Approximately Revenue-Maximizing Auctions for Deliberative Agents,” Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), Toronto, 2012.
  (Acceptance rate: 294/1129=26%.)
• David R. M. Thompson, Samantha Leung, Kevin Leyton-Brown. “Computing Nash Equilibria of Action-Graph Games via Support Enumeration,” The 7th Workshop on Internet and Network Economics (WINE-11), Singapore, 2011.
  (Acceptance rate: 30/100=30%.)
• David R. M. Thompson, Kevin Leyton-Brown. “ Dominant-Strategy Auction Design for Agents with Uncertain, Private Values,” Twenty-Fifth Conference on Artificial Intelligence (AAAI-11), Association for the Advancement of Artificial Intelligence, 2011. [poster] [slides]
  (Acceptance rate: 242/975=25%.)
• David R. M. Thompson, Kevin Leyton-Brown. “Comparing Position Auctions Computationally,” NECTAR: The AAAI-10 Special Track on New Scientific and Technical Advances in Research, Association for the Advancement of Artificial Intelligence, 2010.
  (Acceptance rate: 12/48=25%.)
• David Robert Martin Thompson, Kevin Leyton-Brown. “Computational Analysis of Perfect-Information Position Auctions,” The 10th ACM Electronic Commerce Conference, ACM: Special Interest Group on Electronic Commerce, 2009. [slides]
  (Acceptance rate: 40/161=25%.)
• David R. M. Thompson, Kevin Leyton-Brown. “Valuation Uncertainty and Imperfect Introspection in Second-Price Auctions,” The Twenty-Second National Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence (AAAI), 2007.
  (Acceptance rate: 253/921=27%.)

 Publications: Refereed Conferences and Workshops

• David Robert Martin Thompson, Kevin Leyton-Brown. “Tractable Computational Methods for Finding Nash Equilibria of Perfect-Information Position Auctions, ” Fourth Workshop on Ad Auctions, 2008. [slides]
• David R.M. Thompson, Albert Xin Jiang, Kevin Leyton-Brown. “Game-Theoretic Analysis of Network Quality-of-Service Pricing,” BCNET 2007.
• David R.M. Thompson, Kevin Leyton-Brown. “Valuation Uncertainty and Imperfect Introspection in Sealed-bid Auctions,” DIMACS Workshop on Auctions with Transaction Costs, Center for Discrete Mathematics and Theoretical Computer Science, 2007.
• David Calvert, David Thompson. “Distributed Rasterization in OpenGL,” published in Proceedings of the 16th Annual International Symposium on High Performance Computing Systems and Applications, IEEE Computer Society, 2002.

 Publications: Unrefereed Conferences

• David R.M. Thompson, Albert Xin Jiang, Kevin Leyton-Brown. “Computational Analysis of Imperfect-Information Position Auctions.” INFORMS Annual Meeting. Charlotte, NC, November 2011. (Invited oral presentation.) [slides]
• David R.M. Thompson. “Uncertainty and Learning in Auctions” CS-ECON Seminar Series, Duke University, Durham, NC, November 2011. (Invited oral presentation.) [slides]
• Kevin Leyton-Brown, David R.M. Thompson. “Computational Equilibrium Analysis of Sponsored Search Auctions” Google Research, Mountain Ciew, CA, August 2011. (Invited oral presentation.) [slides]
• David R.M. Thompson, Kevin Leyton-Brown. “Dominant-Strategy Auction Design for Agents with Uncertain, Private Values,” Workshop on Innovations in Algorithmic Game Theory. Institute for Advanced Studies, Hebrew University of Jerusalem, Jerusalem, Israel, May 2011. (Invited oral presentation.) [slides]
• David R.M. Thompson, Kevin Leyton-Brown. “Bayes-Nash Equilibria of Position Auctions,” Workshop on Innovations in Algorithmic Game Theory. Institute for Advanced Studies, Hebrew University of Jerusalem, Jerusalem, Israel, May 2011. [poster]
• David R.M. Thompson, Kevin Leyton-Brown. “Computational Analysis of Perfect-Information Position Auctions.” INFORMS Annual Meeting. San Diego, October 2009. (Invited oral presentation.)
• David R.M. Thompson, Kevin Leyton-Brown. “Computational Analysis of Perfect-Information Position Auctions.” Beyond Search: Semantic Computing and Internet Economics 2009 Workshop. (Invited oral presentation.) [slides]
• David R.M. Thompson, Kevin Leyton-Brown. “Computational Methods for Analyzing Complex Markets: Solving Ad Auctions.” INFORMS Annual Meeting. Washington, October 2008. (Invited oral presentation.) [slides]
• David R.M. Thompson, Kevin Leyton-Brown. “Auctions for Deliberative Agents,” INFORMS Computing Society / Valuation Uncertainty and Revenue Monotonicity Sponsored Session. INFORMS Annual Meeting. Seattle, November 2007. (Invited oral presentation.)

 Ongoing Research Projects

• Using action graph game representations to model and efficiently solve position auctions for online advertising. In collaboration with Kevin Leyton-Brown and Samantha Leung. [website]
• Using action graph game representations to model and efficiently solve discrete network games. In collaboration with Albert Xin Jiang, Nimalan Mahendran and Kevin Leyton-Brown.

 Editorial Activity

 Awards

 Teaching