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


2006.6.19

犬童健良

関東学園大学経済学部


はじめに


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

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

 ラテン方格とは,あるトリプルが,すべての3順位をもれなくとる ランキングの最小集合である.トリプル{x,y,z}とすると, {(x,y,z),(y,z,x),(z,x,y)}および{(x,z,y),(y,x,z),(z,y,x)} の2つがラテン方格である.
 
 ラテン方格なしの条件は,ランクの分布がぎっしりつまって おらず,どこかにホールがあることを意味する.すなわち, ある代替案があるトリプルで, 1位にならない場合,2位にならない場合,および3位にならない 場合のいずれかにあたることに等しい. これは価値制限 (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
 
 以下の実験用コード内では,3代替案の場合を基準に, 各ランキングをシンボルで名前付けした.3代替案の場合は, 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
?- 


 また,経済学の文献では, それぞれ1位にならない場合を 単谷性(single-cavedness; sc),3位にならない場合を単峰性 (single-peakedness; sp),および2位にならない場合を, 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代替案の 場合の最大サイズ4にあたる相対ドメイン(Figure 2)を割り当てていけば いいのではないかと思うだろうが,これは効率的な 解き方ではない. Fishburnは,比較的少ない代替案 (16以下)のときに(たぶん最大の)非循環的集合を求める ヒューリスティックス,Alternating Schema(以下スキーマAと呼ぶ) を提案した.トリプルにおいて, もとの代替案のリストでの順番が奇数の場合,それを トップランク落ちに,また偶数のときはボトムランク落ち にする(またはこれらの逆)という制約をつける. 6代替案までは,スキーマAで最大の非循環的集合を 求めることができる(Fishburn, 2000).

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

[1]一方上界について はもっと曖昧であり,Raz(2000)が帰納的確率(VC次元)の議論によって, 未知正定数cに対してc^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を用いてもとまる(真の)最大長は, 4代替案で9,5代替案で20, 6代替案で45であった.また7代替案では100となるが, これが真に最長かどうかはわかっていない.

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

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

 なお私のノートPC (SONY VAIOやSotecの数年前のもの)だと,7代替案で79あるいは82 が,生成できる限界であった.途中までのデータを見ると, 長さ64の最初の解から,1ランキングずつ追加しているだけだったので, 途中までで得た長さk−1の結果にもとづき,上記の条件を満たす ランキングを追加して拡張するようにしたところ,長さ100の 領域を得た.
 以下は4〜7代替案数のときに,それぞれ最初に見つけた スキーマAによる最大の非循環的集合のみを示す.

4代替案の場合


 本システムは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という名のファイル へ出力される.以降の5代替案以上の実験についても,同様の 方法で行う.ただし,7代替案のときは,途中で打ち切って, モードを切り替えて再出発する必要がある.



?- 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 ------------%


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

5代替案の場合




?- 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]

6代替案の場合




?- 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]

7代替案の場合


 まず5代替案以下のときと同様の実験を途中まで行い, 適当なところで打ち切って,はじめにでのべたように 本プログラムでは下界で最初の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() を,一緒にロードして使います.
上の実験後,ランキングを事実節に一括変換するように プログラム修正したところ,少しだけ,早くなりました. 以前はランキングを一いち再帰で作成していたため であろうと思われます.
お断り・お詫び:

参考文献


[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)への言及.等幅フォントおよび表スタイルの変更.

lastely revised: 30 Jun 2006 18:03, 27 Aug 2006 16:06, 1 Sep 2006 10:25 Copyright (c) 2006 Kenryo INDO