zbMATH — the first resource for mathematics

Testing consumer rationality using perfect graphs and oriented discs. (English) Zbl 1406.91096
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 187-200 (2015).
Summary: Given a consumer data-set, the axioms of revealed preference proffer a binary test for rational behaviour. A natural (non-binary) measure of the degree of rationality exhibited by the consumer is the minimum number of data points whose removal induces a rationalisable data-set. We study the computational complexity of the resultant consumer rationality problem in this paper. This problem is, in the worst case, equivalent (in terms of approximation) to the directed feedback vertex set problem. Our main result is to obtain an exact threshold on the number of commodities that separates easy cases and hard cases. Specifically, for two-commodity markets the consumer rationality problem is polynomial time solvable; we prove this via a reduction to the vertex cover problem on perfect graphs. For three-commodity markets, however, the problem is NP-complete; we prove this using a reduction from planar 3-sat that is based upon oriented-disc drawings.
For the entire collection see [Zbl 1326.68026].

91B08 Individual preferences
91B42 Consumer behavior, demand theory
05C90 Applications of graph theory
Full Text: DOI
[1] Afriat, S.: The construction of a utility function from expenditure data. Int. Econ. Rev. 8, 67–77 (1967) · Zbl 0248.90001 · doi:10.2307/2525382
[2] Afriat, S.: On a system of inequalities in demand analysis: an extension of the classical method. Int. Econ. Rev. 14, 460–472 (1967) · Zbl 0332.90002 · doi:10.2307/2525934
[3] Apesteguia, J., Ballester, M.: A measure of rationality and welfare. Journal of Political Economy (2015, to appear) · doi:10.1086/683838
[4] Berge, C.: Färbung von Graphen deren sämtliche beziehungsweise deren ungerade Kreise starr sind (Zusammenfassung). Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114–115 (1961)
[5] Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006) · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[6] Dean, M., Martin, D.: Measuring rationality with the minimum cost of revealed preference violations. Review of Economics and Statistics (2015, to appear)
[7] Deb, R., Pai, M.: The geometry of revealed preference. J. Math. Econ. 50, 203–207 (2014) · Zbl 1286.91079 · doi:10.1016/j.jmateco.2013.11.005
[8] Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005) · Zbl 1084.68051 · doi:10.4007/annals.2005.162.439
[9] Earl, R.: Geometry II: 3.1 Stereographic Projection and the Riemann Sphere (2007). https://people.maths.ox.ac.uk/earl/G2-lecture5.pdf
[10] Echenique, F., Lee, S., Shum, M.: The money pump as a measure of revealed preference violations. J. Polit. Econ. 119(6), 1201–1223 (2011) · doi:10.1086/665011
[11] Gross, J.: Testing data for consistency with revealed preference. Rev. Econ. Stat. 77(4), 701–710 (1995) · doi:10.2307/2109817
[12] Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discret. Math. 21, 325–356 (1984) · Zbl 0554.05041
[13] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimisation. Springer-Verlag, Berlin (1988) · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[14] Guruswami, V., Hastad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: every ordering CSP is approximation resistant. SIAM J. Comput. 40(3), 878–914 (2011) · Zbl 1235.68075 · doi:10.1137/090756144
[15] Famulari, M.: A household-based, nonparametric test of demand theory. Rev. Econ. Stat. 77, 372–383 (1995) · doi:10.2307/2109872
[16] Heufer, J.: A geometric approach to revealed preference via Hamiltonian cycles. Theor. Decis. 76(3), 329–341 (2014) · Zbl 1298.91083 · doi:10.1007/s11238-013-9373-4
[17] Houthakker, H.: Revealed preference and the utility function. Economica New Ser. 17(66), 159–174 (1950) · doi:10.2307/2549382
[18] Houtman, M., Maks, J.: Determining all maximal data subsets consistent with revealed preference. Kwantitatieve Methoden 19, 89–104 (1950)
[19] Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972) · doi:10.1007/978-1-4684-2001-2_9
[20] Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of STOC, pp 767–775 (2002) · Zbl 1192.68367
[21] Koo, A.: An emphirical test of revealed preference theory. Econometrica 31(4), 646–664 (1963) · doi:10.2307/1909164
[22] Lovász, L.: Normal hypergraphs and the perfect graph conjecture. Discret. Math. 2(3), 253–267 (1972) · Zbl 0239.05111 · doi:10.1016/0012-365X(72)90006-4
[23] Rose, H.: Consistency of preference: the two-commodity case. Rev. Econ. Stud. 25, 124–125 (1958) · doi:10.2307/2296210
[24] Samuelson, P.: A note on the pure theory of consumer’s behavior. Economica 5(17), 61–71 (1938) · doi:10.2307/2548836
[25] Samuelson, P.: Consumption theory in terms of revealed preference. Economica 15(60), 243–253 (1948) · doi:10.2307/2549561
[26] Seymour, P.: Packing directed circuits fractionally. Combinatorica 15(2), 281–288 (1995) · Zbl 0826.05031 · doi:10.1007/BF01200760
[27] Svensson, O.: Hardness of vertex deletion and project scheduling. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol. 7408, pp. 301–312. Springer, Heidelberg (2012) · Zbl 1370.68112 · doi:10.1007/978-3-642-32512-0_26
[28] Swafford, J., Whitney, G.: Nonparametric test of utility maximization and weak separability for consumption, leisure and money. Rev. Econ. Stat. 69, 458–464 (1987) · doi:10.2307/1925533
[29] Varian, H.: Revealed preference. In: Szenberg, M., et al. (eds.) Samulesonian Economics and the 21st Century, pp. 99–115. Oxford University Press, New York (2005)
[30] Varian, H.: Goodness-of-fit in optimizing models. J. Econometrics 46, 125–140 (1990) · Zbl 04580373 · doi:10.1016/0304-4076(90)90051-T
[31] Wang, D., Kuo, Y.: A study on two geometric location problems. Inf. Process. Lett. 28(6), 281–286 (1988) · Zbl 0675.68071 · doi:10.1016/0020-0190(88)90174-3
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.