On identifying efficient, fair and stable allocations in "generalized" sequencing games.

Banerjee, Sreoshi (2024): On identifying efficient, fair and stable allocations in "generalized" sequencing games.

Abstract

We model sequencing problems as coalitional games and study the Shapley value and the non-emptiness of the core. The ”optimistic” cost of a coalition is its minimum waiting cost when the members are served first in an order. The ”pessimistic” cost of a coalition is its minimum waiting cost when the members are served last. We take the weighted average of the two extremes and define the class of ”weighted optimistic pessimistic (WOP)” cost games. If the weight is zero, we get the optimistic scenario and if it is one, we get the pessimistic scenario. We find a necessary and sufficient condition on the associated weights for the core to be non-empty. We also find a necessary and sufficient condition on these weights for the Shapley value to be an allocation in the core. We impose ”upper bounds” to protect agents against arbitrarily high disuilities from waiting. If an agent’s disutility level is his Shapley payoff from the WOP cost game, we find necessary and sufficient conditions on the upper bounds for the Shapley value to conform to them.

• Item Type: MPRA Paper
• Language: English
• Keywords: Sequencing, disutility upper bounds, core, cooperative game, Shapley value
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

References

[1] BANERJEE, S., DE, P., AND MITRA, M. A welfarist approach to sequencing problems with incentives.

[2] CHUN, Y. Consistency and monotonicity in sequencing problems. Tech. rep.,Working paper, 2004.

[3] CHUN, Y. No-envy in queueing problems. Economic Theory 29, 1 (2006), 151–162.

[4] CHUN, Y. A pessimistic approach to the queueing problem. Mathematical Social Sciences 51, 2 (2006), 171–181.

[5] CHUN, Y., MITRA, M., AND MUTUSWAMI, S. Egalitarian equivalence and strategyproofness in the queueing problem. Economic Theory 56, 2 (2014), 425–442.

[6] CHUN, Y., MITRA, M., AND MUTUSWAMI, S. Reordering an existing queue. Social Choice and Welfare 49, 1 (2017), 65–87.

[7] CHUN, Y., MITRA, M., AND MUTUSWAMI, S. Egalitarianism in the queueing problem. Journal of Mathematical Economics 81 (2019), 48–56.

[8] CHUN, Y., AND YENGIN, D. Welfare lower bounds and strategy-proofness in the queueing problem. Games and Economic Behavior 102 (2017), 462–476.

[9] CURIEL, I., PEDERZOLI, G., AND TIJS, S. Sequencing games. European Journal of Operational Research 40, 3 (1989), 344–351.

[10] DE, P. Mechanism Design In Sequencing Problems. PhD thesis, Indian Statistical Institute, Kolkata, 2016.

[11] DE, P., AND MITRA, M. Incentives and justice for sequencing problems. Economic Theory 64, 2 (2017), 239–264.

[12] DOLAN, R. J. Incentive mechanisms for priority queuing problems. The Bell Journal of Economics (1978), 421–436.

[13] GERSHKOV, A., AND SCHWEINZER, P. When queueing is better than push and shove. International Journal of Games Theory 39 (07 2010), 409–430.

[14] HARSANYI, J. C., AND HARSANYI, J. C. A simplified bargaining model for the n-person cooperative game. Papers in game theory (1982), 44–70.

[15] KAR, A., MITRA, M., AND MUTUSWAMI, S. On the coincidence of the prenucleolus and the shapley value. Mathematical Social Sciences 57, 1 (2009), 16–25.

[16] KAYI, C¸ ., AND RAMAEKERS, E. Characterizations of pareto-efficient, fair, and strategy-proof allocation rules in queueing problems. Games and Economic Behavior 68, 1 (2010), 220–232.

[17] KUHN, H. W., AND TUCKER, A. W. Contributions to the Theory of Games. No. 28. Princeton University Press, 1953.

[18] MANIQUET, F. A characterization of the shapley value in queueing problems. Journal of Economic Theory 109, 1 (2003), 90–103.

[19] MENDELSON, H., AND WHANG, S. Optimal incentive-compatible priority pricing for the m/m/1 queue. Operations research 38, 5 (1990), 870–883.

[20] MISHRA, D., AND RANGARAJAN, B. Cost sharing in a job scheduling problem. Social Choice and Welfare 29, 3 (2007), 369–382.

[21] MITRA, M. Mechanism design in queueing problems. Economic Theory 17, 2 (2001), 277–305.

[22] MITRA, M. Achieving the first best in sequencing problems. Review of Economic Design 7, 1 (2002), 75–91.

[23] MITRA, M. Preferences lower bound in the queueing model. In Econophysics of markets and business networks. Springer, 2007, pp. 233–237.

[24] MOULIN, H. Welfare bounds in the fair division problem. Journal of Economic Theory 54, 2 (1991), 321–337.

[25] MOULIN, H. On scheduling fees to prevent merging, splitting, and transferring of jobs. Mathematics of Operations Research 32, 2 (2007), 266–283.

[26] SHAPLEY, L. S. Additive and non-additive set functions. Princeton University, 1953.

[27] SMITH, W. E., ET AL. Various optimizers for single-stage production. Naval Research Logistics Quarterly 3, 1-2 (1956), 59–66.

[28] SUIJS, J. On incentive compatibility and budget balancedness in public decision making. Economic design 2, 1 (1996), 193–209.

[29] YENGIN, D. Identical preferences lower bound for allocation of heterogenous tasks and nimby problems. Journal of Public Economic Theory 15, 4 (2013), 580–601.