Prof. Matt Weinberg (adviser) ,
Prof. Mark Braverman (reader),
Prof. Rediet Abebe (reader),
Prof. Zeev Dvir (examiner), and
Prof. Huacheng Yu (examiner).
All are welcome to attend.
In algorithmic mechanism design, classical desiderata are typically seller-centered: the objectives aim to protect and maximize the well-being of the sellers. Examples of such objectives are efficiency, revenue or profit maximization, and strategyproofness. This often creates negative externalities that harm the users purchasing the goods and the people targeted by the market. Examples of such externalities are not treating the users fairly and equally, not protecting against malicious or adversarial sellers, and not maximizing the social welfare or utility of the users. Many frameworks attempt to mitigate these undesirable outcomes by either setting constraints on current goals or by redesigning the goals altogether. In our work, we focus on the latter and design frameworks that center user well-being. 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 the classical seller-centered desiderata such as profit-maximization and strategyproofness?
The challenge stems from balancing (sometimes conflicting) interests of both parties and using tools from algorithmic game theory to ensure that all the agents involved will behave as expected and the desired output is achieved. In this thesis, we present three different settings where we study such problems.
--------------------------------------------------------------------
Project 1. First, in [1] we consider a revenue-maximizing seller with multiple items for sale to a single population of buyers. Our main result shows that for a single population of additive buyers with independent (but not necessarily identically distributed) item values, bundling all items together achieves a constant-factor approximation to the revenue-optimal item-symmetric mechanism. We motivate this direction via fairness in ad auctions. In ad auction domains the items correspond to views from particular demographics, and recent works have therefore identified a novel fairness constraint: equally-qualified users from different demographics should be shown the same desired ad at equal rates. Prior work abstracts this to the following fairness guarantee: if an advertiser places an identical bid on two users, those two users should view the ad with the same probability. We first propose a relaxation of this guarantee from worst-case to Bayesian settings, which circumvents strong impossibility results from these works, and then study this guarantee through the lens of symmetries, as any item-symmetric auction is also fair (by this definition). Observe that in this domain, bundling all items together corresponds to concealing all demographic data.
Project 2. Next, in [2] we consider a revenue-maximizing seller with a single item for sale to multiple buyers with independent and identically distributed valuations. Previous work showed that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. 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.
Project 3. Finally, in [3] we study a problem inspired by regulated health insurance markets, such as those created by the government in the Affordable Care Act Exchanges or by employers when they contract with private insurers to provide plans for their employees. The market regulator can choose to do nothing, running a Free Market, or can exercise her regulatory power by limiting the entry of providers (decreasing consumer welfare by limiting options, but also decreasing revenue via enhanced competition). We investigate whether limiting entry increases or decreases the utility (welfare minus revenue) of the consumers who purchase from the providers, specifically in settings where the outside option of "purchasing nothing" is prohibitively undesirable.
--------------------------------------------------------------------
[1] M. Essaidi, S. M. Weinberg. On symmetries and fairness in multi-dimensional mechanism design. In: Proceedings of the 17th International Conference on Web and Internet Economics, 2021, p. 59–75.
[2] M. Essaidi, M. V. X. Ferreira, S. M. Weinberg. Credible, strategyproof, optimal, and bounded expected-round single-item auctions for all distributions. In: Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022, pp. 66:1–66:19.
[3] M. Essaidi, K. Goldner, S. M. Weinberg. When to limit market entry under mandatory purchase. In: 3rd Workshop on Mechanism Design for Social Good, arXiv preprint arXiv:2002.06326 (2019).