Research Repository

Obviously strategyproof mechanisms without money for scheduling

Kyropoulou, Maria and Ventre, Carmine (2019) Obviously strategyproof mechanisms without money for scheduling. In: AAMAS '19: 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019-05-13 - 2019-05-17, Montreal QC Canada.

AAMAS-osp-scheduling.pdf - Accepted Version

Download (714kB) | Preview


We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a stronger notion of truthfulness termed obvious strategyproof-ness (OSP) and explore its possibilities and its limitations. OSP formalizes the concept of truthfulness for agents/machines with a certain kind of bounded rationality, by making an agent's incentives to act truthfully obvious in some sense: Roughly speaking, the worst possible outcome after selecting her true type is at least as good as the best possible outcome after misreporting her type. Under the weaker constraint of truthfulness, Koutsoupias [2011] proves a tight approximation ratio of for one task. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive-compatibility from truthfulness to OSP. To achieve this, we introduce the notion of strict monitoring and prove that such a monitoring framework is essential, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Leibniz International Proceedings in Informatics, LIPIcs
Uncontrolled Keywords: Bounded Rationality; Extensive-form Mechanisms; Approximate Mechanism Design
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 24 Mar 2022 18:35
Last Modified: 24 Mar 2022 18:35

Actions (login required)

View Item View Item