Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910972943269888 |
|---|---|
| author | Amanatidis, Georgios Klumper, Sophie Markakis, Evangelos Schäfer, Guido Tsikiridis, Artem |
| author_facet | Amanatidis, Georgios Klumper, Sophie Markakis, Evangelos Schäfer, Guido Tsikiridis, Artem |
| contents | Budget-feasible procurement has been a major paradigm in mechanism design since its introduction by Singer (2010). An auctioneer (buyer) with a strict budget constraint is interested in buying goods or services from a group of strategic agents (sellers). In many scenarios it makes sense to allow the auctioneer to only partially buy what an agent offers, e.g., an agent might have multiple copies of an item to sell, they might offer multiple levels of a service, or they may be available to perform a task for any fraction of a specified time interval. Nevertheless, the focus of the related literature has been on settings where each agent's services are either fully acquired or not at all. The main reason for this, is that in settings with partial allocations like the ones mentioned, there are strong inapproximability results. Under the mild assumption of being able to afford each agent entirely, we are able to circumvent such results in this work. We design a polynomial-time, deterministic, truthful, budget-feasible $(2+\sqrt{3})$-approximation mechanism for the setting where each agent offers multiple levels of service and the auctioneer has a discrete separable concave valuation function. We then use this result to design a deterministic, truthful and budget-feasible $O(1)$-approximation mechanism for the setting where any fraction of a service can be acquired and the auctioneer's valuation function is separable concave (i.e., the sum of concave functions). For the special case of a linear valuation function, we improve the best known approximation ratio for the problem from $1+ϕ$ (by Klumper & Schäfer (2022)) to $2$. This establishes a separation between this setting and its indivisible counterpart. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_07385 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents Amanatidis, Georgios Klumper, Sophie Markakis, Evangelos Schäfer, Guido Tsikiridis, Artem Computer Science and Game Theory Budget-feasible procurement has been a major paradigm in mechanism design since its introduction by Singer (2010). An auctioneer (buyer) with a strict budget constraint is interested in buying goods or services from a group of strategic agents (sellers). In many scenarios it makes sense to allow the auctioneer to only partially buy what an agent offers, e.g., an agent might have multiple copies of an item to sell, they might offer multiple levels of a service, or they may be available to perform a task for any fraction of a specified time interval. Nevertheless, the focus of the related literature has been on settings where each agent's services are either fully acquired or not at all. The main reason for this, is that in settings with partial allocations like the ones mentioned, there are strong inapproximability results. Under the mild assumption of being able to afford each agent entirely, we are able to circumvent such results in this work. We design a polynomial-time, deterministic, truthful, budget-feasible $(2+\sqrt{3})$-approximation mechanism for the setting where each agent offers multiple levels of service and the auctioneer has a discrete separable concave valuation function. We then use this result to design a deterministic, truthful and budget-feasible $O(1)$-approximation mechanism for the setting where any fraction of a service can be acquired and the auctioneer's valuation function is separable concave (i.e., the sum of concave functions). For the special case of a linear valuation function, we improve the best known approximation ratio for the problem from $1+ϕ$ (by Klumper & Schäfer (2022)) to $2$. This establishes a separation between this setting and its indivisible counterpart. |
| title | Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2307.07385 |