Probabilistic Verification for Obviously Strategyproof Mechanisms
Authors: Diodato Ferraioli, Carmine Ventre
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | To this aim, we define a model of probabilistic verification wherein agents are caught misbehaving with a certain probability, and show how OSP mechanisms can implement every social choice function at the cost of either imposing very large fines or verifying a linear number of agents. We prove that, in this setting, it is possible to obtain an OSP mechanism for every specific problem of interest; we essentially show that we can always define verification probabilities and fines to make any lie obviously dominated. On the technical level, we show that there is a trade-off between the kind of verification device needed (i.e., the verification probabilities) and the amount of fines imposed to lying agents that are caught. Our results imply that we can set the fines so that only a constant number of agents is verified in expectation. |
| Researcher Affiliation | Academia | Diodato Ferraioli University of Salerno, Italy dferraioli@unisa.it Carmine Ventre University of Essex, UK c.ventre@essex.ac.uk |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not include any statement about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. The public project problem is discussed as a theoretical model, not an empirical dataset. |
| Dataset Splits | No | The paper is theoretical and does not specify dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |