Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders

References

• Alon N., Matias Y., Szegedy M. The space complexity of approximating the frequency moments. J. Comput. System Sci. (1999) 58(1):137–147Crossref, Google Scholar
• Blumrosen L., Nisan N. On the computational power of iterative auctions I: demand queries. (2005) . Discussion Paper 381, The Center for the Study of Rationality, The Hebrew University of Jerusalem, Jerusalem. (An extended abstract in EC'05 contained preliminary results.)Google Scholar
• Cramton P., Shoham Y., Steinberg R.Combinatorial Auctions (2006) (MIT Press, Cambridge, MA) 507–538Chapter 22Google Scholar
• Dobzinski S. Two randomized mechanisms for combinatorial auctions. Approximation, Randomization, and Combinatorial Optization Algorithms and Techniques (2007) 4627(Springer, Berlin/Heidelberg) 89–103Lecture Notes in Comput. Sci.Crossref, Google Scholar
• Dobzinski S., Nisan N. Limitations of VCG-based mechanisms. Proc. 39th Annual ACM Sympos. on Theory of Comput. (2007) San Diego, CA(ACM, New York) 338–344Google Scholar
• Dobzinski S., Nisan N., Schapira M. Truthful randomized mechanisms for combinatorial auctions. Proc. 38th Annual ACM Sympos. Theory Comput. (2006) Seattle(ACM, New York) 644–652Google Scholar
• Dobzinski S., Schapira M. Optimal upper and lower approximation bounds for k-duplicates combinatorial auctions. (2005) . Working paper, The Hebrew University of Jerusalem, JerusalemGoogle Scholar
• Feige U. A threshold of ln n for approximating set cover. J. ACM (1998) 45(4):634–652Crossref, Google Scholar
• Feige U. On maximizing welfare when utility functions are subadditive. Proc. 38th Annual ACM Sympos. Theory Computing (2006) (ACM, New York) 41–50Google Scholar
• Feige U., Vondrák J. Approximation algorithms for allocation problems: Improving the factor of 1−1/e. Proc. of the 47th Annual IEEE Sympos. on Foundations of Comput. Sci. (2006) (IEEE Computer Society, Washington, DC) 667–676Google Scholar
• Khot S., Lipton R. J., Markakis E., Mehta A. Inapproximability results for combinatorial auctions with submodular utility functions. Proc. WINE'05, Lecture Notes in Computer Science (2005) 387(Springer, Berlin) Google Scholar
• Lehmann B., Lehmann D. J., Nisan N. Combinatorial auctions with decreasing marginal utilities. Proc. ACM Conf. Electronic Commerce (2001) (ACM, New York) 18–28Google Scholar
• Lehmann D., O'Callaghan L. I., Shoham Y. Truth revelation in approximately efficient combinatorial auctions. J. Assoc. Comput. Machinery (2002) 49(5):577–602Crossref, Google Scholar
• Mirrokni V. S., Schapira M., Vondrák J. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. ACM Conf. Electronic Commerce (2008) (ACM, New York) 70–77Google Scholar
• Mitzenmacher M., Upfal E.Probability and Computing (2005) (Cambridge University Press, Cambridge, UK) Google Scholar
• Nisan N. The communication complexity of approximate set packing and covering. ICALP (2002) 2380(Springer, Berlin/Heidelberg) 868–875Lecture Notes in Computer ScienceCrossref, Google Scholar
• Nisan N., Cramton P., Shoham Y., Steinberg R.Combinatorial Auctions (2006) (MIT Press, Cambridge, MA) Bidding LanguagesChapter 1Google Scholar
• Nisan N., Nisan N., Roughgarden T., Tardos E., Vazirani V. Introduction to mechanism design (for computer scientists). Algorithmic Game Theory (2007) (Cambridge University Press, New York) 209–242Crossref, Google Scholar
• Nisan N., Ronen A. Computationally feasible VCG mechanisms. J. Artificial Intelligence Res. (2007) 29:19–47Crossref, Google Scholar
• Nisan N., Segal I. The communication requirements of efficient allocations and supporting prices. J. Econom. Theory (2006) 129(1):192–224Crossref, Google Scholar
• Sandholm T. An algorithm for optimal winner determination in combinatorial auctions. Proc. Internat. Joint Conf. Artificial Intelligence (1999) (Morgan Kaufmann, San Francisco, Springer) 542–547Google Scholar
• Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 40th Annual ACM Sympos. Theory Comput. (2008) (ACM, New York) 67–74Crossref, Google Scholar