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.
2020
Budget feasible mechanisms; Hereditary property; Matroid intersection; Mechanism design
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1470518
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact