Budget Feasible Mechanisms Over Graphs


  • Xiang Liu Southeast University, Nanjing, P.R. China
  • Weiwei Wu Southeast University, Nanjing, P.R. China
  • Minming Li City University of Hong Kong, Hongkong, P.R. China City University of Hong Kong Shenzhen Research Institute, Shenzhen, P.R. China
  • Wanyuan Wang Southeast Univerity, Nanjing, P.R. China




Auctions and Market-Based Systems


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.




How to Cite

Liu, X., Wu, W., Li, M., & Wang, W. (2021). Budget Feasible Mechanisms Over Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5549-5556. https://doi.org/10.1609/aaai.v35i6.16698



AAAI Technical Track on Game Theory and Economic Paradigms