The Power of Verification for Greedy Mechanism Design

摘要: Greedy algorithms are known to provide near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders, ignoring incentive compatibility. Borodin and Lucier [5] however proved that truthful greedy-like mechanisms CAs multi-minded bidders do not achieve good guarantees. In this work, we seek a deeper understanding of greedy mechanism design investigate under which general assumptions, can have efficient CAs. Towards goal, use the framework priority weak strong verification, where allowed overbid on their winning set or any subsets set, respectively. We complete characterization power verification showing it is sufficient necessary fixed algorithm become money not, depending ordering bids. Moreover, show [20], 2-approximate submodular CAs, in finite bidding domains. Our proof based an interesting structural analysis strongly connected components declaration graph.