Packing a Knapsack with Items Owned by Strategic Agents
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913537991901184 |
|---|---|
| author | Cembrano, Javier Klimm, Max Knaack, Martin |
| author_facet | Cembrano, Javier Klimm, Max Knaack, Martin |
| contents | This paper considers a scenario within the field of mechanism design without money where a mechanism designer is interested in selecting items with maximum total value under a knapsack constraint. The items, however, are controlled by strategic agents who aim to maximize the total value of their items in the knapsack. This is a natural setting, e.g., when agencies select projects for funding, companies select products for sale in their shops, or hospitals schedule MRI scans for the day. A mechanism governing the packing of the knapsack is strategyproof if no agent can benefit from hiding items controlled by them to the mechanism. We are interested in mechanisms that are strategyproof and $α$-approximate in the sense that they always approximate the maximum value of the knapsack by a factor of $α\in [0,1]$. First, we give a deterministic mechanism that is $\frac{1}{3}$-approximate. For the special case where all items have unit density, we design a $\frac{1}ϕ$-approximate mechanism where $1/ϕ\approx 0.618$ is the inverse of the golden ratio. This result is tight as we show that no deterministic strategyproof mechanism with a better approximation exists. We further give randomized mechanisms with approximation guarantees of $1/2$ for the general case and $2/3$ for the case of unit densities. For both cases, no strategyproof mechanism can achieve an approximation guarantee better than $1/(5ϕ-7)\approx 0.917$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06080 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Packing a Knapsack with Items Owned by Strategic Agents Cembrano, Javier Klimm, Max Knaack, Martin Computer Science and Game Theory Theoretical Economics Optimization and Control This paper considers a scenario within the field of mechanism design without money where a mechanism designer is interested in selecting items with maximum total value under a knapsack constraint. The items, however, are controlled by strategic agents who aim to maximize the total value of their items in the knapsack. This is a natural setting, e.g., when agencies select projects for funding, companies select products for sale in their shops, or hospitals schedule MRI scans for the day. A mechanism governing the packing of the knapsack is strategyproof if no agent can benefit from hiding items controlled by them to the mechanism. We are interested in mechanisms that are strategyproof and $α$-approximate in the sense that they always approximate the maximum value of the knapsack by a factor of $α\in [0,1]$. First, we give a deterministic mechanism that is $\frac{1}{3}$-approximate. For the special case where all items have unit density, we design a $\frac{1}ϕ$-approximate mechanism where $1/ϕ\approx 0.618$ is the inverse of the golden ratio. This result is tight as we show that no deterministic strategyproof mechanism with a better approximation exists. We further give randomized mechanisms with approximation guarantees of $1/2$ for the general case and $2/3$ for the case of unit densities. For both cases, no strategyproof mechanism can achieve an approximation guarantee better than $1/(5ϕ-7)\approx 0.917$. |
| title | Packing a Knapsack with Items Owned by Strategic Agents |
| topic | Computer Science and Game Theory Theoretical Economics Optimization and Control |
| url | https://arxiv.org/abs/2410.06080 |