English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The design of algorithms or protocols that are able to align the goals of theplanner with the selfish interests of the agents involved in these protocols isof paramount importance in almost every decentralized setting (such as,computer networks, markets, etc.) as shown by the rich literature in MechanismDesign. Recently, huge interest has been devoted to the design of mechanismsfor imperfectly rational agents, i.e., mechanisms for which agents are able toeasily grasp that there is no action different from following the protocol thatwould satisfy their interests better. This work has culminated in thedefinition of Obviously Strategyproof (OSP) Mechanisms, that have been shown tocapture the incentives of agents without contingent reasoning skills.  Without an understanding of the algorithmic nature of OSP mechanisms, it ishard 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 asingle number, recent work has shown that a generalization of greedy completelycharacterizes OSP. In this work, we strengthen the connection between greedyand OSP by providing a characterization of OSP mechanisms for all optimizationproblems involving these single-parameter agents. Specifically, we prove thatOSP mechanisms must essentially work as follows: they either greedily look foragents with ``better'' types and allocate them larger outcomes; or reversegreedily look for agents with ``worse'' types and allocate them smalleroutcomes; or, finally, split the domain of agents in ``good'' and ``bad''types, and subsequently proceed in a reverse greedy fashion for the former andgreedily for the latter. We further demonstrate how to use thischaracterization to give bounds on the approximation guarantee of OSPmechanisms for the well known scheduling related machines problem.

On the Connection between Greedy Algorithms and Imperfect Rationality