An improved approximation algorithm for combinatorial auctions with submodular bidders

ABSTRACT

We explore the allocation problem in combinatorial auctions with submodular bidders. We provide an e/e-1 approximation algorithm for this problem. Moreover, our algorithm applies to the more general class of XOS bidders. By presenting a matching unconditional lower bound in the communication model, we prove that the upper bound is tight for the XOS class.Our algorithm improves upon the previously known 2-approximation algorithm. In fact, we also exhibit another algorithm which obtains an approximation ratio better than 2 for submodular bidders, even in the value queries model.Throughout the paper we highlight interesting connections between combinatorial auctions with XOS and submodular bidders and various other combinatorial optimization problems. In particular, we discuss coverage problems and online problems.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: Nir Andelman and Yishay Mansour. Auctions with budget constraints. In SWAT, pages 26--38, 2004.
• 3: Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiří Sgall, and Tomáš Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. In STACS, pages 187--198, 2004.
• 4: Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
• 5: Chandra Chekuri and Amit Kumar. Maximum coverage problem with group budget constraints and applications. In APPROX-RANDOM, pages 72--83, 2004.
• 6: Francis Y. L. Chin and Stanley P. Y. Fung. Online scheduling for partial job values: Does timesharing or randomization help? Algorithmica, 37:149--164, 2003.
• 7: Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060681]
• 8: Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109675]
• 9: Shahar Dobzinski and Michael Schapira. Optimal upper and lower approximation bounds for k-duplicates combinatorial auctions, 2005. Working paper.
• 10: Uriel Feige. On maximizing welfare where the utility functions are subadditive. Manuscript, 2005.
• 11: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 12: Bruce Hoppe , Éva Tardos, “The quickest transshipment problem”, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.512-521, January 22-24, 1995, San Francisco, California, United States
• 13: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 14: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 15: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer overflow management in QoS switches, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.520-529, July 2001, Hersonissos, Greece [doi>10.1145/380752.380847]
• 16: Subhash Khot, Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. To appear in WINE 2005.
• 17: Ron Lavi and Noam Nisan. Private Communication.
• 18: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 19: Lászlo Lovász. Submodular functions and convexity. In A. Bachem, M. Grotschel and B. Korte (eds), Mathematical Programming -- The State of the Art. Springer, 1983.
• 20: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 21: Herv Moulin and Scott Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. Economic Theory, 18(3):511--533, 2001.
• 22: George L. Nemhauser and Laurence A. Wolsey. Maximizing submodular set functions: Formulations and analysis of algorithms. In Studies of Graphs and Discrete Programming. North-Holland, 1981.
• 23: Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. To appear in Journal of Economic Theory.
• 24: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
• 25: Arie Tamir, A unifying location model on tree graphs based on submodularity properties, Discrete Applied Mathematics, v.47 n.3, p.275-283, Dec. 21, 1993 [doi>10.1016/0166-218X(93)90132-8]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory