zbMATH — the first resource for mathematics

Obvious strategyproofness, bounded rationality and approximation. The case of machine scheduling. (English) Zbl 1431.91090
Fotakis, Dimitris (ed.) et al., Algorithmic game theory. 12th International symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11801, 77-91 (2019).
Summary: Obvious strategyproofness (OSP) has recently emerged as the solution concept of interest to study incentive compatibility in presence of agents with a specific form of bounded rationality, i.e., those who have no contingent reasoning skill whatsoever. We here want to study the relationship between the approximation guarantee of incentive-compatible mechanisms and the degree of rationality of the agents, intuitively measured in terms of the number of contingencies that they can handle in their reasoning. We weaken the definition of OSP to accommodate for cleverer agents and study the trade-off between approximation and agents’ rationality for the paradigmatic machine scheduling problem. We prove that, at least for the classical machine scheduling problem, “good” approximations are possible if and only if the agents’ rationality allows for a significant number of contingencies to be considered, thus showing that OSP is not too restrictive a notion of bounded rationality from the point of view of approximation.
For the entire collection see [Zbl 1422.91031].

91B03 Mechanism design theory
90B35 Deterministic scheduling theory in operations research
91A68 Algorithmic game theory and complexity
Full Text: DOI Link