Budget-feasible Mechanisms for Representing Groups of Agents Proportionally
Authors: Xiang Liu, Hau Chan, Minming Li, Weiwei Wu
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The proposed mechanisms guarantee desirable theoretical properties including budget feasibility, individual rationality, truthfulness, and approximation guarantee. In particular, for (1), we construct a novel greedy mechanism that considers all possible proportion ratios and appropriate payment schemes that select agents from each group satisfying the ratios and ensuring budget feasibility. The proposed mechanism achieves approximation performance that depends on the size of the largest and smallest groups. Moreover, we show the asymptotic matching lower bound that no budget-feasible proportion-representative mechanisms can achieve better performance asymptotically. |
| Researcher Affiliation | Academia | 1Southeast University, China 2University of Nebraska Lincoln, Nebraska, USA 3City University of Hong Kong, Hong Kong SAR, China |
| Pseudocode | Yes | Algorithm 1: Mechanism BPSG(B, b, S, G), Algorithm 2: Mechanism BPMG-S(B, b, S, G), Algorithm 3: Function Agent Select( S, G, k) |
| Open Source Code | No | The paper does not include an unambiguous statement about releasing source code for the described methodology, nor does it provide a direct link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve experiments with datasets; therefore, it does not mention public dataset availability or access information. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation or data splitting (training, validation, test sets). |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or system-level training settings. |