Obviously Strategy-Proof Mechanisms without Money for Scheduling

We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategyproofness, termed obvious strategyproofness (OSP) and explore its possibilities and its limitations. OSP formalizes the concept of strategyproofness for agents/machines with a certain kind of bounded ratio- nality, by making an agent’s incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after providing information about her true type is at least as good as the best possible out- come after misreporting information about her type. Under the weaker constraint of strategyproofness, Koutsoupias [2014] proves a tight approximation ratio of n+1/2 for the makespan for one task, under the monitor- ing paradigm. 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 strategyproofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.