Abstract
We analyze dynamic assignment problems where agents successively receive different objects (positions, offices, etc.). A finite set of n vertically differentiated indivisible objects are assigned to n agents who live n periods. At each period, a new agent enters society, and the oldest agent retires, leaving his object to be reassigned. We define independent assignment rules (where the assignment of an object to an agent is independent of the way other objects are allocated to other agents), efficient assignment rules (where there does not exist another assignment rule with larger expected surplus), and fair assignment rules (where agents experiencing the same circumstances have identical histories in the long run). When agents are homogenous, we characterize efficient, independent and fair rules as generalizations of the seniority rule. When agents draw their types at random, we prove that independence and efficiency are incompatible, and that efficient and fair rules only exist when there are two types of agents. We characterize two simple rules (type-rank and type-seniority) which satisfy both efficiency and fairness criteria in dichotomous settings.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abdulkadiroglu A, Loertscher S (2007) Dynamic house allocations. Duke University and University of Melbourne, Mimeo
Abdulkadiroglu A, Sonmez T (1999) House allocation with existing tenants. J Econ Theory 88: 233–260
Athey S, Segal I (2007) An efficient dynamic mechanism. Stanford University, Mimeo
Bartholomew J (1982) Stochastic models for social processes. Wiley, New York
Bergemann D, Välimäki J (2010) The dynamic pivot mechanism. Econometrica 78: 771–789
Blum Y, Roth AE, Rothblum UG (1997) Vacancy chains and equilibration in senior-level labor markets. J Econ Theory 103: 429–443
Cantala D (2004) Restabilizing matching markets at senior level. Games Econ Behav 48: 1–17
Cantala D, Sanchez F (2008) Welfare and stability in senior matching markets. Int J Game Theory 36: 369–392
Gershkov A, Moldovanu B (2009a) Learning about the future and dynamic efficiency. Am Econ Rev 99: 1576–1587
Gershkov A, Moldovanu B (2009b) Dynamic revenue maximization with heterogeneous objects: A mechanism design approach. Am Econ J 1: 168–198
Isaacson D, Masden R (1976) Markov chains: Theory and applications. Wiley, New York
Kemeny J, Snell L (1960) Finite Markov chains. Van Nostrand, New York
Kurino M (2008) House allocation with overlapping agents: A mechanism design approach. University of Pittsburgh, Mimeo
Moulin H, Stong R (2002) Fair queuing and other probabilistic allocation methods. Math Oper Res 27: 1–31
Moulin H, Stong R (2003) Filling a multicolor urn: An axiomatic analysis. Games Econ Behav 45: 242–269
Nilakantan K, Ragavendhra BG (2005) Control aspects in proportionality Markov manpower systems. Appl Math Model 29: 85–116
Parkes DC, Singh S (2003) An MDP approach to online mechanism design. Proceedings of the 17th annual conference on neural information processing systems (NIPS 03)
Roth A, Sotomayor M (1990) Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge
Sonmez T, Ünver U (2008) House allocation with existing tenants: A charcetrization. Games Econ Behav 69: 425–445
Talluri K, van Ryzin G (2004) The theory and practice of revenue management. Springer, New York
Thomson W (2007) Fair allocation rules. University of Rochester, Mimeo
Ünver U (2010) Dynamic kidney exchange. Rev Econ Stud 77: 372–414
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bloch, F., Cantala, D. Markovian assignment rules. Soc Choice Welf 40, 1–25 (2013). https://doi.org/10.1007/s00355-011-0566-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-011-0566-x