Final Project Topics

Projects should be submitted in groups of 2-3 students.
Please let us know if you would like a specific topic. First come, first serve.

Topic	References	Status
Truthful mechanisms for complement free bidders	Shahar Dobzinski, Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders. CoRR abs/1602.05914 (2016). Piotr Krysta, Berthold Vöcking, Online Mechanism Design (Randomized Rounding on the Fly). ICALP (2) 2012: 636-647. Shahar Dobzinski, Two Randomized Mechanisms for Combinatorial Auctions. APPROX-RANDOM 2007: 89-103
Posted price mechanisms	Chawla/Hartline/Malec/Sivan, Multi-parameter mechanism design and sequential posted pricing , STOC 2010. Alaei/Hartline/Niazadeh/Pountourakis/Yuan, Optimal Auctions vs. Anonymous Pricing, FOCS 2015. Feldman/Lucier/Gravin, Combinatorial Auctions via Posted Prices, SODA 2015. Cohen-Addad/Eden/Feldman/Fiat, The Invisible Hand of Dynamic Market Pricing, working paper. Cohen/Eden/Fiat/Jez, Pricing Online Decisions: Beyond Auctions, SODA 2015.
Beyond Walrasian Equilibrium	Fu/Kleinberg/Lavi, Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding, EC 2012. Feldman/Gravin/Lucier, Combinatorial walrasian equilibrium, STOC 2013. Roughgarden/Talgam-Cohen, Why prices need algorithms, EC 2015.
Multi-Parameter revenue maximization	Babaioff/Immorlica/Lucier/Weinberg, A Simple and Approximately Optimal Mechanism for an Additive Buyer, FOCS 2014. Yao, An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications, SODA 2015. Rubinstein/Weinberg, Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity, EC 2015. Rubinstein On the Computational Complexity of Optimal Simple Mechanisms, ITCS 2016
Adaptive Seeding in social networks	Seeman/Singer, Adaptive Seeding in Social Network, FOCS 2013. Rubinstein/Seeman/Singer, Approximability of Adaptive Seeding under Knapsack Constraints, EC 2015. Badanidiyuru/Papadimitriou/Rubinstein/Seeman/Singer, Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions, SODA 2016
Signaling in mechanism design	Emek/Feldman/Gamzu/Paes-Leme/Tennenholtz, Signaling schemes for revenue maximization, EC 2012. Dughmi/Immorlica/Roth, Constrained Signaling in Auction Design, SODA 2014. Dughmi/Xu, Algorithmic Bayesian Persuasion, STOC 2016. Dughmi On the Hardness of Signaling, FOCS 2014
Single-Minded Bidders	Lehman/O’Callaghan/Shoham, Truth revelation in approximately efficient combinatorial auctions, ACM 2002. Mu'alem/Nisan, Truthful Approximation Mechanisms for Restricted Combinatorial Auctions, AAAI 2002. Archer/Papadimitriou/Talwar/Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, SODA 2003
Bayesian Mechanism Design	Hartline/Lucier, Bayesian algorithmic mechanism design, STOC 2010. Hartline, Bayesian Mechanism Design, FTTCS 2013. Chawla/Hartline/Malec/Sivan Multi-parameter mechanism design and sequential posted pricing , STOC 2010.
Implicit payment calculations	Babaioff/Kleinberg/Slivkins, Single-parameter mechanisms with implicit payment computation, EC 2010. Babaioff/Kleinberg/Slivkins, Multi-parameter mechanisms with implicit payment computation, EC 2013.
Simple auctions	Hartline/ Roughgarden, Simple versus optimal mechanisms, SIGecom Exchanges 8(1) (2009). Dhangwatnotai/Roughgarden/Yan Revenue maximization with a single sample, EC 2010
Bayesian price of anarchy	George Christodoulou, Annamária Kovács, Michael Schapira: Bayesian Combinatorial Auctions. ICALP 2008. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Noam Nisan: Non-price equilibria in markets of discrete goods. EC 2011. Michal Feldman, Nick Gravin, Brendan Lucier: Combinatorial walrasian equilibrium. STOC 2013. Syrgkanis/Tardos Composable and efficient mechanisms, STOC 2013
Sequential Auctions	Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos: Sequential auctions and externalities. SODA 2012. Vasilis Syrgkanis, Éva Tardos: Bayesian sequential auctions, EC 2012
Mechanism design without money: cake cutting	Ariel D. Procaccia, Moshe Tennenholtz: Approximate mechanism design without money. EC 2009. Yuga J. Cohler, John K. Lai, David C. Parkes, Ariel D. Procaccia: Optimal Envy-Free Cake Cutting. AAAI 2011
Stable Matching	Itai Ashlagi, Mark Braverman, Avinatan Hassidim: Matching with couples revisited, EC 2011. Itai Ashlagi, Yashodhan Kanoria, Jacob D. Leshno: Unbalanced random matching markets, EC 2013
Envy Free Mechanisms	Venkatesan Guruswami et al,: On profit-maximizing envy-free pricing. SODA 2005. Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky: Envy-free makespan approximation: extended abstract. Ec 2010
Price of Stability	Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden: The Price of Stability for Network Design with Fair Cost Allocation. FOCS 2004. Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo: On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. ICALP 2006. Euiwoong Lee, Katrina Ligett: Improved bounds on the price of stability in network cost sharing games EC 2013
Cost Sharing	Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker: Sharing the cost of muliticast transmissions (preliminary version). STOC 2000. Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker: Approximation and collusion in multicast cost sharing. EC 2003
Job Scheduling	Noam Nisan, Amir Ronen: Algorithmic Mechanism Design (Extended Abstract). STOC 1999, Aaron Archer, Éva Tardos: Truthful Mechanisms for One-Parameter Agents. FOCS 2001, Nir Andelman, Yossi Azar, Motti Sorani: Truthful Approximation Mechanisms for Scheduling Selfish Related Machines. STACS 2005
Communication complexity of combinatorial auctions	Shahar Dobzinsk: An impossibility result for truthful combinatorial auctions with submodular valuations. STOC 2011. Shaddin Dughmi, Jan Vondrák: Limitations of Randomized Mechanisms for Combinatorial Auctions. FOCS 2011, S. Dobzinski and J. Vondrak: Communication complexity of combinatorial auctions with submodular valuations. SODA 2013
Truthful (in expectation) mechanisms via linear programming	Ron Lavi, Chaitanya Swamy: Truthful and Near-Optimal Mechanism Design via Linear Programming. FOCS 2005. Robert D. Carr, Santosh Vempala: Randomized metarounding (extended abstract). STOC 2000
Sponsored search auctions (batched)	Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005. Aggarwal, Hartline, "Knapsack Auctions" SODA 2006. Optional Reference: Balcan, Blum, Hartline, Mansour, "Mechanism Design via Machine Learning", FOCS 2005. Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.
Sponsored search auctions (online)	Mehta, Saberi, Vazirani, Vazirani, "AdWords and Generalized Online Matching", FOCS 2005. Hajiaghayi, Kleinberg, Parkes, "Adaptive Limited-Supply Online Auctions", EC 2004. Optional Reference: Awerbuch, Azar, Meyerson, "Reducing truth-telling online mechanisms to online optimization", STOC 2003. Optional Reference: Blum, Hartline, "Near-Optimal Online Auctions" EC 2005.
Random sampling, double auctions, and worst case competitive ratio	Baliga and Vohra, "Market Research and Market Design", Advances in Theoretical Economics 2003. Feige, Flaxman, Hartline, Kleinberg, "On the competitive ratio of the random sampling auction", WINE 2005.
Multi-unit auctions	Shahar Dobzinski, Noam Nisan: Mechanisms for multi-unit auctions. ACM Conference on Electronic Commerce 2007. Shahar Dobzinski, Ron Lavi, Noam Nisan: Multi-unit Auctions with Budget Limits. FOCS 2008. Optional reference: Berthold Vöcking: A universally-truthful approximation scheme for multi-unit auctions. SODA 2012.
Online limited supply auctions with budgets	Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005. Hajiaghayi, Kleinberg, Parkes, "Adaptive Limited-Supply Online Auctions", EC 2004. Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.
Approximate Winner Determination with Subadditive Valuations	Shahar Dobzinski, Noam Nisan, Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders. STOC 2005. Uriel Feige, On Maximizing Welfare when Utility Functions are Subadditive, STOC 2006.
Approximate Winner Determination with Submodular Valuations	Lehmann/Lehmann/Nisan, Combinatorial auctions with decreasing marginal utilities, EC 2001. Dobzinski/Schapira, An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders, SODA 2006.
Optimal mechanism design	Cai/Daskalakis/Weinberg Optimal multidimensional mechanism design: Reducing revenue to welfare maximization. FOCS 2012
Randomization in Mechanism Design	Dobzinski/Dughmi On the power of randomization in algorithmic mechanism design. FOCS 2009, Dughmi/Vondrak: Limitations of randomized mechanisms for combinatorial auctions. FOCS 2011
Strong equilibrium analysis	Andelman/Feldman/Mansour Strong price of anarchy, SODA 2007. Epstein/Feldman/Mansour Strong equilibrium in cost sharing connection games, EC 2007. Albers On the value of coordination in network design. SIAM JoC 2009. Harks/Klimm/Möhring Strong equilibria in games with the lexicographical improvement property. IJoGT 2013
Convergence to equilibrium	Goemans/Mirrokni/Vetta Sink equilibria and convergence, FOCS 2005. Christodoulou/Mirrokni/Sidiropoulos Convergence and Approximation in Potential Games, STACS 2006. Chien/Sinclair Convergence to approximate Nash equilibria in congestion games, SODA 2007. Awerbuch/Azar/Epstein/Mirrokni Fast convergence to nearly optimal solutions in potential games, EC 2008.
Ascending auctions	Fu/Kleinberg/Lavi Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding, EC 2012. Feldman/Gravin/Lucier Combinatorial walrasian equilibrium, STOC 2013. Feldman/Lucier Clearing Markets via Bundles, SAGT 2014. Dobzinski/Feldman/Talgam-Cohen/Weinstein Welfare and Revenue Guarantees for Competitive Bundling Equilibrium, working paper.
Price of anarchy of simple auctions	Bhawalkar/Roughgarden Welfare guarantees for combinatorial auctions with item bidding, SODA 2011. Babaioff/Lucier/Nisan/Paes Leme On the efficiency of the walrasian mechanism, EC 2014.