Cited By
View all- Kelly T(2024)Programmer Job Interviews: The Hidden AgendaQueue10.1145/363944421:6(16-26)Online publication date: 15-Jan-2024
Offline Algorithms in Low-Frequency Trading: Clearing Combinatorial Auctions
Abstract
Expectations run high for software that makes real-world decisions, particularly when money hangs in the balance. This third episode of the Drill Bits column shows how well-designed software can effectively create wealth by optimizing gains from trade in combinatorial auctions. We'll unveil a deep connection between auctions and a classic textbook problem, we'll see that clearing an auction resembles a high-stakes mutant Tetris, we'll learn to stop worrying and love an NP-hard problem that's far from intractable in practice, and we'll contrast the deliberative business of combinatorial auctions with the near-real-time hustle of high-frequency trading. The example software that accompanies this installment of Drill Bits implements two algorithms that clear combinatorial auctions.
References
[1]
Andersson, A., Tenhunen, M., Ygge, F. 2000. Integer programming for combinatorial auction winner determination. In Proceedings of the International Conference on Multi-Agent Systems (ICMAS); https://doi.ieeecomputersociety.org/10.1109/ICMAS.2000.858429; http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/icmas00.pdf
[2]
Byde, A., Kelly, T., Zhou, Y., Tarjan, R. 2009. Efficiently generating k-best solutions to procurement auctions. In Algorithmic Aspects in Information and Management, ed. A. V. Goldberg and Y. Zhou. Lecture Notes in Computer Science 5564. Springer; https://doi.org/10.1007/978-3-642-02158-9_8; http://www.hpl.hp.com/techreports/2009/HPL-2009-163.pdf. Also U.S. Patents #7,801,769 and #8,086,520.
[3]
Kellerer, H., Pferschy, U., Pisinger, D. 2004. Knapsack Problems. Springer.
[4]
Kelly, T. 2003. Utility-directed allocation. In Self-Managing Systems (June); https://www.hpl.hp.com/techreports/2003/HPL-2003-115.pdf. Also U.S. Patent #7,844,967.
[5]
Kelly, T. 2004. Generalized knapsack solvers for multi-unit combinatorial auctions. In Agent-Mediated Electronic Commerce VI, ed. P. Faratin and J. A. Rodríguez-Aguilar. Lecture Notes in Computer Science 3435. Springer; https://doi.org/10.1007/11575726_6; https://web.eecs.umich.edu/~tpkelly/papers/LNAI_3435_0073_auction_knapsack_connection.pdf
[6]
Kelly, T. 2020. Efficient graph search. acmqueue 18(4); https://queue.acm.org/detail.cfm?id=3424304
[7]
Krugman, P. 2009. Rewarding bad actors. New York Times (August 2); https://www.nytimes.com/2009/08/03/opinion/03krugman.html
[8]
Loveless, J., Stoikov, S., Waeber, R. 2013. Online algorithms in high-frequency trading. acmqueue 11(8); https://dl.acm.org/doi/10.1145/2523426.2534976
[9]
MacKie-Mason, J. K., Varian, H. R. 1994. Generalized Vickrey Auctions. University of Michigan Department of Economics Technical Report; http://hdl.handle.net/2027.42/41250
[10]
Papadimitriou, C. H., Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity, 388. Dover.
[11]
Sedgewick, R., Wayne, K. 2011. Algorithms, 4th edition, 679. Addison-Wesley.
[12]
Stiglitz, J. E. 2014. Tapping the brakes. In Federal Reserve Bank Atlanta Financial Markets Conference (April); https://www.frbatlanta.org/-/media/Documents/news/conferences/2014/fmc/Stiglitz.pdf
[13]
Treleaven, P., Galas, M., Lalchand, V. 2013. Algorithmic trading review. Communications of the ACM 56(11), 76?85; https://doi.org/10.1145/2500117
[14]
Varian, H. R. 2008. Designing the perfect auction. Communications of the ACM 51(8), 9?11; https://cacm.acm.org/magazines/2008/8/5343-designing-the-perfect-auction/fulltext; https://doi.org/10.1145/1378704.1378708
Index Terms
- Offline Algorithms in Low-Frequency Trading: Clearing Combinatorial Auctions
Index terms have been assigned to the content through auto-classification.
Recommendations
Competitive algorithms for unbounded one-way trading
In the one-way trading problem, a seller has L units of product to be sold to a sequence of buyers u 1 , u 2 , , u arriving online and he needs to decide, for each u i , the amount of product to be sold to u i at the then-prevailing market price p i . ...
Inventory Management for High-Frequency Trading with Imperfect Competition
We study Nash equilibria for inventory-averse high-frequency traders (HFTs), who trade to exploit information about future price changes. For discrete trading rounds, the HFTs' optimal trading strategies and their equilibrium price impact are described by ...
High-Frequency Trading: The Faster, the Better?
The floor of the New York Stock Exchange, filled with traders in a frenzy of activity, is perhaps the iconic image of financial markets. But today, the TV pictures we see of the trading floor are largely symbolic. The frenzy of activity instead takes ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November-December 2020
131 pages
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 January 2021
Published in QUEUE Volume 18, Issue 6
Check for updates
Badges
Qualifiers
- Column
- Opinion
- Editor picked
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 61,935Total Downloads
- Downloads (Last 12 months)1,779
- Downloads (Last 6 weeks)145
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
Cited By
View all- Kelly T(2024)Programmer Job Interviews: The Hidden AgendaQueue10.1145/363944421:6(16-26)Online publication date: 15-Jan-2024
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMagazine Site
View this article on the magazine site (external)
Magazine SiteLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in