Incentives and justice for sequencing problems.

Mitra, Manipushpak and De, Parikshit (2015): Incentives and justice for sequencing problems.

Abstract

We address the mechanism design issue for the sequencing problem. We identify the just sequencing rule that serves the agents in the non-increasing order of their waiting costs and prove that it is a Rawlsian rule. We identify all rVCG mechanisms that implement the just sequencing rule. The other properties of the just sequencing rule that we identify are the following. It is an affine cost minimizer. It can be implemented with budget balanced rVCG mechanisms. Finally, when waiting cost and processing time are private information, we identify all generalized rVCG mechanisms that ex-post implement the just sequencing rule.

• Item Type: MPRA Paper
• Language: English
• Keywords: sequencing, implementation, outcome efficient sequencing rule, just sequencing rule, budget balance, ex-post implementation.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design

References

Bergemann, D. and Morris, S. (2008). Ex-post implementation. Games and Economic Behavior 63, 527-566.

Bikhchandani, S. (2006). Ex-post implementation in environments with private goods. Theoretical Economics 1 , 369-393.

Chichilnisky, G. and Heal, G. M. (1997). The geometry of implementation: a necessary and sufficient condition for straightforward games. Social choice and Welfare 14, 259-294.

Chun, Y. (2006). No-envy in queueing problems. Economic Theory 29, 151-162.

Chun, Y., Mitra, M. and Mutuswami, S. (2014). Egalitarian equivalence and strategyproofness in the queueing problem. Economic Theory 56, 425-442.

Chun, Y., Mitra, M. and Mutuswami, S. (2015). A characterization of the symmetrically balanced VCG rule in the queueing problem. Article in press: Games and Economic Behavior,doi:10.1016/j.geb.2015.04.001.

Chung, K.-S. and Ely, J. C. (2003). Ex-post incentive compatible mechanism design.Working Paper, Department of Economics, Northwestern University.

Clarke, E. H., (1971). Multi-part pricing of public goods. Public Choice 11, 17-33.

Deb, R. and Mishra, D. (2014). Implementation with contingent contracts. Econometrica 82, 2371- 2393.

Dolan, R. J. (1978). Incentive mechanisms for priority queuing problems. The Bell Journal of Economics 9, 421-436.

Duives, J., Heydenreich, B., Mishra, D., Muller, R. and Uetz, M. (2012). On Optimal Mechanism Design for a Sequencing Problem. mimeo.

Groves, T. (1973). Incentives in teams. Econometrica 41, 617-631.

Hain, R. and Mitra, M. (2004). Simple sequencing problems with interdependent costs. Games and Economic Behavior 48, 271-291.

Hashimoto, K., and Saitoh, H. (2012). Strategy-proof and anonymous rule in queueing problems: a relationship between equity and efficiency. Social Choice and Welfare 38, 473-480.

Holmstr¨om, B., (1979). Groves’ schemes on restricted domains. Econometrica 47, 1137-1144.

Hurwicz, L., (1975). On the existence of allocative systems whose manipulative Nash equilibria are Pareto optimal. Mimeo, University of Minnesota.

Hurwicz, L. and Walker, M. (1990). On the generic non-optimality of dominant strategy allocation mechanisms: A general theorem that includes pure exchange economies. Econometrica 58, 683-704.

Jehiel, P., Meyer-ter-Vehn, M., Moldovanu, B. and Zame, W. R. (2006). The limits of ex-post implementation. Econometrica 74, 585-610.

Jehiel, P. and Moldovanu, B. (2001). Efficient design with interdependent valuations. Econometrica, 69, 1237-1259.

Kayi, C. and Ramaekers, E. (2010). Characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems. Games and Economic Behavior 68, 220-232.

Fieseler, K. Kittsteiner, T. and Moldovanu, M. (2003). Partnerships, lemons and efficient trade. Journal of Economic Theory 113, 223-234.

Lavi, R., Mu’alem, A. and Nisan, N. (2004). Towards a Characterization of Truthful Combinatorial Auctions.Working paper-School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel.

Maniquet, F. (2003). A characterization of the Shapley value in queueing problems. Journal of Economic Theory, 109(1), 90-103.

Mitra, M., (2001). Mechanism design in queueing problems. Economic Theory 17, 277-305.

Mitra, M., (2002). Achieving the first best in sequencing problems. Review of Economic Design 7, 75-91.

Mitra, M. and Sen, A. (2010). Efficient allocation of heterogenous commodities with balanced transfers. Social ChoiceWelfare 35, 29-48.

Moulin, H., (2007). On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs. Mathematics of Operations Research 32, 266-283.

Mukherjee, C. (2013).Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines. International Journal of Game Theory, 42(1), 131-163.

Mitra, M., & Mutuswami, S. (2011). Group strategyproofness in queueing models. Games and Economic Behavior, 72(1), 242-254.

Rawls, J. (1972). A theory of Justice. Harvard University Press.

Roberts, K. (1979). The characterization of implementable choice rules. In Jean-Jacques Laffont, editor, Aggregation and Revelation of Preferences. Papers presented at the first European Summer Workshop of the Econometric Society, pages 321-349, North-Holland Publications.

Smith, W. (1956). Various optimizers for single stage production. Naval Research Logistics Quarterly 3, 59-66.

Suijs, J. (1996). On incentive compatibility and budget balancedness in public decision making. Economic Design 2, 193-209.

Velez, R. A. (2011). Are incentives against economic justice? Journal of Economic Theory 146, 326- 345.

Vickrey,W. (1961). Counterspeculation, auctions and competitive sealed tenders. Journal of Finance 16, 8-37.

Walker, M. (1980). On the non-existence of dominant strategy mechanisms for making optimal public decisions. Econometrica 48, 1521-1540.

Zhou, L. (2007). The failure of Groves mechanisms in canonical allocation models. Mimeo, Arizona State University.