Learning Anonymous Pricing for Online Resource Allocation
For online resource allocation problems, this work addresses fairness and prior knowledge limitations of existing dynamic pricing approaches.
The paper studies online resource allocation with heterogeneous agents, aiming to learn anonymous pricing algorithms that avoid fairness issues and do not require knowing arrival order. They show that polynomial samples suffice to learn the classic dual pricing algorithm, and polynomial pricing queries suffice to learn a near-optimal anonymous pricing algorithm.
We study the online resource allocation problem, where a seller sequentially receives independent requests for $m$ types of resources with limited supplies from $n$ heterogeneous agents arriving in an unknown order. Each request from an agent can be fulfilled in different ways, with resource consumption in $[0,1]^m$, and generates different values for the agent. The objective of the seller is to maximize the social welfare, which is the sum of the values obtained from each agent. Recently, Ghuge, Singla, and Wang [GSW STOC'25] studied the learnability of the online resource allocation problem with heterogeneous agents and proposed a learnable pricing algorithm using only a single sample. However, their core algorithm is a dynamic pricing algorithm, which may introduce fairness concerns, as different agents face different prices. Furthermore, the algorithm crucially needs to know the arrival order of the agents in advance. To address these issues, in this paper, we study the learnability of anonymous pricing algorithms for online resource allocation using samples and queries to agents' value distributions. First, we show that a polynomial number of samples suffices to learn the classic dual pricing algorithm. Second, we show that a polynomial number of pricing queries suffices to learn a near-optimal anonymous pricing algorithm, in which the item pricing vector faced by each agent is drawn from the same predetermined distribution.