×

A modified homotopy method for solving the principal-agent bilevel programming problem. (English) Zbl 1409.91157

Summary: In this paper, the principal-agent bilevel programming problem with integral operator is considered, in which the upper-level object is the agent that maximizes its expected utility with respect to an agreed compensation contract. The constraints are the principal’s participation and the agent’s incentive compatibility. The latter is a lower-level optimization problem with respect to its private action. To solve an equivalent single-level nonconvex programming problem with integral operator, a modified homotopy method for solving the Karush-Kuhn-Tucker system is proposed. This method requires only an interior point and, not necessarily, a feasible initial approximation for the constraint shifting set. Global convergence is proven under some mild conditions. Numerical experiments were performed by our homotopy method as well as by fmincon in Matlab, LOQO and MINOS. The experiments showed that: designing a piecewise linear contract is much better than designing a piecewise constant contract and only needs to solve a much lower-dimensional optimization problem and hence needs much less computation time; the optimal value of the principal-agent model with designing piecewise linear contract tends to a limitation, while the discrete segments gradually increase; and finally, the proposed modified homotopy method is feasible and effective.

MSC:

91B40 Labor market, contracts (MSC2010)
90C26 Nonconvex programming, global optimization
14F99 (Co)homology theory in algebraic geometry

Software:

Matlab; HOMPACK
Full Text: DOI

References:

[1] Allgower EL, Georg K (2003) Introduction to Numerical Continuation Methods. 2nd edn. SIAM Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1036.65047
[2] Alvi, E, First-order approach to principal-agent problems: A generalization, Geneva Risk Insur Rev, 22, 59-65, (1997) · doi:10.1023/A:1008663531322
[3] Andreani, R; Castro, SLC; Chela, JL; Friedlander, A; Santos, SA, An inexact-restoration method for nonlinear bilevel programming problems, Comput Optim Appl, 43, 307-328, (2009) · Zbl 1170.90484 · doi:10.1007/s10589-007-9147-4
[4] Bueno LF, Haeser G, Martłnez JM (2016) An inexact restoration approach to optimization problems with multiobjective constraints under weighted-sum scalarization. Optim Lett. doi:10.1007/s11590-015-0928-x (to appear) · Zbl 1353.90143
[5] Chow, SN; Mallet-Paret, J; Yorke, JA, Finding zeros of maps: homotopy methods that are constructive with probability one, Math Comput, 32, 887-899, (1978) · Zbl 0398.65029 · doi:10.1090/S0025-5718-1978-0492046-9
[6] Conlon, JR, Two new conditions supporting the first-order approach to multisignal principal-agent problem, Econometrica, 77, 249-278, (2009) · Zbl 1160.91314 · doi:10.3982/ECTA6688
[7] Feng GC, Yu B (1995) Combined homotopy interior point method for nonlinear programming problems. In: Ushijima T, Shi ZC, Kako T (eds) Advances in Numerical Mathematics, Proceeding of the second Japan-China Seminar on Numerical Mathematics. Kinokuniya, Tokyo, Japan, pp 9-16 · Zbl 0836.65081
[8] Feng, GC; Lin, ZH; Yu, B, Existence of an interior pathway to a karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Anal., 32, 761-768, (1998) · Zbl 1060.90692 · doi:10.1016/S0362-546X(97)00516-6
[9] Grossman, SJ; Hart, OD, An analysis of the principal-agent problem, Econometrica, 51, 7-45, (1983) · Zbl 0503.90018 · doi:10.2307/1912246
[10] Jewitt, I, Justifying the first-order approach to principal-agent problems, Economica, 56, 1177-1190, (1988) · Zbl 0654.90001
[11] Kellogg, RB; Li, TY; Yorke, JA, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J Num Anal, 13, 473-483, (1976) · Zbl 0355.65037 · doi:10.1137/0713041
[12] Koehne S (2010) The first-order approach to moral hazard problems with hidden saving. Working paper, University of Mannheim, Mannheim, Germany · Zbl 1180.90188
[13] LiCalzi, M; Spaeter, S, Distributions for the first-order approach to principal-agent problems, Econ Theor, 21, 167-173, (2003) · Zbl 1030.91018 · doi:10.1007/s00199-001-0250-y
[14] Lin ZH, Li Y, Yu B (1996) A combined homotopy interior point method for general nonlinear programming problems. Appl Math Comput 80:209-222 · Zbl 0883.65054
[15] Lin, G; Mengwei, X; Ye, JJ, On solving simple bilevel programs with a nonconvex lower level program, Math Progr Ser A, 144, 277-305, (2014) · Zbl 1301.65050 · doi:10.1007/s10107-013-0633-4
[16] Mengwei, X; Ye, JJ, A smoothing augmented Lagrangian method for solving simple bilevel programs, Comput Optim Appl, 59, 353-377, (2014) · Zbl 1326.90068 · doi:10.1007/s10589-013-9627-7
[17] Mirrlees JA (1979) The implication of moral hazard for optimal insurance. Seminar given at conference held in honor of Karl Borch. Mimeo, Bergen, Norway · Zbl 0576.90005
[18] Mirrlees, JA, The theory of moral hazard and unobservable behavior: part I, mimeo, 1975, nuffild college, Oxford, Rev Econ Stud, 66, 3-21, (1999) · Zbl 0958.91027 · doi:10.1111/1467-937X.00075
[19] Myerson, RB, Optimal coordination mechanisms in generalized principal-agent problems, J Math Econ, 10, 67-81, (1982) · Zbl 0481.90001 · doi:10.1016/0304-4068(82)90006-4
[20] Prescott, ES, A primer on moral-hazard models, Fed Reserve Bank of Richmond Quanterly Rev, 85, 47-77, (1999)
[21] Prescott, ES, Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm, J Econ Dynam Control, 28, 777-800, (2004) · Zbl 1180.90188 · doi:10.1016/S0165-1889(03)00053-8
[22] Qi, L; Wei, Z, On the constant positive linear dependence condition and its application to SQP methods, SIAM J Optim, 10, 963-981, (2000) · Zbl 0999.90037 · doi:10.1137/S1052623497326629
[23] Richard L, Burden J, Faires D (2004) Numerical Analysis. 8th edn. Brooks Cole, USA · Zbl 0788.65001
[24] Rogerson, WP, The first-order approach to principal-agent problems, Economica, 53, 1357-1367, (1985) · Zbl 0576.90005
[25] Shao, S; Xu, Q, Distributions for the validity of the first-order approach to principal-agent problems, J Fudan Univ, 48, 277-280, (2009) · Zbl 1212.91066
[26] Sinclair-Desgagne, B, The first-order approach to multi-signal principal-agent problems, Econometrica, 62, 459-465, (1994) · Zbl 0798.90020 · doi:10.2307/2951619
[27] Smale, S, A convergent process of price adjustment and global Newton methods, J Math Econ, 3, 107-120, (1976) · Zbl 0354.90018 · doi:10.1016/0304-4068(76)90019-7
[28] Su CL, Judd KL (2007) Computation of moral-hazard problems. Working paper, CMS-EMS, Kellogg School of Management, Northwestern University, Evanston, llinois, USA · Zbl 1170.90484
[29] Watson, LT; Billups, SC; Morgan, AP, Algorithm 652 hompack: a suite of codes for globally convergent homotopy algorithms, ACM Trans Math Softw, 13, 281-310, (1987) · Zbl 0626.65049 · doi:10.1145/29380.214343
[30] Yang, L; Yu, B; Xu, Q, Combined homotopy infeasible interior point method for nonconvex programming, Pac J Optim, 88, 89-101, (2012) · Zbl 1257.49032
[31] Ye, JJ; Zhu, D, New necessary optimality conditions for bilevel programs by combining MPEC and the value function approach, SIAM J Optim, 20, 1885-1905, (2010) · Zbl 1279.90187 · doi:10.1137/080725088
[32] Yu, B; Shang, YF, Boundary moving combined homotopy method for nonconvex nonlinear programming, J Math Res Expos, 26, 831-834, (2006) · Zbl 1126.65057
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.