×

zbMATH — the first resource for mathematics

Automated optimal OSP mechanisms for set systems. The case of small domains. (English) Zbl 1435.91060
Caragiannis, Ioannis (ed.) et al., Web and Internet economics. 15th international conference, WINE 2019, New York, NY, USA, December 10–12, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11920, 171-185 (2019).
Summary: 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 [D. Ferraioli et al., “Obviously strategyproof mechanisms for machine scheduling”, Preprint, arXiv:1805.04190]. 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.
For the entire collection see [Zbl 1429.91006].

MSC:
91B03 Mechanism design theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adamczyk, M., Borodin, A., Ferraioli, D., de Keijzer, B., Leonardi, S.: Sequential posted price mechanisms with correlated valuations. In: Markakis, E., Schäfer, G. (eds.) WINE 2015. LNCS, vol. 9470, pp. 1-15. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48995-6_1 · Zbl 1406.91138
[2] Ashlagi, I., Gonczarowski, Y.A.: Stable matching mechanisms are not obviously strategy-proof. J. Econ. Theory 177, 405-425 (2018) · Zbl 1417.91379
[3] Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: FOCS 2014, pp. 21-30 (2014)
[4] Bade, S., Gonczarowski, Y.A.: Gibbard-Satterthwaite success stories and obvious strategyproofness. In: EC 2017, p. 565 (2017)
[5] Chawla, S., Hartline, J., Malec, D., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC 2010, pp. 311-320 (2010) · Zbl 1293.91078
[6] Dütting, P., Gkatzelis, V., Roughgarden, T.: The performance of deferred-acceptance auctions. Math. Oper. Res. 42(4), 897-914 (2017) · Zbl 1386.91072
[7] Eden, A., Feldman, M., Friedler, O., Talgam-Cohen, I., Weinberg, S.M.: A simple and approximately optimal mechanism for a buyer with complements. In: EC 2017, p. 323 (2017)
[8] Feldman, M., Fiat, A., Roytman, A.: Makespan minimization via posted prices. In: EC 2017, pp. 405-422 (2017)
[9] Ferraioli, D., Meier, A., Penna, P., Ventre, C.: Obviously strategyproof mechanisms for machine scheduling. In: ESA 2019 (2019) · Zbl 1435.91060
[10] Ferraioli, D., Ventre, C.: Obvious strategyproofness needs monitoring for good approximations. In: AAAI 2017, pp. 516-522 (2017)
[11] Ferraioli, D., Ventre, C.: Probabilistic verification for obviously strategyproof mechanisms. In: IJCAI 2018 (2018)
[12] Ferraioli, D., Ventre, C.: Obvious strategyproofness, bounded rationality and approximation: the case of machine scheduling. In: SAGT 2019 (2019) · Zbl 1431.91090
[13] Hartline, J., Roughgarden, T.: Simple versus optimal mechanisms. In: EC 2009, pp. 225-234 (2009)
[14] Kagel, J., Harstad, R., Levin, D.: Information impact and allocation rules in auctions with affiliated private values: a laboratory study. Econometrica 55, 1275-1304 (1987)
[15] Kyropoulou, M., Ventre, C.: Obviously strategyproof mechanisms without money for scheduling. In: AAMAS 2019 (2019)
[16] Li, S.: Obviously strategy-proof mechanisms. Am. Econ. Rev. 107(11), 3257-3287 (2017)
[17] Mackenzie, A.: A revelation principle for obviously strategy-proof implementation. Research Memorandum 014 (GSBE) (2017)
[18] Milgrom, P., Segal, I.: Deferred-acceptance auctions and radio spectrum reallocation. In: EC 2014 (2014)
[19] Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166-196 (2001) · Zbl 0996.68251
[20] Penna, P., Ventre, C.: Optimal collusion-resistant mechanisms with verification. Games Econ. Behav. 86, 491-509 (2014) · Zbl 1296.91130
[21] Rochet, J.C.: The taxation principle and multitime Hamilton-Jacobi equations. J. Math. Econ. 14(2), 113-128 (1985) · Zbl 0594.90006
[22] Saks, M., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: EC 2005, pp. 286-293 (2005)
[23] Sandholm, T.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.