最適に買い物するのはNP困難？ - Essay, dated.一部の計算機科学者に言わせると経済学の市場の理論は使えないということらしい。なぜかというと、そもそも消費者の効用最大化問題さえNP困難ということ。コンピュータにも大変な計算が何で人間に出来るだろうかというわけだ。 しかし経済学者からすると、そのような見方はモデルを文字通りに解釈しすぎているように感じる。計算機科学者がNP困難というとき、それはもちろん最悪のケース*1を考えているわけだが、実際に消費者が解いている問題は結構簡単な問題かもしれないではないか。 もっと経済学っぽく計算複雑性にアプローチすることはできないだろうか？一つのやり方はいわゆる顕示選好理論と計算の複雑性を組みあわせることだ。 経済学者はしばしば次のような問いの立てかたをする。 さまざまな価格が与えられたときにある消費者がどのように消費するかという有限のデータが与えられたとしよう。このデータが消費者の効用最大化問題の結果にな
