2026-09-08T02:22:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26406 2026-09-05T19:42:22Z ddc:004 open_access

Competitive Bundle Trading Azar, Yossi Buchbinder, Niv Levin, Roie Vardi, Or Online algorithms competitive analysis algorithmic game theory mechanism design dynamic pricing resource allocation Allocating a set of resources to an online sequence of customers is a fundamental problem in online algorithms with an extensive history. However, the natural extension where the algorithm is also allowed to purchase inventory from suppliers, who also arrive online, is essentially unexplored. We study this general trading problem under the objective of profit maximization, which is the difference between revenue from sales and cost of purchases. Maximizing the difference between two competing quantities is significantly more challenging than the sell-only case. We show a logarithmic competitive ratio relative to the optimal offline solution. Our algorithm is an exponential-weight–update dynamic pricing scheme, and our analysis dual-fits the algorithm’s profit with respect to a linear programming relaxation that upper bounds the optimal offline profit; we also prove (nearly) matching lower bounds. Finally, we extend our results by designing an incentive-compatible mechanism for the setting in which customers are strategic and may misreport their true valuations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yossi Azar and Niv Buchbinder and Roie Levin and Or Vardi 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.17 urn:nbn:de:0030-drops-264066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode