TY - GEN
T1 - Competitive Online Optimization with Multiple Inventories
T2 - 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/PERFORMANCE 2022
AU - Lin, Qiulin
AU - Mo, Yanfang
AU - Su, Junyan
AU - Chen, Minghua
N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).
PY - 2022/6
Y1 - 2022/6
N2 - We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of ln θ+1 if N ≤ ln θ+1, where N is the number of inventories and θ represents the revenue function uncertainty; it attains a CR of 1/[1-e-1/(ln θ+1)] ∈ [ln θ+1, ln θ+2) otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.
AB - We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of ln θ+1 if N ≤ ln θ+1, where N is the number of inventories and θ represents the revenue function uncertainty; it attains a CR of 1/[1-e-1/(ln θ+1)] ∈ [ln θ+1, ln θ+2) otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.
KW - inventory constraints
KW - one-way trading
KW - resource allocation
KW - revenue maximization
UR - http://www.scopus.com/inward/record.url?scp=85132191830&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85132191830&origin=recordpage
U2 - 10.1145/3489048.3530969
DO - 10.1145/3489048.3530969
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781450391412
T3 - SIGMETRICS/PERFORMANCE - Abstract Proceedings of the ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems
SP - 83
EP - 84
BT - SIGMETRICS/PERFORMANCE ’22 Abstracts
PB - Association for Computing Machinery
CY - New York
Y2 - 6 June 2022 through 10 June 2022
ER -