Stability and fairness in sequencing games: optimistic approach and pessimistic scenarios

Banerjee, Sreoshi (2023): Stability and fairness in sequencing games: optimistic approach and pessimistic scenarios.

Abstract

Sequencing deals with the problem of assigning slots to agents who are waiting for a service. We study sequencing problems as coalition form games defined in optimistic and pessimistic scenarios. Each agent's level of utility is his Shapley value payoff from the corresponding coalition form game. First, we show that while the core of the optimistic game is always empty, the Shapley value of the pessimistic game is an allocation in its core. Second, we impose the "generalized welfare lower bound" (GWLB) that ex-ante guarantees each agent a minimum level of utility. One of many application of GWLB is the "expected costs bound". It guarantees each agent his expected cost when all arrival orders are equally likely. We prove that the Shapley value payoffs (in both optimistic and pessimistic scenarios) satisfy GWLB if and only if it satisfies the expected costs bound (ECB).

• Item Type: MPRA Paper
• Language: English
• Keywords: Sequencing, welfare lower 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 > D0 - General; D - Microeconomics > D3 - Distribution; D - Microeconomics > D3 - Distribution > D30 - General; D - Microeconomics > D6 - Welfare Economics; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

References

1] ABDULKADIRO ̆GLU, A., AND S ̈ONMEZ, T. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 3 (1998), 689–701.

[2] ALKAN, A., DEMANGE, G., AND GALE, D. Fair allocation of indivisible goods and criteria of justice. Econometrica: Journal of the Econometric Society (1991), 1023–1039.

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

[4] BONDAREVA, O. N. Some applications of linear programming methods to the theory of cooperative games. Problemy kibernetiki 10, 119 (1963), 139.

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

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

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

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

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

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

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

[12] CRE ́AS, H., AND MOULIN, H. Sequencing with opting out: Improving upon random priority. Working Paper (1998).

[13] CR `ES, H., AND MOULIN, H. Free access to the commons: random priority versus average cost.

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

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

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

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

[18] KALAI, E., AND SAMET, D. On weighted shapley values. International journal of game theory 16, 3 (1987), 205–222.

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

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

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

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

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

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

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

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

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

[28] MOULIN, H. An application of the shapley value to fair division with money. Econometrica: Journal of the Econometric Society (1992), 1331–1349.

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

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

[31] SHAPLEY, L. S. On balanced sets and cores. Naval Research Logistics Quarterly 14, 4 (1967), 453–460.

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

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

[34] TADENUMA, K. Trade-off between equity and efficiency in a general economy with indivisible goods. Social Choice and Welfare 13, 4 (1996), 445–450.

[35] TADENUMA, K., AND THOMSON, W. No-envy and consistency in economies with indivisible goods. Econometrica: Journal of the Econometric Society (1991), 1755–1767.

[36] TADENUMA, K., AND THOMSON, W. The fair allocation of an indivisible good when monetary compensations are possible. Mathematical Social Sciences 25, 2 (1993), 117–132.

[37] TADENUMA, K., AND THOMSON, W. Refinements of the no-envy solution in economies with indivisible goods. Theory and Decision 39, 2 (1995), 189–206.

[38] THOMSON, W. On monotonicity in economies with indivisible goods. Social Choice and Welfare 21, 2 (2003), 195–205.

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