TY - JOUR
T1 - Obvious Strategyproofness, Bounded Rationality and Approximation
AU - Ferraioli, Diodato
AU - Ventre, Carmine
N1 - Funding Information:
Carmine Ventre is partially supported by EPSRC grant EP/V00784X/1.
Funding Information:
Diodato Ferraioli is partially supported by GNCS-INdAM and by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”.
Publisher Copyright:
© 2022, The Author(s).
PY - 2022/4/25
Y1 - 2022/4/25
N2 - 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 two paradigmatic problems: machine scheduling and facility location. We prove that, for both problems, “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.
AB - 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 two paradigmatic problems: machine scheduling and facility location. We prove that, for both problems, “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.
UR - http://www.scopus.com/inward/record.url?scp=85128808025&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/s00224-022-10071-2
DO - https://doi.org/10.1007/s00224-022-10071-2
M3 - Article
SN - 1433-0490
VL - 66
SP - 696
EP - 720
JO - THEORY OF COMPUTING SYSTEMS
JF - THEORY OF COMPUTING SYSTEMS
IS - 3
ER -