Deterministic Impartial Selection with Weights
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929447657013248 |
|---|---|
| author | Cembrano, Javier Griesbach, Svenja M. Stahlberg, Maximilian J. |
| author_facet | Cembrano, Javier Griesbach, Svenja M. Stahlberg, Maximilian J. |
| contents | In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is $α$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $α$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14991 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Deterministic Impartial Selection with Weights Cembrano, Javier Griesbach, Svenja M. Stahlberg, Maximilian J. Computer Science and Game Theory Theoretical Economics In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is $α$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $α$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$. |
| title | Deterministic Impartial Selection with Weights |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2310.14991 |