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

Monaco G.;
2021-01-01

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 in questo prodotto:
File Dimensione Formato  
s00453-020-00781-9.pdf

accesso aperto

Tipologia: PDF editoriale
Dimensione 1.62 MB
Formato Adobe PDF
1.62 MB Adobe PDF Visualizza/Apri

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/11564/795068
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact