×

Optimal affine leader functions in reverse Stackelberg games. Existence conditions and characterization. (English) Zbl 1334.91028

Summary: A generalizing analysis is made in order to ease the solvability of the generally complex single-leader-single-follower reverse Stackelberg game. This game is of a hierarchical nature and can therefore be implemented as a structure for multi-level decision-making problems, like in road pricing. In particular, a leader function of the affine type is analyzed in order to procure a systematic approach to solving the game to optimality. To this end, necessary and sufficient existence conditions for this optimal affine leader function are developed. Compared to earlier results reported in the literature, differentiability of the follower objective functional is relaxed, and locally strict convexity of the sublevel set at the desired reverse Stackelberg equilibrium is replaced with the more general property of an exposed point. Moreover, a full characterization of the set of optimal affine leader functions that is derived, which use in the case of secondary optimization objectives as well as for a constrained decision space, is illustrated.

MSC:

91A65 Hierarchical games (including Stackelberg games)
91A80 Applications of game theory
91B06 Decision theory

Software:

Qhull
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Staňková, K., Olsder, G., Bliemer, M.: Comparison of different toll policies in the dynamic second-best optimal toll design problem: case study on a three-link network. Eur. J. Transp. Infrastruct. Res. 9(4), 331-346 (2009)
[2] von Stackelberg, H.: Marktform und Gleichgewicht. Julius Springer, Vienna, Austria (1934)
[3] Scattolini, R.: Architectures for distributed and hierarchical model predictive control: a review. J. Process Control 19(5), 723-731 (2009) · doi:10.1016/j.jprocont.2009.02.003
[4] Ho, Y.C., Luh, P., Muralidharan, R.: Information structure, Stackelberg games, and incentive controllability. IEEE Trans. Autom. Control 26(2), 454-460 (1981) · Zbl 0476.90089 · doi:10.1109/TAC.1981.1102652
[5] Ho, Y.C., Luh, P., Olsder, G.: A control-theoretic view on incentives. Automatica 18(2), 167-179 (1982) · Zbl 0477.90003 · doi:10.1016/0005-1098(82)90106-6
[6] Olsder, G.: Phenomena in inverse Stackelberg games, part 1: static problems. J. Optim. Theory Appl. 143(3), 589-600 (2009) · Zbl 1182.91056 · doi:10.1007/s10957-009-9573-9
[7] Olsder, G.: Phenomena in inverse Stackelberg games, part 2: dynamic problems. J. Optim. Theory Appl. 143(3), 601-618 (2009) · Zbl 1182.91055 · doi:10.1007/s10957-009-9572-x
[8] Zheng, Y.P., Başar, T.: Existence and derivations of optimal affine incentive schemes for Stackelberg games with partial information: A geometric approach. Int. J. Control 35(6), 997-1011 (1982) · Zbl 0484.90099 · doi:10.1080/00207178208922667
[9] Cansever, D., Başar, T.: A minimum sensitivity approach to incentive design problems. Large Scale Syst. 5, 233-244 (1983) · Zbl 0531.90054
[10] Groot, N., De Schutter, B., Hellendoorn, H.: Toward system-optimal routing in traffic networks: a reverse Stackelberg game approach. In: IEEE Transactions on Intelligent Transportation Systems (2014) Accepted for publication
[11] Chang, T.S., Ho, Y.C.: Incentive problems: a class of stochastic Stackelberg closed-loop dynamic games. Systems and Control Letters 1(1), 16-21 (1981) · Zbl 0481.93055 · doi:10.1016/S0167-6911(81)80006-0
[12] Ehtamo, H., Hämäläinen, R.: Incentive strategies and equilibria for dynamic games with delayed information. J. Optim. Theory Appl. 63(3), 355-369 (1989) · Zbl 0662.90102 · doi:10.1007/BF00939802
[13] Martín-Herrán, G.; Zaccour, G.; Pourtallier, O. (ed.); Gaitsgory, V. (ed.); Bernhard, P. (ed.), Credible linear-incentive equilibrium strategies in linear-quadratic differential games, No. 10, 1-31 (2009), Boston · Zbl 1179.91040 · doi:10.1007/978-0-8176-4834-3_14
[14] Li, M., Cruz Jr, J., Simaan, M.: An approach to discrete-time incentive feedback Stackelberg games. IEEE Trans. Syst. Man Cybern. Part A Syst. Hum. 32(4), 472-481 (2002) · doi:10.1109/TSMCA.2002.804816
[15] Salman, M., Cruz Jr, J.: An incentive model of duopoly with government coordination. Automatica 17(6), 821-829 (1981) · Zbl 0471.90023 · doi:10.1016/0005-1098(81)90069-8
[16] Tolwinski, B.: Closed-loop Stackelberg solution to a multistage linear-quadratic game. J. Optim. Theory Appl. 34(4), 485-501 (1981) · Zbl 0431.90097 · doi:10.1007/BF00935889
[17] Groot, N., De Schutter, B., Hellendoorn, H.: Existence conditions for an optimal affine leader function in the reverse Stackelberg game. In: Proceedings of the 15th IFAC Workshop on Control Applications of Optimization, p. Paper 16. Rimini, Italy (2012) · Zbl 1334.91028
[18] Groot, N., De Schutter, B., Hellendoorn, H.: A full characterization of the set of optimal affine leader functions in the reverse Stackelberg game. In: Proceedings of the 51st IEEE Conference on Decision and Control, pp. 6484-6488. Maui, HI (2012)
[19] Başar, T.: General theory for Stackelberg games with partial state information. Large Scale Syst. 3(1), 47-56 (1982) · Zbl 0477.90098
[20] Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235-256 (2007) · Zbl 1159.90483 · doi:10.1007/s10479-007-0176-2
[21] Vicente, L., Calamai, P.: Bilevel and multilevel programming: a bibliography review. J. Glob. Optim. 5(3), 291-306 (1994) · Zbl 0822.90127 · doi:10.1007/BF01096458
[22] Jeroslow, R.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32(4), 146-164 (1985) · Zbl 0588.90053 · doi:10.1007/BF01586088
[23] Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194-1217 (1992) · Zbl 0760.65063 · doi:10.1137/0913069
[24] Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer Monographs in Mathematics. Springer, New York, NY (2003) · Zbl 1017.49001
[25] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton, NJ (1970) · Zbl 0932.90001 · doi:10.1515/9781400873173
[26] Clarke, F.: Optimization and Nonsmooth Analysis. Wiley, New York, NY (1983) · Zbl 0582.49001
[27] Başar, T., Olsder, G.: Dynamic Noncooperative Game Theory. Classics in Applied Mathematics, 2nd edn. SIAM, Philadelphia, PA (1999) · Zbl 0946.91001
[28] Åström, K., Wittenmark, B.: Computer-Controlled Systems: Theory and Applications, 3rd edn. Prentice Hall, Upper Saddle River, NJ (1997)
[29] Franklin, G., Powell, J., Emami-Naeini, A.: Feedback Control of Dynamic Systems, 6th edn. Prentice-Hall, Upper Saddle River, NJ (2010) · Zbl 0615.93001
[30] Hasselblatt, B., Katok, A.: A First Course in Dynamics. Cambridge University Press, Cambridge, UK (2003) · Zbl 1027.37001 · doi:10.1017/CBO9780511998188
[31] Gellert, W., Gottwald, S., Hellwich, M., Kästner, H., Künstner, H.E.: VNR Concise Encyclopedia of Mathematics, 2nd edn. Van Nostrand Reinhold, New York, NY (1989) · Zbl 0744.00007
[32] Motzkin, T.; Raiffa, H.; Thompson, G.; Thrall, R.; Kuhn, H. (ed.); Tucker, A. (ed.), The double description method, No. 28, 51-73 (1953), Princeton, NJ · Zbl 0050.14201
[33] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester, UK (1986) · Zbl 0665.90063
[34] Golub, G., Van Loan, C.: Matrix Computations, 2nd edn. The John Hopkins University Press, Baltimore, MD (1989) · Zbl 0733.65016
[35] Barber, C., Dobkin, D., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22(4), 469-483 (1996) · Zbl 0884.65145 · doi:10.1145/235815.235821
[36] Rosenbrock, H.: An automatic method for finding the greatest or least value of a function. Comput. J. 3(3), 175-184 (1960) · doi:10.1093/comjnl/3.3.175
[37] De Jong, K.: An analysis of the behavior of a glass of genetic adaptive systems. PhD dissertation, University of Michigan (1975)
[38] Boyd, S., Vandenberge, L.: Convex Optimization. Cambridge University Press, Cambridge, UK (2004) · doi:10.1017/CBO9780511804441
[39] Groot, N., De Schutter, B., Hellendoorn, H.: On systematic computation of optimal nonlinear solutions for the reverse Stackelberg game. IEEE Trans. Syst. Man Cybern. Syst. 44(10), 1315-1327 (2014) · doi:10.1109/TSMC.2014.2311756
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.