×

zbMATH — the first resource for mathematics

\(S\)-modular games, with queueing applications. (English) Zbl 0858.90142
Summary: The notion of \(S\)-modularity was developed by P. Glasserman and the author [Math. Oper. Res. 19, No. 2, 449-476 (1994; Zbl 0801.60077)] in the context of optimal control of queueing networks. \(S-\)modularity allows the objective function to be supermodular in some variables and submodular in others. It models both compatible and conflicting incentives, and hence conveniently accommodates a wide variety of applications.
In this paper, we introduce \(S\)-modularity into the context of \(n\)-player noncooperative games. This generalizes the well-known supermodular games of D. M. Topkis [SIAM J. Control Optimization 17, 773-787 (1979; Zbl 0433.90091)], where each player maximizes a supermodular payoff function (or equivalently, minimizes a submodular payoff function). We illustrate the theory through a variety of applications in queueing systems.

MSC:
91A10 Noncooperative games
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Altman, Flow control using the theory of zero sum Markov games, IEEE Trans. Autom. Contr. 39 (1994) 814-818. · Zbl 0809.90050 · doi:10.1109/9.286259
[2] E. Altman and A. Hordijk, Zero-sum Markov games and worst-case optimal control of queueing systems, Queueing Systems 21 (1995) 415-447 (this issue). · Zbl 0859.90141 · doi:10.1007/BF01149169
[3] E. Altman and G. Koole, Stochastic scheduling games with Markov decision arrival processes, Comp. Math. Appl. 26 (1993) 141-148. · Zbl 0793.90020 · doi:10.1016/0898-1221(93)90123-D
[4] J.A. Buzacott and J.G. Shanthikumar, Design of manufacturing systems using queueing models, Queueing Systems 12 (1992) 135-213. · Zbl 0769.90043 · doi:10.1007/BF01158638
[5] S. Dewan and H. Mendelson, User delay costs and internal pricing for a service facility, Manag. Sci. 36 (1990) 1502-1517. · Zbl 0717.90029 · doi:10.1287/mnsc.36.12.1502
[6] A. Federgruen and H. Groenevelt, The impact of the composition of the customer base in general queueing models, J. Appl. Prob. 24 (1987) 709-724. · Zbl 0626.60093 · doi:10.2307/3214101
[7] E. Gelenbe and I. Mitrani,Analysis and Synthesis of Computer Systems (Academic Press, New York, 1980). · Zbl 0484.68026
[8] P. Glasserman and D.D. Yao, Generalized semi-Markov processes: Antimatroid structure and second order properties, Math. Oper. Res. 17 (1992) 444-469. · Zbl 0753.60086 · doi:10.1287/moor.17.2.444
[9] P. Glasserman and D.D. Yao, Monotone optimal control of permutable GSMP’s, Math. Oper. Res. 19 (1994) 449-476. · Zbl 0801.60077 · doi:10.1287/moor.19.2.449
[10] P. Glasserman and D.D. Yao,Monotone Structure in Discrete-Event Systems (Wiley, New York, 1994). · Zbl 0920.93003
[11] Y.A. Korilis and A.A. Lazar, Why is flow control hard: Optimality, fairness, partial and delay information, Technical Report, Center for Telecommunications Research, Columbia University, New York, NY 10027 (1992).
[12] Y.A. Korilis and A.A. Lazar, On the existence of equilibria in noncooperative optimal flow control, J. ACM, to appear. · Zbl 0885.68015
[13] S. Li and T. Basar, Distributed algorithms for the computation of noncooperative equilibria, Automatica 23 (1987) 523-533. · Zbl 0619.90092 · doi:10.1016/0005-1098(87)90081-1
[14] P. Milgrom and J. Roberts, Rationalizability, learning, and equilibrium in games with strategic complementarities, Econometrica 58 (1990) 1255-1277. · Zbl 0728.90098 · doi:10.2307/2938316
[15] J. Nash, Equilibrium points in N-person games, Proc. Nat. Acad. Sci. USA 36 (1950) 48-49. · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48
[16] J. Nash, The bargaining problem, Econometrica 18 (1950) 155-162. · Zbl 1202.91122 · doi:10.2307/1907266
[17] J. Nash, Non-cooperative games, Ann. Math. 54 (1951) 285-295. · Zbl 0045.08202 · doi:10.2307/1969529
[18] J.B. Rosen, Existence and uniqueness of equilibrium points for concave N-person games, Econometrica 33 (1965) 520-534. · Zbl 0142.17603 · doi:10.2307/1911749
[19] J.G. Shanthikumar and D.D. Yao, Multiclass queueing systems: Polymatroidal structure and optimal scheduling control, Oper. Res. 40 (1992) S293-S299. · Zbl 0764.90036 · doi:10.1287/opre.40.3.S293
[20] S. Stidham, Jr., Pricing and capacity decisions for a service facility: Stability and multiple optima, Manag. Sci. 38 (1992) 1121-1139. · Zbl 0773.90031 · doi:10.1287/mnsc.38.8.1121
[21] D. Topkis, Minimizing a submodular function on a lattice, Oper. Res. 26 (1978) 305-321. · Zbl 0379.90089 · doi:10.1287/opre.26.2.305
[22] D. Topkis, Equilibrium points in nonzero-sum n-person submodular games, SIAM J. Contr. Optim. 17 (1979) 773-787. · Zbl 0433.90091 · doi:10.1137/0317054
[23] R.R. Weber and S. Stidham, Jr., Optimal control of service rates in networks of queues, Adv. Appl. Prob. 19 (1987) 202-218. · Zbl 0617.60090 · doi:10.2307/1427380
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.