  The design of algorithms or protocols that are able to align the goals of the
planner with the selfish interests of the agents involved in these protocols is
of paramount importance in almost every decentralized setting (such as,
computer networks, markets, etc.) as shown by the rich literature in Mechanism
Design. Recently, huge interest has been devoted to the design of mechanisms
for imperfectly rational agents, i.e., mechanisms for which agents are able to
easily grasp that there is no action different from following the protocol that
would satisfy their interests better. This work has culminated in the
definition of Obviously Strategyproof (OSP) Mechanisms, that have been shown to
capture the incentives of agents without contingent reasoning skills.
  Without an understanding of the algorithmic nature of OSP mechanisms, it is
hard to assess how well these mechanisms can satisfy the goals of the planner.
For the case of binary allocation problems and agents whose private type is a
single number, recent work has shown that a generalization of greedy completely
characterizes OSP. In this work, we strengthen the connection between greedy
and OSP by providing a characterization of OSP mechanisms for all optimization
problems involving these single-parameter agents. Specifically, we prove that
OSP mechanisms must essentially work as follows: they either greedily look for
agents with ``better'' types and allocate them larger outcomes; or reverse
greedily look for agents with ``worse'' types and allocate them smaller
outcomes; or, finally, split the domain of agents in ``good'' and ``bad''
types, and subsequently proceed in a reverse greedy fashion for the former and
greedily for the latter. We further demonstrate how to use this
characterization to give bounds on the approximation guarantee of OSP
mechanisms for the well known scheduling related machines problem.
