Abstract
We consider various lexicographic allocation procedures for coalitional games with transferable utility where the payoffs are computed in an externally given order of the players. The common feature of the methods is that if the allocation is in the core, it is an extreme point of the core. We first investigate the general relationships between these allocations and obtain two hierarchies on the class of balanced games. Secondly, we focus on assignment games and sharpen some of these general relationships. Our main result shows that, similarly to the core and the coalitionally rational payoff set, also the dual coalitionally rational payoff set of an assignment game is determined by the individual and mixed-pair coalitions, and present an efficient and elementary way to compute these basic dual coalitional values. As a byproduct we obtain the coincidence of the sets of lemarals (vectors of lexicographic maxima over the set of dual coalitionally rational payoff vectors), lemacols (vectors of lexicographic maxima over the core) and extreme core points. This provides a way to compute the AL-value (the average of all lemacols) with no need to obtain the whole coalitional function of the dual assignment game.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Lemacols are named lexinals in Tijs et al. (2011). We change the name trying to find a common nomenclature that includes the lexicographic minimization over the core and also the lexicographic minimization (respectively maximization) over the set of coalitionally rational payoff vectors (respectively over the set of dual coalitionally rational payoff vectors), where efficiency is not required.
Izquierdo et al. (2007) show that in an assignment game all the lemirals are extreme core points if and only if the game is exact, or alternatively, if the game has a large core.
The AL-value was first introduced by Prof. Stef Tijs with the name of Alexia value.
References
Balinski, M. L., & Gale, D. (1987). On the core of the assignment game. In L. J. Leifman (Ed.), Functional analysis, optimization, and mathematical economics (pp. 274–289). New York: Oxford University Press.
Biswas, A., Parthasarathy, T., Potters, J. A. M., & Voorneveld, M. (1999). Large cores and exactness. Games and Economic Behavior, 20, 1–12.
Demange, G. (1982). Strategy proofness in the assignment market game. Paris: Mimeo, Laboratoire d’Econométrie de l’École Politechnique.
Estévez-Fernández, A. (2012). New characterizations for largeness of the core. Games and Economic Behavior, 76, 160–180.
Hamers, H., Klijn, F., Solymosi, T., Tijs, S., & Villar, J. P. (2002). Assignment games satisfy the CoMa-property. Games and Economic Behavior, 38, 231–239.
Ichiishi, T. (1981). Supermodularity: Applications to convex games and to the greedy algorithm for LP. Journal of Economic Theory, 25, 283–286.
Izquierdo, J. M., Núñez, M., & Rafels, C. (2007). A simple procedure to obtain the extreme core allocations of an assignment market. International Journal of Game Theory, 36, 17–26.
Kuipers, J. (1993). On the core of information graph games. International Journal of Game Theory, 21, 339–350.
Kongo, T., Funaki, Y., Branzei, R., & Tijs, S. (2010). Non-cooperative and axiomatic characterizations of the average lexicographic value. International Game Theory Review, 12(4), 417–435. doi:10.1142/S0219198910002751.
Leonard, H. B. (1983). Elicitation of honest preferences for the assignment of individuals to positions. Journal of Political Economy, 91, 461–479.
Martínez-de-Albéniz, J., Núñez, M., & Rafels, C. (2011). Assignment markets with the same core. Games and Economic Behavior, 73(2), 553–563.
Núñez, M., & Rafels, C. (2002). Buyer–seller exactness in the assignment game. International Journal of Game Theory, 31, 423–436.
Owen, G. (1992). The assignment game: The reduced game. Annales D’Economie et de Statistique, 25(26), 71–79.
Shapley, L. S. (1971). Cores of convex games. International Journal of Game Theory, 1, 11–26.
Shapley, L. S., & Shubik, M. (1972). The assignment game I: The core. International Journal of Game Theory, 1, 111–130.
Solymosi, T., & Raghavan, T. (2001). Assignment games with stable core. International Journal of Game Theory, 30, 177–185.
Tijs, S., Borm, P., Lohmann, E., & Quant, M. (2011). An average lexicographic value for cooperative games. European Journal of Operational Research, 213, 210–220.
van Gellekom, J. R. G., Potters, J. A. M., & Reijnierse, J. H. (1999). Prosperity properties of TU-games. International Journal of Game Theory, 28, 211–227.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author’s research has been supported by Grant ECO2014-52340-P of the Spanish Ministry of Science and Innovation and 2014SGR40 of the Government of Catalonia, and also partly supported by COST Action IC1205 on Computational Social Choice. The second author’s research has been supported by OTKA Grant K-101224, by the Hungarian Academy of Sciences under its Momentum Programme (LD-004/2010), and also partly supported by COST Action IC1205 on Computational Social Choice.
Rights and permissions
About this article
Cite this article
Núñez, M., Solymosi, T. Lexicographic allocations and extreme core payoffs: the case of assignment games. Ann Oper Res 254, 211–234 (2017). https://doi.org/10.1007/s10479-017-2435-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-017-2435-1