All are welcome to attend.

Title:

"User-Centered Algorithmic Mechanism Design"

Abstract:

In algorithmic mechanism design, classical desiderata are typically seller-centered and

aim to protecting them and maximizing their well-being. 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 outputs 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 preexisting 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 itemsymmetric 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