Machine learning promises to unlock troves of economic value. As advanced machine-learning techniques proliferate, they raise acute fairness concerns. These concerns must be addressed in order for the economic surpluses and externalities generated by machine learning to benefit society equitably. In this thesis, we focus on the economic context of data markets and theoretically study the impacts of intervening to achieve machine-learning fairness. We find that to effectively and efficiently intervene requires taking the data market into account in the design and application of the fairness intervention, i.e., how the intervention impacts the data market, how the data market impacts the intervention, and how their impacts interact. We study this interaction in two data-market settings to understand what information is necessary. We find that without taking into account the incentive structure and economics of a data market, fairness interventions can induce greater losses to efficiency than are necessary to achieve fairness—even potentially inducing market collapse. Yet, we also find that these losses can be recovered or even amortized away by suitably designing the intervention with appropriate information or under favorable market conditions. Overall, this thesis elucidates how data markets present both novel challenges and opportunities for machine-learning fairness. It demonstrates that efficiently intervening for machine-learning fairness can be more complicated in data markets—even infeasible! Excitingly, however, it also demonstrates that under favorable market conditions, fairness can be achieved at lower relative cost to efficiency than has previously been understood to be possible. We hope that these initial theoretical findings ultimately contribute to the development of efficient and practical fairness interventions suitable for real-world application.

We study two classes of problems within Algorithmic Economics: revenue guarantees of simple mechanisms, and social welfare guarantees of auctions. We develop new structural and algorithmic tools for addressing these problems, and obtain the following results: In the 𝑘-unit model, four canonical mechanisms can be classified as: (i) the discriminating group, including Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous group, including Anonymous Reserve and Anonymous Pricing. We prove that any two mechanisms from the same group have an asymptotically tight revenue gap of 1 + θ(1 /√𝑘), while any two mechanisms from the different groups have an asymptotically tight revenue gap of θ(log 𝑘). In the single-item model, we prove a nearly-tight sample complexity of Anonymous Reserve for every value distribution family investigated in the literature: [0, 1]-bounded, [1, 𝐻]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific sample complexity poly(𝜖⁻¹) depends on the precision 𝜖 ∈ (0, 1), but not on the number of bidders 𝑛 ≥ 1. Further, in the two bounded-support settings, our algorithm allows correlated value distributions. These are in sharp contrast to the previous (nearly-tight) sample complexity results on Myerson Auction. In the single-item model, we prove that the tight Price of Anarchy/Stability for First Price Auctions are both PoA = PoS = 1 - 1/𝜖² ≈ 0.8647.