Fairness and Incentive Compatibility via Percentage Fees
Pages 517 - 535
Abstract
We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentive-compatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model.
We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results.
References
[1]
Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2017. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9--11, 2017, Berkeley, CA, USA (LIPIcs, Vol. 67), Christos H. Papadimitriou (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 36:1--36:12.
[2]
Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2--9, 2021. AAAI Press, 5119--5126. https://ojs.aaai.org/index.php/AAAI/article/view/16647
[3]
Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. 2020. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. In 28th Annual European Symposium on Algorithms, ESA 2020, September 7--9, 2020, Pisa, Italy (Virtual Conference) (LIPIcs, Vol. 173), Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11:1--11:17.
[4]
Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang. 2021. Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. CoRR abs/2110.00767 (2021). arXiv:2110.00767 https://arxiv.org/abs/2110.00767
[5]
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation. 557--574.
[6]
Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer, and Chris Umans. 2010. Inapproximability for VCG-Based Combinatorial Auctions. In ACM-SIAM SODA. 518--536.
[7]
Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119, 6 (2011), 1061--1103.
[8]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. 2019. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC) 7, 3 (2019), 1--32.
[9]
E. H. Clarke. 1971. Multipart Pricing of Public Goods. Public Choice (1971), 17--33.
[10]
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. 2011. Truth, Envy, and Truthful Market Clearing Bundle Pricing. In Internet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11--14, 2011. Proceedings (Lecture Notes in Computer Science, Vol. 7090), Ning Chen, Edith Elkind, and Elias Koutsoupias (Eds.). Springer, 97--108.
[11]
Richard Cole and Vasilis Gkatzelis. 2015. Approximating the Nash social welfare with indivisible items. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 371--380.
[12]
Richard Cole, Vasilis Gkatzelis, and Gagan Goel. 2013. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the fourteenth ACM conference on Electronic commerce. 251--268.
[13]
Amit Daniely, Michael Schapira, and Gal Shahaf. 2015. Inapproximability of truthful mechanisms via generalizations of the VC dimension. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. 401--408.
[14]
Shahar Dobzinski. 2007. Two Randomized Mechanisms for Combinatorial Auctions. In APPROX. 89--103.
[15]
Shahar Dobzinski. 2011. An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations. In STOC. 139--148.
[16]
Shahar Dobzinski and Noam Nisan. 2007. Limitations of VCG-Based Mechanisms. In STOC. 338--344.
[17]
Shahar Dobzinski and Noam Nisan. 2010. Mechanisms for multi-unit auctions. Journal of Artificial Intelligence Research 37 (2010), 85--98.
[18]
Shahar Dobzinski, Noam Nisan, and Michael Schapira. 2010. Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders. Math. Oper. Res. 35, 1 (2010), 1--13.
[19]
Shahar Dobzinski and Jan Vondrák. 2012. The computational complexity of truthfulness in combinatorial auctions. In EC. 405--422.
[20]
Shaddin Dughmi and Jan Vondrák. 2011. Limitations of randomized mechanisms for combinatorial auctions. In FOCS. 502--511.
[21]
Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, and Jan Vondrák. 2023. Approximating Nash Social Welfare by Matching and Local Search. STOC (2023).
[22]
Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. 2020. Approximating Nash social welfare under submodular valuations through (un) matchings. In Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms. SIAM, 2673--2687.
[23]
T. Groves. 1973. Incentives in teams. Econometrica (1973), 617--631.
[24]
Herman B Leonard. 1983. Elicitation of honest preferences for the assignment of individuals to positions. Journal of political Economy 91, 3 (1983), 461--479.
[25]
Wenzheng Li and Jan Vondrák. 2022. A constant-factor approximation algorithm for Nash social welfare with submodular valuations. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 25--36.
[26]
R. B. Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58--73.
[27]
Kevin Roberts. 1979. The characterization of implementable choice rules. In Aggregation and Revelation of Preferences. Papers presented at the first European Summer Workshop of the Economic Society, Jean-Jacques Laffont (Ed.). North-Holland, 321--349.
[28]
W. Vickrey. 1961. Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance (1961), 8--37.
Index Terms
- Fairness and Incentive Compatibility via Percentage Fees
Recommendations
Testing Incentive Compatibility in Display Ad Auctions
WWW '18: Proceedings of the 2018 World Wide Web ConferenceConsider a buyer participating in a repeated auction, such as those prevalent in display advertising. How would she test whether the auction is incentive compatible? To bid effectively, she is interested in whether the auction is single-shot incentive ...
Budget-Constrained Incentive Compatibility for Stationary Mechanisms
EC '20: Proceedings of the 21st ACM Conference on Economics and ComputationMotivated by online advertising applications, we study incentive properties of stationary mechanisms that satisfy budget constraints in expectation at a stationary equilibrium. We consider a general repeated auction setting where a seller sells ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1253 pages
ISBN:9798400701047
DOI:10.1145/3580507
- Chair:
- Kevin Leyton-Brown,
- Program Chair:
- Jason D Hartline,
- Program Co-chair:
- Larry Samuelson
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 July 2023
Check for updates
Qualifiers
- Research-article
Funding Sources
Conference
EC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Upcoming Conference
EC '25
- Sponsor:
- sigecom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 277Total Downloads
- Downloads (Last 12 months)146
- Downloads (Last 6 weeks)81
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in