Equitable Auction Design with Provable Regret Guarantees

Abstract

We study a mechanism design problem where a seller aims to allocate a good to multiple bidders, each with a private value. The seller supports or favors a specific group, referred to as the minority group. Specifically, the seller requires that allocations to the minority group are at least a predetermined fraction (equity level) of those made to the rest of the bidders. We include the equity requirements as constraints in the design of a mechanism, and our goal is to characterize equitable mechanisms with provable performance guarantees. Motivated by settings where reliable information about the bidders' values is unavailable, our main focus is a regret-based mechanism design problem, which makes no assumptions about the distribution of the bidders' values and aims to minimize the maximum ex-post regret. Here, regret is defined as the difference between the highest revenue achievable in hindsight and the revenue generated by a mechanism. We propose a closed-form mechanism and prove that its ex-post regret is at most a constant multiple (dependent on the equity level) of the optimal worst-case regret. When bidders' value supports are identical, this factor is less than 1.31 across all equity levels. As a benchmark, we also study a stochastic mechanism design problem that assumes known bidder value distributions and maximizes expected revenue. We characterize the optimal mechanism under standard independence and regularity assumptions. Both mechanisms can be interpreted as set-asides, a common policy tool that reserves a fraction of goods for minority groups. Numerical results demonstrate that the stochastic mechanism performs well when the bidders' value distribution is accurately estimated, while the regret-based mechanism exhibits greater robustness under estimation errors.

An earlier iteration of this paper was disseminated under a different title ('Equitable Auction Design: With and Without Distributions'). The current manuscript substantially extends and supersedes that preliminary version