Heuristics for deciding collectively rational consumption behavior

F. Talla Nobibon, L.J.H. Cherchye, B. de Rock, J. Sabbe, F. Spieksma

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We propose a directed graph for testing whether observed household consumption behavior satisfies the Collective Axiom of Revealed Preferences (CARP). More precisely, the data satisfy CARP if the graph allows a node-partitioning into two induced subgraphs that are acyclic. We prove that partitioning the obtained graph into two acyclic subgraphs is NP-complete. Next, we derive a necessary condition for CARP that can be verified in polynomial time, and we present an example to show that our necessary and sufficient conditions do not coincide. We also propose and implement fast heuristics for testing the sufficient condition. These heuristics can be used to check reasonably large data sets for CARP, and can be of particular interest when used prior to computationally demanding approaches. Finally, based on computational results for both real-life and synthetic data, we conclude that our heuristics are effective in testing CARP.
Original languageEnglish
Pages (from-to)173-204
JournalComputational Economics
Volume38
Issue number2
Publication statusPublished - 2011

Fingerprint

Testing
Directed graphs
Polynomials
Consumption behavior
Revealed preference
Heuristics
Axiom
Partitioning
Graph
NP-complete
Node
Directed graph
Household consumption

Cite this

Talla Nobibon, F., Cherchye, L. J. H., de Rock, B., Sabbe, J., & Spieksma, F. (2011). Heuristics for deciding collectively rational consumption behavior. Computational Economics, 38(2), 173-204.
Talla Nobibon, F. ; Cherchye, L.J.H. ; de Rock, B. ; Sabbe, J. ; Spieksma, F. / Heuristics for deciding collectively rational consumption behavior. In: Computational Economics. 2011 ; Vol. 38, No. 2. pp. 173-204.
@article{fbd5395238f34483b62bf1c4b3ec1609,
title = "Heuristics for deciding collectively rational consumption behavior",
abstract = "We propose a directed graph for testing whether observed household consumption behavior satisfies the Collective Axiom of Revealed Preferences (CARP). More precisely, the data satisfy CARP if the graph allows a node-partitioning into two induced subgraphs that are acyclic. We prove that partitioning the obtained graph into two acyclic subgraphs is NP-complete. Next, we derive a necessary condition for CARP that can be verified in polynomial time, and we present an example to show that our necessary and sufficient conditions do not coincide. We also propose and implement fast heuristics for testing the sufficient condition. These heuristics can be used to check reasonably large data sets for CARP, and can be of particular interest when used prior to computationally demanding approaches. Finally, based on computational results for both real-life and synthetic data, we conclude that our heuristics are effective in testing CARP.",
author = "{Talla Nobibon}, F. and L.J.H. Cherchye and {de Rock}, B. and J. Sabbe and F. Spieksma",
year = "2011",
language = "English",
volume = "38",
pages = "173--204",
journal = "Computational Economics",
issn = "0927-7099",
publisher = "Springer Netherlands",
number = "2",

}

Talla Nobibon, F, Cherchye, LJH, de Rock, B, Sabbe, J & Spieksma, F 2011, 'Heuristics for deciding collectively rational consumption behavior', Computational Economics, vol. 38, no. 2, pp. 173-204.

Heuristics for deciding collectively rational consumption behavior. / Talla Nobibon, F.; Cherchye, L.J.H.; de Rock, B.; Sabbe, J.; Spieksma, F.

In: Computational Economics, Vol. 38, No. 2, 2011, p. 173-204.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Heuristics for deciding collectively rational consumption behavior

AU - Talla Nobibon, F.

AU - Cherchye, L.J.H.

AU - de Rock, B.

AU - Sabbe, J.

AU - Spieksma, F.

PY - 2011

Y1 - 2011

N2 - We propose a directed graph for testing whether observed household consumption behavior satisfies the Collective Axiom of Revealed Preferences (CARP). More precisely, the data satisfy CARP if the graph allows a node-partitioning into two induced subgraphs that are acyclic. We prove that partitioning the obtained graph into two acyclic subgraphs is NP-complete. Next, we derive a necessary condition for CARP that can be verified in polynomial time, and we present an example to show that our necessary and sufficient conditions do not coincide. We also propose and implement fast heuristics for testing the sufficient condition. These heuristics can be used to check reasonably large data sets for CARP, and can be of particular interest when used prior to computationally demanding approaches. Finally, based on computational results for both real-life and synthetic data, we conclude that our heuristics are effective in testing CARP.

AB - We propose a directed graph for testing whether observed household consumption behavior satisfies the Collective Axiom of Revealed Preferences (CARP). More precisely, the data satisfy CARP if the graph allows a node-partitioning into two induced subgraphs that are acyclic. We prove that partitioning the obtained graph into two acyclic subgraphs is NP-complete. Next, we derive a necessary condition for CARP that can be verified in polynomial time, and we present an example to show that our necessary and sufficient conditions do not coincide. We also propose and implement fast heuristics for testing the sufficient condition. These heuristics can be used to check reasonably large data sets for CARP, and can be of particular interest when used prior to computationally demanding approaches. Finally, based on computational results for both real-life and synthetic data, we conclude that our heuristics are effective in testing CARP.

M3 - Article

VL - 38

SP - 173

EP - 204

JO - Computational Economics

JF - Computational Economics

SN - 0927-7099

IS - 2

ER -

Talla Nobibon F, Cherchye LJH, de Rock B, Sabbe J, Spieksma F. Heuristics for deciding collectively rational consumption behavior. Computational Economics. 2011;38(2):173-204.