A welfarist approach to sequencing problems with incentives

Banerjee, Sreoshi and De, Parikshit and Mitra, Manipushpak (2020): A welfarist approach to sequencing problems with incentives.

Abstract

We adopt a welfarist approach to study sequencing problems in a private information setup. The ”generalized minimum welfare bound” (GMWB) is a universal representation of all the specific bounds that have been previously studied in the literature. Every agent is offered a protection in the form of a minimum guarantee on their utilities. We provide a necessary and sufficient condition to identify an outcome efficient and strategy-proof mechanism that satisfies GMWB.We then characterize the entire class of mechanisms that satisfy outcome efficiency, strategy proofness and GMWB. These are termed as the class of ”relative pivotal mechanisms”. Our paper proposes relevant theoretical applications namely; ex-ante initial order, identical costs bound and expected cost bound. We also give insights on the issues of feasibility and/or budget balance.

• Item Type: MPRA Paper
• Language: English
• Keywords: sequencing problems, generalized minimum welfare bounds, outcome efficiency, strategyproofness, feasibility, budget balance
• 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 > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design

References

[1] Bevia, C., 1996. Identical preferences lower bound solution and consistency in economies with indivisible goods. Social Choice andWelfare 13, 113–126.

[2] Chun, Y. 2006. No-envy in queueing problems. Economic Theory 29, 151–162.

[3] Chun, Y. 2006. A pessimistic approach to the queueing problem. Mathematical Social Sciences 51, 171–181.

[4] Chun, Y. and Mitra, M. 2014. Subgroup Additivity in the Queueing Problem. European Journal of Operational Research 238 (1), 281-289.

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

[6] Chun, Y., Mitra, M., and Mutuswami, S. 2015. A characterization of the symmetrically balanced VCG rule in the queueing problem. Games and Economic Behavior, DOI:10.1016/j.geb.2015.04.001.

[7] Chun, Y., Mitra, M., and Mutuswami, S. 2017. Reordering an existing queue. With Youngsub Chun and Suresh Mutuswami. Social Choice and Welfare, 49 (1), 65–87.

[8] Chun, Y., Mitra, M. and Mutuswami, S. 2019. Egalitarianism in the queueing problem. Journal of Mathematical Economics, 81, 48-56.

[9] Clarke, E.H., 1971. Multipart pricing of public goods. Public choice, 11(1), pp.17-33.

[10] Chun, Y., and Yengin, D. 2017. Welfare lower bounds and strategy-proofness in the queueing problem. Games and Economic Behavior 102, 462–476.

[11] Curiel I., Pederzoli G. and Tijs S. 1989. Sequencing games. European Journal of Operational Research 40, 344–351.

[12] De, P. 2017. Mechanism Design in Sequencing Problems. Doctoral dissertation, Indian Statistical Institute.

[13] De, P. 2019. Incentive and normative analysis on sequencing problem. MPRA Working Paper No. 92952 https://mpra.ub.uni-muenchen.de/92952.

[14] De, P. and Mitra, M. 2017. Incentives and justice for sequencing problems. Economic Theory, 64 (2), 239- 264.

[15] De, P. and Mitra, M. 2019. Balanced implementability of sequencing rules. Games and Economic Behavior, 118, 342-353.

[16] Dolan, R. J. 1978. Incentive mechanisms for priority queueing problems. The Bell Journal of Economics 9, 421-436.

[17] Duives, J., Heydenreich, B., Mishra, D., Muller, R. and Uetz, M. 2012. On Optimal Mechanism Design for a Sequencing Problem. Journal of scheduling 18, 45-59,

[18] Groves, T., 1973. Incentives in teams. Econometrica 41, 617-631.

[19] Gershkov, A. and Schweinzer, P. 2010. When queueing is better than push and shove. International Journal Game Theory 39, 409–430.

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

[21] Hanning, M., 1996. Maximum waiting-time guarantee-an attempt to reduce waiting lists in Sweden. Health policy, 36(1), pp.17-35.

[22] Hashimoto, K., 2018. Strategy-proofness and identical preferences lower bound in allocation problem of indivisible objects. Economic Theory, 65(4), pp.1045-1078.

[23] Holmstr¨om, B. 1979. Groves’ Scheme on Restricted Domains. Econometrica 47, 1137–1144.

[24] 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.

[25] Maniquet, F. 2003. A characterization of the Shapley value in queueing problems. Journal of Economic Theory 109, 90–103.

[26] McKeever, T., Sweeney, M.R. and Staines, A., 2006. An investigation of the impact of prolonged waiting times on blood donors in Ireland. Vox sanguinis, 90(2), pp.113-118.

[27] Mitra, M. 2001. Mechanism design in queueing problems. Economic Theory 17, 277–305.

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

[29] Mitra, M. 2007. Preferences lower bound in the queueing model. in: B. K. Chakrabarti and A. Chatterjee eds., Econophysics of Markets and Business Networks, Springer Verlag Italia, Milan, 233–237.

[30] Mitra, M. and Mutuswami, S. 2011. Group strategyproofness in queueing models. Games and Economic Behavior, 72, 242-254.

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

[32] Moulin, H. (1991). Welfare bounds in the fair division problem. Journal of Economic Theory, 54(2), 321- 337.

[33] Moulin, H., 1990. Fair division under joint ownership: recent results and open problems. Social Choice and Welfare, 7(2), pp.149-170.

[34] 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.

[35] Smith, W. 1956. Various optimizers for single stage production. Naval Research Logistics Quarterly 3, 59-66.

[36] Steinhaus, H. 1948. The problem of fair division. Econometrica 16, 101-104.

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

[38] van Brummelen, S.P.J., van Dijk, N.M., van den Hurk, K. and de Kort,W.L., 2018.Waiting time-based staff capacity and shift planning at blood collection sites. Health systems, 7(2), pp.89-99.

[39] Vickrey, W., 1961. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1), pp.8-37.

[40] Yengin, D., 2013. Identical preferences lower bound for allocation of heterogenous tasks and NIMBY problems. Journal of Public Economic Theory, 15(4), pp.580-601.