Abstract
We consider an externality game in which nonatomic agents choose from a finite set of alternatives and disutility is determined only by the number of agents choosing each alternative. The equilibrium is defined with respect to the agents’ choices so that taste heterogeneity, modeled through randomized parameters, can be estimated from collective choice data. The joint density of the taste parameters is computed by a biquadratic inverse optimization process that matches observed choices to the equilibrium condition associated with a set-valued best-response function, and hence imposes no prior assumptions on the taste parameters. The model is capacitated with disutility generalized into an arbitrary function that is continuous in attributes and measurable in taste parameters. The existence of an equilibrium under such a disutility model is established by observing that, in an externality game, the proposed aggregate equilibrium is actually equivalent to the agent-specific Nash equilibrium previously established by Schmeidler (J Stat Phys 7(4):295–300, 1973). In a comparison test on intensive metro route-choice data, we demonstrate that the proposed model is a good alternative to existing nongame choice models. An extended test also demonstrates the advantage of the general disutility model in describing agents choice behaviors in other contexts.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R. K., & Orlin, J. B. (2001). Inverse optimization. Operations Research, 49(5), 771–783.
Allen, R. G. D. (1938). Mathematical analysis for economists. London: Macmillan.
Arrow, K. J., Chenery, H. B., Minhas, B. S., & Solow, R. M. (1961). Capital-labor substitution and economic efficiency. The Review of Economics and Statistics, 43(3), 225–250.
Aumann, R. J. (1965). Integrals of set-valued functions. Journal of Mathematical Analysis and Applications, 12(1), 1–12.
Axhausen, K., Horni, A. & Nagel, K. ( 2016). The multi-agent transport simulation MATSim.
Beckmann, M., McGuire, C. B., & Winsten, C. B. (1956). Studies in the Economics of Transportation. Yale: Yale University Press.
Bertsimas, D., Gupta, V., & Paschalidis, I. C. (2015). Data-driven estimation in equilibrium using inverse optimization. Mathematical Programming, 153(2), 1–39.
Bhat, C. R. (1998). Accommodating variations in responsiveness to level-of-service measures in travel mode choice modeling. Transportation Research Part A: Policy and Practice, 32(7), 495–507.
Blackwell, D. (1951). The range of certain vector integrals. Proceedings of the American Mathematical Society, 2(3), 390–395.
Bomze, I. M., Ling, C., Qi, L., & Zhang, X. (2012). Standard bi-quadratic optimization problems and unconstrained polynomial reformulations. Journal of Global Optimization, 52(4), 663–687.
Brown, G. W. & Von Neumann, J. ( 1950). Solutions of games by differential equations.
Chen, A., Ji, Z., & Recker, W. (2002). Travel time reliability with risk-sensitive travelers. Transportation Research Record: Journal of the Transportation Research Board, 1783, 27–33.
Cheridito, P., Horst, U., Kupper, M., & Pirvu, T. A. (2015). Equilibrium pricing in incomplete markets under translation invariant preferences. Mathematics of Operations Research, 41(1), 174–195.
Dafermos, S. C. (1972). The traffic assignment problem for multiclass-user transportation networks. Transportation Science, 6(1), 73–87.
Dial, R. B. (1996). Bicriterion traffic assignment: Basic theory and elementary algorithms. Transportation Science, 30(2), 93–111.
Epstein, L. G. (1988). Risk aversion and asset prices. Journal of Monetary Economics, 22(2), 179–192.
Fellendorf, M., & Vortisch, P. (2010). Microscopic traffic flow simulator VISSIM, International Series in Operations Research & Management. Science, 145, 63–93.
Fisk, C. (1980). Some developments in equilibrium traffic assignment. Transportation Research Part B: Methodological, 14(3), 243–255.
Fosgerau, M. (2007). Using nonparametrics to specify a model to measure the value of travel time. Transportation Research Part A: Policy and Practice, 41(9), 842–856.
Fox, J. T., Kim, K., Ryan, S. P., & Bajari, P. (2011). A simple estimator for the distribution of random coefficients. Quantitative Economics, 2(3), 381–418.
Heckman, J. J. (2001). Micro data, heterogeneity, and the evaluation of public policy: Nobel lecture. Journal of Political Economy, 109(4), 673–748.
Hong, S.-P., Kim, K. M., Byeon, G., & Min, Y.-H. (2017). A method to directly derive taste heterogeneity of travellers route choice in public transport from observed routes. Transportation Research Part B: Methodological, 95, 41–52.
Hong, S.-P., Min, Y.-H., Park, M.-J., Kim, K. M., & Oh, S. M. (2016). Precise estimation of connections of metro passengers from Smart Card data. Transportation, 43(5), 749–769.
Jang, S., Rasouli, S., & Timmermans, H. (2017). Bias in random regret models due to measurement error: Formal and empirical comparison with random utility model. Transportmetrica A: Transport Science, 13(5), 405–434.
Kakutani, S. (1941). A generalization of Brouwer’s fixed point theorem. Duke Mathematical Journal 8, 457–459.
Kim, D. ( 2014). Improvement of path selecting cost function for Seoul metropolitan area using Smart Card data. MS thesis. Seoul National University.
Kim, K. M., Hong, S.-P., Ko, S.-J., & Kim, D. (2015). Does crowding affect the path choice of metro passengers? Transportation Research Part A: Policy and Practice, 77, 292–304.
Klump, R., McAdam, P., & Willman, A. (2007). Factor substitution and factor-augmenting technical progress in the United States: A normalized supply-side system approach. The Review of Economics and Statistics, 89(1), 183–192.
Knowles, J. K., & Sternberg, E. (1975). On the ellipticity of the equations of nonlinear elastostatics for a special material. Journal of Elasticity, 5(3–4), 341–361.
Konishi, H. (2004). Uniqueness of user equilibrium in transportation networks with heterogeneous commuters. Transportation Science, 38(3), 315–330.
Konno, H. ( 1971) , Bilinear programming: Part I. Algorithm for solving bilinear programs, Technical Report 71-9, Operations Research House, Stanford University (Stanford, CA).
Konno, H. (1976). A cutting plane algorithm for solving bilinear programs. Mathematical Programming, 11(1), 14–27.
Korea Railroad Research Institute (2010). Development of NxTIS to implement railway oriented public transportation framework (In Korean), Technical Report 2010-132.
Leurent, F. (1993). Cost versus time equilibrium over a network. European Journal of Operational Research, 71(2), 205–221.
Ling, C., Nie, J., Qi, L., & Ye, Y. (2009). Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM Journal on Optimization, 20(3), 1286–1310.
Ling, C., Zhang, X., & Qi, L. (2012). Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints. Numerical Linear Algebra with Applications, 19(1), 113–131.
Mandel, B., Gaudry, M., & Rothengatter, W. (1994). Linear or nonlinear utility functions in logit models? The impact on German high-speed rail demand forecasts. Transportation Research Part B: Methodological, 28(2), 91–101.
Marcotte, P., & Zhu, D. L. (1997). Equilibria with infinitely many differentiated classes of customers. Philadelphia: SIAM.
McFadden, D., & Train, K. E. (2000). Mixed MNL models for discrete response. Journal of Applied Econometrics, 15(5), 447–470.
Meunier, F., & Pradeau, T. (2019). Computing solutions of the multiclass network equilibrium problem with affine cost functions. Annals of Operations Research, 274(1), 447–469.
Nash, J. F. (1951). Non-cooperative games. Annals of Mathematics, 54(2), 286–295.
Powell, W. B., & Sheffi, Y. (1982). The convergence of equilibrium algorithms with predetermined step sizes. Transportation Science, 16(1), 45–55.
Rath, K. P. (1992). A direct proof of the existence of pure strategy equilibria in games with a continuum of players. Economic Theory, 2(3), 427–433.
Raveau, S., Muñoz, J. C., & De Grange, L. (2011). A topological route choice model for metro. Transportation Research Part A: Policy and Practice, 45(2), 138–147.
Rosenthal, R. W. (1973). A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2(1), 65–67.
Roughgarden, T., & Tardos, E. (2002). How bad is selfish routing? Journal of ACM, 49(2), 236–259.
Roughgarden, T. & Tardos, E. ( 2004). Bouding the inefficiency of equilibria in nonatomic congestion games. In Games and Economic Behavior (pp. 389–403).
Sandholm, W. H. (2001). Potential games with continuous player sets. Journal of Economic Theory, 97(1), 81–108.
Schmeidler, D. (1973). Equilibrium points of nonatomic games. Journal of Statistical Physics, 7(4), 295–300.
Sun, L., Lu, Y., Jin, J. G., Lee, D. H., & Axhausen, K. W. (2015). An integrated Bayesian approach for passenger flow assignment in metro networks. Transportation Research Part C: Emerging Technologies, 52, 116–131.
Train, K. E. (2008). EM algorithms for nonparametric estimation of mixing distributions. Journal of Choice Modelling, 1(1), 40–69.
Von Neumann, J., & Morgenstern, O. (1953). The theory of games and economic behavior. Princeton: Princeton University Press.
Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineers, 1(11), 325–378.
Yang, L., & Lam, W. (2006). Probit-type reliability-based transit network assignment. Transportation Research Record: Journal of the Transportation Research Board, 1977, 154–163.
Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No. 2021R1A2C1011341). The authors give their thanks to Eric Hong for his translation and proofreading. The authors are also grateful to Max Kapur for his proofreading and helpful suggestions for revision of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A BNN and best-response dynamics
A BNN and best-response dynamics
For current aggregate choice x \(\in \) X, the \(x_i\) of each alternative i \(\in \) N can be disaggregated into \(x_i(\gamma )\), the portions from \(\gamma \in {\hat{\Gamma }}\): \(x_i\) \(=\) \(\sum _{\gamma \in {\hat{\Gamma }}} x_i(\gamma )\), i \(\in \) N. We define a response function \(r_i(x; \gamma )\) and step size \(\lambda (x; \gamma )\) so that the next point \(x'_i\) is defined as \(x'_i(\gamma )\) \(=\) \(x_i(\gamma )\) \(+\) \(\lambda (x;\gamma ) \left( r_i(x; \gamma ) - x_i(\gamma )\right) \). The Brown-von Neumann-Nash (BNN) dynamics use \(r_i(x;\gamma ) = {\hat{g}}(\gamma ) \frac{p_i(x; \gamma )}{\sum _{j \in N} p_j(x; \gamma )}\), and \(\lambda (x ; \gamma ) = \frac{\sum _{j \in N} p_j(x;\gamma )}{1+\sum _{j \in N} p_j(x;\gamma )}\), where \(p_i(x ; \gamma ) = \max \left\{ \frac{1}{{\hat{g}}(\gamma )}\sum _{j \in N} x_j(\gamma ) u_j(x ; \gamma ) -u_i(x; \gamma ), 0\right\} \). On the other hand, the best-response dynamics consider the set \(S(x;\gamma )\) of alternatives with the minimum disutility for \(\gamma \). For simplicity, write S \(\equiv \) \(S(x;\gamma )\) hereafter. Let \(r_i(x; \gamma )\) \(=\) \({\tilde{\rho }}_i(\gamma )\) if \(i \in S\) or 0 otherwise, where \({\tilde{\rho }}(\gamma )\) is generated randomly from the simplices \(\{\rho (\gamma ): \sum _{i \in S} \rho _i(\gamma ) = {\hat{g}}(\gamma )\), \(\rho _i(\gamma ) \ge 0\}\) for \(\gamma \) \(\in \) \({\hat{\Gamma }}\). We adopted the usual moderated step-size rule \(\lambda _k = \frac{1}{k+1}\) (see e.g. Fisk (1980)). In both dynamics, we hired stopping criterion \(\Vert x- x'\Vert \) < \(\epsilon \Vert x\Vert \) for \(\epsilon = 0.01\).
Rights and permissions
About this article
Cite this article
Hong, SP., Kim, K.M. & Ko, SJ. Estimating heterogeneous agent preferences by inverse optimization in a randomized nonatomic game. Ann Oper Res 307, 207–228 (2021). https://doi.org/10.1007/s10479-021-04270-2
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-021-04270-2