Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.14173 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909115786199040 |
|---|---|
| author | Dobzinski, Shahar Oren, Sigal Vondrak, Jan |
| author_facet | Dobzinski, Shahar Oren, Sigal Vondrak, Jan |
| contents | 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 \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14173 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fairness and Incentive Compatibility via Percentage Fees Dobzinski, Shahar Oren, Sigal Vondrak, Jan Computer Science and Game Theory 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 \emph{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. |
| title | Fairness and Incentive Compatibility via Percentage Fees |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.14173 |