Impartial Selection Under Combinatorial Constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912052206895104 |
|---|---|
| author | Cembrano, Javier Klimm, Max Merino, Arturo |
| author_facet | Cembrano, Javier Klimm, Max Merino, Arturo |
| contents | Impartial selection problems are concerned with the selection of one or more agents from a set based on mutual nominations from within the set. To avoid strategic nominations of the agents, the axiom of impartiality requires that the selection of each agent is independent of the nominations cast by that agent. This paper initiates the study of impartial selection problems where the nominations are weighted and the set of agents that can be selected is restricted by a combinatorial constraint. We call a selection mechanism $α$-optimal if, for every instance, the ratio between the total sum of weighted nominations of the selected set and that of the best feasible set of agents is at least $α$. We show that a natural extension of a mechanism studied for the selection of a single agent remains impartial and $\frac{1}{4}$-optimal for general independence systems, and we generalize upper bounds from the selection of multiple agents by parameterizing them by the girth of the independence system. We then focus on independence systems defined by knapsack and matroid constraints, giving impartial mechanisms that exploit a greedy order of the agents and achieve approximation ratios of $\frac{1}{3}$ and $\frac{1}{2}$, respectively, when agents cast a single nomination. For graphic matroids, we further devise an impartial and $\frac{1}{3}$-optimal mechanism for an arbitrary number of unweighted nominations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20477 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Impartial Selection Under Combinatorial Constraints Cembrano, Javier Klimm, Max Merino, Arturo Computer Science and Game Theory Theoretical Economics Impartial selection problems are concerned with the selection of one or more agents from a set based on mutual nominations from within the set. To avoid strategic nominations of the agents, the axiom of impartiality requires that the selection of each agent is independent of the nominations cast by that agent. This paper initiates the study of impartial selection problems where the nominations are weighted and the set of agents that can be selected is restricted by a combinatorial constraint. We call a selection mechanism $α$-optimal if, for every instance, the ratio between the total sum of weighted nominations of the selected set and that of the best feasible set of agents is at least $α$. We show that a natural extension of a mechanism studied for the selection of a single agent remains impartial and $\frac{1}{4}$-optimal for general independence systems, and we generalize upper bounds from the selection of multiple agents by parameterizing them by the girth of the independence system. We then focus on independence systems defined by knapsack and matroid constraints, giving impartial mechanisms that exploit a greedy order of the agents and achieve approximation ratios of $\frac{1}{3}$ and $\frac{1}{2}$, respectively, when agents cast a single nomination. For graphic matroids, we further devise an impartial and $\frac{1}{3}$-optimal mechanism for an arbitrary number of unweighted nominations. |
| title | Impartial Selection Under Combinatorial Constraints |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2409.20477 |