Approximation Algorithms for GPU Pricing under Finite Capacity

We study revenue-optimal posted-price design for GPU markets under a finite capacity $B$. We focus on two settings: \emph{sales}, where each purchase permanently consumes a vendor's GPU inventory, and \emph{rentals}, where each job occupies GPUs for a finite duration and then releases them. In both settings, the vendor must commit to an anonymous price menu before observing customers' valuation, GPU demand, and job duration. First, in the sales setting, we show that computing the optimal anonymous static menu is NP-hard, and that the common practice of linear pricing (per-GPU price) can be highly suboptimal. We develop three methods with varying approximation guarantees, all of which outperform linear pricing. Our main method is a convex program (CP) obtained via an ex-ante relaxation of the problem, which obtains a $\tfrac{1-\epsilon}{2}$ approximation to the optimum when the maximum GPU demand $\overline{N}$ satisfies $\overline{N}\leq \epsilon B$. Building on these results, we analyze the \emph{rental} model. We again show that linear pricing (per-GPU-hour price) is highly suboptimal, and design duration-aware posted-price policies based on slot-coupled ex-ante CP. Our \emph{Throttled CP-Menu Posted Pricing} (TCMPP) policy posts the CP-induced menu randomly and achieves a $\frac{1-\epsilon}{4}$ approximation. We further introduce a slackened version of the same convex program, which reserves capacity in each time slot and achieves stronger guarantees in the small job regime. We corroborate our theoretical results with simulations.