Two-Sided Market Design for Goods with Perishable Utility

Abstract

We study two-sided market design for goods whose utility perishes if unconsumed. Motivated by decentralized compute markets, we propose a mechanism that decouples price discovery from allocation; a load-based posted-price rule determines a per-period market price, while a greedy matching algorithm with second-price payments handles job assignment. We prove existence and uniqueness of equilibria, and give sufficient conditions under which equilibria are admissible~(i.e., active supply covers demand without rationing). On the allocation side, we show that the welfare-optimal matching algorithm is not strategy-proof and introduce Cheapest-Feasible Matching with Second-Price Payment~(CFM-SP), under which myopic providers truthfully report costs while staking their full availability. CFM-SP achieves a tight $1/2$-competitive ratio for demand-side welfare under adversarial arrivals; when providers' costs are monotone in availability, the ratio improves to~$1$.

12 main pages, 13 appendix pages