Budget Feasible Mechanisms Over Graphs
Authors: Xiang Liu, Weiwei Wu, Minming Li, Wanyuan Wang5549-5556
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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, incentivecompatibility 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. |
| Researcher Affiliation | Academia | Xiang Liu1, , Weiwei Wu1, , Minming Li2,3, Wanyuan Wang1, 1 Southeast University, Nanjing, P.R. China 2 City University of Hong Kong, Hongkong, P.R. China 3 City University of Hong Kong Shenzhen Research Institute, Shenzhen, P.R. China {xiangliu,weiweiwu}@seu.edu.cn, minming.li@cityu.edu.hk, wywang@seu.edu.cn |
| Pseudocode | Yes | Algorithm 1: Mechanism BDM-H(B, b , S, Nmax); Algorithm 2: Mechanism BDM-G(B, b , S, Nmax) |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments on a dataset. The 'Running example' described is illustrative and does not involve an actual dataset or data splits for training, validation, or testing. |
| Dataset Splits | No | This paper is theoretical and does not conduct empirical experiments with datasets. Therefore, there is no mention of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware (e.g., GPU models, CPU models, or cloud computing resources) used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies, libraries, or solvers with version numbers used for implementing or testing the mechanisms. |
| Experiment Setup | No | The paper is theoretical and focuses on mechanism design and proofs. It does not include details on experimental setup such as hyperparameters, model initialization, training schedules, or system-level settings, as no empirical experiments were conducted. |