User-Centered Algorithmic Mechanism Design: theoretical frameworks at different levels of central regulation

Abstract

In algorithmic mechanism design, classical desiderata define standards used to evaluate the performance of an algorithm or mechanism. Examples of such desiderata are efficiency, revenue maximization, and strategyproofness. These desiderata are oftentimes seller-centered and tend to create negative externalities that harm the users targeted by the market. Examples of such externalities are not treating the users equally, not protecting against adversarial sellers, and not maximizing user utility. In this thesis, we explore the frontier between user-centric and seller-centric performance at different levels of leverage offered by central regulation. We ask: how can we design new solutions that prioritize user-centered desiderata while maintaining the pre-existing seller-centered desiderata or without too great a cost to them? We present theoretical frameworks at three levels of intervention: no regulation for private goods, minimal regulation for "protected" goods, and significant regulation for essential and public goods. Our first framework is credible auctions. We consider a revenue-maximizing seller with a single item for sale to multiple users with independent-and-identically-distributed valuations. In this work, assuming the existence of cryptographically-secure commitment schemes, we identify a new single-item auction that is credible, strategyproof, revenue-optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price. Our second framework is fair and symmetric ad auctions. We consider a revenue-maximizing seller with multiple items for sale to a single population of additive buyers with independent item values. We motivate this via fairness in ad auctions where items correspond to (views from) users, and equally-qualified users from different demographics should be shown the same desired ad at equal rates. We show that bundling all items together achieves a constant-factor approximation to the revenue-optimal item-symmetric mechanism; as any item-symmetric auction is also fair. Observe that in this domain, bundling all items together corresponds to concealing all demographic data. Our last framework is markets with mandatory purchase. We study a problem inspired by regulated health-insurance markets, and investigate whether limiting entry of providers increases or decreases the utility (welfare minus revenue) of users who purchase from the providers, specifically in settings where the outside option of "purchasing nothing" is prohibitively undesirable.