Obviously strategyproof (OSP) mechanisms have recently come to the fore as a tool to deal with imperfect rationality. They, in fact, incentivize people with no contingent reasoning skills to “follow the protocol” and be honest. However, their exact power is still to be determined. For example, even for settings relatively well understood, such as binary allocation problems, it is not clear when optimal solutions can be computed with OSP mechanisms. We here consider this question for the large class of set system problems, where selfish agents with imperfect rationality own elements whose cost can take one among few values. In our main result, we give a characterization of the instances for which the optimum is possible. The mechanism we provide uses a combination of ascending and descending auctions, thus extending to a large class of settings a design paradigm for OSP mechanisms recently introduced in [9]. Finally, we dig deeper in the characterizing property and observe that the set of conditions can be quickly verified algorithmically. The combination of our mechanism and algorithmic characterization gives rise to the first example of automated mechanism design for OSP.

Automated Optimal OSP Mechanisms for Set Systems: The Case of Small Domains

Ferraioli, D.;Penna, P.;Ventre, C.
2019-01-01

Abstract

Obviously strategyproof (OSP) mechanisms have recently come to the fore as a tool to deal with imperfect rationality. They, in fact, incentivize people with no contingent reasoning skills to “follow the protocol” and be honest. However, their exact power is still to be determined. For example, even for settings relatively well understood, such as binary allocation problems, it is not clear when optimal solutions can be computed with OSP mechanisms. We here consider this question for the large class of set system problems, where selfish agents with imperfect rationality own elements whose cost can take one among few values. In our main result, we give a characterization of the instances for which the optimum is possible. The mechanism we provide uses a combination of ascending and descending auctions, thus extending to a large class of settings a design paradigm for OSP mechanisms recently introduced in [9]. Finally, we dig deeper in the characterizing property and observe that the set of conditions can be quickly verified algorithmically. The combination of our mechanism and algorithmic characterization gives rise to the first example of automated mechanism design for OSP.
2019
978-303035388-9
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4732749
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact