For the course 'operations research' I have to solve a case about shopping behaviour rationality.

The case goes as follows:

"Suppose that you do your weekly shopping at the local Delhaize. So, every Saturday morning, you buy a set of goods, denoted by a bundle q. The prices of the available goods are represented by a vector p. Since you do your shopping on Saturday 1, Saturday 2, …, up to Saturday T, we can define a dataset S = { (pt, qt)| t=1, 2, …, T}. This dataset reflects your behavior.

The question of interest is whether your shopping reflects a utility function that is rational. To be able to answer such a question, we need to understand, and define what it means to be rational. In the economic scientific literature, rationality is defined using the following concept:

Bundle qt is directly revealed preferred over bundle qs when

8]pt x qt ≥ pt x qs.

Notice that the left-hand side of this inequality equals the amount you paid on Saturday t; apparently, this is not less than the price you would have paid when you would have acquired bundle qs on that Saturday. But since you bought qt , and not qs, we say that qt is directly revealed preferred over bundle qs.

Now, clearly, given a dataset S, we can find out for each pair of bundles whether one bundle is directly revealed preferred to the other one. Moreover, we can find out whether there exists a ‘cycle’ of revealed preferences: bundle qa is directly revealed preferred over bundle qb, which in turn is directly revealed preferred over bundle qc, which in turn is …. which in turn is directly revealed preferred over bundle qa. If such a cycle is present in dataset S, we say that S violates the Strong Axiom of Revealed Preference (SARP).

However, in practice a dataset often violates SARP. It is then interesting to compute how ‘close’ a dataset is to satisfying SARP. We measure this by minimizing the number of observations that have to be deleted from S such that the resulting dataset satisfies SARP.

This is our problem: given a dataset S, what is the minimum number of observations that have to be deleted such that S satisfies SARP."

I have to solve this with a program like Lindo or Cplex and we have to give a mathematical programmic formulation of the problem but I don't really know how to start.

I was thinking about a method that uses (directed) graphs?

Does somebody have an idea how to start?

Topic