Research Repository

Probabilistic Verification for Obviously Strategyproof Mechanisms

Ferraioli, Diodato and Ventre, Carmine (2018) Probabilistic Verification for Obviously Strategyproof Mechanisms. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018-07-10 - 2018-07-15, Stockholm.

[img]
Preview
Text
osp2_cr.pdf - Published Version

Download (269kB) | Preview

Abstract

Obviously strategyproof (OSP) mechanisms maintain the incentive compatibility of agents that are not fully rational. They have been object of a number of studies since their recent definition. We are motivated by the result showing that OSP mechanisms without money cannot return good approximations, even if the designer monitors the agents during the execution of the mechanism We ask whether there are different (harsher) forms of punishments and novel ways to exert control over the agents that can overcome this impossibility. We define a model of probabilistic verification wherein agents are caught misbehaving with a certain probability and show how OSP mechanisms without money can implement a given social choice function at the cost of either imposing very large fines for lying or verifying a linear number of agents.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: _not provided_
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 22 Nov 2018 14:56
Last Modified: 22 Nov 2018 14:56
URI: http://repository.essex.ac.uk/id/eprint/21816

Actions (login required)

View Item View Item