Final Project Topics

Please let us know if you would like a specific topic. First come, first serve.

Topic References Status
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 Yehonatan Ginzberg & Moshe Sulamy
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. available
Simple auctions Hartline/ Roughgarden, Simple versus optimal mechanisms, SIGecom Exchanges 8(1) (2009). Dhangwatnotai/Roughgarden/Yan Revenue maximization with a single sample, EC 2010 Yonatan and Ofri
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. אורן גילאון, גיא שלו
Sequential Auctions Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos: Sequential auctions and externalities. SODA 2012. Vasilis Syrgkanis, Éva Tardos: Bayesian sequential auctions, EC 2012 Elizabeth Firman and Aviv Kuvent
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 Nimrod Fiat and Iddan Golomb
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 Vadim Stotland and Kalev Alpernas
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 Sivan Keret and Nave Frost
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 available
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 Amir Rubnstein, Yael Amsterdamer
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 Jonathan Kalechstain Alon Har
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 ברק ארקיס ברוך ויצמן
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 available
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. Slava Novgorodov and Ilia Gorelik
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. reserved
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. available
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. omri sharabi
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. Alon Ardenboim and Adi Vardi
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. available
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License