最適に買い物するのはNP困難？
一部の計算機科学者に言わせると経済学の市場の理論は使えないということらしい。なぜかというと、そもそも消費者の効用最大化問題さえNP困難ということ。コンピュータにも大変な計算が何で人間に出来るだろうかというわけだ。
しかし経済学者からすると、そのような見方はモデルを文字通りに解釈しすぎているように感じる。計算機科学者がNP困難というとき、それはもちろん最悪のケース*1を考えているわけだが、実際に消費者が解いている問題は結構簡単な問題かもしれないではないか。
もっと経済学っぽく計算複雑性にアプローチすることはできないだろうか？一つのやり方はいわゆる顕示選好理論と計算の複雑性を組みあわせることだ。
経済学者はしばしば次のような問いの立てかたをする。
さまざまな価格が与えられたときにある消費者がどのように消費するかという有限のデータが与えられたとしよう。このデータが消費者の効用最大化問題の結果になっているとみなせるような効用関数は存在するだろうか？
この問いにはAfriatによるよく知られた答えがある。データがある条件（GARP)を満たすかどうかが、消費者の行動が効用最大化とみなせるかどうかの必要十分条件になっているのである。しかも、GARPが満たされているときはデータを合理化する＝最適化の解として説明する効用関数として非常に便利な選好（凸で単調）を見つけることが出来る。*2
さて、ここに計算の複雑性を追加的な条件として加えてみよう。すると問いはつぎのようになる。
さまざまな価格が与えられたときにある消費者がどのように消費するかという有限のデータが与えられたとしよう。このデータが消費者の効率的に計算可能な効用最大化問題の結果になっているとみなせるような効用関数は存在するだろうか？
つまりすべての可能な効用関数を考えるのではなく、データを説明するような効用関数のなかで計算量の観点から便利なものはあるかと聞くわけだ。するともちろん答えはAfriatの定理より、GARPが満たされる限り然りということになる。凸最適化問題の解は効率的に計算可能であるからだ。別の言い方をすれば、計算複雑性は顕示選好理論に関して制約として効いていないということになる。どのようなデータが与えられても、必ずそれが効用最大化と整合的でないかさもなくば効率的に計算可能な凸最適化問題（＝効用最大化問題）の解として解釈できるかのどちらかになるのである。
......というCalTechの計算機科学者と経済学者の共著の論文*3の発表を、エンジニアと計算機科学者と経済学者を集めた会議で聞いてきたんだけど、これはなかなか面白かった。次に熱いのはCS/Econの境界領域かもね。
