We study several problems related to game theory. These problems are motivated by e-commerce applications and applications of game theory to computer system and network design. In mechanism design, we aim to develop mechanisms with useful properties which optimize an objective function, such as seller's revenue or global welfare of the system, in the worst- or average-case. Our work shows that techniques from learning, on-line algorithms, and coding theory can be applied to mechanism design. We also study complexity of computational problems that come up in implementations of game-theoretic mechanisms. Finally, we are interested in research problems on the borderline of Economics and Computer Science, including Game Theory, Social Networks, and Electronic Markets.

• Moshe Babaioff
• Liad Blumrosen
• Andrew Goldberg
• Aleksandrs Slivkins
• Kunal Talwar

• Jason Hartline

• Avrim Blum
• Amos Fiat
• Anna Karlin

• Moshe Babaioff, Liad Blumrosen, Moni Naor and Michael Schapira, The Informational Overhead of Incentive Compatibility , In The 9th ACM conference on Electronic Commerce (EC’08).
• Liad Blumrosen and Thomas Holenstein, Posted prices vs. Negotiation: an asymptotic analysis , In The 9th ACM conference on Electronic Commerce (EC’08).
• Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian and Kunal Talwar, Balloon Popping With Applications to Ascending Auctions , In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)
• Frank McSherry and Kunal Talwar, Mechanism Design via Differential Privacy , In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)
• Shuchi Chawla and Jason D. Hartline and Robert Kleinberg, Algorithmic Pricing via Virtual Valuations, In The 8th ACM conference on Electronic Commerce (EC’07).
• Jason D. Hartline and Vladlen Koltun, Near-Optimal Pricing in Near-Linear Time, In 9th International Workshop Algorithms and Data Structures (WADS 2005), Frank K. H. A. Dehne and Alejandro López-Ortiz and Jörg-Rüdiger Sack (eds.), Waterloo, Canada, August 15-17, 2005, pages 422-431.
• Jason D. Hartline and Robert McGrew, From optimal limited to unlimited supply auctions, In Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), Vancouver, BC, Canada, June 5-8, 2005, pages 175-182.
• Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, and Madhu Sudan, Derandomization of auctions, In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), Harold N. Gabow and Ronald Fagin (eds.), Baltimore, MD, USA, May 22-24, 2005, pages 619-625.
• Andrew V. Goldberg and Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2005), Vancouver, British Columbia, Canada, January 23-25, 2005, pages 620-629.
• Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry, On profit-maximizing envy-free pricing, In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2005), Vancouver, British Columbia, Canada, January 23-25, 2005, pages 1164-1173.
• Avrim Blum and Jason D. Hartline, Near-optimal online auctions, In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2005), Vancouver, British Columbia, Canada, January 23-25, 2005, pages 1156-1163.
• Andrew Goldberg and Jason Hartline, Collusion-Resistant Mechanisms for Single-Parameter Agents, Technical Report, MSR-TR-2004-40, May, 2004.
• Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, and Michael E. Saks, A Lower Bound on the Competitive Ratio of Truthful Auctions, In 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS 2004), Volker Diekert and Michel Habib (eds.), March 25-27, 2004, pages 644-655.