Algorithmic Contract Design for Crowdsourced Ranking
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917573796298752 |
|---|---|
| author | Frangias, Kiriaki Lin, Andrew Vitercik, Ellen Zampetakis, Manolis |
| author_facet | Frangias, Kiriaki Lin, Andrew Vitercik, Ellen Zampetakis, Manolis |
| contents | Ranking is fundamental to many areas, such as search engine optimization, human feedback for language models, as well as peer grading. Crowdsourcing, which is often used for these tasks, requires proper incentivization to ensure accurate inputs. In this work, we draw on the field of \emph{contract theory} from Economics to propose a novel mechanism that enables a \emph{principal} to accurately rank a set of items by incentivizing agents to provide pairwise comparisons of the items. Our mechanism implements these incentives by verifying a subset of each agent's comparisons, a task we assume to be costly. The agent is compensated (for example, monetarily or with class credit) based on the accuracy of these comparisons. Our mechanism achieves the following guarantees: (1) it only requires the principal to verify $O(\log s)$ comparisons, where $s$ is the total number of agents, and (2) it provably achieves higher total utility for the principal compared to ranking the items herself with no crowdsourcing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09974 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Algorithmic Contract Design for Crowdsourced Ranking Frangias, Kiriaki Lin, Andrew Vitercik, Ellen Zampetakis, Manolis Computer Science and Game Theory Ranking is fundamental to many areas, such as search engine optimization, human feedback for language models, as well as peer grading. Crowdsourcing, which is often used for these tasks, requires proper incentivization to ensure accurate inputs. In this work, we draw on the field of \emph{contract theory} from Economics to propose a novel mechanism that enables a \emph{principal} to accurately rank a set of items by incentivizing agents to provide pairwise comparisons of the items. Our mechanism implements these incentives by verifying a subset of each agent's comparisons, a task we assume to be costly. The agent is compensated (for example, monetarily or with class credit) based on the accuracy of these comparisons. Our mechanism achieves the following guarantees: (1) it only requires the principal to verify $O(\log s)$ comparisons, where $s$ is the total number of agents, and (2) it provably achieves higher total utility for the principal compared to ranking the items herself with no crowdsourcing. |
| title | Algorithmic Contract Design for Crowdsourced Ranking |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2310.09974 |