Budget Feasible Mechanisms Over Graphs

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efficient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.