Note on Afriat™s Theorem, Ichiro Obara, September 29, 2009

1 Note on Afriat s Theorem, Ichiro Obara, September 29, 2009 This note is based on Fostel, Scarf, and Todd (2004).Consider a nite data setD= pt; xt 2RL++ RL+; t= 1; :::; T . Thisnote proves the following proposition, which is the step skipped in the 1 Suppose that a nite data setDsatis es GARP:Then thereexists t>0; Ut; t= 1; :::; Tsuch thatUj Ui+ ipi xj xi for alli; j2f1; :::; TgDenote byMTthe set ofT Tmatrices where all diagonal elements are0. We say thatA2 MTsatis es GA if the following condition is satis ed.(GA) For anyfat(n)t(n+1)gNn=1;ifat(n)t(n+1) 0forn= 1:::N 1;thenat(N)t(1) 0whereaN;N+1=aN;1:Note that theT Tmatrix whereijentry is givenbyaij=pi xj xi satis es GA ifDsatis es we show that GA is equivalent to the following condition.(GA*) For anyfat(n)t(n+1)gNn=1;ifat(n)t(n+1) 0forn= 1:::N;thenat(n)t(n+1)= 0forn= 1:::N.

2 :Lemma 2GA and GA* are that GA is satis ed. Ifat(n)t(n+1) 0for alln;thenanyat(n)t(n+1)can be regarded as the tail of a cycle (the one starting atat(n+1)t(n+2)) in GA. Soat(n)t(n+1) 0;henceat(n)t(n+1)= 0for , suppose that GA* is satis ed. Ifat(n)t(n+1) 0forn=1:::N 1;thenat(N)t(1)<0cannot be the case because then GA* impliesat(N)t(1)= 0, a contradiction. Henceat(N)t(1) 0:Now we prove the above of proof is based on induction. We show that we can nd such t>0; Ut; t= 1; :::; Tfor everyA2 MTthat satis es GA* if we can nd themfor everyA2MT 1that satis es GA*. Since this is trivially true forT= 1;this proves that the same property holds for everyT:We start with the following 3 Suppose thatA2 MTsatis es GA*:Then there existst suchthatat t 0fort= 1; :::; not. Then we can construct a cycle at(n)t(n+1); n= 1; :::; N such thatqt(n)t(n+1)<0for alln:This contradicts GA*.

3 Suppose thatA2 MTsatis esGAand, without loss of generality, as-sume thataT t 0for allt:Now de ne(T 1) (T 1) aijifaT j>0minfaij; aiTgifaT j= 0(Note that any diagonal element is zero(a0ii=aii= 0);soA02MT 1:Ifnot, thena0ii=aiT<0:ButaiT<0andaT i= 0violates GA*).Lemma 4 IfA2 MTsatis es GA*, thenA02MT 1satis es GA* not. Then we can nd a cyclena0t(n)t(n+1); n= 1; :::; Nosuch thata0t(n)t(n+1) 0for allnsuch that at least one inequality is everya0ijisaijin this cycle, then this contradicts the assumption thatAsatis es GA*:So suppose that there existsa0ijwithin this cycle such thata0ij=aiT 0andaT j= 0:Then we can replacea0ijwithaiTandaT jinthe original cycle. In this way, we can eliminate sucha0ijand guarantee thateach element of this cycle is fromA:Thus again we reach a satisfy GA*Now we can complete the proof. By the inductive assumption, thereexists t>0; Ut; t= 1; :::; T 1such thatUj Ui+ ia0ijfor alli; j2f1; :::; T 1g::By de nition ofa0ij;we haveUj Ui+ iaijfor alli; j2f1; :::; T 1g:2De neUTand T>0as ;:::;T 1g Ui+ iaiT T= max 1;maxj:aTj6=0 Uj UTaT J We are done if we can showUT Ui+ iaiTfor alli:Uj UT+ TaT jfor allj:The rst inequalities are satis ed by de nition.

4 As for the second inequality,it follows from the de nition for anyjwhenaT j>0:IfaT j= 0;thenUj Ui+ ia0ij=Ui+ iaiTfor anyi2f1; :::; T 1g:by de nition ofa0ij. Hence we getUj mini2f1;:::;T 1g Ui+ iaiT =UT=UT+ TaT j:This proves that we can nd such t>0; Ut; t= 1; :::; Tfor everyA2 MTthat satis es GA*. Since GA*is equivalent to GA by the lemmaand GA is satis ed whenDsatis es GARP, the proposition is proved. 3