Prologによる２×３のケースの不可能性定理の自動証明： Gibbard-Satterthwaiteの定理とArrowの定理

2006.3.8

last revision:2007.11.22

犬童健良

関東学園大学経済学部

はじめに

ギッバード＝サタスウェイトの定理（Gibbard(1973), Satterthwaite(1975)）は、経済学・政策科学・倫理学などの分野における基本定理として知られています。 Kenneth J. Arrow やAmartya Sen によって開拓された社会的選択理論 (Arrow, 1963; Sen, 1982; Arrow et al., 2002)における不可能性定理のひとつです。
２人以上のメンバーからなる社会に、３つ以上の代替案があるとして、人々の選好モデルと社会的選択のルール（社会的選択関数；SCF）が所定の条件（定義域の非限定性と市民主権）を満たすとき、戦略的に操作不可能な社会的選択関数（SCF）は、必然的に独裁者を発生させるというのがその内容です。
社会的選択関数が、戦略的に操作不可能(strategy-proof) であるというのは、自分の本当の選好を偽ったところで、その人自身にとって何もいいことはないという条件です。
この定理は、Arrowの定理に知的刺激を受けた Vickrey(1960)が、戦略的操作の問題との関連を推測し、それをGibbardやSatterthwaiteが独立に探求して、その厳密な証明を与えたものです。
本論文では、Prologというプログラム言語を使って、上記の定理（およびArrowの定理）を自動証明します。Prologは人工知能システムの研究、とりわけ自然言語処理や自動定理証明の分野の成果の一つとして知られ、C言語やJava言語のような手続き型（というか普通の）プログラミング言語にはなかった、プログラム自体が論理式としての意味を持つ性質を持ちます。プログラム自体が「読める」という性質は、宣言型プログラミング言語ともいわれます。今日の多くのプログラミング言語で普通に使われる「関数」と似ていますが、一方、それとはちがって、Prologプログラムの実行そのものが、論理式で書かれた命題（ゴール）の自動証明になっているところが特色です。
今回作成したPrologプログラム(sproof.pl 付録1参照)は、石井・西条・塩沢(1995)による解説と証明を参考にしました。彼らの証明ではとくにマスキン単調性（ＭＭ条件）と呼ばれる条件を、上記の戦略的操作不可能性（ＳＰ条件）の代わりに用いているのですが、これは「あるプロフィールでＳＣＦによって選ばれる案は、プロフィールが変わっても、誰にとってもランクが落ちていないのであれば、再びそのＳＣＦで選出されていなければならない。」というものです。
ＳＰ条件がメンバーの誠実性を保証するのとは、一見、関連がありませんので、直観的にはそう見えないかもしれませんが、しかし、後で述べるように、ＭＭ条件はＳＰ条件（戦略的操作不可能性）と論理的に同じです。
また若干のコード変更により、Arrowの不可能性定理(Arrow, 1963)についても同様のプログラム化と実験結果を示すことができます。これは付録3としました。

社会的選択問題のモデル

ここでは社会的選択とか合理的選択の理論におけるモデルについて、基本的な概念を説明します。これらのことに詳しい人は次の節まで読み飛ばしてかまいません。
理論的なモデルでは、まず３つのことを定めておきます。社会全体で選ぶべき代替案の集合、社会のメンバー（エージェント）とその選好です。エージェントの選好は、代替案のペア比較（順序）によってあらわします。選好関係は代替案ペアについての２項関係ですが、以下の性質を満たす場合、選好順序と呼ばれます。
合理的選択の理論的フレームワークでは、選好関係について、完備性と推移性を仮定するのがならわしです。
完備性は、どの論理的に可能なペア比較についても、順序が定義されている（つまり比較可能である）ということです。つまり、任意のペアｘとｙを比較すると、「ｘがｙより望ましい」か、あるいは「ｙがｘより望ましい」という判断がかならずつくということ（完備性）を仮定します。またこれらが同時に成り立つときは、ｘとｙが無差別といい、また「ｘがｙより望ましい」かつ「ｙがｘより望ましいことはない」、つまり一方だけが成り立つ場合を厳密な選好関係といいます。
以下では簡単のため、これらを(X,Y)、(Y,X)、(X,Y)&(Y,X) のように表すことにします。つまり「XがYより好まれる」か、その逆であるか、あるいは無差別であるかのいずれかを示します。なお無差別は(X=Y)や(Y=X)と書いてもいいことにします。

(X,Y) or (Y,X) (is always true)    完備性(completeness)

なお、とくにｘ＝ｙの場合を、反射性(reflexiveness, reflexivity, ウリィークレクシヴァチ？) と呼ぶことがあります。またそれ以外の完備性のケースは、連結性(connectedness)と呼ばれます(Arrow, 1963)。

(X,X)                   反射性(reflexivity)
not (X=Y) -> (X,Y) or (Y,X)     連結性(connectedess)
(X,Y)&(Y,Z)==>(X,Z)     推移性(transitivity)
(X,Y)=>(Y,X)            対称性(symmetry)

推移性は、「もしＡよりＢがよく、ＢよりＣがよいならば、ＡよりＣがよい。」という条件です。ちょうど、論理学において三段論法と呼ばれるものを、ペア比較に適用した形になっています。
弱順序では、「より望ましい」という関係が、同等かそれ以上の意味として解釈されます。同時に「ｘがｙ以上」と「ｙがｘ以下」、すなわち無差別ということが、ありえる世界です。一方、線形順序は、無差別（タイ）を許さないモデリングで、これらはいずれか一方のみ成り立ちます。ところで、任意の案をそれ自分に対して比較したとき、強順序を仮定すると、「ＡはＡより好ましい」というのはおかしいですね。一方、「ＡはＡより好ましくないわけではない」というのは、正しいでしょう。弱順序の場合は、反射性により、つねにこの場合が成り立ちますが、強順序では「ＡはBより好ましい」かつ「BはＡより好ましい」といえるのはA=Bのときかつそのときだけという条件（反対称性）をつけてこれを制限します。
反対称性は「XとYが同じものの異名にすぎないのなら、 XがYより好ましいのは、YよりXが好ましくないときに限られる」というのと同じです。以下に論理的推論の例を示すことを兼ねて、これを証明します。

not(X==Y)==>
  (X,Y)==>not (Y,X)       反対称性(anti-symmetry)

<==>

 (X=Y) or (not(X,Y) or not(Y,X))
   because (p==>q) <==> (not p or q)

<==>

 (X=Y) or not((X,Y) & (Y,X)) 
  because not(p & q) <==> (not p or not q)

<==>

  ((X,Y) & (Y,X))==>(X=Y)

例えば2つの案xとyから一つを選ぶとき、メンバーが2人だけですと、それぞれが「xがyより好ましい」か、あるいは「yがxより好ましい」のいずれかの選好パタンをもつことが可能です。両者の選好順序を組みにしたものをそのプロフィール(プロファイル)といいます。
こうしたエージェントの選好順序で、どのような可能性も排除しないということは、非制限的領域の条件（あるいは普遍的領域の条件）と呼ばれます。
社会的選択関数（social choice function; ＳＣＦ）とは、任意の選好プロフィールに対して、ある代替案を選ぶものです。たとえば関数ｆの値が、 2人の社会で選好プロフィールがP＝((x,y),(x,y))のときｆ（P)＝x、それ以外の，P=((x,y),(y,x))、((y,x),(x,y))、または((y,x),(y,x))のときｆ（P)＝ｙとなるとすると、これは一つの社会的選択関数です。（より正確には代替案の任意の部分集合（アジェンダ）に対して一つの代替案を選ぶ．またより一般的にはプロフィールに対して代替案の部分集合を選ぶが，その場合を社会的選択対応（social choice correspondence；ＳＣＣ）と呼ぶこともある．）
政策意思決定の文脈でいうと、ＳＣＦとは、選挙の仕組み（投票手続き）を、より抽象的に表現したものといえます。ですから、その文脈では、メンバーのことを投票者（voter）と呼びます。経済学の文脈では、ＳＣＦは市場（マーケット）による資源配分の決定を表すことが多いようです。
なお、無差別の可能性を考慮に入れると、より一般的な選好順序になりますが、定理の結果には影響しません。しかし、考察すべきパタン数が多いからというより、プログラムがが煩雑になるので、以下のシステムでは線形順序を仮定してよりシンプルなモデリングを選んでいます。

PROLOGによる論理的モデリングと自動証明

PROLOGシステムは前節で述べたような選好順序や社会的選択関数（SCF)、社会的厚生関数（SWF）にかんする論理的条件を、シミュレーションするのに便利です。プログラミング言語ですが、論理的条件や集合論的操作をほぼそのままプログラムとして書き、それを証明（推論）しようとして機械的に試行錯誤するのですが、PROLOGに代表される論理プログラミング言語は「正しい定理は必ず有限時間で証明できる」という完全性（Completeness)と呼ばれる性質によって品質保証されています。例えば、「beeはbugであり、bugはtickleであれば、beeはtickleである．」からという三段論法の例を、 PROLOGで書いて、証明してみますと、以下のようになります。


% a PROLOG code of the `bug-->tickle' theorem.
bug( bee).
tickle(A) :-  bug (A).

% a demo of the program.
?- tickle( bee).

Yes
?-

つまり「蜂は虫である」と「虫はむずがゆいものだ」がともに正しいとき、「蜂はむずがゆい」という結論を導いたわけです。 "bug(tick)"は、１つの引数を持つ述語 (predicate)で「tickはbugである」という一つの事実を表し、"tickle(A) :- bug (A)"はルールあるいは、条件文 bug (A)==>tickle(A)を表します。事実とルールは、いずれも節と呼ばれるPROLOGプログラムの基本単位です。
"?- "はシステムの表示するプロンプトであり、ユーザーはコマンド代わりに、証明したい目標（ゴール節）をタイプします。（プログラム自体はファイルからロードするか、assert述語を使ってマニュアルで登録できます．）
ルールの中の首記号":－"は、それにより区切られた左側は頭(head) で、肯定の述語が一つだけ使え、右側の本体には、複数の条件をカンマで区切って、連言(and, conjunction)として書けます。プログラムの実行は、背理法と言われているよく知られた推論基本原理を機械化したものといって、おおむね間違いありません。すなわち、目標pを証明するため、プロンプトから?- p. と入力し、Enterキーを押すと、 p:-q というルールをPROLOGシステムが見つけて、それを示すにはqという十分条件を探せばよいと判断します。（条件文ないしIF THEN ELSE文に相当するものとしては、 X -> Yあるいは X-> Y; Zというのが立派にありますが、上の形式でも同じように書けるのであまり使わないのがよいでしょう。）事実qが見つかれば、Yesという値を返し成功、なければNo という値を返し失敗します。
ところで、読者は「蜂はむずがゆいかね？　さされていたいんじゃないの？」と反論したくなるかもしれない。 3段論法は形式的な推論ですが、論理的に正しい推論です。言い換えると、言葉の意味とは無関係に、機械的に（ブール代数の演算として）前提から結論を導くもののです。上のような疑問は正当なものですがその要求は、「論理式で表されたものが、私たちが表したいと思っているものと一致するかどうか」、すなわちモデリングの正しさの問題です。以下に、もう少し洗練した論理モデリングを示します。


% another PROLOG code

bug( tick).
bug( bee).
has_a_style(bee).

tickle(A) :-  bug(A), \+ has_a_style(A).
prickle(A) :-  bug(A), has_a_style(A).


% a demo of the program.

?- [bug06].
% bug06 compiled 0.00 sec, 344 bytes

Yes
?- tickle(A).

A = tick

Yes
?- prickle(A).

A = bee ;

No
?-

修正点を要約しますと、「針を持った虫」は、「むずがゆい」ではなく，「ちくちくする」というルールを設けることによって、論理モデルを変更しました。これでもまだ不満だという読者はご自身でプログラムを改良することをお奨めします。
なお"\+"は否定の演算子です。より厳密には「失敗による否定」であり、その述語の証明に失敗したとき、成功します。なお"A"は変数を表しますが、代入できるのは「項」(term)と呼ばれるもの、つまり定数、数値、文字列、リスト、関数、そしてPROLOG プログラムの単位である節を使えます。このようにPROLOGは、自分自身でプログラムを作り直すことができるので、柔軟で強力な記述力を持つ言語です。
PROLOGのこの証明能力を使うと、恣意的に失敗させて、所定の条件を満たすすべてのパタン（実行可能解）を枚挙させることができます。これもPROLOGの強力な機能です。ただし、解がかなり多数ある場合や、無限にあるときはなかなか終了しないか、あるいはただちに暴走することもあるので、注意が必要です。カット"!" は、それが出現する以前の部分がいったん成功すると、失敗してもそこで試行錯誤（バックトラック）をせき止めることができます。熟達した PROLOGプログラマは、これをたくみに用いて計算を効率化しています。しかし乱用すると、論理的な意味を損ねることにもなります。



?- bug(A),nl,write(A),fail.

tick
bee

No
?-

最後に、選好の推移性を確かめるプログラムを、 PROLOGで書いてみます。


% the PROLOG code for the transitivity of preference relations


a(x).
a(y).
a(z).

r( x, y).
r( y, z).
r( x, z).

p(X,Y):- r(X,Y), \+ r(Y,X).

is_transitively_deducible(X,Y,Z):-
   r(X,Y),
   r(Y,Z).

is_not_transitive(X,Y,Z):-
   is_transitively_deducible(X,Y,Z),
   \+ r(X,Z).

is_transitive:-
   \+ (
     a(X), a(Y), a(Z),
     is_not_transitive(X,Y,Z)
   ).



% the demo


?- is_transitive.

Yes
?-

ところでコンピュータを使って経済学の理論をシミュレーションしたりするというのは、計算経済学(computational economics)と呼ばれる分野である。PROLOGがこの分野で活躍することはこれまであまりなかったようだ。社会的選択と情報科学の問題で境界的な研究自体は、マルチエージェントシステムなどで、近年盛んになっているが、計算複雑性とアルゴリズムの効率化の話や、進化的あるいは創発的なシミュレーションなどが中心で、こうした基礎的理論のもつ論理モデリングを手軽に再現・検証できるシステムの実例、しかも知識処理の代表的手法を用いた研究は、寡聞にしてしりません。
武隈(2000)は本論文（付録）と同じ２人3代替案のケース（ただし弱順序の場合）でアローの定理をMathemeticaと呼ばれるプログラミング言語を用いて証明している。Mathematicaは数学的なモデル分析とその視覚化のための有名なパッケージソフトウェア製品で、理工学の研究・教育用として使われている。氏曰く「経済学では，その学問の性質から，数値では表現されない抽象概念がしばしば用いられる。したがって，経済学における新しい利用の仕方として，コンピュータは抽象概念の思考において有効に利用されることになると思われる。」しかし、もしそうであるとしたら、おそらく、PROLOGはその役に立つはずである。
ところで他の言語でも、同じことができるだろうと考えている読者も少なくないかもしれませんね。原理的にはもちろん、不可能だとはいえません。実際、多くのPROLOG処理系が C言語など他の言語上の抽象マシンとして実装されていますから。アローの定理（あるいはＧＳの定理）の証明は一つのパレート条件を満たすSWFを作り始めて、結局、IIA（ＧＳ定理のなら操作不可能性）も満たすように拡張するには、独裁にしかなりませんねというのを繰り返すわけです．が、「もうこれ以上はつくれません」というところまで、いかないと、また、論理的にこれ以上は不可能であることを保証できなければ、厳密な証明にはならないのです。導出原理に基づきバックトラックを自動制御してくれるので、PROLOGではそれができますが、普通のプログラミング言語でそういうルーチンを作るのはおそらくきわめてめんどうでしょう。

システムsproof.plについて

システムsproof.plは、Prolog言語で作られたプログラムであり、（ソースコードは付録1） Gibbard-Satterthwaite定理の２×３のケースの自動証明を次の方法で行う。すなわち、線形順序（強順序のみ。無差別の場合を除く）を仮定し、任意の（ＰＥ条件（パレート効率性）[*0]をみたす、あるいはみたさないにかかわらず）選好プロフィールからスタートし、順次的にＭＭ条件（マスキン単調性）[*1]およびＣＳ条件（市民主権）[ *2] を用いて、決定力（後で詳しく述べる）を伝播することによって、独裁者を帰結する。
これらの条件については、以下のノートもご覧下さい。
有限の順序構造を生成してその論理的な制約条件を満たすものを精査するというたぐいの作業は、Prolog（論理プログラミング言語）のもっとも得意とするジャンルである。線形順序はリストと呼ばれる付属のデータ構造によって、直接的にモデル化できる。
また帰納的（再帰的）に制約条件を満たす社会的選択関数を自動生成するということも、Prologの再帰的プログラミングにたいへんよくなじむ。実際、本システムでは、基本的に上記の文献に述べられた方略を用い、きわめて自然にこの不可能性定理の証明を自動化することができた（ただし弱順序の場合、SPかつCSかつ独裁性を満たすSWFが多数存在するため、図のように単純な枚挙によって証明できません。[<==大変申し訳ありませんが，この記述は誤りです．ちゃんと証明できます．新しいプログラム( cswf07.pl) を使って検証できますので，もし興味が残っていれば試してみてください．] しかし準推移的順序の場合は、増えるパタンは一つだけのようです）。
より詳しく言うと、本システムでは、まずＰｒｏｌｏｇ言語によって２ｘ３のケースについての社会的選択理論の描く世界（選好順序は弱順序または強順序、非制限的で、市民主権をみたす）をモデリングし、つぎに上記の証明方法を再帰的なPrologコードとして、実現した。
図1と図2にソースコードsproof.plからの抜粋とＳＣＦの自動生成実験の結果の一部を示した。
これにより、ＳＰ条件をみたすＳＣＦの自動デザインを行い、独裁的であること [ *3] を示すことができる。ただし単調性と戦略的操作不可能性の同値性（Muller and Satterthwaite, 1977)については、証明されたものとして用いている。

ＳＰ条件はＭＭ条件と同値であることを前提とすれば、「ＭＭ条件とＣＳ条件をともに満たす」というのが、伝播すべき局所的な制約条件になる。そして、一つの選好順序プロフィールからはじめて、帰納的（再帰的）に、両制約を満たす可能な社会的選択関数だけを生成する(図1のコード参照）。このコードをPrologシステムによって実行することにより、最終的に、独裁的なＳＣＦのみを得るという、同定理の帰結を確認することができる(図2参照）。
またそれゆえ、本システムの特色として、所定の条件を満足するＳＣＦの生成方法が、以前、筆者がナッシュ遂行のPrologによるモデリング（impl13.pl）で試みたような、素朴な生成テスト方式ではない点に着目してもらいたい。[*4]
なおArrowの本を含めて多くの文献が２ｘ３のケースでの証明を例示しているが、これは最も簡単な一つのケースだからというだけでなく、不可能性定理の論理構造自体が、基本的にこのケースに帰着されるためである。任意の代替案ペアの間での決定力伝播が、不完全性定理の核であるが、それは非制限的領域だけではなく、許容的領域においても、任意の3代替案において非自明なペア（対立する意見がふくまれる）の集合において、決定力含意の分解不可能性を考えれば必要十分条件を得る (Kalai and Muller, 1977)。



auto_scf( Domain, FL,Property):-
   all_possible_preference_pair_n_domain( Domain, L),
   auto_scf( Domain, FL, L, Property).

auto_scf( _, [],[], _).
auto_scf( Domain, [R-> X | H], [R|Q], pareto):-
   auto_scf( Domain, H,Q,pareto),
   is_pareto_efficient( Domain, R,X).

auto_scf( Domain, [R-> X | H], [R|Q], monotone):-
   auto_scf( Domain, H,Q,monotone),
   alternative(X),
   \+ (
     member( (S->Y), H),
     monotonic_change( Domain, S->R, Y),
     X \= Y
   ),
   \+ (
     monotonic_change( Domain, R->S, X),
     member( (S->Y), H),
     X \= Y
   ).

図１．ＭＭ条件とＣＳ条件をともに満たすＳＣＦを自動生成するためのPrologコード



?- generate_cs_scf(A,monotone,C),
display_scf(A,C).

domain:urd(2, 3) scf:auto(sp)
row=r(1) [a, a, b, b, c, c]
row=r(2) [a, a, b, b, c, c]
row=r(3) [a, a, b, b, c, c]
row=r(4) [a, a, b, b, c, c]
row=r(5) [a, a, b, b, c, c]
row=r(6) [a, a, b, b, c, c]

A = urd(2, 3)
C = auto(sp) ;

domain:urd(2, 3) scf:auto(sp)
row=r(1) [a, a, a, a, a, a]
row=r(2) [a, a, a, a, a, a]
row=r(3) [b, b, b, b, b, b]
row=r(4) [b, b, b, b, b, b]
row=r(5) [c, c, c, c, c, c]
row=r(6) [c, c, c, c, c, c]

A = urd(2, 3)
C = auto(sp);

No
?-

図２．ＳＣＦ自動生成実験による２ｘ３の場合の不可能性定理の証明

社会的選択理論における不可能性定理とその証明方法について

ちなみに、同値のアローの定理(Arrow's general (im)possibility theorem) では、SCFではなく、集団で選好順序（社会的厚生関数；SWF）を作成するが、同じようにその証明では、任意のパレート効率から始めて、ＩＩＡ条件（無関係な代替案からの独立性）を用いて決定力を伝播し、独裁者の存在を帰結する。

一般可能性定理[*5]　 (Arrow(1963) Theorem 2, p.97)
もし領域が非制限的であるなら、 IIA条件とパレート条件をともにみたす社会的厚生関数で、かつ独裁的でないものは存在しない。

ちなみに、一般不可能性定理と呼ばれることが多いが、 Arrowは一般可能性定理と書いている。ところで Arrowの定理やGibbard-Satterthwaiteの定理の証明を簡潔化・透明化しようという研究は、いまだに続けられている（近年公刊されたものとして、Reny(2001)やGeanakoplos(2005)がある）。付録2におおよその証明を紹介した。
異なるプロフィール間での制約伝播は、Gibbard－Satterthwaite の定理の証明でＭＭ条件が果たしていたが、同じことがこの場合にも言える。決定力の伝播についての補題は帰結2として示されている(op sit, p.53)。 Arrowは最初、パレート条件（条件P）(op sit, pp.96)ではなく、社会と個人の価値の正結合条件（条件2）、つまり単調性と、市民主権を、IIA条件とともに用いていたのだが、これら３つからパレート条件が導かれ(op sit, pp.97)、またそれによって証明が簡略化されている。こうして件の定理、「非制限領域で２条件PとIIAのみから、独裁的SWFのみ導かれる」が得られる。
つまり、あるプロファイルであるペアの代替案についてある個人ないしグループが決定力を持つとすると、それはすべてのプロファイルとすべてのペアにまで感染拡大してしまう。また、それゆえに、この定理が意味する論理的モデルは表層的には計算不可能であるが、実質的にはほとんど計算しなくていいのである。これは実際に上記の方法でプログラムを作ればわかる。 [*7]
いずれにせよ、コード化は（GS定理の場合より）やや煩雑になるだろう。でもそうむずかしくはないはずだろうから、読者の練習問題とする（付録3に解答例を示す）。
なお社会的選択分野の入門的読み物として、佐伯(1980)『決め方の論理』がある。とくにAmartya Sen によって証明された「自由主義の背理」[*6]をめぐっての解説であるIV章やII章のArrowの定理の初等的な証明が興味深い。また柴田(1992)やBinmore(1976)はグラフィカルなArrowの定理の証明の方法を提案している。
なお社会的決定関数SDFの場合、つまり社会的に最適なものを選べさえすれば、推移性が成り立たなくてもよいという条件に SWFの定義を緩めるとすると、 Arrowの不可能性は覆えせる（実験例は付録4で示した）。この背理はその場合にも成り立つ。すなわち、IIA条件ばかりか、社会の選好の推移性すら要求していない。証明は、2人の弱順序ペアと、条件Pにしたがって導かれる社会の順序が、ラテン方格を構成することを示すもので、Arrowの定理におけるフィールド拡張補題の証明で用いられている論法と類似する。

不可能性の回避と関連研究

アローの定理は、厳密な定式化を示すとほとんどの人がむずかしく感じるでしょうから、しかたないのですが、入門的文献の記述だけから、「どんなことがあっても、順序に基づく選好モデルでは民主義的な選択が不可能なのだ」という誤った印象を与えているかもしれません。
不可能性定理は、ここかそこかを緩めない限りはいくらがんばっても無駄ということですから、いいかえれば、アローが与えた諸条件の、どこを緩めれば非独裁的な社会的厚生関数（ＳＷＦ）が得られる可能性が出てくるか、すなわち客観的にやりがいのある努力目標をある程度きちんと示すものといえます。
他の分野の不可能性定理、たとえば計算複雑性の問題がそうですが、所与の目標を達成するために、原理的に不可能だったり、必要な資源が不足していたら、いくら努力してもどうしようもないので、逆に、資源をもっと割り当てるための努力、制約を緩和するための交渉をしないといけない、ということになるのでしょう。
実際には、アローの条件を緩和することにより、可能性の結果が得られます。例えば、後の研究者の努力で、条件Ｐを緩めてもたいした変わりはないということも分かっています。これはＷｉｌｓｏｎが示した定理(wilson, 1972)ですが、ここで示したコードを用いて実験できます。英文論文にまとめてあります。またコードはここで示したものを少しコンパクトにしてあります（Ａｒｒｏｗの定理とＷｉｌｓｏｎの定理の実験）。
選好の非限定性を緩める場合も、決定力の伝播をどこかで遮断することによって、はじめて、可能性が得られます。決定力含意に基づく分解という方法が、ＫａｌａｉとＭｕｌｌｅｒによって、明確にされています(Kalai and Muller, 1977)。この方法は、本稿の方法と違い、ＳＷＦを枚挙しませんので、弱順序の場合の不可能性の証明に使えます。筆者自身も、これに基づくＰｒｏｌｏｇによる実験を、別のところで行っていますので、よかったらご覧下さい ( 領域制限の実験研究の紹介）。
上記のＫａｌａｉとＭｕｌｌｅｒの方法では、個人の選好領域を線形順序（ないし弱順序）の一部に一律に制限するのですが、それによって非独裁的であるＳＷＦが作れる選好領域では、同時に戦略的に操作不可能なＳＣＦが得られれることが証明されています。さらに、ＳＣＦは代替案全体だけでなく、その任意の部分集合（アジェンダ) についても、操作不可能であることが保証されます。
なお、同一の許容的領域に個人の選好を一律に制限するこの方法ことによって作成可能な非独裁的ＳＷＦは、結局、単調性を満たすものに限られることが知られています(Blair and Muller, 1983)。そこを回避するには少なくとも、3人以上のモデルで個人ごとに許される選好の集合を変えてやらないといけませんが、その場合の必要十分条件は、BlairとMullerによって本質的分解可能性として明らかにされています（ＳＷＦやＳＣＦの本質性はその用語を用いていないけれどpivotal voterの存在、また本質的分解可能性はある代替案ペアについての反対方向の決定力に勝利提携を分割できることといった感じで、これも事実上simple gameが用いられています。が中村の定理は使っていないし、その直観的意味を知りたい、というのが当面の目標です.12/31，そのコードを追加しました． here）。
また単純多数決原理の場合は、Ｓｅｎや稲田によって、その条件が見いだされました。かれらの条件についても、筆者はＰｒｏｌｏｇでコード化し、いくつかの実験を行っています ( 多数決の実験研究の紹介）。
なお、これらＡｒｒｏｗ、Ｓｅｎ、稲田、村上らの開拓した初期の選好集計理論は、後の人々にとって、人類、とくに経済学に携わる者たちの打ち立てた金字塔として尊敬される一方、ある意味、抽象的なお話しとしてうけながされていったのは、おそらく現実なわけですが、例えば（ＭｏｕｌｉｎやＰｅｌｅｇのような）公理的アプローチを引き継ぐ研究たちによって、現代まで着実に、より具体的な社会的意思決定の手続きとして精密化されていきました。単峰性領域は、上記の多数決について、あるいはアローのＳＷＦについて、可能性が得られる領域として早くから知られていますが、一定の利益を分配する問題に広くあてはまり、具体的な社会的意思決定の手続きを議論することができるため、理論だけでなく、計算的手法（アルゴリズム）の研究が進んでいる領域でもあります。

この節のまとめ

不可能性を回避するには、以下のようなオプションが考えられます。

定義域を制限あるいは緩和する
値域を制限あるいは緩和する
条件ＩＩＡを緩和する
条件Ｐを緩和する

ＳＷＦやＳＣＦが定義されている領域は、あらゆる個人の選好順序のプロフィールからなりますが、この定義域を制限すること (domain restriction)はもっともよく研究されている可能性の達成方法といえます(Gaertner, 2001)。上で述べたように、決定性含意の下での分解可能性や、多数決原理が矛盾しないための価値制限がその代表的なものです。また定義域を緩和するというのは、個人の選好順序を線形順序や弱順序だけでなく、より緩やかな条件の２項関係に置き換えるものです。その場合、とうぜん、値域の方も変えることになるでしょう。
値域を制限するというのは、市民主権の条件に違反することですが、例えば２者択一のケースなら、アローの定理から逃れることができます。また値域を緩和する方法には、さらに２つの異なるアプローチがあります。一つは、定義域の場合と同じく、オリジナルの不可能性定理では線形順序か弱順序だったものを、準順序や非循環関係に緩和する方法です。
付録4にＳＷＦの値域を準推移的順序に拡張した場合の実験を示します。実際、独裁的でなく、いずれのエージェントもどの代替案ペアについても決定力を持たないＳＷＦが得られています。
もう一つのアプローチは、一つ目とも関連するのですが、値域を多値化することです。とくにＳＣＦの場合は一つのプロフィールに対して、一つの代替案を選ぶので、不独裁的であれば、操作可能になるのですが、多値化して、適切に操作不可能性概念を修正すれば、非独裁的かつ操作不可能な社会的選択ルールが得られます。もっともこれは間接的に、社会的順序を、準順序か非循環関係に緩めておいて、その極大元集合を選ぶことと、ほとんど同じように思えます。このあたりは、協力ゲームのコアの分析で使われた支配関係（ブロック関係）を使ってよく調べてみないといけないわけですが、その副産物で、現実の社会的決定でよく用いられる「消去法による選出」の手続きが、文句の出ない選択結果になる条件が論じられています (Moulin, 1988; Danilov and Sotskov, 2002)。

付録1．システムsproof.plのソースコード

sproof.pl（言語 Prolog；日付 13 Jan 2006 ) ソースコード●

以下のArrowの独裁定理やSenの寡頭制定理を含め，すべての実験を統一コードの下で実験できるようにしました（言語 Prolog；日付 22 Dec 2006 ) ●

付録2．Arrowの定理の証明

証明は２つのステップで行われる。まず任意の代替案ペアにかんして決定力のあるグループを作ると、それが全ペアまで拡張してしまうことを示す。次に任意の決定力をもつグループを分割し、結局、シングルトン（＝独裁者）まで分解できることを示す。その出発点として、パレート条件により全員が決定力をもつのでこれを分解していけば、単独の独裁者を見出せる (Arrow(1963), pp.51-9, pp.97-100; Sen(1995), p.4; Vickrey(1960, pp. 509-11))。
Arrowによる証明の短い方は、正結合と市民主権の代わりに、パレート原理とIIAを用いてより簡潔にされている。第2版で追加した章に、 Blauの指摘した誤りとその対処、およびMayやMurakamiによる多数決原理との関係の明確化を含めて掲載されているが、基本的には1952年の論文に掲載された証明である。そもそもArrowの定理の狙うところは、パレート原理盲信と新厚生経済学への警鐘であったから、初版ではあえて分かりにくくしたということは考えられなくもない。
証明のアイディアとしてはArrowのオリジナルやVickreyの解説と大きく変わるものではないが、以下で紹介するA.セン(Sen, 1995)の証明に見られるように、まず局所的な決定力が伝播して全代替案ペアにまで浸潤することを示し（フィールド拡張補題）、次に、決定力をサブグループに分解し（グループ縮約補題）、最終的に特定の個人に帰着させる。 Senのレビュー論文(Sen,1995) において、これらの２つの証明ステップは、それぞれ脚注９と脚注１０にあたる。厳密には3ステップあるが、最後の２つは合わせて後半部分をなすと考えればよい。以下にSenの証明を紹介しておく。
まず決定力の定義について述べておこう。

「あるグループGがペア(x,y)について決定力を持つというのは、彼らの全員がｘをｙより好む(　<-->　r(G,x,y)　)ならば、 G以外のメンバーの選好順序がどうであろうとも、社会的選好順序においてもそうである(　<-->　r(x,y)=r(N,x,y)　) ときである。また、あるグループGが決定力を持つというのは、Gが任意のペアについて決定力を持つときのことである。」

決定力（decisiveness；あるいは、指令性)の定義は、じつは2種類あって、ここではそのグループ以外のメンバーの選好順序は任意という方を使っている。選好順序が反対という決定力’のもう一つの定義も証明の中で現れる。これらは２種類のdecisivenessの定義はIIA条件および正結合条件の下で同値である(Arrow, p.53, Consequence 2)。しかしここでは正結合条件の代わりに、パレート原理を用いる。また、パレート原理それ自体が強い正結合とIIAと市民主権の３条件からの帰結である。
ある一人のメンバーが自分だけで決定力を持つことを、「独裁」という。社会のメンバー全員が、一つのグループNとして、決定力を持つ（持たねばならぬ）ということは、「パレート原理」と呼ばれる。このように独裁者を、決定力のあるグループという概念に緩和すると、見通しがよくなる。 Arrowは非制限領域の社会的選好順序（＝社会厚生関数）で、独裁者が不在で、パレート原理とIIA条件を同時にみたすものはないということを証明した。

ステップ2:グループ縮約補題

(*)ステップ2（グループ縮約補題）はだいたい以下のように証明される。
「任意のグループGが決定力を持つとき、２つのサブグループG1とG2に分割できて、いずれかが決定力を維持する。仮にG1のメンバーすべての選好が、
r(G1,x,y)、r(G1,x,z)、
つまり、G1のメンバーは一致してｘがベストだと考え、また
r(G2,x,y)、r(G2,z,y)、
すなわちG2のメンバーすべてが、ｙを最悪と考えていたとする。ただし上以外のペアについてのGのメンバーの選好や、 G以外のメンバーの選好はどうであってもかまわない。このときG1またはG2が決定力を有することを示すことができる。
ここで、もし社会的選好順序がr(x,z)であったなら、明確にこの順序で好むのは G1のメンバー以外にいないのだから、G1のメンバーは(x,y)について決定力を持つことになる。またこれにとどまらず、（すべてのペア比較について）G1は決定力を持つ。それ以外の場合、つまりG1が決定力を持たないときは、 G1の外に少なくとも一人のメンバーiがいて、r(i, z, x)かつ r(z,x)である。一方、Gは決定力もつと仮定したから、r(x,y)となる。よって推移率により、r(z,y)を得る。すなわち、サブグループG2が (z,y)について決定力を持つ。前半ステップが証明されていることを前提とすれば、G2は決定力を持つ。証明終わり。」

ちなみにSenのこの証明方法は、鈴村・後藤(2002、pp.46-49）でも紹介されているが、そのステップ2の証明に文表現上のちがいがある。上記の太字部分はそれを強調しているが、上で述べた 2種類の決定力の同等性を考えればよい。

ステップ1:フィールド拡張補題

自己完結のため、ステップ1（フィールド拡張補題）の証明も紹介する。

「あるグループGがペア(x,y)について決定力を持つとき、Gは決定力を持つことを証明する。x,y,a,bを相異なる４つの社会状態とする。（そうでない場合の証明も同様。） (x,y)についてGが決定力を持つと仮定して、(a,b)についても決定力を持つことを示す。非制限領域ゆえ、
グループG内の全員がr(G,a,x),r(G,x,y),r(G,y,b)、かつ
グループG以外のメンバーはすべて r(-G,a,x),r(-G,y,b)かつ
それ以外のペアについては任意の選好順序である。
このとき、社会の選好順序は、Gの決定力の仮定によりr(x,y)、またパレート原理に従いr(a,x),r(y,b)となる。よって推移率から、r(a,y)、再び推移率からr(a,b)となる。IIAにより、ペア（a,b）についての社会的選好順序が他のペア比較についてのだれかの選好順序に依存して変わることはない。それゆえそれ以外のメンバーの選好順序によらず、 Gのメンバーだけはつねにr(G,a,b)であるから、 Gは(a,b)について決定力を持つことが示された。証明終わり。」

定理の証明を完成させるためには、パレート原理により全員から初めて、あとは縮約補題を使ってグループサイズがシングルトンになるまで細かく割ればよい（スッテプ3）。
上の証明は簡潔だが、私たちの理解しようとする目的からすると、その意味はかならずしも明確でないように思われる。私たちが欲している証明は、ある選好順序のプロフィール（および任意のペア）で決定力（あるいはピボタリティ。ノート[*6]を参照）を持つことが判明したメンバー（あるいはグループ）は、ほかのどのプロフィールでもやはりそうならねばならないということだ。それが上記補題中に暗に含まれており、それゆえ証明を理解するためには、さまざまな選好順序プロフィールの可能性を、頭の中でフラッシュしなければならない。
Arrowのオリジナルの証明やVickreyの言語化と比較しながら落ち着いて検討してみることになった。 Arrowの決定力伝播は表にするとよく分かる。また VickreyによるArrowの証明の紹介は、Senの細かい表現上の曖昧さやArrowの証明のガチガチ感を解消してくれる。
すなわち、この部分では、まず決定力の仮定とパレート条件、およびSWFの推移性を用いて、ある投票背理の起こらないランキングペアで、２つの代替案ペア間で決定力の伝播を示し、次に別のランキングペアとの間で、IIAに基づいて、決定力を伝播させる。これを繰り返すことで連鎖的に、対角代替案ペア以外のすべてにまで伝播させることができるというしくみだ。
なおオリジナルの証明では後半部分で、いわゆる投票の背理を起す選好組（ラテン方格）が明示的に用いられる。

latin square	pattern 1	pattern 2
1st ranking	1.(x,y,z)	2.(x,z,y)
2nd ranking	4.(y,z,x)	3.(y,x,z)
3rd ranking	5.(z,x,y)	6.(z,y,x)

上で示した2つのラテン方格、｛１，４，５｝と｛２，３，６｝はそれぞれ、各ペアの個人が１つづつ合意できる代替案ペアを持ち、それ以外の２ペアでは対立する意見を持つ。とくにある１つの案については互いの最悪と最善の両極に位置する。このラテン方格は投票背理において鍵となる選好パタンである。実際、3人がパタン１＝｛１，４，５｝内でそれぞれ別の強順序をとるとすると、(x,y)の順で好むのが2人、(y,z)の順で好むのが2人、 (z,x)の順で好むのが2人であり、単純多数決で得られる社会的順序は循環する。
Senの証明では、やはり後半部分で、決定力のあるグループ内で一方のサブグループに決定力を渡さないとすれば、他方のグループに渡すことになるということを示すために、非明示的にそれが現れる。またこの論法は自由主義背理の証明（付録5参照）と基本的に同じであるが、その場合は特定のプロフィールで値付けが不可能であるであることだけ示せばよいから、IIAを使わなくてすむ。

付録3．システムswf.plについて

ソースコードと実験結果

swf.pl（言語 Prolog；日付 7 Feb 2006 ) ソースコード● は、Arrowの定理の２×３のケースの自動証明を次の方法で行う。すなわち、文献における証明と同様、パレート原理をみたすひとつの選好プロフィールに対する社会的選好順序からスタートし、順次的にＩＩＡ条件（無関係な代替案からの独立性）かつパレート最適性条件をみたすように、任意の社会的厚生関数を再帰的に構成し、これによって独裁者を帰結することを示す。
一部コードを加えたswf_b.pl（ソースコード●）を用いて、生成経過を調べてみた（auto_swf(_,_,iia(4))）。ワークシートswf_b.xls（ =>swf_a.zip 416KB）は、記録された中間ゴールをテキストファイル出力し、エクセルで集計したものである。また独裁的SWFが見つかるまでの試行錯誤（バックトラック）のようすが視覚的にわかるよう工夫してある。

実験結果

シートswf_a（とfigure 1）には２つの独裁的SWFを含む、すべての探索のようすが集計されている。最初の独裁的SWFを求めるまでには、計111パタンの値割り当てを試みている。 2つ目の独裁的SWFは第208番目に見つかっており、それは 19個目のSWFの候補であった。その後26個目のSWFまで作りかけて、第339番目のr(3),r(4)->r(4)を破棄したところで、探索を終え、証明を終了している。
さらにauto_swfの再帰的コードにおいて、パレート条件の部分をグループ選択集合に基づくオリジナルの定義から、文献でよく見られるunanimityに変えることにより、探索効率はさらによくなる(シートswf_bおよびfigure 2)

実験結果のデータと集計方法

まずswf.plからいったんcsv形式で出力したデータを、第B列から第E列までの4列に写してある。それ以外の部分は、計算・集計・グラフ化のために追加した。データの値はプロフィールおよびSWF値に使った順序のモデル内番号である。たとえば、プロフィール(r(6),r(6))に対してSWF値r(1)が割り当てられたとすると、該当する行のC～E列は、それぞれ6,6,1となる。第B列は再帰の深さ、すなわちそれ以前に暫定的に値割当済みのプロフィール数である。
各プロフィールに割り当てた値（社会的順序）が、一つの完成したSWFの要素になっている場合、第F列の値が1、それ以外は値0である。第G列はそのプロフィールが何回目の割当ての試みであるかを表す。これらの各プロフィールに対する値の割り当てのようすは、シートの第J列から第AS列に加工され、さらに条件付書式によって色分けされる。セルの値はSWF値に使った順序番号である。ただし決定済みのところは、番号に100を加えた。
なお、データ終了行以降では、各プロフィールの探索データを集計し、その効率を図表にまとめた。これを見れば、ほとんどの値は試していないことが、より明確になるだろう。

バックトラックのようすを解析する

PrologシステムによるSWF値の割り当てと、バックトラック(やり直し）のおおまかなようすは、本シートによって視覚的に理解できる。ラベル行（第5行目）、右端の6-6というプロフィール (r(6),r(6))をあらわす）から左側のプロフィールに向かって再帰による社会的順序の割り当てが試みられていることに注意されたい。
この範囲のセル背景色は、それが成功した場合がピンクで示され、試行錯誤中の（そして結局失敗する）ところは、黄色で示される。 figure 1と2は、それらの縮小表示である。
実験結果からわかることを手短に述べよう。くりかえすが、このプログラムは36プロフィールのそれぞれに対して、極大性（パレート最適性）とIIAをともに局所的な制約として満たす社会的順序、すなわちSWFの一つの値の候補を見つけようとする。
集計データをより詳しく見ると、プロフィールの中で値が最初に決定されたr(6),r(6)->r(6)はその第72番目であり、しかし2回しか値を変えていない。それ以降のやりなおしは4回だけであり、最後のそれは第87番目である。
なおr(6),r(6)->r(6)はそのプロフィールでパレート最適性を満たす（可能なSWFの局所的な）パタン120個の最後に生成されるものだ。
最大のバックトラック回数は、r(5),r(5)->r(?)の11回、全体の第82番目でこのプロフィールに対するSWFの値r(5)が確定した。これは prologシステム内臓のバックトラック（試行錯誤、やりなおし）により、途中まで作りかけて破棄したSWFの作りかけが、それまでに10個あったことを意味する。

今後の課題(2006.2.27)

付録2の証明に沿って一般的なケースでのモデリングをするには、代替案と人に関して、再帰するように、プログラムを書き換えればよいと思う。 IIA条件（二項性）ゆえ、リストによる選好順序のモデリングを捨てられる。しかし今回に至るまでに、forallやfindallで「えい」とやらないよう習慣づけしてきたのに、リバウンドしそうなどと逡巡しています。これからやってみます。

付録3への追記(2006.3.6-7)

二項関係でモデリングしなおした出力結果の一部を紹介します。＝＞swf_d.txt● swf_d.txtは、パレート条件で決定できる組を埋めた後、１つのプロフィール(2,1)で１つのペア(b,c)についてだけ決定権を与えられた2が、IIA条件と推移性の下で他のすべてのプロフィールへの感染源となり、独裁者になりあがっていくようすを示したものです（ソースコード (sef_d.pl, prolog 2006.3.6)）。ピボタリティの検査もできます（実験結果のワークシート(swf_c_pivotal.xls, 2006.3.4)）。また、参考までにIIA条件の下で同値となるプロフィールを図案化して示します。コードはそのままswf.plに追加して使えます。＝＞●

付録4．値域を準推移的順序に一般化した場合のSWFについて

ここではＳＷＦの値域を、強順序から、弱順序、そして無矛盾的順序（非循環的2項関係）に緩めることによる不可能性からの脱出経路を紹介しましょう。じつはこれらの間に、もう一段階、準推移的順序というのがあります。アローの定理は、もともと弱順序で証明されていますが、準順序までいけば、不可能性が覆ることが知られています。Ｓｅｎの本にもそうのように紹介されており、 1970年代にゲーム理論を使ってアローの定理を再構成する研究がはやったときにも、いろいろな研究者が、いろいろな方法でそれを証明しています。そして、強プロパー単純ゲームがＡｒｒｏｗのＳＷＦの要請と同値であることが解明されるています。[*8] またArrowのSWFは推移性を要請しますが、準推移性や非循環性に弱めた場合が、今日、中村数と呼ばれている、単純ゲーム（あるいはその投票手続きとしての解釈）の安定性を判定する指標を用いて一般化されます。これらに関係する実験を行った結果の一部を、最近作成した報告資料の付録にまとめてあります．同時にコードも付けてあります． ⇒○
しかし、実際にどんなＳＷＦ（ＳＤＦ）ができるのかは、たぶん、ほとんど知られていないのではないでしょうか？この節ではやはりＰＲＯＬＯＧの力を借りて、抽象的な理論を、可視化してみました。
本文中に書き加えましたが、SWF/SCFの定義域と値域をともに弱順序に一般化した場合、線形順序のように独裁ルールが２つしかないのとちがって、PとIIAを満たすもの、あるいは独裁的なものは、たくさん存在するため、図２のようにすっきりした自動証明にはなりません。
新しいコードで試したものとして、以下にＳＷＦ値を準推移的順序に一般化した場合のArrowの定理の実験を掲載します（図3）。なお定義域は以下のように線形順序のままにしてあります。



[1]:[+, +, +]:[ (x, y): +, (x, z): +, (y, z): +] => (x,y,z)
[3]:[-, +, +]:[ (x, y): -, (x, z): +, (y, z): +] => (y,x,z)
[9]:[-, -, +]:[ (x, y): -, (x, z): -, (y, z): +] => (y,z,x)
[19]:[+, +, -]:[ (x, y): +, (x, z): +, (y, z): -] => (x,z,y)
[25]:[+, -, -]:[ (x, y): +, (x, z): -, (y, z): -] => (z,x,y)
[27]:[-, -, -]:[ (x, y): -, (x, z): -, (y, z): -] => (z,y,x)

図3中ではSWFをバイナリー（代替案ペアごとの表形式）で表示しています。また図中で、＋、－、０はそれぞれ(X,Y)、(Y,X)、(X,Y)&(Y,X) に対応します。つまり「XがYより（強く）好まれる」か、その逆であるか、あるいは無差別であるかのいずれかを示します。



?- [sp06b1].

---orderings:[1][2][3][4][5][6][8][9][10][11][12][13][14][15][16][17][18][19][20][22][23][24][25][26][27]
25 orderings has updated in r_x/5.
25 consistent orderings have been recovered in r_0/5.
% sp06b1 compiled 0.00 sec, 9,344 bytes

Yes
?- make_preference(q-trans).

---orderings:[1][2][3][5][6][9][10][11][13][14][15][17][18][19][22][23][25][26][27]
19 orderings has updated in r_x/5.

Yes
?- make_preference(weak).

---orderings:[1][2][3][6][9][10][14][18][19][22][25][26][27]
13 orderings has updated in r_x/5.

Yes
?- make_preference(strict).

---orderings:[1][3][9][19][25][27]
6 orderings has updated in r_x/5.

Yes
?- switch_swf_order_type(_->q-trans).

Yes
?- [menu].
% menu compiled 0.00 sec, 18,784 bytes

Yes
3-a.sp06d.plをロードし，いろいろな選好関係を生成する


% When the range of social choice is relaxed to 
% quasi-transitive order (q-trans) or consistent order, 
% ----thereby SDF (Sen, 1982) we adopt instead of SWF (Arrow, 1963), 
% nondictatorial rules are readily obtained.

?- stopwatch(b_swf([p,i],F),T),show_swf(F),fail.


% time elapsed (sec): 2.344


pair: (x, y):[+, -, -, +, +, -]
------------------------------
[+, +, +]:1:[+, -, -, +, +, -]
[-, +, +]:3:[+, -, -, +, +, -]
[-, -, +]:9:[+, -, -, +, +, -]
[+, +, -]:19:[+, -, -, +, +, -]
[+, -, -]:25:[+, -, -, +, +, -]
[-, -, -]:27:[+, -, -, +, +, -]

pair: (x, z):[+, +, -, +, -, -]
------------------------------
[+, +, +]:1:[+, +, -, +, -, -]
[-, +, +]:3:[+, +, -, +, -, -]
[-, -, +]:9:[+, +, -, +, -, -]
[+, +, -]:19:[+, +, -, +, -, -]
[+, -, -]:25:[+, +, -, +, -, -]
[-, -, -]:27:[+, +, -, +, -, -]

pair: (y, z):[+, +, +, -, -, -]
------------------------------
[+, +, +]:1:[+, +, +, -, -, -]
[-, +, +]:3:[+, +, +, -, -, -]
[-, -, +]:9:[+, +, +, -, -, -]
[+, +, -]:19:[+, +, +, -, -, -]
[+, -, -]:25:[+, +, +, -, -, -]
[-, -, -]:27:[+, +, +, -, -, -]

% time elapsed (sec): 4.797


pair: (x, y):[+, -, -, +, +, -]
------------------------------
[+, +, +]:1:[+, 0, 0, +, +, 0]
[-, +, +]:3:[0, -, -, 0, 0, -]
[-, -, +]:9:[0, -, -, 0, 0, -]
[+, +, -]:19:[+, 0, 0, +, +, 0]
[+, -, -]:25:[+, 0, 0, +, +, 0]
[-, -, -]:27:[0, -, -, 0, 0, -]

pair: (x, z):[+, +, -, +, -, -]
------------------------------
[+, +, +]:1:[+, +, 0, +, 0, 0]
[-, +, +]:3:[+, +, 0, +, 0, 0]
[-, -, +]:9:[0, 0, -, 0, -, -]
[+, +, -]:19:[+, +, 0, +, 0, 0]
[+, -, -]:25:[0, 0, -, 0, -, -]
[-, -, -]:27:[0, 0, -, 0, -, -]

pair: (y, z):[+, +, +, -, -, -]
------------------------------
[+, +, +]:1:[+, +, +, 0, 0, 0]
[-, +, +]:3:[+, +, +, 0, 0, 0]
[-, -, +]:9:[+, +, +, 0, 0, 0]
[+, +, -]:19:[0, 0, 0, -, -, -]
[+, -, -]:25:[0, 0, 0, -, -, -]
[-, -, -]:27:[0, 0, 0, -, -, -]

% time elapsed (sec): 7.11


pair: (x, y):[+, -, -, +, +, -]
------------------------------
[+, +, +]:1:[+, +, +, +, +, +]
[-, +, +]:3:[-, -, -, -, -, -]
[-, -, +]:9:[-, -, -, -, -, -]
[+, +, -]:19:[+, +, +, +, +, +]
[+, -, -]:25:[+, +, +, +, +, +]
[-, -, -]:27:[-, -, -, -, -, -]

pair: (x, z):[+, +, -, +, -, -]
------------------------------
[+, +, +]:1:[+, +, +, +, +, +]
[-, +, +]:3:[+, +, +, +, +, +]
[-, -, +]:9:[-, -, -, -, -, -]
[+, +, -]:19:[+, +, +, +, +, +]
[+, -, -]:25:[-, -, -, -, -, -]
[-, -, -]:27:[-, -, -, -, -, -]

pair: (y, z):[+, +, +, -, -, -]
------------------------------
[+, +, +]:1:[+, +, +, +, +, +]
[-, +, +]:3:[+, +, +, +, +, +]
[-, -, +]:9:[+, +, +, +, +, +]
[+, +, -]:19:[-, -, -, -, -, -]
[+, -, -]:25:[-, -, -, -, -, -]
[-, -, -]:27:[-, -, -, -, -, -]

No
3-b.パレート条件(p)と独立性(i)の両オプションを指定してSWFを生成する．
上では２つのSWFが代替案ペアごとの形式で出力され，各プロフィールにおける
グループ全体の選好が表形式で表されている．ただし表の各行の左端はエージェン
ト1の選好とその番号を表す見出しであり，各列は同じ順序でエージェントの2の
選好を表す．


?- show_a_swf_0([p,i],F),nl,fail.

[+, +, +]:1:[1, 3, 9, 19, 25, 27]
[-, +, +]:3:[1, 3, 9, 19, 25, 27]
[-, -, +]:9:[1, 3, 9, 19, 25, 27]
[+, +, -]:19:[1, 3, 9, 19, 25, 27]
[+, -, -]:25:[1, 3, 9, 19, 25, 27]
[-, -, -]:27:[1, 3, 9, 19, 25, 27]

[+, +, +]:1:[1, 2, 5, 10, 13, 14]
[-, +, +]:3:[2, 3, 6, 11, 14, 15]
[-, -, +]:9:[5, 6, 9, 14, 17, 18]
[+, +, -]:19:[10, 11, 14, 19, 22, 23]
[+, -, -]:25:[13, 14, 17, 22, 25, 26]
[-, -, -]:27:[14, 15, 18, 23, 26, 27]

[+, +, +]:1:[1, 1, 1, 1, 1, 1]
[-, +, +]:3:[3, 3, 3, 3, 3, 3]
[-, -, +]:9:[9, 9, 9, 9, 9, 9]
[+, +, -]:19:[19, 19, 19, 19, 19, 19]
[+, -, -]:25:[25, 25, 25, 25, 25, 25]
[-, -, -]:27:[27, 27, 27, 27, 27, 27]

No
?- show_swf_0_max([p,i],F),nl,member(P:G,F),
is_decisive_swf(P,F,J),write(d(P:J)),nl,fail.

[+, +, +]:1:[[x], [y], [y], [x], [z], [z]]
[-, +, +]:3:[[x], [y], [y], [x], [z], [z]]
[-, -, +]:9:[[x], [y], [y], [x], [z], [z]]
[+, +, -]:19:[[x], [y], [y], [x], [z], [z]]
[+, -, -]:25:[[x], [y], [y], [x], [z], [z]]
[-, -, -]:27:[[x], [y], [y], [x], [z], [z]]
d((x, y):2)
d((x, z):2)
d((y, z):2)

[+, +, +]:1:[[x], [x, y], [x, y], [x], [x, z], [x, y, z]]
[-, +, +]:3:[[x, y], [y], [y], [x, y], [x, y, z], [y, z]]
[-, -, +]:9:[[x, y], [y], [y], [x, y, z], [y, z], [y, z]]
[+, +, -]:19:[[x], [x, y], [x, y, z], [x], [x, z], [x, z]]
[+, -, -]:25:[[x, z], [x, y, z], [y, z], [x, z], [z], [z]]
[-, -, -]:27:[[x, y, z], [y, z], [y, z], [x, z], [z], [z]]

[+, +, +]:1:[[x], [x], [x], [x], [x], [x]]
[-, +, +]:3:[[y], [y], [y], [y], [y], [y]]
[-, -, +]:9:[[y], [y], [y], [y], [y], [y]]
[+, +, -]:19:[[x], [x], [x], [x], [x], [x]]
[+, -, -]:25:[[z], [z], [z], [z], [z], [z]]
[-, -, -]:27:[[z], [z], [z], [z], [z], [z]]
d((x, y):1)
d((x, z):1)
d((y, z):1)

No
?-

3-c.生成されたSWFを順序の番号や最善案によって別表示する．
また後者では各代替案ペアについての指令性(決定権）を持つエージェント
を表示させる

図３．準推移的順序を値域とするSWFをPrologで生成する

線形順序での２つの独裁的SWFに加えて一つのパターンが増えているのが分かります。また実験データをバックグラウンドで節に保存し、そこから社会的順序（のモデル上の番号１～２７。線形順序、弱順序、準推移的順序などはその一部）を復元した表、および最善案（極大元）の集合の表の、計3通りの表示を使っています。

その２番目が独裁的でないものです。いずれのエージェントもどの代替案ペアについても決定力を持たないＳＷＦが得られていますが、これはＳｅｎの自由主義背理の定理と一致しています。

付録5．自由主義の背理（リベラルパラドックス）と決定力の伝播

自由主義背理（liberal paradox）ではIIA条件は用いないが、パレート原理が代替案ペア比較についての制約として用いられ、半ばその性質を帯びているため、Arrowの結果と類似の奇妙な定理が導かれる。自由主義（L)という条件は最低各人が勝手に決められる（決定力のある）ペアを一つはもつという条件である。このとき非制限領域において条件Pと条件LをみたすSWFはない。また最小自由主義（ML)は、そういう個人が高々2人でいいという条件で、これでも同じ結論が言える（Sen(1982)の13章、 JPE 78:152-7, 1970のリプリントを参照）。
ちなみに「決定力」(decisiveness)とその伝播は、いわゆるパレート伝染病(The Paretian epidemic)と文献で呼ばれるもので、これらの不可能性の背理に共通する現象、病理の根源をさすことばである。 ---その物議をかもした自由主義者の背理（リベラルパラドックス）は、オリジナルよりやや弱いバージョンの決定力概念を使っても同様に示せる。このため、 Amartya Senが自身が一般化して名づけたものである（Sen(1982)の14章、 Economica 43:217-45, 1976のリプリントを参照）。
Senの背理は、特定のプロフィールで社会的厚生関数が作れないことを示すものだが、Arrowの定理(Arrow, 1963)では、これとほぼ同じ論理によって、決定力の（代替案ペア間での）伝播が、独裁的な社会的厚生関数に至る道筋が証明される。許容的領域での不可能性定理の必要十分条件である先述のKalai and Muller(1977)の「決定力含意に基づく代替案ペアの分解不可能性」という性質には、実は自由主義背理を発生させるプロフィールが使われている。
そのプロフィールとは、例えば(x,y,z)と(z,x,y)のように、ちょうど一つのペア(x,y)については両者が合意しており、それ以外の(x,y) や(z,x)については、対立している場合である。背理の証明も単純である。
このようなケースでは (x,y,z)を選好とする一方（エージェント1とする）に対して (y,z)についての決定力を、当局が与えるとすると、他方（エージェント2とする）に(z,x)についての決定力を与えることは論理的に不可能になる。なぜならば、(y,z)についてのエージェントの決定力は、合意のある(x,y)からパレート原理を用いて、社会が(y,z)の順に好み、かつ(x,y）の順に好むということを導き、さらにこれらを合わせて、「社会的に最適なのはxである」という結論に反するからである。（またこの結論を導くのに推移性は使わなくてもよい。他のいずれもｘに勝らないということで十分である。）
すなわち(y,z)についてのエージェント1の決定力は (x,z)についての同じエージェント1の決定力を含意する。また同じように、(z,x)についてのエージェント2の決定力は (z,y)についての同じエージェント2の決定力を含意する。よって両方向から対立する決定力を与えと、矛盾ししまう。言い換えれば、お互いにこれらの争点を譲りあえさえできれば、一つの完全に一致した選好が得られる。
こういうプロフィールが---どのように配置しているかは、以下のように対角成分を除く市松模様になるのですが、----発生する箇所では、決定力が一方通行になり、Arrowの定理の場合は、これがIIA条件によって、順次別の箇所に伝播していき、やがてボードを埋め尽くすことになる。


             [ 1,  3,  9, 19, 25, 27]
-------------------------------------
[+, +, +]: 1:[--, --, ##, --, ##, --]
[-, +, +]: 3:[--, --, --, ##, --, ##]
[-, -, +]: 9:[##, --, --, --, ##, --]
[+, +, -]:19:[--, ##, --, --, --, ##]
[+, -, -]:25:[##, --, ##, --, --, --]
[-, -, -]:27:[--, ##, --, ##, --, --]

補足になりますが、上の表で行見出しの[+,+,+]とその番号1は、プラスマイナスの記号が左から順にxy, xz, yzの３ペアの比較の向きを表し、全体で(x,y,z)という順序に対応します。以下のすべて線形順序で、付録4の最初に述べたとおりです。なお以前のコードでは19：(y,x,z)は、 r(2)、2番目のランキングという位置にありました。残りの並び方は同じです。その場合、以下のように図柄的には右上がりの楕円（6角形？）になります。


          #r   [(1),(2),(3),(4),(5),(6)]
----------------------------------------
[+, +, +]:r(1):[--, --, --, ##, ##, --]
[+, +, -]:r(2):[--, --, ##, --, --, ##]
[-, +, +]:r(3):[--, ##, --, --, --, ##]
[-, -, +]:r(4):[##, --, --, --, ##, --]
[+, -, -]:r(5):[##, --, --, ##, --, --]
[-, -, -]:r(6):[--, ##, ##, --, --, --]

なんだそれだけかと思われたかもしれませんが、多くの文献がそうしたように、反直観的な印象を与える変な例題、「おせっかいな社会」の具体例を作り出すことができます。例えば、

ｘ：親猫を避妊手術する、
ｙ：猫を飼わない、
ｚ：子猫を保健所に引渡す、

という３代替案を考えたときに、ある人（Aさん．その選好：(x,y,z)）に対して、社会が、猫を飼わないか、あるいは避妊手術をすべきかいずれかを決める自由を認めるとすると、他の人（Bさん．(z,x,y)）はAさんから、保健所に引き取らせ、処分させるようなことはせずに、避妊手術せよという結論を、当局の折り紙つきで、おしつけられることになる。（良識的にはそうかもしれないが．．）逆もまたしかりであり、 Bさんの「猫の権利を侵害する避妊手術よりもましだ」という主張を個人の権利として認めると、猫を飼って、子猫を保健所に引き渡せと、Aさんは、Bさんとその後ろ盾の当局から、指図されることになる。
このとき社会の選好は、まずパレート原理から(x,y)と決まり、もしＡさんの(y,z)にかんする決定力（自由）を認めればその結果、社会の選好が(x,y,z)となってＡさんの独裁、あるいはＢさんの (z,x)にかんする決定力を認めると、社会の選好が(z,x,y)となってＢさんの独裁になる。これは先に述べた自由主義背理である。
こうなるといくら猫ずき仲間同士といえども、平和的解決は難しい。（もっとも、猫に興味がない人々にとっては、どちらにせよたいしたことではないかもしれないが。つまるところ、彼らはｙという案を取る自由がないから、不幸なコンフリクトに直面している。いや、こうのように勝ち組と負け組みが明確に分かれざるを得ない状況下において、両者が仲たがいしないようにせよとの勅を受けた「当局」が、一番不幸かもしれない。）
なおこの例題は、最近週刊誌やブログでとりあげられていた問題をヒントにしました。あるいはちょっと苦しいけれど、例えば、温暖化ガスの問題を考えますと、ｚを京都議定書を批准する、ｘを批准なしの排出権ビジネス促進政策、ｙを自由奔放とすると、(x,y,z）は米国の選好になりますでしょう？　(z,x,y)は批准賛成の他の国。現時点で、両者の自由はありますが、この定理によって、パレート劣位の選択を社会はしているわけです。
あるいは決定力の概念をその「自由」に読み替えて、いずれの人々にも、個人の権利とか自由とかいったものを、認めてあげなければならないのだとする倫理観、社会規範、あるいは政策的理念といったものの整合性を吟味するとしたら、この場合、Ａさんの自由のもつ含意(y,z)->(x,z)となり、Ｂさんの自由のもつ含意(z,x) ->(z,y)となる。いずれの示し方をするにせよ、両立しないのは明らかだ。
ところで、上の例で両者の前提＝それぞれの個人の自由(y,z)と(z,x)の組合せで(y,z,x)という第3の選好を作ることができる。これを「当局」と言う第3のエージェントを追加して拡張した社会の選好パタンとすると、どうなるだろうか？　この順序を、もともとの両者の(x,y,z)と(z,x,y)という 2順序に追加することによって、ラテン方格と呼ばれるパタンが完成する。


(z, x, y)    <=  [25]:[+, -, -]
(x, y, z)    <=   [1]:[+, +, +]
(y, z, x)    <=   [9]:[-, -, +]
-------------------------------
majority     <=   ?   [+, -, +]

他の部分で述べたように、これはどの案もすべての順位をとりうる最小のパタンである（その場合、多数決原理が循環することに注意しよう）。


?- r_0(K,[+,-,+],A,B,C).

K = 7
A = [ (x, y): +, (x, z): -, (y, z): +]
B = [inconsistent, not(q-trans), complete]
C = [ (x, y), (z, x), (y, z)] 

Yes
?-

ちなみに完備な３代替案上の２項関係で，（強順序で）循環する選好は上を含めて２つあり、線形順序のときのラテン方格に一致します。本プログラムでconsistent（無矛盾）となっているそれ以外の選好関係をすべて含む領域のことを、acyclic relations（非循環関係）と呼ぶ文献もあります(Moulin, 1988)。



?- r_0(K,R,A,[inconsistent|B],C).

K = 7
R = [+, -, +]
A = [ (x, y): +, (x, z): -, (y, z): +]
B = [not(q-trans), complete]
C = [ (x, y), (z, x), (y, z)] ;

K = 21
R = [-, +, -]
A = [ (x, y): -, (x, z): +, (y, z): -]
B = [not(q-trans), complete]
C = [ (y, x), (x, z), (z, y)] ;

No
?-

こうして、別名、パレート的自由主義の不可能性定理と呼ばれていながら（というか、そちらが正式名称だけれども）、じつは自由主義背理は、パレート原理すら小者で、その背後に矛盾発生のメカニズムを潜ませているのが分かる。これがArrow の定理の証明で用いられていた、不可能性の核である。
「権利の与え方」＝ゲーム形式（および選好パタンの組合せ方）によっては、変なことになるということをこの例は示している。実際、自由主義背理がそれ以降の「権利」システム研究に与えた影響は少なくない。ちなみに、変な権利の与え方の研究は、別名（というか、そちらが正式名称だけれども）、洗練された投票 (sophisticated voting)と呼ばれてきた。またこれら分野の交点は、単純ゲーム(simple game)とか効力関数(effectivity function) と呼ばれる理論ツールを使って、見通しをつけるのが伝統的なやり方であった。これらについては別の機会に紹介したい。ここでは一つの例をあげておく。
実は、有名な大岡裁き（ソロモン王）での偽親問題も、これと同じパタンです。ｚ：2（本物の親）に子供を与える、ｘ：1（偽親）に子供を与える、ｙ：子供を孤児院に入れる．(x,y,z)は偽親の選好順序、(z,x,y)は真の親の選好順序とします。
普通の大岡越前は、偽親にはxとyのいずれがよいかを訊き、また本当の親にyとzのいずれがよいかを訊くでしょう。偽親はきっぱり(x,z)を選ぶにちがいない。また本当の親は、とうぜんながら、(z,y)という。よって、両者の言い分をそれぞれ尊重すると、社会的にｘが最適であるという結論になる。
悪い大岡越前は、本当の親にzとxのいずれがよいかを訊き、偽親にはyとzのいずれがよいかを訊くでしょう。本当の親は、とうぜんながら、(z,x)という。一方偽親は、「偽親に渡されてひどい目に合わされるよりは」などと言って(y,z)というでしょう。よって、両者の言い分をそれぞれ尊重すると、社会的にy、つまり子供を孤児院に入れることが最適であるという結論になる。
もっとも、これだと倫理的なルールに基づき、（オリジナルの裁きのように）偽親だとばれてしまうので、偽親は「子供を孤児院に入れるくらいなら偽親に」などと、いけしゃーしゃーと、(z,y)を選ぶかもしれない。そうすると、両者の言い分をそれぞれ尊重した結果、社会的に本物の親に渡すことが最適であるという結論になる。

ノート

[*0] つねに両者のトップランクの代替案のどれかを社会的に選択すること。
[*1] Muller and Satterthwaite(1977)が、戦略的操作不能条件との同値性を証明した。もともとArrowの本で用いられていた社会厚生関数についての条件を、社会的選択対応（社会的選択関数はその1値の場合）に一般化したものであり、強正結合(Strong Positive Association)条件とも呼ばれる。またオリジナルの正結合性条件（そのやや強められた形で）は、IIAと CSの下ではパレート条件（P）を帰結する(Arrow(1963), p.97)。また線形順序においては、この条件下でCSはPと同値である (Muller and Satterthwaite, 1977)。
[*2] 市民主権の条件、あるいは忌避的代替案の不在の条件とも呼ばれる。
[*3] つまりその得られたＳＣＦでは、「ある一人のメンバーが、どのプロフィールでも、自分のベストだと思う案を通していること。」
[*4] ３代替案のとき、個人の選好順序は6通り、無差別を許して13通りある。 2人の社会的選択関数は、よって6^2=36通りのプロフィールに対して、3^36通りの社会的選択関数が定義できる。また後出の社会厚生関数の場合は、6^36通りとなり、素朴な生成シミュレーションでは事実上証明不可能である。
[*5] Arrow(1963)における定理の記述は次のようであった。

一般可能性定理 (Arrow(1963) Theorem 2, p.59)
もし３つ以上の代替案があって、領域が非制限的（つまりいかなる選好順序のプロフィールも可能）であるならば、 IIA条件と「個人と社会の価値の正結合」(PASIV)条件（本文では、正結合条件と略す）とをともにみたす社会的厚生関数（つまり推移的でありかつ完備的な社会的順序）は、独裁的であるか、あるいは市民主権の条件に違反する（つまりあるペア(x,y)についてはどのプロフィールでもその一方のみ選ばれつづける）かのいずれかである。

Arrow(1963)の8章では、正結合条件と市民主権性の部分がパレート条件Pに置き換えられ、より簡潔な形で述べなおされている。 PはIIAとその2条件から含意される。現在殆どの文献で紹介されているのはこの形式である。
[*6] 付録5参照。
[*7] ソースコードと実験結果の集計については付録3参照。
[*8] 単純ゲームは代替案の集合Ａと勝利提携の集まりＷのペア（Ｗ，Ａ）として定義される。そのうちの勝利提携のいくつかを集めた積が空になる----すなわち内部にveto playerを持たないそれ自体内部的に安定した部分集合σ⊆Ｗたちを集める。そしてそれらのそれぞれの提携個数をランク関数とする一種のマトロイド（マトロイドは行列のようなものの一般化です）を考える。中村の定理は単純ゲーム(simple game)のコアの安定性、つまり任意のプロフィールでコアが非空であることの、必要十分条件----すべての勝利提携の積が非空、すなわちveto playerが存在するか、あるいは単純ゲームのランク関数（＝容量）の最小値が、代替案の数を超えること----を与えるものです。またそれが、副産物としてアローの定理や単純多数決原理の推移性の条件を一般化することになりました。またＭｏｕｌｉｎとＰｅｌｅｇおよびＫｅｉｄｉｎｇによって、権利システムの形式モデルである効力関数 (effectivity function)の安定性の必要十分条件に拡張されています(Peleg and Moulin, 1982; Keiding, 1985)。

追記

2006.8.27--2007.10.29

Proogや人工知能手法を経済学の理論に応用することについて、はじめにとこの追記において、若干の文章を加えます。なお、新しいコードを用いた実験については、付録4として独立させました。また人工知能とPROLOGにかんする説明は第3 節として独立し、そちらに追加しました(9/7)。
付録2のラテン方格の説明、および脚注[ *6]の自由主義背理との関係の部分の文章を補いました。とくに「自由主義の背理」については付録5して分割しました．いろいろな順序の種類で実験できる新しいシステムを作成中です．上記はその過渡的な結果の一つですが，いずれ実験結果を含めて報告します．（追記 11/20 その結果とコード ⇒○）
06/9/7,9,10. 順序（選好関係）の表記法と番号が、新しいコードでは少し変わりましたので、その補足を付録4と付録5に追加しました。第2節の選好順序の性質および記法についても補いました。PROLOG　や人工知能手法の適用に関する文章を第2節として追加しました。自由主義背理の例題における文章表現を少し変えました。Sen(1970)は、その増補改訂版ともいえるSen(1982)よりも古く、また本文中では引用していませんが、訳本があります（正誤表が訳者のホームページで公開されています）。最近翻訳が出版された Arrowら(2002)のハンドブック（訳本は未入手です）と共に、文献リストにあげてあります。
06/9/10-12. 虫のプログラムがバグでしたので直しました。またコードの表す論理的モデリングの直観的意味を説明する文章を補いました。付録4の前書きを増補し、筆者が他に行っている実験研究を紹介しました。不可能性の回避と関連研究についての節を追加し、また追記自体を節として独立させました。中村の定理についての脚注[*8]を追加。
9/27. 上記の文献タイトルを直しました(voters-->vetoers)。
06/11/20. 中村数などに言及した文章の語句の誤りを訂正。最近行った実験結果についての紹介．11/25.スタイルシートを修正し，図中のコードなどを見易くし，かつ図の説明を補足した．
06/12/22. すべてのコードをコンパクトに作り直し，３つのプログラムとしてまとめました．12/25.　以上のプログラムの改訂および共通許容的領域での分解可能性のコードを追加．他の箇所のソースコードへのリンクの誤りを訂正． 12/31. シンプルゲームとBlair-Mullerの本質的分解可能性のコードを追加(here)．懸案のコード化がなんとか年内に間に合いましたが，解釈などについては稿を改めます．
07/5/24. 虫のプログラムを直しました。仮想実行だけだといけませんね。
07/10/29-30,11/22. 図解を用いたアローの定理のより詳しい説明、より一般的な場合のPrologコードなどについては、研究のページからご覧ください。

参考文献

Arrow, K. J. (1951/1963). Social Choice and Individual Values. Cowles Foundation Monograph 12.
Arrow, K. J., Sen, A. K. Suzumura, K. (2002). Handbook of Social Coice and Welfare. North-Holland.( 鈴村興太郎ら（訳），『社会的選択と厚生経済学ハンドブック』，丸善，2006)
Barbera, S. (1980). Pivotal voters: A new proof of Arrow's theorem. Economic Letters 6: 13-6.
Binmore, K. G. (1976). Social choice and parties, Review of Economic Studies 43: 459-464.
Blair, D. and Muller, E. (1983). Essential aggregation procedure on restricted domains of preferences. Journal of Economic Theory, Vol. 30, pp.34-53.
Danilov, V. I. and Sotskov, A. I. (2002). Social Choice Mechanisms. Springer.
Gaertner, W. (2001). Domain Conditions in Social Choice Theory. Cambridge University Press.
Geanakoplos, J. (2005). Three brief proofs of Arrow's impossibility theorem. Economic Theory 26: 211-5.
Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica 41: 587-602.
Kalai, E. and Muller, E. (1977). Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures, Journal of Economic Theory, Vol. 16, pp.457-469.
Satterthwaite, M.A. (1975). Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory 10: 187-217.
Moulin, H. (1988). Axioms of Cooperative Decision Making. Cambridge University Press.
Muller, E. and M.A. Satterthwaite (1977). The equivalence of strong positive association and strategy-proofness. Journal of Economic Theory 14: 412-8.
Nakamura, K. (1979). The vetoers in a simple game with ordinal preferences. International Journal of Game Theory, Vol. 8: 55-61.
Reny, P. J. (2001). Arrow's theorem and the Gibbard-Satterthwaite theorem: A unified approach, Economic Letters, Vol. 70: 99-105.
Sen, A. (1970). Collective Choice and Social Welfare, Holden-Day. (志田基与師（訳）, 『集合的選択と社会的厚生』, 勁草書房, 2000.)
Sen, A. (1982). Choice, Welfare and Measurement, MIT Press.
Sen, A. (1995). Rationality and social choice. American Economic Review 85(1):1-24.
Vickrey, W.(1960). Utility, strategy, and social decision rules, Quarterly Journal of Economics, Vol. 74(4): 507-535.
石井安憲・西条辰義・塩澤修平(1995).『入門ミクロ経済学』有斐閣.
鈴村興太郎・後藤玲子(2002).『アマルティア・セン：経済学と倫理学』改装新版、実教出版．
佐伯胖(1980).『決め方の論理』東京大学出版会.
柴田弘文(1992).「アローの一般不可能性定理の図形的証明」経済研究43(1):1-13.
武隈愼一 (2000). 数理経済学とコンピュータ, 特集金融・数理経済学とコンピュータ：数理モデルで読み解く経済現象, Computer Today 17 (98): 10-15.
Arrow's impossibility theorem: Information From Answers.com http://www.answers.com/topic/arrow-s-impossibility-theorem