Budget Feasible Mechanisms on Matroids
- PDF / 1,072,829 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 248 Views
Budget Feasible Mechanisms on Matroids Stefano Leonardi1 · Gianpiero Monaco2 · Piotr Sankowski3 · Qiang Zhang1 Received: 23 July 2019 / Accepted: 26 October 2020 © The Author(s) 2020
Abstract Motivated by many practical applications, in this paper we study budget feasible mechanisms with the goal of procuring an independent set of a matroid. More specifically, we are given a matroid M = (E, I) . Each element of the ground set E is controlled by a selfish agent and the cost of the element is private information of the agent itself. A budget limited buyer has additive valuations over the elements of E. The goal is to design an incentive compatible budget feasible mechanism which procures an independent set of the matroid of largest possible value. We also consider the more general case of the pair M = (E, I) satisfying only the hereditary property. This includes matroids as well as matroid intersection. We show that, given a polynomial time deterministic algorithm that returns an 𝛼-approximation to the problem of finding a maximum-value independent set in M , there exists an individually rational, truthful and budget feasible mechanism which is (3𝛼 + 1)-approximated and runs in polynomial time, thus yielding also a 4-approximation for the special case of matroids. Keywords Mechanism design · Budget feasible mechanisms · Matroid intersection · Hereditary property
A preliminary version of this work appeared in the Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization (IPCO) [20]. This work was partially supported by FET IP project MULTIPEX 317532, by the polish funds for years 2011–2015 for cofinanced international projects, NCN Grant UMO-2014/13/B/ST6/00770, ERC Project PAAL-POC 680912. It was also partly supported by the Google Focused Award on Algorithms for Large-scale Data Analysis, ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets”, and MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets” * Stefano Leonardi [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction Procurement auctions (a.k.a. reverse auctions) are executed by governments or private companies to purchase commodities and services from providers. The budget that can be spent in a procurement auction is often limited thus imposing a limit on the total payments that can be handled to the providers. Motivated by the setting described above, in this work we study the problem of a budget limited buyer with additive valuations on a set of indivisible items, each item controlled from an independent strategic agent. More specifically, we assume rational agents with quasilinear utilities, i.e., they aim to maximize the difference between the payment they receive and the true cost of the item. We consider the case of a buyer that is constrained to purchase a subset of objects that forms an independent set of an underlying matroid structure. Matroids are in
Data Loading...
