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 |