Automated Mechanism Design for Classification with Partial Verification
Authors: Hanrui Zhang, Yu Cheng, Vincent Conitzer5789-5796
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of automated mechanism design with partial verification, where each type can (mis)report only a restricted set of types (rather than any other type), induced by the principal s limited verification power. We prove hardness results when the revelation principle does not necessarily hold, as well as when types have even minimally different preferences. In light of these hardness results, we focus on truthful mechanisms in the setting where all types share the same preference over outcomes, which is motivated by applications in, e.g., strategic classification. We present a number of algorithmic and structural results, including an efficient algorithm for finding optimal deterministic truthful mechanisms, which also implies a faster algorithm for finding optimal randomized truthful mechanisms via a characterization based on convexity. |
| Researcher Affiliation | Academia | Hanrui Zhang,1 Yu Cheng, 2 Vincent Conitzer 1 1 Duke University 2 University of Illinois at Chicago hrzhang@cs.duke.edu, yucheng2@uic.edu, conitzer@cs.duke.edu |
| Pseudocode | Yes | Algorithm 1: Finding an optimal deterministic mechanism. Algorithm 2: Finding an optimal (possibly randomized) truthful mechanism. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code is open or publicly available. |
| Open Datasets | No | The paper is theoretical and does not mention using any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation, training, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setup details such as hyperparameters or training configurations. |