Online algorithms for market clearing

ABSTRACT

In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online clearing problem of deciding which buy and sell bids to match without knowing what bids will arrive in the future. For maximizing profit, we present a (randomized) online algorithm with a competitive ratio of ln(p_max − p_min) + 1, when bids are in a range [p_min, p_max], which we show is the best possible. A simpler algorithm has a ratio twice this, and can be used even if expiration times are not known. For maximizing the number of trades, we present a simple greedy algorithm that achieves a factor of 2 competitive ratio if no money-losing trades are allowed. We also show that if the online algorithm is allowed to subsidize matches---match money-losing pairs if it has already collected enough money from previous pairs to pay for them---then it can actually be 1-competitive with respect to the optimal offline algorithm that is not allowed subsidy. That is, for maximizing the number of trades, the ability to subsidize is at least as valuable as knowing the future. We also consider objectives of maximizing buy or sell volume and social welfare. We present all of these results as corollaries of theorems on online matching in an incomplete interval graph.We also consider the issue of incentive compatibility, and develop a nearly optimal incentive-compatible algorithm for maximizing social welfare. For maximizing profit, we show that no incentive-compatible algorithm can achieve a sublinear competitive ratio, even if only one buy bid and one sell bid are alive at a time. However, we provide an algorithm that, under certain mild assumptions on the bids, performs nearly as well as the best fixed pair of buy and sell prices, a weaker but still natural performance measure. This latter result uses online learning methods, and we also show how such methods can be used to improve our “optimal” algorithms to a broader notion of optimality. Finally, we show how some of our results can be generalized to settings in which the buyers and sellers themselves have online bidding strategies, rather than just each having individual bids.

REFERENCES

• 1: Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
• 2: Amitabha Bagchi , Amitabh Chaudhary , Rahul Garg , Michael T. Goodrich , Vijay Kumar, Seller-Focused Algorithms for Online Auctioning, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.135-147, August 08-10, 2001
• 3: Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
• 4: Berge, C. 1957. Two theorems in graph theory. In Proceedings of the National Academy of Sciences. 43, 842--844.
• 5: Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000 [doi>10.1023/A:1007621832648]
• 6: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Theoretical Computer Science, v.324 n.2-3, p.137-146, 20 September 2004 [doi>10.1016/j.tcs.2004.05.012]
• 8: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 9: Bredin, J., and Parkes, D. 2005. Models for truthful online double auctions. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI). 50--59.
• 10: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 11: Kaustubh Deshmukh , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Truthful and Competitive Double Auctions, Proceedings of the 10th Annual European Symposium on Algorithms, p.361-373, September 17-21, 2002
• 12: Domowitz, I. 1993. Automating the continuous double auction in practice: Automated trade execution systems in financial markets. In The Double Auction Market, D. Friedman and J. Rust, Eds. Santa Fe Institute Studies in the Sciences of Complexity, vol. 14. Addison-Wesley, Reading, PA, 27--60.
• 13: El-Yaniv, R., Fiat, A., Karp, R. M., and Turpin, G. 1992. Competitive analysis of financial games. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 327--333.
• 14: Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238163]
• 15: Goldberg, A., Hartline, J., and Wright, A. 2000. Competitive auctions and multiple digital goods. Tech. rep., InterTrust 00--01.
• 16: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 17: Sally A. Goldman , Jyoti Parwatikar , Subhash Suri, Online scheduling with hard deadlines, Journal of Algorithms, v.34 n.2, p.370-389, Feb. 2000 [doi>10.1006/jagm.1999.1060]
• 18: Gong, J. 2002. Exchanges for complex commodities: Search for optimal matches. M.S. dissertation, University of South Florida.
• 19: Hagerty, K., and Rogerson, W. 1987. Robust trading mechanisms. J. Econ. Theory 42, 94--107.
• 20: 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]
• 21: Mohammad T. Hajiaghayi, Online auctions with re-usable goods, Proceedings of the 6th ACM conference on Electronic commerce, p.165-174, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064027]
• 22: 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]
• 23: Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
• 24: 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]
• 25: R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States
• 26: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 27: Myerson, R., and Satterthwaite, M. 1983. Efficient mechanisms for bilateral trading. J. Econ. Theory 28, 265--281.
• 28: Sandholm, T. 2002. eMediator: A next generation electronic commerce server. Computat. Intel. 18, 4, 656--676. (Special issue on Agent Technology for Electronic Commerce.)
• 29: Sandholm, T., Levine, D., Concordia, M., Martyn, P., Hughes, R., Jacobs, J., and Begg, D. 2006. Changing the game in strategic sourcing at Procter & Gamble: Expressive competition enabled by optimization. Interfaces 36, 1, 55--68.
• 30: Tuomas Sandholm , Subhash Suri, Market Clearing with Supply and Demand Curves, Proceedings of the 13th International Symposium on Algorithms and Computation, p.600-611, November 21-23, 2002
• 31: Tuomas Sandholm , Subhash Suri, BOB: improved winner determination in combinatorial auctions and generalizations, Artificial Intelligence, v.145 n.1-2, p.33-58, April 2003 [doi>10.1016/S0004-3702(03)00015-8]
• 32: Sandholm, T., and Suri, S. 2006. Side constraints and non-price attributes in markets. Games and Economic Behavior 55, 321--330. (Early version in IJCAI-01 Workshop on Distributed Constraint Reasoning, 55--61.)
• 33: Tuomas Sandholm , Subhash Suri , Andrew Gilpin , David Levine, Winner determination in combinatorial auction generalizations, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544760]
• 34: Peter R. Wurman , William E. Walsh , Michael P. Wellman, Flexible double auctions for electionic commerce: theory and implementation, Decision Support Systems, v.24 n.1, p.17-27, Nov. 1998 [doi>10.1016/S0167-9236(98)00060-8]
• 35: Peter R. Wurman , Michael P. Wellman , William E. Walsh, The Michigan Internet AuctionBot: a configurable auction server for human and software agents, Proceedings of the second international conference on Autonomous agents, p.301-308, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280847]
• 36: Martin Zinkevich , Avrim Blum, Theoretical guarantees for algorithms in multi-agent settings, 2004

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Economics, Theory

Keywords:
Competitive analysis, double auctions, exchanges, online algorithms