Abstract
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.
Similar content being viewed by others
References
Allgower EL, Georg K (2003) Introduction to Numerical Continuation Methods. 2nd edn. SIAM Society for Industrial and Applied Mathematics, Philadelphia
Alvi E (1997) First-order approach to principal-agent problems: A Generalization. Geneva Risk Insur Rev 22:59–65
Andreani R, Castro SLC, Chela JL, Friedlander A, Santos SA (2009) An inexact-restoration method for nonlinear bilevel programming problems. Comput Optim Appl 43:307–328
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)
Chow SN, Mallet-Paret J, Yorke JA (1978) Finding zeros of maps: homotopy methods that are constructive with probability one. Math Comput 32:887–899
Conlon JR (2009) Two new conditions supporting the first-order approach to multisignal principal-agent problem. Econometrica 77:249–278
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
Feng GC, Lin ZH, Yu B (1998) Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem. Nonlinear Anal. 32:761–768
Grossman SJ, Hart OD (1983) An Analysis of the principal-agent problem. Econometrica 51:7–45
Jewitt I (1988) Justifying the first-order approach to principal-agent problems. Economica 56:1177–1190
Kellogg RB, Li TY, Yorke JA (1976) A constructive proof of the Brouwer fixed-point theorem and computational results. SIAM J Num Anal 13:473–483
Koehne S (2010) The first-order approach to moral hazard problems with hidden saving. Working paper, University of Mannheim, Mannheim, Germany
LiCalzi M, Spaeter S (2003) Distributions for the first-order approach to principal-agent problems. Econ Theor 21:167–173
Lin ZH, Li Y, Yu B (1996) A combined homotopy interior point method for general nonlinear programming problems. Appl Math Comput 80:209–222
Lin G, Mengwei X, Ye JJ (2014) On solving simple bilevel programs with a nonconvex lower level program. Math Progr Ser A 144:277–305
Mengwei X, Ye JJ (2014) A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput Optim Appl 59:353–377
Mirrlees JA (1979) The implication of moral hazard for optimal insurance. Seminar given at conference held in honor of Karl Borch. Mimeo, Bergen, Norway
Mirrlees JA (1999) The theory of moral hazard and unobservable behavior: part I, mimeo, 1975, Nuffild College, Oxford. Rev Econ Stud 66:3–21
Myerson RB (1982) Optimal coordination mechanisms in generalized principal-agent problems. J Math Econ 10:67–81
Prescott ES (1999) A primer on Moral-Hazard models. Fed Reserve Bank of Richmond Quanterly Rev 85:47–77
Prescott ES (2004) Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm. J Econ Dynam Control 28:777–800
Qi L, Wei Z (2000) On the constant positive linear dependence condition and its application to SQP methods. SIAM J Optim 10:963–981
Richard L, Burden J, Faires D (2004) Numerical Analysis. 8th edn. Brooks Cole, USA
Rogerson WP (1985) The first-order approach to principal-agent problems. Economica 53:1357–1367
Shao S, Xu Q (2009) Distributions for the validity of the first-order approach to principal-agent problems. J Fudan Univ 48:277–280
Sinclair-Desgagne B (1994) The first-order approach to multi-signal principal-agent problems. Econometrica 62:459–465
Smale S (1976) A convergent process of price adjustment and global newton methods. J Math Econ 3:107–120
Su CL, Judd KL (2007) Computation of moral-hazard problems. Working paper, CMS-EMS, Kellogg School of Management, Northwestern University, Evanston, llinois, USA
Watson LT, Billups SC, Morgan AP (1987) Algorithm 652 hompack: a suite of codes for globally convergent homotopy algorithms. ACM Trans Math Softw 13:281–310
Yang L, Yu B, Xu Q (2012) Combined homotopy infeasible interior point method for nonconvex programming. Pac J Optim 88:89–101
Ye JJ, Zhu D (2010) New necessary optimality conditions for bilevel programs by combining MPEC and the Value Function Approach. SIAM J Optim 20:1885–1905
Yu B, Shang YF (2006) Boundary moving combined homotopy method for nonconvex nonlinear programming. J Math Res Expos 26:831–834
Acknowledgments
The authors gratefully acknowledge the support of the National Natural Science Foundation of China (11171051, 91230103), the China Postdoctoral Science Foundation funded project (No. 2016M591468) and the Education Department Foundation of Jilin province (No. 2015348). The authors are also grateful to Dr. Bryan Williams from the University of Liverpool for improving the English writing and the anonymous referees for their insightful comments and suggestions that have greatly improved the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, Z., Yu, B. A modified homotopy method for solving the principal-agent bilevel programming problem. Comp. Appl. Math. 37, 541–566 (2018). https://doi.org/10.1007/s40314-016-0361-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40314-016-0361-5
Keywords
- Principal-agent model
- Piecewise linear contractual function
- Homotopy method
- Nonconvex programming
- Simpson’s rule