revealed preference axioms; rationality; mixed-integer programming; global optimization; simulated annealing
Abstract :
[en] This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np}-complete. This makes the application of these tests problematic for (increasingly available) large(r) scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming ({\sc mip}) formulations of the collective rationality tests, which can be usefully applied to medium sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data.
Research center :
QuantOM HEC-ULiège
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Talla Nobibon, Fabrice
Cherchye, Laurens
Crama, Yves ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Demuynck, Thomas
De Rock, Bram
Spieksma, Frits C.R.
Language :
English
Title :
Revealed preference tests of collectively rational consumption behavior: formulations and algorithms
Publication date :
November 2016
Journal title :
Operations Research
ISSN :
0030-364X
eISSN :
1526-5463
Publisher :
Operations Research Society of America, Baltimore, United States - Maryland
Volume :
64
Issue :
6
Pages :
1197–1216
Peer reviewed :
Peer Reviewed verified by ORBi
Name of the research project :
PAI COMEX
Funders :
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique
Afriat, S.N., The construction of utility functions from expenditure data (1967) Internat. Econom. Rev., 8 (1), pp. 67-77
Ahuja, R.K., Magnanti, T.L., Orlin, J.B., (1993) Network Flows: Theory, Algorithms, and Applications, , (Prentice Hall, Upper Saddle River, NJ)
Apesteguia, J., Ballester, M., The computational complexity of ratio-nalizing behavior (2010) J. Math. Econom., 46 (3), pp. 356-363
Apps, P.F., Rees, R., Taxation and the household (1988) J. Public Econom., 35 (3), pp. 355-369
Bargain, O., Donni, O., Expenditure on children: A Rothbarth-type method consistent with scale economies and parents' bargaining (2012) Eur. Econom. Rev., 56 (4), pp. 792-813
Baron, R., Durieu, J., Haller, H., Solal, P., Finding a Nash equilibrium in spatial games is an NP-complete problem (2004) Econom. Theory, 23 (2), pp. 445-454
Baron, R., Durieu, J., Haller, H., Savani, R., Solal, P., Good neighbors are hard to find: Computational complexity of network formation (2008) Rev. Econom. Design, 12 (1), pp. 1-19
Blundell, R., Chiappori, P.-A., Meghir, C., Collective labor supply with children (2005) J. Political Econom., 115 (6), pp. 1277-1306
Bourguignon, F., Browning, M., Chiappori, P.-A., Efficient intra-household allocations and distribution factors: Implications and identification (2009) Rev. Econom. Stud., 76 (2), pp. 503-528
Brandt, F., Fisher, F., Computing the minimal covering set (2008) Math. Soc. Sci., 56 (2), pp. 254-268
Brandt, F., Fisher, F., Harrenstein, P., Mair, M., A computational analysis of the tournament equilibrium set (2010) Soc. Choice and Welfare, 34 (4), pp. 597-609
Browning, M., Chiappori, P.-A., Efficient intra-household allocations: A general characterization and empirical tests (1998) Econometrica, 66 (6), pp. 1241-1278
Cechlarova, K., Hajdukova, J., Computational complexity of stable partitions with B-preferences (2002) Internat. J. Game Theory, 31 (3), pp. 353-364
Cherchye, L., Vermeulen, F., Nonparametric analysis of household labor supply: Goodness of fit and power of the unitary and the col-lective model (2008) Rev. Econom. Statist., 90 (2), pp. 267-274
Cherchye, L., De Rock, B., Vermeulen, F., The collective model of household consumption: A nonparametric characterization (2007) Econo-metrica, 75 (2), pp. 553-574
Cherchye, L., De Rock, B., Vermeulen, F., Opening the black box of intra-household decision making (2009) J. Political Econom., 117 (6), pp. 1074-1104
Cherchye, L., De Rock, B., Vermeulen, F., An Afriat theorem for the collective model of household consumption (2010) J. Econom. Theory, 145 (3), pp. 1142-1163
Cherchye, L., Demuynck, T., De Rock, B., Testable implications of general equilibrium models: An integer programming approach (2011) J. Math. Econom., 47 (4-5), pp. 564-575
Cherchye, L., De Rock, B., Vermeulen, F., The revealed preference approach to collective consumption behavior: Testing and sharing rule recovery (2011) Rev. Econom. Stud., 78, pp. 176-198
Cherchye, L., De Rock, B., Vermeulen, F., Collective household con-sumption behavior: Revealed preference analysis (2012) Foundations and Trends Econom., 4 (4), pp. 225-312
Cherchye, L., De Rock, B., Sabbe, J., Vermeulen, F., Nonparametric tests of collectively rational consumption behavior: An integer programming procedure (2008) J. Econometrics, 147 (2), pp. 258-265
Chiappori, P.A., Collective labor supply and welfare (1992) J. Political Econom., 100 (3), pp. 437-467
Chu, F., Halpern, J., On the NP-completeness of finding an optimal strategy in games with common payoffs (2001) Internat. J. Game Theory, 30 (1), pp. 99-106
Chvátal, V., (1983) Linear Programming, , (W. H. Freeman and Company, New York)
Conitzer, V., Sandholm, T., New complexity results about Nash equi-libria (2008) Games Econom. Behav., 63 (2), pp. 621-641
Deb, R., (2011) An Efficient Nonparametric Test of the Collective Household Model, , Mimeo, University of Toronto, Canada
Dekkers, A., Aarts, E., Global optimization and simulated annealing (1991) Math. Programming, 50 (1), pp. 367-393
Demuynck, T., The computational complexity of rationalizing Pareto optimal choice behavior (2014) Soc. Choice and Welfare, 42 (3), pp. 529-549
Diewert, W.E., Afriat and revealed preference theory (1973) Rev. Econom. Stud., 40 (3), pp. 419-425
Dunbar, G.R., Lewbel, A., Pendakur, K., Children's resources in col-lective households: Identification, estimation, and an application to child poverty in Malawi (2013) Amer. Econom. Rev., 103 (1), pp. 438-471
Echenique, F., Lee, S., Shum, M., (2010) Revealed Preference Tests Using Supermarket Data: The Money Pump, , Social science Working Paper 1328, California Institute of Technology, Pasadena, CA
Echenique, F., Lee, S., Shum, M., The money pump as a measure of revealed preference violations (2011) J. Political Econom., 119 (6), pp. 1201-1223
Echenique, F., Golovin, D., Wierman, A., A revealed preference approach to computational complexity in economics (2011) Proc. 12th ACM Conf. Electronic Commerce, EC '11, pp. 101-110. , (ACM, New York)
Fang, Q., Zhu, S., Cai, M., Deng, X., On computational complexity of membership test in flow games and linear production games (2002) Internat. J. Game Theory, 31 (1), pp. 39-45
Farin, G., Class A Bézier curves (2006) Comput. Aided Geometric Design, 23 (7), pp. 573-581
Fortin, B., Lacroix, G., A test of the unitary and collective models of household labour supply (1997) Econom. J., 107 (443), pp. 933-955
Galambos, A., (2009) The Complexity of Nash Rationalizability, , Technical report, Lawrence University, Appleton, WI
Gilboa, I., Zemel, E., Nash and correlated equilibria: Some complexity considerations (1989) Games Econom. Behav., 1 (1), pp. 80-93
Goffe, W.L., Ferrier, G.D., Rogers, J., Global optimization of statistical functions with simulated annealing (1994) J. Econometrics, 60 (1-2), pp. 65-99
Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 2nd Ed., 57. , (North Holland, Netherlands)
Hudry, O., A survey on the complexity of tournament solutions (2009) Math. Soc. Sci., 57 (3), pp. 292-303
Kalyanaraman, S., Umans, C., The complexity of rationlizing match-ings (2008) Proc. ISAAC2008, Lecture Notes Comput. Sci., 5369, pp. 171-182
Karmarkar, N., A new polynomial-time algorithm for linear programming (1984) Combinatorica, 4 (4), pp. 373-395
Khachiyan, L.G., A polynomial algorithm in linear programming (1979) Doklady Akademii Nauk SSSR, 244 (5), pp. 1093-1096. , translated in Soviet Mathematics Doklady 20: 191-194
Locatelli, M., Simulated annealing algorithms for continuous global optimization: Convergence conditions (2000) J. Optim. Theory Appl., 104 (1), pp. 121-133
Procaccia, A.D., Rosenschein, J.S., On the complexity of achieving proportional representation (2008) Soc. Choice and Welfare, 30 (3), pp. 353-362
Sabbe, J., (2010) Revealed Preference Analysis of Consumption and Production Behavior: Applications of the Collective Model, , PhD thesis, KU Leuven, Leuven, Belgium
Samuelson, P.A., A note on the pure theory of consumer's behaviour (1938) Economica, 5 (17), pp. 61-71
Samuelson, P.A., Consumption theory in terms of revealed prefer-ence (1948) Economica, 15 (60), pp. 243-253
Smeulders, B., Cherchye, L., De Rock, B., Fcr, S., Talla Nobibon, F., Transitive preferences in multi-member households (2015) Econom. Theory Bull., 3 (2), pp. 243-254
Talla Nobibon, F., Fcr, S., On the complexity of testing the collective axiom of revealed preference (2010) Math. Soc. Sci., 60 (2), pp. 123-136
Talla Nobibon, F., Smeulders, B., Spieksma, F.R., A note on test-ing axioms of revealed preference (2015) J. Optim. Theory Appl., 166 (3), pp. 1063-1070
Talla Nobibon, F., Caj, H., Leus, R., Fcr, S., Coloring graphs using two colors while avoiding monochromatic cycles (2012) INFORMS J. Comput., 24 (3), pp. 485-499
Talla Nobibon, F., Cherchye, L., De Rock, B., Sabbe, J., Fcr, S., Heuristics for deciding collectively rational consumption behavior (2011) Computational Econom., 38 (2), pp. 173-204
Teo, C.-P., Vohra, R., (2003) Afriat's Theorem and Negative Cycles, , Mimeo, Northwestern University, Evanston, IL
Varian, H.R., The nonparametric approach to demand analysis (1982) Econometrica, 50 (4), pp. 945-974
Varian, H.R., Revealed preference (2006) Samuelsonian Economics and the Twenty-First Century, pp. 99-115. , Szenberg M, Ramrattan L, Gottes-man A, eds (Oxford University Press, New York)
Walters, J.A., Nonnegative matrix equations having positive solutions (1969) Math. Comput., 23 (108), p. 827
Woeginger, G.J., Banks winners in tournaments are difficult to rec-ognize (2003) Soc. Choice and Welfare, 20 (3), pp. 523-528
