Bicriteria Multidimensional Mechanism Design with Side Information
Authors: Siddharth Prasad, Maria-Florina F. Balcan, Tuomas Sandholm
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop a versatile new methodology for multidimensional mechanism design that incorporates side information about agent types to generate high social welfare and high revenue simultaneously. In this paper we adopt a prior-free perspective that makes no assumptions on the correctness, accuracy, or source of the side information. First, we design a meta-mechanism that integrates input side information with an improvement of the classical VCG mechanism. The welfare, revenue, and incentive properties of our meta-mechanism are characterized by novel constructions we introduce based on the notion of a weakest competitor, which is an agent that has the smallest impact on welfare. We show that our meta-mechanism, when carefully instantiated, simultaneously achieves strong welfare and revenue guarantees parameterized by errors in the side information. When the side information is highly informative and accurate, our mechanism achieves welfare and revenue competitive with the total social surplus, and its performance decays continuously and gradually as the quality of the side information decreases. Finally, we apply our meta-mechanism to a setting where each agent s type is determined by a constant number of parameters. Specifically, agent types lie on constant-dimensional subspaces (of the potentially high-dimensional ambient type space) that are known to the mechanism designer. We use our meta-mechanism to obtain the first known welfare and revenue guarantees in this setting. |
| Researcher Affiliation | Collaboration | Maria-Florina Balcan School of Computer Science Carnegie Mellon University ninamf@cs.cmu.edu Siddharth Prasad Computer Science Department Carnegie Mellon University sprasad2@cs.cmu.edu Tuomas Sandholm Computer Science Department Carnegie Mellon University Optimized Markets, Inc. Strategy Robot, Inc. Strategic Machine, Inc. sandholm@cs.cmu.edu |
| Pseudocode | Yes | Meta-mechanism M Input: subsets eΘ1, . . . , eΘn Θ given to mechanism designer. Based on eΘ1, . . . , eΘn, come up with bΘ1, . . . , bΘn. Agents asked to reveal types θ1, . . . , θn. Let α = argmaxα Γ Pn i=1 θi[α] and for each i let pi = mineθi WC(bΘi) maxα Γ Pj =i θj[α] + eθi[α] Pj =i θj[α ]. Let I = {i : θi[α ] pi 0} . If agent i / I, i is excluded and receives zero utility (zero value and zero payment).a If agent i I, i enjoys allocation α and pays pi. |
| Open Source Code | No | The paper does not provide any links to open-source code or explicitly state that code for their methodology is available. |
| Open Datasets | No | The paper is theoretical and does not describe experiments with datasets, nor does it mention any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware used for any computational experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers for reproducing experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |