Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Budget Feasible Mechanisms on Matroids

Uproszczony widok
dc.abstract.enMotivated 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 M=(E,I) 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryKanada
dc.conference.datefinish2017-06-28
dc.conference.datestart2017-06-26
dc.conference.placeWaterloo
dc.conference.seriesConference on Integer Programming and Combinatorial Optimization
dc.conference.seriesConference on Integer Programming and Combinatorial Optimization
dc.conference.seriesshortcutIPCO
dc.conference.shortcutIPCO 2017
dc.conference.weblinkhttp://www.math.uwaterloo.ca/ipco2017/
dc.contributor.authorLeonardi, Stefano
dc.contributor.authorMonaco, Gianpiero
dc.contributor.authorSankowski, Piotr
dc.contributor.authorZhang, Qiang
dc.date.accessioned2024-01-24T18:57:13Z
dc.date.available2024-01-24T18:57:13Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.identifier.doi10.1007/978-3-319-59250-3_30
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/102582
dc.identifier.weblinkhttp://link.springer.com/content/pdf/10.1007/s00453-020-00781-9.pdf
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages368-379
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleBudget Feasible Mechanisms on Matroids
dc.typeJournalArticle
dspace.entity.typePublication