Motivated by many practical applications, in this paper we study budget feasible mechanisms where the goal is to procure independent sets from matroids. More specifically, we are given a matroid =(,) where each ground (indivisible) element is a selfish agent. The cost of each element (i.e., for selling the item or performing a service) is only known to the element itself. There is a buyer with a budget having additive valuations over the set of elements E. The goal is to design an incentive compatible (truthful) budget feasible mechanism which procures an independent set of the matroid under the given budget that yields the largest value possible to the buyer. Our result is a deterministic, polynomial-time, individually rational, truthful and budget feasible mechanism with 4-approximation to the optimal independent set. Then, we extend our mechanism to the setting of matroid intersections in which the goal is to procure common independent sets from multiple matroids. We show that, given a polynomial time deterministic blackbox that returns -approximation solutions to the matroid intersection problem, there exists a deterministic, polynomial time, individually rational, truthful and budget feasible mechanism with (3+1) -approximation to the optimal common independent set.

Budget feasible mechanisms on matroids / Leonardi, Stefano; Monaco, Gianpiero; Sankowski, Piotr; Zhang, Qiang. - 10328:(2017), pp. 368-379. ((Intervento presentato al convegno 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 tenutosi a Waterloo; Canada nel 2017 [10.1007/978-3-319-59250-3_30].

Budget feasible mechanisms on matroids

Leonardi, Stefano;Sankowski, Piotr;Zhang, Qiang
2017

Abstract

Motivated by many practical applications, in this paper we study budget feasible mechanisms where the goal is to procure independent sets from matroids. More specifically, we are given a matroid =(,) where each ground (indivisible) element is a selfish agent. The cost of each element (i.e., for selling the item or performing a service) is only known to the element itself. There is a buyer with a budget having additive valuations over the set of elements E. The goal is to design an incentive compatible (truthful) budget feasible mechanism which procures an independent set of the matroid under the given budget that yields the largest value possible to the buyer. Our result is a deterministic, polynomial-time, individually rational, truthful and budget feasible mechanism with 4-approximation to the optimal independent set. Then, we extend our mechanism to the setting of matroid intersections in which the goal is to procure common independent sets from multiple matroids. We show that, given a polynomial time deterministic blackbox that returns -approximation solutions to the matroid intersection problem, there exists a deterministic, polynomial time, individually rational, truthful and budget feasible mechanism with (3+1) -approximation to the optimal common independent set.
978-3-319-59249-7
978-3-319-59250-3
File allegati a questo prodotto
File Dimensione Formato  
Leonardi_Postprint_Budget-Feasible-Mechanisms_2017.pdf

accesso aperto

Note: https://link.springer.com/chapter/10.1007/978-3-319-59250-3_30
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 318.27 kB
Formato Adobe PDF
318.27 kB Adobe PDF Visualizza/Apri PDF
Leonardi_Budget-Feasible-Mechanisms_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 229.86 kB
Formato Adobe PDF
229.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/1073150
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact