zbMATH — the first resource for mathematics

Impartial selection and the power of up to two choices. (English) Zbl 1406.91080
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 146-158 (2015).
Summary: We study mechanisms that select members of a set of agents based on nominations by other members and that are impartial in the sense that agents cannot influence their own chance of selection. Prior work has shown that deterministic mechanisms for selecting any fixed number of agents are severely limited, whereas randomization allows for the selection of a single agent that in expectation receives at least 1/2 of the maximum number of nominations. The bound of 1/2 is in fact best possible subject to impartiality. We prove here that the same bound can also be achieved deterministically by sometimes but not always selecting a second agent. We then show a separation between randomized mechanisms that make exactly two or up to two choices, and give upper and lower bounds on the performance of mechanisms allowed more than two choices.
For the entire collection see [Zbl 1326.68026].

91B06 Decision theory
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
05C90 Applications of graph theory
Full Text: DOI
[1] Alon, N., Fischer, F., Procaccia, A.D., Tennenholtz, M.: Sum of us: Strategyproof selection from the selectors. In: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 101–110 (2011) · doi:10.1145/2000378.2000390
[2] Birkhoff, G.: Tres observaciones sobre el algebra lineal. Revista Facultad de Ciencias Exactas, Puras y Aplicadas Universidad Nacional de Tucumán, Serie A 5, 147–151 (1946)
[3] Bousquet, N., Norin, S., Vetta, A.: A near-optimal mechanism for impartial selection. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 133–146. Springer, Heidelberg (2014) · Zbl 1406.91101 · doi:10.1007/978-3-319-13129-0_10
[4] de Clippel, G., Moulin, H., Tideman, N.: Impartial division of a dollar. J. Econ. Theor. 139(1), 176–191 (2008) · Zbl 1132.91509 · doi:10.1016/j.jet.2007.06.005
[5] Fischer, F., Klimm, M.: Optimal impartial selection. In: Proceedings of the 15th ACM Conference on Economics and Computation, pp. 803–820 (2014) · Zbl 1335.91030 · doi:10.1145/2600057.2602836
[6] Holzman, R., Moulin, H.: Impartial nominations for a prize. Econometrica 81(1), 173–196 (2013) · Zbl 1274.91177 · doi:10.3982/ECTA10523
[7] Mackenzie, A.: Symmetry and impartial lotteries. Games Econ. Behav. 94, 15–28 (2015) · Zbl 1347.91133 · doi:10.1016/j.geb.2015.08.007
[8] Mitzenmacher, M., Richa, A.W., Sitaraman, R.: The power of two random choices: a survey of techniques and results. In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J. (eds.) Handbook of Randomized Computing, vol. 1, pp. 255–312. Springer (2001) · Zbl 1056.68166 · doi:10.1007/978-1-4615-0013-1_9
[9] Tamura, S., Ohseto, S.: Impartial nomination correspondences. Soc. Choice Welfare 43(1), 47–54 (2014) · Zbl 1302.91090 · doi:10.1007/s00355-013-0772-9
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.