Probabilistic Verification for Obviously Strategyproof Mechanisms

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.