Testing consumer rationality using perfect graphs and oriented discs

DOI10.1007/978-3-662-48995-6_14MaRDI QIDQ3460788zbMATH OpenOpenAlexFDO

Authors Shant Boodaghians, Adrian Vetta

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1507.07581

Mathematics Subject Classification ID

Applications of graph theory (05C90) Individual preferences (91B08) Consumer behavior, demand theory (91B42)

Abstract: 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 thisusing a reduction from planar 3-SAT that is based upon oriented-disc drawings.

Recommendations

• The computational complexity of rationalizing behavior
• The Complexity of Rationalizing Matchings
• Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms
• Revealed preference dimension via matrix sign rank
• Revealed preference test and shortest path problem; graph theoretic structure of the rationalizability test

Cites work

• A geometric approach to revealed preference via Hamiltonian cycles
• A study on two geometric location problems
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Geometric algorithms and combinatorial optimization
• Hardness of vertex deletion and project scheduling
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• On a System of Inequalities in Demand Analysis: An Extension of the Classical Method
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Packing directed circuits fractionally
• The Construction of Utility Functions from Expenditure Data
• The geometry of revealed preference
• The strong perfect graph theorem

Cited in

(5)

• Revealed preference theory: an algorithmic outlook
• Revealed preference dimension via matrix sign rank
• Revealed preference test and shortest path problem; graph theoretic structure of the rationalizability test
• On the computational complexity of consumer decision rules
• The computational complexity of rationalizing behavior

This page was built for publication: Testing consumer rationality using perfect graphs and oriented discs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460788)