Beyond Regularity: Simple versus Optimal Mechanisms, Revisited

A large proportion of the Bayesian mechanism design literature is restricted to the family of regular distributions $\mathbb{F}_{\text {reg }}$ [Mye81] or the family of monotone hazard rate (MHR) distributions $\mathbb{F}_{M H R}$ [BMP63], which has overshadowed this rich and well-developed theory. We (re-)introduce two generalized families: quasi-regular distributions $\mathbb{F}_{Q-r e g}$ and quasi-MHR distributions $\mathbb{F}_{Q-M H R}$. Altogether, these four families form the following hierarchy: $\mathbb{F}_{\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cap \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{\mathrm{reg}}, \mathbb{F}_{Q-\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cup \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{Q-\mathrm{reg}}$ Likewise, the parameterized families of $\lambda$-regular (a.k.a. $\alpha$ strongly regular) distributions [CR14], [SS19], which smoothly interpolate $\mathbb{F}_{\text {reg }}$ and $\mathbb{F}_{\text {MHR }}$, generalize to $\lambda$-quasi-regular distributions. The significance of our new families is manifold. Firstly, their defining conditions are immediate “economic” relaxations of the original defining conditions (e.g., regularity as monotonicity of the virtual value functions), capturing key economic intuitions. Secondly, they satisfy natural mathematical properties (about order statistics) failed for the original families, thus technically more tractable. Thirdly, numerous results (by [BK96], [HR09a], [CD15], [DRY15], [HR14], [AHN ${ }^{+}$19], [JLTX20], [JLQ ${ }^{+}$19b], [FLR19], [GHZ19b], [JLX23], [LM24] etc) known merely for the original families now can extend to our new families. Many of these extensions incur no quantitative loss, or even improve the state of the art for the original families. Finally, beyond the third point, our new families guide us to entirely new perspectives and thus entirely unknown results. For example, regarding revenue maximization for symmetric versus asymmetric regular buyers, we acquire $\frac{1}{2}$ - versus 0.1908 -approximations for the (less-than-)one-sample prophet inequalities, respectively. To the best of our knowledge, such results are blank in the literature, despite their widely-studied welfare maximization counterparts [CDFS22], [RWW20], [CCES20], [CDF ${ }^{+}$21], [CCES24].