Online auctions with re-usable goods

ABSTRACT

This paper concerns the design of mechanisms for online scheduling in which agents bid for access to a re-usable resource such as processor time or wireless network access. Each agent is assumed to arrive and depart dynamically, and in the basic model require the resource for one unit of time. We seek mechanisms that are truthful in the sense that truthful revelation of arrival, departure and value information is a dominant strategy, and that are online in the sense that they make allocation decisions without knowledge of the future. First, we provide two characterizations for the class of truthful online allocation rules. The characterizations extend beyond the typical single-parameter settings, and formalize the role of restricted misreporting in reversing existing price-based characterizations. Second, we present an online auction for unit-length jobs that achieves total value that is 2-competitive with the maximum offline value. We prove that no truthful deterministic online mechanism can achieve a better competitive ratio. Third, we consider revenue competitiveness and prove that no deterministic truthful online auction has revenue that is constant-competitive with that of the offline Vickrey-Clarke-Groves (VCG) mechanism We provide a randomized online auction that achieves a competitive ratio of O(log h), where h is the ratio of maximum value to minimum value among the agents; this mechanism does not require prior knowledge of h. Finally, we generalize our model to settings with multiple re-usable goods and to agents with different job lengths.

REFERENCES

• 1: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 2: Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780616]
• 3: Y. Bartal, F. Chin, M. Chrobak, S. Fung, R. Lavi, J. Sgall, and T. Tichy. Online competitive algorithms for maximizing weighted throughput of unit jobs. In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science, pages 187--198, 2004.
• 4: S. Bikhchandani, S. de Vries, J. Schummer, and R. Vohra. Linear programming and vickrey auctions. IMA Volumes in Mathematics and its Applications, Mathematics of the Internet: E-Auction and Markets, 127:75--116, 2001.
• 5: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: F. Chin and S. Fung. Online scheduling for partial job values: Does timesharing or randomization help? Algorithmica, 37:149--164, 2003.
• 7: Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779978]
• 8: B. Hajek. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 2001 Conference on Information Sciences and Systems, 2001.
• 9: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 10: 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]
• 11: Robert Kleinberg , Tom Leighton, The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.594, October 11-14, 2003
• 12: V. Krishna. Auction Theory. Academic Press, 2002.
• 13: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 14: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 15: Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 17: Chaki Ng , David C. Parkes , Margo Seltzer, Virtual worlds: fast and strategyproof auctions for dynamic resource allocation, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779977]
• 18: D. C. Parkes and S. Singh. An MDP-based approach to Online Mechanism Design. In Proc. 17th Annual Conf. on Neural Information Processing Systems (NIPS'03), 2003.
• 19: D. C. Parkes and S. Singh. Approximately efficient online mechanism design. In Proc. 18th Annual Conf. on Neural Information Processing Systems (NIPS'04), 2004.
• 20: Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988783]
• 21: Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory