Qiang Zhang, Institute of Informatics, University of Warsaw
Title: Budget Feasible Mechanisms on Matchings
We study budget feasible mechanisms where the goal is to procure matchings from graphs under given budgets. More specially, we are given a buyer with a budget and a graph G = (V,E) where each edge is owned by a selfish agent. The weight of each edge is public knowledge while the cost of each edge is only known to the selfish agent.The objective of the buyer is to design budget feasible mechanisms which give selfish agents incentives for declaring true costs of edges and procure matchings under the budget of the buyer. Moreover, the buyer would like to want those mechanisms to approximate the optimal weighted matching in i graph G under the given budget. Our result is a deterministic, polynomial-time, budget feasible, individual rational and truthful mechanism with 4-approximation to the optimal weighted matching under the budget of the buyer.