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.
Budget Feasible Mechanisms on Matroids / Leonardi, S.; Monaco, G.; Sankowski, P.; Zhang, Q.. - In: ALGORITHMICA. - ISSN 0178-4617. - (2020). [10.1007/s00453-020-00781-9]
Budget Feasible Mechanisms on Matroids
Leonardi 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.File | Dimensione | Formato | |
---|---|---|---|
Leonardi_preprint_Budget-Feasible_2020.pdf
accesso aperto
Note: DOI: 10.1007/s00453-020-00781-9
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
313.15 kB
Formato
Adobe PDF
|
313.15 kB | Adobe PDF | |
Leonardi_Budget-Feasible_2020.pdf
solo gestori archivio
Note: Article in press
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.05 MB
Formato
Adobe PDF
|
1.05 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.