License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.42
URN: urn:nbn:de:0030-drops-156385
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15638/
Chawla, Shuchi ;
Jagadeesan, Meena
Individual Fairness in Advertising Auctions Through Inverse Proportionality
Abstract
Recent empirical work demonstrates that online advertisement can exhibit bias in the delivery of ads across users even when all advertisers bid in a non-discriminatory manner. We study the design ad auctions that, given fair bids, are guaranteed to produce fair outcomes. Following the works of Dwork and Ilvento [2019] and Chawla et al. [2020], our goal is to design a truthful auction that satisfies "individual fairness" in its outcomes: informally speaking, users that are similar to each other should obtain similar allocations of ads. Within this framework we quantify the tradeoff between social welfare maximization and fairness.
This work makes two conceptual contributions. First, we express the fairness constraint as a kind of stability condition: any two users that are assigned multiplicatively similar values by all the advertisers must receive additively similar allocations for each advertiser. This value stability constraint is expressed as a function that maps the multiplicative distance between value vectors to the maximum allowable ?_{∞} distance between the corresponding allocations. Standard auctions do not satisfy this kind of value stability.
Second, we introduce a new class of allocation algorithms called Inverse Proportional Allocation that achieve a near optimal tradeoff between fairness and social welfare for a broad and expressive class of value stability conditions. These allocation algorithms are truthful and prior-free, and achieve a constant factor approximation to the optimal (unconstrained) social welfare. In particular, the approximation ratio is independent of the number of advertisers in the system. In this respect, these allocation algorithms greatly surpass the guarantees achieved in previous work. We also extend our results to broader notions of fairness that we call subset fairness.
BibTeX - Entry
@InProceedings{chawla_et_al:LIPIcs.ITCS.2022.42,
author = {Chawla, Shuchi and Jagadeesan, Meena},
title = {{Individual Fairness in Advertising Auctions Through Inverse Proportionality}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {42:1--42:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15638},
URN = {urn:nbn:de:0030-drops-156385},
doi = {10.4230/LIPIcs.ITCS.2022.42},
annote = {Keywords: Algorithmic fairness, advertising auctions}
}
|
Keywords: |
|
Algorithmic fairness, advertising auctions |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
