Prologによる非循環的集合の生成

2006.6.19

犬童健良

関東学園大学経済学部

はじめに

　線形順序（同順位のないランキング）の非循的環集合は，ペアワイズ多数決投票が循環を生じない領域である．

　単純多数決原理（すなわち，ペアワイズ多数決による社会的ランキングの導出）が循環を生じないための必要十分条件は，奇数人数のとき，可能なランキングの集合が，任意の３代替案ないし３人の候補者（以下トリプルと書く）において，この条件を満たすことである(Inada, 1969; Sen and Pattanaik, 1969)．またこれは，各トリプルにおいてラテン方格を含まないことと等しい(Sen, 1966;Ward, 1965)．

　ラテン方格とは，あるトリプルが，すべての３順位をもれなくとるランキングの最小集合である．トリプル{x,y,z}とすると， {(x,y,z),(y,z,x),(z,x,y)}および{(x,z,y),(y,x,z),(z,y,x)} の２つがラテン方格である．
　
　ラテン方格なしの条件は，ランクの分布がぎっしりつまっておらず，どこかにホールがあることを意味する．すなわち，ある代替案があるトリプルで，１位にならない場合，２位にならない場合，および３位にならない場合のいずれかにあたることに等しい．これは価値制限 (value restriction)，あるいはネバー制限（ never restriction, never constraint）と呼ばれることがある．

latin square	pattern 1	pattern 2
#s of rankings	[1,4,5]	[2,3,6]
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)

Fig. 1 the latin squares for a triple of alternatives

　
　以下の実験用コード内では，３代替案の場合を基準に，各ランキングをシンボルで名前付けした．３代替案の場合は， r(1)=(a,b,c), r(2)=(a,c,b), r(3)=(b,a,c), r(4)=(b,c,a), r(5)=(c,a,b), r(6)=(c,b,a)とした．それゆえ，ラテン方格は {1,4,5}と{2,3,6}と表せる．

　なお4代替案以上の場合は，追加した代替案の挿入位置によって指標付けした．例えば， r((1,1))は代替案dを最後の位置に追加したものである． PROLOGコードを使えば，この例を以下のように確認することができる．


?- possible_ranking_0(r((1,1)),X).

X = [a, b, c, d] 

Yes
?-

　また，経済学の文献では，それぞれ１位にならない場合を単谷性(single-cavedness; sc)，３位にならない場合を単峰性 (single-peakedness; sp)，および２位にならない場合を， 2群分割可能性(separability into two groupes; s2)と呼ぶこともある．

　ところで価値制限(value restriction)という名称は， Amartya Senによって最初に導入された(Sen, 1966)．単峰性はBlack, Arrowによって（十分性が）研究されていたが，後の2つもその自然な一般化であり，上記の Senの論文に先立って稲田献一 (Kenichi Inada)が導入した．

　このように1960年代には，Amartya Sen，稲田，そしてラテン方格の意義を看破したWard，そしてVickreyらが，多数決の推移性の必要十分条件を競って研究していた．さまざまなアプローチが試みられた末，稲田が，1969年の論文で，ついに非推移性の発生の厳密な条件を特定し，またそれに触発されたSenとPattanaikのペアが同じ年の論文で，総仕上げをしている．（もっともラテン方格のことを含めて,Vickrey(1960)が厳密ではないにせよ，Arrowの定理の証明でそれが用いられていることを詳しく追求し，多数決原理との関係を示唆している．）

　ちなみに弱順序のときの必要十分条件は，価値制限よりもやや広く，限定合意(limited agreement）あるいは極値制限(extremal restriction) と呼ばれる条件を含めたいずれかが，任意のトリプルで成立することである．

type of value restriction	never be worst (sp)	never be middle (s2)	never be best (sc)
a	[1,2,3,5]	[1,3,5,6]	[3,4,5,6]
b	[1,3,4,6]	[2,3,4,5]	[1,2,5,6]
c	[2,4,5,6]	[1,2,4,6]	[1,2,3,4]

Fig. 2 maximal value restricted domains for 3-alternative case

　なお，偶数人数の場合を含めて，価値制限を満たしていれば，社会全体で一つのランキングとそのベストな案を選出することはつねに可能である．すなわち，SenとPattanaikがいうところの社会的意思決定関数が定義される(Sen and Pattanaik, 1969)．（それは必要十分条件である．ただし，ここでいう人数の偶数とか奇数は，領域中のランキングに対して，特定の人数の割り振り方をすればできるとかできないといった意味であり，実際， 2人のときは反例を作れる．例えばラテン方格そのものをとると，明らかに価値制限を満たさないが，これをどのように2人に割り当てようとも，準推移性に矛盾しない．準推移性とは厳密順序で，(x,y)&(y,z)のとき，(x,z)となることである．また反対順序のペアを2人に対してそれぞれ割り当てたときのように，すべて無差別なら，自明に準推移性は満たされる．）．

　ところで，小さな数の代替案の場合を除くと，非循環的集合（あるいは価値制限を満たす領域），すなわちラテン方格を含まない最も大きなランキングの集合（最大無矛盾領域と呼ぶ文献もある）が果たしてどのくらいの大きさになるのかは，厳密には知られていないようだ．一方，文献によると，いくつかの下界が得られている．最大サイズは当初Cravenによって2^(n-1)が予想されたが，反例が作られ，ついで3*2^(n-2)-4が予想されたが，これも反例を作ることができる．筆者のPROLOGコードでは，比較的少ない数の代替案のとき，後者は（後述のスキーマAによって）前者のサイズの初期解を計算するのに便利であり，またその単調な拡張によって最善下界を与えることができる．

　素朴には，任意のトリプルで，3代替案の場合の最大サイズ４にあたる相対ドメイン（Figure 2）を割り当てていけばいいのではないかと思うだろうが，これは効率的な解き方ではない． Fishburnは，比較的少ない代替案（１６以下）のときに（たぶん最大の）非循環的集合を求めるヒューリスティックス，Alternating Schema（以下スキーマAと呼ぶ）を提案した．トリプルにおいて，もとの代替案のリストでの順番が奇数の場合，それをトップランク落ちに，また偶数のときはボトムランク落ちにする（またはこれらの逆）という制約をつける．６代替案までは，スキーマAで最大の非循環的集合を求めることができる(Fishburn, 2000)．

　より大きなサイズの領域では，スキーマAは最善ではなくなる．最善下界はn>=16について2.1708^nが知られている．[1] つまり７～１６の間はグレーゾーンであり，スキーマAは最適であるかもしれないし,あるいはそれでは作れないもっと大きな非循環的集合があるかもしれない．代わりにs2を活用して，2つ以上のacyclic setsを合成する方法が，CravenやFishburnの論文で提案されている．これをFishburnは，replacement scheme（スキーマRとしておこう）と呼んでいる．

[1]一方上界についてはもっと曖昧であり，Raz(2000)が帰納的確率（VC次元）の議論によって，未知正定数ｃに対してｃ^n未満を証明したが，これに対して Fishburn(2002)はより具体的に2.591^(n-2)と予想している．

　3代替案の場合の最大非循環的集合を調べると分かるが， s2のそれは反対順序ペアのペアでできており，ある代替案が対称のセンターになる．spやscの最大集合は，一つの反対順序ペアと，もう一つのペアからなるが，そこでは反対順序ペアでセンターになった代替案がトップ（spのとき）またはボトム（scのとき）になっている．
　AbelloとJohnsonは，1980年代に，非循環的集合が，順序（ランキング）において隣接する代替案ペアの互換によって，反対順序の両極が接続するようにできており，かつそれが最長チェーンであることを見出した．最近の研究によると，この方法を洗練すると，上記の Craven-Fishburnの方法を包含する方法が見えてくるらしい．

　今回はPROLOGで価値制限領域を生成するコード sproof_f.plを作成し，またこのコードに，上で述べたスキーマA を組み込んでみた．（またAbelloの方法も，一応試してあるが，効率的に解がもとまらなかったのでペンディングとする．）

　文献が示すように，スキーマAを用いてもとまる(真の）最大長は，４代替案で９，５代替案で２０，６代替案で４５であった．また７代替案では１００となるが，これが真に最長かどうかはわかっていない．

　３代替案のコードは瞬時に価値制限領域などを枚挙できたが，４代替案以上への拡張では，その素朴なコードから出発し，いろいろ工夫が必要だった．

　基本的な戦略は，任意のトリプルに対し価値制限を満たすランキングを，一つずつ増やしていく再帰である．ただし，各トリプルに対する価値制限（どの代替案につき，どのランク落ちか）のデータを保持しながら再帰する．また，この価値制限について，先述のスキーマAを制約として課した．

　なお私のノートPC （SONY VAIOやSotecの数年前のもの）だと，７代替案で７９あるいは８２が，生成できる限界であった．途中までのデータを見ると，長さ６４の最初の解から，１ランキングずつ追加しているだけだったので，途中までで得た長さｋ－１の結果にもとづき，上記の条件を満たすランキングを追加して拡張するようにしたところ，長さ１００の領域を得た．
　以下は４～７代替案数のときに，それぞれ最初に見つけたスキーマAによる最大の非循環的集合のみを示す．

４代替案の場合

　本システムはsproof_f.plというファイルにテキスト形式で記述されたPROLOGプログラムである．SWI-PROLOG 5.0.9 を用いて実験を行った（新しいバージョンだと，複数行のコマンド入力ができないとか，ストリーム出力でエラーが生じるといった問題があるので使用しない）．
　以下のようにPROLOGのコマンドを入力して実験を行った．なお時間計測やファイル出力など実験用ルーチンはmenu.plという別のプログラムを使う．


?- [sproof_f].

?- [menu].
% menu compiled 0.00 sec, 17,420 bytes

Yes
?- test_sup_vr_by_triples(P/N,4).
start, [date(2006/6/19), time(10:1:41)]

P = 10
N = 24 

Yes
?-

　実験結果は実行ディレクトリのsup_vr.txtという名のファイルへ出力される．以降の５代替案以上の実験についても，同様の方法で行う．ただし，７代替案のときは，途中で打ち切って，モードを切り替えて再出発する必要がある．


?- test_sup_vr_by_triples(P/N,4).
start, [date(2006/6/20), time(0:17:56)]
complete
successfully expanded by adding a ranking :
r((6, 4))complete

P = 10
N = 24 

Yes
?- 

(...以下，ファイル出力より...)


%----------  start from here ------------%

8:[r((1, 2)), r((1, 1)), r((3, 4)), r((3, 3)), r((3, 2)), r((3, 1)), r((4, 4)), r((4, 3))]
 (b, c, d):[1, 2, 5]:sc:c
 (a, c, d):[1, 2, 5, 6]:sc:c
 (a, b, d):[1, 3, 4, 6]:sp:b
 (a, b, c):[1, 3, 4]:sp:b
time:0[max]
9:[r((1, 2)), r((1, 1)), r((3, 4)), r((3, 3)), r((3, 2)), r((3, 1)), r((4, 4)), r((4, 3)), r((6, 4))]
 (b, c, d):[1, 2, 5, 6]:sc:c
 (a, c, d):[1, 2, 5, 6]:sc:c
 (a, b, d):[1, 3, 4, 6]:sp:b
 (a, b, c):[1, 3, 4, 6]:sp:b
time:0[max]
%----------  end of data ------------%

　出力形式の読み方は，１行目ランキング数：許容的領域（非循環的集合），２行目以降各トリプルの相対的領域と価値制限の種類が表示される．実験は，適当な下界（上記は２^(n-1)を使用）から出発して，発見できなくなるまで続ける．またコマンドtest_sup_vr_by_triples/2は，第１引数の分子に，最初に失敗した長さ（上界）を帰す．第２引数には実験するモデルの代替案数を指定する．

５代替案の場合


?- test_sup_vr_by_triples(P/N,5).
start, [date(2006/6/20), time(0:18:1)]
complete
successfully expanded by adding a ranking :
r((4, 4, 3))complete
successfully expanded by adding a ranking :
r((4, 3, 3))complete
successfully expanded by adding a ranking :
r((6, 4, 5))complete
successfully expanded by adding a ranking :
r((6, 4, 4))complete

P = 21
N = 120 

Yes
?- 

(...以下，ファイル出力より...)

20:[r((1, 1, 2)), r((1, 1, 1)), r((2, 2, 3)), r((2, 1, 3)), r((2, 1, 2)), r((2, 1, 1)), r((5, 4, 5)), r((5, 3, 5)), r((5, 3, 4)), r((5, 2, 5)), r((5, 2, 4)), r((5, 2, 3)), r((5, 1, 5)), r((5, 1, 4)), r((5, 1, 3)), r((5, 1, 2)), r((5, 1, 1)), r((6, 4, 5)), r((6, 3, 5)), r((6, 3, 4))]
 (c, d, e):[1, 2, 5, 6]:sc:d
 (b, d, e):[1, 2, 5, 6]:sc:d
 (b, c, e):[1, 3, 4, 6]:sp:c
 (b, c, d):[1, 3, 4, 6]:sp:c
 (a, d, e):[1, 2, 5, 6]:sc:d
 (a, c, e):[1, 3, 4, 6]:sp:c
 (a, c, d):[1, 3, 4, 6]:sp:c
 (a, b, e):[1, 2, 5, 6]:sc:b
 (a, b, d):[1, 2, 5, 6]:sc:b
 (a, b, c):[1, 2, 5, 6]:sc:b
time:0.282[max]

６代替案の場合


?- test_sup_vr_by_triples(P/N,6).
start, [date(2006/6/20), time(0:24:14)]
complete
successfully expanded by adding a ranking :
r((3, 2, 1, 1))complete
successfully expanded by adding a ranking :
r((3, 1, 1, 2))complete
successfully expanded by adding a ranking :
r((3, 1, 1, 1))complete
successfully expanded by adding a ranking :
r((4, 4, 5, 6))complete
successfully expanded by adding a ranking :
r((4, 4, 4, 6))complete
successfully expanded by adding a ranking :
r((4, 4, 4, 5))complete
successfully expanded by adding a ranking :
r((4, 4, 3, 6))complete
successfully expanded by adding a ranking :
r((4, 4, 3, 5))complete
successfully expanded by adding a ranking :
r((4, 4, 3, 4))complete
successfully expanded by adding a ranking :
r((4, 3, 3, 4))complete
successfully expanded by adding a ranking :
r((6, 4, 5, 6))complete
successfully expanded by adding a ranking :
r((6, 4, 4, 6))complete
successfully expanded by adding a ranking :
r((6, 4, 4, 5))complete

P = 46
N = 720 

Yes
?- 

(...以下，ファイル出力より...)

45:[r((1, 2, 2, 3)), r((1, 2, 1, 3)), r((1, 2, 1, 2)), r((1, 2, 1, 1)), r((1, 1, 1, 2)), r((1, 1, 1, 1)), r((3, 4, 5, 6)), r((3, 4, 4, 6)), r((3, 4, 4, 5)), r((3, 4, 3, 6)), r((3, 4, 3, 5)), r((3, 4, 3, 4)), r((3, 4, 2, 6)), r((3, 4, 2, 5)), r((3, 4, 2, 4)), r((3, 4, 2, 3)), r((3, 4, 1, 6)), r((3, 4, 1, 5)), r((3, 4, 1, 4)), r((3, 4, 1, 3)), r((3, 4, 1, 2)), r((3, 4, 1, 1)), r((3, 3, 3, 4)), r((3, 3, 2, 4)), r((3, 3, 2, 3)), r((3, 3, 1, 4)), r((3, 3, 1, 3)), r((3, 3, 1, 2)), r((3, 3, 1, 1)), r((3, 2, 2, 3)), r((3, 2, 1, 3)), r((3, 2, 1, 2)), r((3, 2, 1, 1)), r((3, 1, 1, 2)), r((3, 1, 1, 1)), r((4, 4, 5, 6)), r((4, 4, 4, 6)), r((4, 4, 4, 5)), r((4, 4, 3, 6)), r((4, 4, 3, 5)), r((4, 4, 3, 4)), r((4, 3, 3, 4)), r((6, 4, 5, 6)), r((6, 4, 4, 6)), r((6, 4, 4, 5))]
 (d, e, f):[1, 2, 5, 6]:sc:e
 (c, e, f):[1, 2, 5, 6]:sc:e
 (c, d, f):[1, 3, 4, 6]:sp:d
 (c, d, e):[1, 3, 4, 6]:sp:d
 (b, e, f):[1, 2, 5, 6]:sc:e
 (b, d, f):[1, 3, 4, 6]:sp:d
 (b, d, e):[1, 3, 4, 6]:sp:d
 (b, c, f):[1, 2, 5, 6]:sc:c
 (b, c, e):[1, 2, 5, 6]:sc:c
 (b, c, d):[1, 2, 5, 6]:sc:c
 (a, e, f):[1, 2, 5, 6]:sc:e
 (a, d, f):[1, 3, 4, 6]:sp:d
 (a, d, e):[1, 3, 4, 6]:sp:d
 (a, c, f):[1, 2, 5, 6]:sc:c
 (a, c, e):[1, 2, 5, 6]:sc:c
 (a, c, d):[1, 2, 5, 6]:sc:c
 (a, b, f):[1, 3, 4, 6]:sp:b
 (a, b, e):[1, 3, 4, 6]:sp:b
 (a, b, d):[1, 3, 4, 6]:sp:b
 (a, b, c):[1, 3, 4, 6]:sp:b
time:13.953[max]

７代替案の場合

　まず５代替案以下のときと同様の実験を途中まで行い，適当なところで打ち切って，はじめにでのべたように本プログラムでは下界で最初の1個を見つけたら，それを記録し，拡張する．


100:[r((6, 4, 4, 5, 5)), r((1, 1, 1, 1, 1)), r((1, 1, 1, 2, 1)), r((1, 1, 1, 2, 2)), r((1, 2, 1, 1, 1)), r((1, 2, 1, 2, 1)), r((1, 2, 1, 2, 2)), r((1, 2, 1, 3, 1)), r((1, 2, 1, 3, 2)), r((1, 2, 1, 3, 3)), r((1, 2, 2, 3, 3)), r((3, 1, 1, 1, 1)), r((3, 1, 1, 2, 1)), r((3, 1, 1, 2, 2)), r((3, 2, 1, 1, 1)), r((3, 2, 1, 2, 1)), r((3, 2, 1, 2, 2)), r((3, 2, 1, 3, 1)), r((3, 2, 1, 3, 2)), r((3, 2, 1, 3, 3)), r((3, 2, 2, 3, 3)), r((3, 3, 1, 1, 1)), r((3, 3, 1, 2, 1)), r((3, 3, 1, 2, 2)), r((3, 3, 1, 3, 1)), r((3, 3, 1, 3, 2)), r((3, 3, 1, 3, 3)), r((3, 3, 1, 4, 1)), r((3, 3, 1, 4, 2)), r((3, 3, 1, 4, 3)), r((3, 3, 1, 4, 4)), r((3, 3, 2, 3, 3)), r((3, 3, 2, 4, 3)), r((3, 3, 2, 4, 4)), r((3, 3, 3, 4, 4)), r((3, 4, 1, 1, 1)), r((3, 4, 1, 2, 1)), r((3, 4, 1, 2, 2)), r((3, 4, 1, 3, 1)), r((3, 4, 1, 3, 2)), r((3, 4, 1, 3, 3)), r((3, 4, 1, 4, 1)), r((3, 4, 1, 4, 2)), r((3, 4, 1, 4, 3)), r((3, 4, 1, 4, 4)), r((3, 4, 1, 5, 1)), r((3, 4, 1, 5, 2)), r((3, 4, 1, 5, 3)), r((3, 4, 1, 5, 4)), r((3, 4, 1, 5, 5)), r((3, 4, 1, 6, 1)), r((3, 4, 1, 6, 2)), r((3, 4, 1, 6, 3)), r((3, 4, 1, 6, 4)), r((3, 4, 1, 6, 5)), r((3, 4, 1, 6, 6)), r((3, 4, 1, 6, 7)), r((3, 4, 2, 3, 3)), r((3, 4, 2, 4, 3)), r((3, 4, 2, 4, 4)), r((3, 4, 2, 5, 3)), r((3, 4, 2, 5, 4)), r((3, 4, 2, 5, 5)), r((3, 4, 2, 6, 3)), r((3, 4, 2, 6, 4)), r((3, 4, 2, 6, 5)), r((3, 4, 2, 6, 6)), r((3, 4, 2, 6, 7)), r((3, 4, 3, 4, 4)), r((3, 4, 3, 5, 4)), r((3, 4, 3, 5, 5)), r((3, 4, 3, 6, 4)), r((3, 4, 3, 6, 5)), r((3, 4, 3, 6, 6)), r((3, 4, 3, 6, 7)), r((3, 4, 4, 5, 5)), r((3, 4, 4, 6, 5)), r((3, 4, 4, 6, 6)), r((3, 4, 4, 6, 7)), r((3, 4, 5, 6, 6)), r((3, 4, 5, 6, 7)), r((4, 3, 3, 4, 4)), r((4, 4, 3, 4, 4)), r((4, 4, 3, 5, 4)), r((4, 4, 3, 5, 5)), r((4, 4, 3, 6, 4)), r((4, 4, 3, 6, 5)), r((4, 4, 3, 6, 6)), r((4, 4, 3, 6, 7)), r((4, 4, 4, 5, 5)), r((4, 4, 4, 6, 5)), r((4, 4, 4, 6, 6)), r((4, 4, 4, 6, 7)), r((4, 4, 5, 6, 6)), r((4, 4, 5, 6, 7)), r((6, 4, 4, 6, 5)), r((6, 4, 4, 6, 6)), r((6, 4, 4, 6, 7)), r((6, 4, 5, 6, 6)), r((6, 4, 5, 6, 7))]
 (e, f, g): * :sp:f
 (d, f, g): * :sp:f
 (d, e, g): * :sc:e
 (d, e, f): * :sc:e
 (c, f, g): * :sp:f
 (c, e, g): * :sc:e
 (c, e, f): * :sc:e
 (c, d, g): * :sp:d
 (c, d, f): * :sp:d
 (c, d, e): * :sp:d
 (b, f, g): * :sp:f
 (b, e, g): * :sc:e
 (b, e, f): * :sc:e
 (b, d, g): * :sp:d
 (b, d, f): * :sp:d
 (b, d, e): * :sp:d
 (b, c, g): * :sc:c
 (b, c, f): * :sc:c
 (b, c, e): * :sc:c
 (b, c, d): * :sc:c
 (a, f, g): * :sp:f
 (a, e, g): * :sc:e
 (a, e, f): * :sc:e
 (a, d, g): * :sp:d
 (a, d, f): * :sp:d
 (a, d, e): * :sp:d
 (a, c, g): * :sc:c
 (a, c, f): * :sc:c
 (a, c, e): * :sc:c
 (a, c, d): * :sc:c
 (a, b, g): * :sp:b
 (a, b, f): * :sp:b
 (a, b, e): * :sp:b
 (a, b, d): * :sp:b
 (a, b, c): * :sp:b

別形式表示

上記のランキングリスト（許容リスト）の部分を，vr_data/1という事実節としてassertしておき，ランキングを代替案によって表示する．また文献にみられるような，代替案に番号で振った表示を併記し，整列しなおすと，以下のようになる．


/*

?- set_of_alternatives(A),vr_data(100:L),findall((M:O:R),
(member(R,L),possible_ranking_0(R,O),findall(K,
(member(X,O),nth1(K,A,X)),M)),W),
sort(W,W1),tell_goal('vr100.txt',
((member(Q,W1),nl,write(Q),fail);true)).
complete

A = [a, b, c, d, e, f, g]
L = [r((6, 4, 4, 5, 5)), r((1, 1, 1, 1, 1)), r((1, 1, 1, 2, 1)), r((1, 1, 1, 2, 2)), r((1, 2, 1, ..., ...)), r((1, 2, ..., ...)), r((1, ..., ...)), r((..., ...)), r(...)|...]
M = _G170
O = _G167
R = _G168
K = _G182
X = _G179
(...)

*/

% file output start time , [date(2006/6/19), time(1:35:12)]

%----------  start from here ------------%

[1, 2, 3, 4, 5, 6, 7]:[a, b, c, d, e, f, g]:r((1, 1, 1, 1, 1))
[1, 2, 3, 4, 6, 5, 7]:[a, b, c, d, f, e, g]:r((1, 1, 1, 2, 1))
[1, 2, 3, 4, 6, 7, 5]:[a, b, c, d, f, g, e]:r((1, 1, 1, 2, 2))
[1, 2, 4, 3, 5, 6, 7]:[a, b, d, c, e, f, g]:r((1, 2, 1, 1, 1))
[1, 2, 4, 3, 6, 5, 7]:[a, b, d, c, f, e, g]:r((1, 2, 1, 2, 1))
[1, 2, 4, 3, 6, 7, 5]:[a, b, d, c, f, g, e]:r((1, 2, 1, 2, 2))
[1, 2, 4, 6, 3, 5, 7]:[a, b, d, f, c, e, g]:r((1, 2, 1, 3, 1))
[1, 2, 4, 6, 3, 7, 5]:[a, b, d, f, c, g, e]:r((1, 2, 1, 3, 2))
[1, 2, 4, 6, 7, 3, 5]:[a, b, d, f, g, c, e]:r((1, 2, 1, 3, 3))
[1, 2, 4, 6, 7, 5, 3]:[a, b, d, f, g, e, c]:r((1, 2, 2, 3, 3))
[2, 1, 3, 4, 5, 6, 7]:[b, a, c, d, e, f, g]:r((3, 1, 1, 1, 1))
[2, 1, 3, 4, 6, 5, 7]:[b, a, c, d, f, e, g]:r((3, 1, 1, 2, 1))
[2, 1, 3, 4, 6, 7, 5]:[b, a, c, d, f, g, e]:r((3, 1, 1, 2, 2))
[2, 1, 4, 3, 5, 6, 7]:[b, a, d, c, e, f, g]:r((3, 2, 1, 1, 1))
[2, 1, 4, 3, 6, 5, 7]:[b, a, d, c, f, e, g]:r((3, 2, 1, 2, 1))
[2, 1, 4, 3, 6, 7, 5]:[b, a, d, c, f, g, e]:r((3, 2, 1, 2, 2))
[2, 1, 4, 6, 3, 5, 7]:[b, a, d, f, c, e, g]:r((3, 2, 1, 3, 1))
[2, 1, 4, 6, 3, 7, 5]:[b, a, d, f, c, g, e]:r((3, 2, 1, 3, 2))
[2, 1, 4, 6, 7, 3, 5]:[b, a, d, f, g, c, e]:r((3, 2, 1, 3, 3))
[2, 1, 4, 6, 7, 5, 3]:[b, a, d, f, g, e, c]:r((3, 2, 2, 3, 3))
[2, 4, 1, 3, 5, 6, 7]:[b, d, a, c, e, f, g]:r((3, 3, 1, 1, 1))
[2, 4, 1, 3, 6, 5, 7]:[b, d, a, c, f, e, g]:r((3, 3, 1, 2, 1))
[2, 4, 1, 3, 6, 7, 5]:[b, d, a, c, f, g, e]:r((3, 3, 1, 2, 2))
[2, 4, 1, 6, 3, 5, 7]:[b, d, a, f, c, e, g]:r((3, 3, 1, 3, 1))
[2, 4, 1, 6, 3, 7, 5]:[b, d, a, f, c, g, e]:r((3, 3, 1, 3, 2))
[2, 4, 1, 6, 7, 3, 5]:[b, d, a, f, g, c, e]:r((3, 3, 1, 3, 3))
[2, 4, 1, 6, 7, 5, 3]:[b, d, a, f, g, e, c]:r((3, 3, 2, 3, 3))
[2, 4, 6, 1, 3, 5, 7]:[b, d, f, a, c, e, g]:r((3, 3, 1, 4, 1))
[2, 4, 6, 1, 3, 7, 5]:[b, d, f, a, c, g, e]:r((3, 3, 1, 4, 2))
[2, 4, 6, 1, 7, 3, 5]:[b, d, f, a, g, c, e]:r((3, 3, 1, 4, 3))
[2, 4, 6, 1, 7, 5, 3]:[b, d, f, a, g, e, c]:r((3, 3, 2, 4, 3))
[2, 4, 6, 7, 1, 3, 5]:[b, d, f, g, a, c, e]:r((3, 3, 1, 4, 4))
[2, 4, 6, 7, 1, 5, 3]:[b, d, f, g, a, e, c]:r((3, 3, 2, 4, 4))
[2, 4, 6, 7, 5, 1, 3]:[b, d, f, g, e, a, c]:r((3, 3, 3, 4, 4))
[2, 4, 6, 7, 5, 3, 1]:[b, d, f, g, e, c, a]:r((4, 3, 3, 4, 4))
[4, 2, 1, 3, 5, 6, 7]:[d, b, a, c, e, f, g]:r((3, 4, 1, 1, 1))
[4, 2, 1, 3, 6, 5, 7]:[d, b, a, c, f, e, g]:r((3, 4, 1, 2, 1))
[4, 2, 1, 3, 6, 7, 5]:[d, b, a, c, f, g, e]:r((3, 4, 1, 2, 2))
[4, 2, 1, 6, 3, 5, 7]:[d, b, a, f, c, e, g]:r((3, 4, 1, 3, 1))
[4, 2, 1, 6, 3, 7, 5]:[d, b, a, f, c, g, e]:r((3, 4, 1, 3, 2))
[4, 2, 1, 6, 7, 3, 5]:[d, b, a, f, g, c, e]:r((3, 4, 1, 3, 3))
[4, 2, 1, 6, 7, 5, 3]:[d, b, a, f, g, e, c]:r((3, 4, 2, 3, 3))
[4, 2, 6, 1, 3, 5, 7]:[d, b, f, a, c, e, g]:r((3, 4, 1, 4, 1))
[4, 2, 6, 1, 3, 7, 5]:[d, b, f, a, c, g, e]:r((3, 4, 1, 4, 2))
[4, 2, 6, 1, 7, 3, 5]:[d, b, f, a, g, c, e]:r((3, 4, 1, 4, 3))
[4, 2, 6, 1, 7, 5, 3]:[d, b, f, a, g, e, c]:r((3, 4, 2, 4, 3))
[4, 2, 6, 7, 1, 3, 5]:[d, b, f, g, a, c, e]:r((3, 4, 1, 4, 4))
[4, 2, 6, 7, 1, 5, 3]:[d, b, f, g, a, e, c]:r((3, 4, 2, 4, 4))
[4, 2, 6, 7, 5, 1, 3]:[d, b, f, g, e, a, c]:r((3, 4, 3, 4, 4))
[4, 2, 6, 7, 5, 3, 1]:[d, b, f, g, e, c, a]:r((4, 4, 3, 4, 4))
[4, 6, 2, 1, 3, 5, 7]:[d, f, b, a, c, e, g]:r((3, 4, 1, 5, 1))
[4, 6, 2, 1, 3, 7, 5]:[d, f, b, a, c, g, e]:r((3, 4, 1, 5, 2))
[4, 6, 2, 1, 7, 3, 5]:[d, f, b, a, g, c, e]:r((3, 4, 1, 5, 3))
[4, 6, 2, 1, 7, 5, 3]:[d, f, b, a, g, e, c]:r((3, 4, 2, 5, 3))
[4, 6, 2, 7, 1, 3, 5]:[d, f, b, g, a, c, e]:r((3, 4, 1, 5, 4))
[4, 6, 2, 7, 1, 5, 3]:[d, f, b, g, a, e, c]:r((3, 4, 2, 5, 4))
[4, 6, 2, 7, 5, 1, 3]:[d, f, b, g, e, a, c]:r((3, 4, 3, 5, 4))
[4, 6, 2, 7, 5, 3, 1]:[d, f, b, g, e, c, a]:r((4, 4, 3, 5, 4))
[4, 6, 7, 2, 1, 3, 5]:[d, f, g, b, a, c, e]:r((3, 4, 1, 5, 5))
[4, 6, 7, 2, 1, 5, 3]:[d, f, g, b, a, e, c]:r((3, 4, 2, 5, 5))
[4, 6, 7, 2, 5, 1, 3]:[d, f, g, b, e, a, c]:r((3, 4, 3, 5, 5))
[4, 6, 7, 2, 5, 3, 1]:[d, f, g, b, e, c, a]:r((4, 4, 3, 5, 5))
[4, 6, 7, 5, 2, 1, 3]:[d, f, g, e, b, a, c]:r((3, 4, 4, 5, 5))
[4, 6, 7, 5, 2, 3, 1]:[d, f, g, e, b, c, a]:r((4, 4, 4, 5, 5))
[4, 6, 7, 5, 3, 2, 1]:[d, f, g, e, c, b, a]:r((6, 4, 4, 5, 5))
[6, 4, 2, 1, 3, 5, 7]:[f, d, b, a, c, e, g]:r((3, 4, 1, 6, 1))
[6, 4, 2, 1, 3, 7, 5]:[f, d, b, a, c, g, e]:r((3, 4, 1, 6, 2))
[6, 4, 2, 1, 7, 3, 5]:[f, d, b, a, g, c, e]:r((3, 4, 1, 6, 3))
[6, 4, 2, 1, 7, 5, 3]:[f, d, b, a, g, e, c]:r((3, 4, 2, 6, 3))
[6, 4, 2, 7, 1, 3, 5]:[f, d, b, g, a, c, e]:r((3, 4, 1, 6, 4))
[6, 4, 2, 7, 1, 5, 3]:[f, d, b, g, a, e, c]:r((3, 4, 2, 6, 4))
[6, 4, 2, 7, 5, 1, 3]:[f, d, b, g, e, a, c]:r((3, 4, 3, 6, 4))
[6, 4, 2, 7, 5, 3, 1]:[f, d, b, g, e, c, a]:r((4, 4, 3, 6, 4))
[6, 4, 7, 2, 1, 3, 5]:[f, d, g, b, a, c, e]:r((3, 4, 1, 6, 5))
[6, 4, 7, 2, 1, 5, 3]:[f, d, g, b, a, e, c]:r((3, 4, 2, 6, 5))
[6, 4, 7, 2, 5, 1, 3]:[f, d, g, b, e, a, c]:r((3, 4, 3, 6, 5))
[6, 4, 7, 2, 5, 3, 1]:[f, d, g, b, e, c, a]:r((4, 4, 3, 6, 5))
[6, 4, 7, 5, 2, 1, 3]:[f, d, g, e, b, a, c]:r((3, 4, 4, 6, 5))
[6, 4, 7, 5, 2, 3, 1]:[f, d, g, e, b, c, a]:r((4, 4, 4, 6, 5))
[6, 4, 7, 5, 3, 2, 1]:[f, d, g, e, c, b, a]:r((6, 4, 4, 6, 5))
[6, 7, 4, 2, 1, 3, 5]:[f, g, d, b, a, c, e]:r((3, 4, 1, 6, 6))
[6, 7, 4, 2, 1, 5, 3]:[f, g, d, b, a, e, c]:r((3, 4, 2, 6, 6))
[6, 7, 4, 2, 5, 1, 3]:[f, g, d, b, e, a, c]:r((3, 4, 3, 6, 6))
[6, 7, 4, 2, 5, 3, 1]:[f, g, d, b, e, c, a]:r((4, 4, 3, 6, 6))
[6, 7, 4, 5, 2, 1, 3]:[f, g, d, e, b, a, c]:r((3, 4, 4, 6, 6))
[6, 7, 4, 5, 2, 3, 1]:[f, g, d, e, b, c, a]:r((4, 4, 4, 6, 6))
[6, 7, 4, 5, 3, 2, 1]:[f, g, d, e, c, b, a]:r((6, 4, 4, 6, 6))
[6, 7, 5, 4, 2, 1, 3]:[f, g, e, d, b, a, c]:r((3, 4, 5, 6, 6))
[6, 7, 5, 4, 2, 3, 1]:[f, g, e, d, b, c, a]:r((4, 4, 5, 6, 6))
[6, 7, 5, 4, 3, 2, 1]:[f, g, e, d, c, b, a]:r((6, 4, 5, 6, 6))
[7, 6, 4, 2, 1, 3, 5]:[g, f, d, b, a, c, e]:r((3, 4, 1, 6, 7))
[7, 6, 4, 2, 1, 5, 3]:[g, f, d, b, a, e, c]:r((3, 4, 2, 6, 7))
[7, 6, 4, 2, 5, 1, 3]:[g, f, d, b, e, a, c]:r((3, 4, 3, 6, 7))
[7, 6, 4, 2, 5, 3, 1]:[g, f, d, b, e, c, a]:r((4, 4, 3, 6, 7))
[7, 6, 4, 5, 2, 1, 3]:[g, f, d, e, b, a, c]:r((3, 4, 4, 6, 7))
[7, 6, 4, 5, 2, 3, 1]:[g, f, d, e, b, c, a]:r((4, 4, 4, 6, 7))
[7, 6, 4, 5, 3, 2, 1]:[g, f, d, e, c, b, a]:r((6, 4, 4, 6, 7))
[7, 6, 5, 4, 2, 1, 3]:[g, f, e, d, b, a, c]:r((3, 4, 5, 6, 7))
[7, 6, 5, 4, 2, 3, 1]:[g, f, e, d, b, c, a]:r((4, 4, 5, 6, 7))
[7, 6, 5, 4, 3, 2, 1]:[g, f, e, d, c, b, a]:r((6, 4, 5, 6, 7))
%----------  end of data ------------%
% file output end time , [date(2006/6/19), time(1:35:12)]

実験に使用したプログラム

実験に使用したプログラムsproof_f.plを示す．
実験用コード（○）．
上の実験では，本ウェッブサイトに掲載されている menu.pl（○）を，一緒にロードして使います．
上の実験後，ランキングを事実節に一括変換するようにプログラム修正したところ，少しだけ，早くなりました．以前はランキングを一いち再帰で作成していたためであろうと思われます．
お断り・お詫び：

８代替案は，いきなりメモリあふれというのは，一応，解決してありますが，初期解はまだ求めていません．
今回の実験以外に，最近半年の研究で累積的に拡張しており，長くなっています．
部分的にデモ結果や未完成のコードが含まれています．
多数決SDFのコードと実験結果デモを追加しました(6/29)
マニュアルはありません．

参考文献


[Arrow 63] Arrow, K.
 Social Choice and Individual Values, Yale University Press, 1963.
[Sen 82] Sen, A.,
 Choice, Welfare and Measurement, The MIT Press, 1982.
[Sen 69] Sen, A. and Pattanaik, P. K.
 Necessary and sufficient condition for rational choice under majority decision,
 Journal of Economic Theory, Vol. 1: 178-202, 1969.
[Sen 66] Sen, A.
 A possibility theorem of majority decisions,
 Econometrica, Vol. 34(2): 490-506, 1966.
[Ward 65] Ward, B.
 Majority voting and alternative forms of public enterprise,
 In J. Margolis (ed.), The Public Economy of Urban Communities.
 Johns Hopkins Press, Chapter 6, pp. 112-126, 1965.
[Inada 64] Inada, K.,
 A note on simple majority decision rule,
 Econometrica, Vol. 32: 525-531, 1964.
[Inada 69] Inada, K.,
 On the simple majority decision rule,
 Econometrica, Vol. 36: 490-506, 1969.
[Fishburn 97] Fishburn, P.
 Acyclic sets of linear orders, 
 Social Choice and Welfare 14:113-124, 1997.
[Fishburn 02] Fishburn, P.
 Acyclic sets of linear orders: A progress report, 
 Social Choice and Welfare 19:431-447, 2002.
[Craven 96] Craven, J.
 Majority-consistent preference orderings, 
 Social Choice and Welfare 13:259-267, 1996.
[Abello 85] Abello, J.
 Intrinsic limitations on the majority rule, an algorithmic approach, 
 SIAM J Alg Discrete Meth 6:133-144, 1985.
[Abello 91] Abello, J.
 The weak Bruhat order of S_sigma, consistent sets, and Catalan numbers,
 SIAM J Alg Discrete Math 4(1):1-16, 1991.
[Raz 00] Raz R. 
 VC-dimension of sets of permutations,
 Combinatorica 20(2): 241-255, 2000.
[Vickrey 60] Vickrey, W.(1960).
 Utility, strategy, and social decision rules,
 Quarterly Journal of Economics, Vol. 74(4): 507-535.
[Kuga 74] Kuga, K, and Nagatani, H. (1974). 
 Voter antagonism and the paradox of voting, 
 Econometrica 42(6): 1045-1067.

追記・修正事項

2006.6.30. 上界・下界の研究の文献
2006.8.27. Vickrey(1960)への言及
2006.9.1. Kuga and Nagatani(1974)への言及．等幅フォントおよび表スタイルの変更．