Bemerkungen zu metrischen Abst immungssystemen

Von Gfi~TER PICKERT

Herrn EMANUET, SPER~ER zum 70. Geburtstag

1. Im folgenden ist P stets eine endliehe niehtleere Menge und !~ eine niehtleere Menge yon Teilmengen von P. Das Paax (P, ~ ) heil3t Abstimmungssystem (AS; siehe [2], [3]), wenn es die folgenden beiden Bedingungen (fiir alle K, K') erftillt :

(I) K' ~ K c P, K ' e ~ = > K e ! ~ ;

(C) K e!~ =~ P \ K ~ .

Dabei kann (C) aueh ersetzt werden dureh

(D) K,K ' e ~ = ~ K n K ' ~O.

Die Wortwahl erkl~rt sieh daxaus, dal3 unter den Bedingungen (I), (C) ein Paar (P, !IB) in dem folgenden Siim ein praktizierbaxes Abstimmungs- verfahren in einer Personenmenge P besehreibt: Ein Antrag gilt genau dann als angenordmen, were1 sieh alle Personen einer Menge K e ~i~, einer Gewinnkoalition (daher die Buehstaben !~B, K !) daf'tir ausspreehen; Abstimmungsverfahren, bei denen es aueh auf Stimmenthaltungen an- kommt, werden dadurch allerdings nicht erfailt. In der Spieltheorie wer- den Abstimmungssysteme als ein]ache Spiele bezeiehnet, wobei man allerdings statt der Menge !~B ihre Indikatorfunktion (bez. der Potenz- menge von P) verwendet und den Fall ~ ~ r einbezieht (siehe [1], S. 159). Nach NEUMAIER [2] wird (P, ~B) Inklusionssystem (IS) genannt, wenn (I) gilt.

Im folgenden sei s (Stimmenverteilung) stets eine Abbildung yon P in die Menge der nichtnegativen reellen Zahlen mit

(N) ~(P) = 1,

wobei allgemein ftir K c__ p

(1) 8(K) = ~ 8(~) x e K

13 Hbg. Math. Abh., Bd. XLIV

194 Giinter Pickert

gesetzt �89 (man beachte im folgenden den Unterschied zwischen s(K) und sK-----{s(x)]xeK}!). Ferner sei q stets eine niehtnegative reelle gaM ~ I. Mit

(2) !~,.q = { g [K _~ P, s ( g ) ~ q}

erhMt man dann das IS (P, !~f~,.q); diese IS heiflen metrisch (in [2] ohne (N), dafttr q ~ s (P) start q ~ 1 ; in [3] werden die metrisehen AS ,,M- darstellbar" genarmt). Setzt man

(3) u , ---- max {s(K) [ P _ K r !~}

(4) o, = rain {s (g) ] g e ~ }

(die Abh/~ngigkeit yon ~ wird einfaehheithalber in den Bezeichnungen nieht angegeben), so gilt offenbar

(5) ~ = ~ , , ~ ~ u , < q _ ~ o , .

Somit �89 (P, ~ ) genau dann ein metrisches IS, wenn es s mit u, < o, gibt, und es gilt dann ~ ----- ~ . a genau ffir die q E ]u,, o,](~=0). Ferner erweist sich (P, !~) genau dann sogar als metrisches AS, wenn es eine Stimmenverteflung s mit u, < o, > �89 gibt; denn aus dieser Ungleichung ergibt sich K ~ 9 =~ s(P \ K) = s (P) - - s (K) ~ 1 - -o , < �89 < o, =~ P k K ~ ![9, also (C), w/ihrend man be�89 u, < o, ~ �89 ein K e ~ mit s (K) ~ �89 und damit s(P \ K) = s(P) - - s(K) ~_ �89 ~ o,, also P \ K e !fi~ im Wider- sprueh zu (C) erh/flt. Be�89 einem metrischen AS (P, !~9,,~) kann man also �89 q > �89 voraussetzen. In der Spieltheorie werden die metrischen AS als gew~htete Majorit~tsspiele bezeichnet, allerdings ohne (N) und q ~ s(P) (siehe [1], S. 158).

Wahrend (5) die ~mderungsm6gliehkeiten ftir den Mehrheitsquotienten q besehreibt, wird eine entsprechende MSgliehkeit fiir die St immenver. teilung s angegeben durch den

Approx imat ionssa tz . Zu jedem metrischen IS (P, ~B) und s mit u, < o, gibt es q derart, daft ~ = !~,,.q gilt/i~r jede Abbildung s* yon P in die Menge der nichtnegativen reellen Zalden mit s*(P) = 1 und

1 (6) I s ( x ) - - s * ( x ) ] < ~ l p ] ( o s - - u , ) /aralle x e P .

B e w e i s . Aus (6) erh/flt man [s(K)--s*(K)[ < � 89 ftir alle K _ P. Daxaus folgt nun

s* (K) > s (K) - - �89 (o, - - u,) ~ o, - - �89 (o, - - u.) ---- �89 (o. -b u.)

ffir alle K e ~ und

s*(K) < s(K) + �89 _< u, -b �89 = �89 + u,)

Bemerkungen zumetr ischenAbst immungssystemen 195

ftir a l e k ~ !~, so dai3

�89 + u=) e ] u . , o . [

gilt und somit nach (5) ~ = ~=., q ftir q = �89 (o= + u=) ist.

Zusammen mit (5) zeigt der Approximationssatz insbesondere, dab man bei metrisehem IS (P, ~!i~=,q) stets die 8(x) (x e P) und q als rationale Zahlen voraussetzen daxf.

Die Schranke in (6) ist keineswegs optimal; so karm man sie wegen 1

8(P)----8*(P)----1 bei IPI > 1 dureh 2 ( i p l _ 1) (o=--u=) ersetzen. Aber

aneh bei dieser ~mderung yon (6) gibt es noch 8, 8", die (6) nieht er- fiiUen und f'ttr die sogar u= = us., o= -- o=. gilt. Um das zu zeigen, wi~l t man a, b mit

1 2 a ~ < a < y , a < b ~ l - - y

und setzt P ~-- {I, 2, 3}, ~ ---- {{1, 2}, {1, 3}, {1, 2, 3}},

8(1)----a, 8(2) " - -b - -a , 8(3)---- l - - b ,

8 " ( 1 ) = 1 - - a , 8*(2) = a + b - - 1 , 8*(3) = 1 - - b .

Dann gilt u= = u=. = a, o= = o8. = b, 8(1) - - 8 " ( 1 ) ---- 2 a - 1, und wMflt man nun a _~ ~ ( < ~), so folgt daher 8(1) - - 8 " ( 1 ) ~ t ( o = - u=).

2. Eine Permutation 9 yon P mit 9 K e !~ ftir alle K e !~ wird als Automorphismus yon (P, !~) bezeiehnet; wegen der Endliehkeit yon !~ ist dann such 9-1 ein Automorphismus. Existenz yon Automorphismen drtiekt Symmetrieeigenschaften von (P, ~ ) aus. Gewisse Symmetrie- eigenschaften eines metrisehen IS lassen nun vermuten, dab man eino Stimmenverteilung 8 mit konstanten Einschrgnkungen 81K auf ge- eigneten (durch die Symmetrieeigensehaften bestimmte) Teilmengen K w~hlen kann. Das besagt der

Symmetriesatz. Ist ~ eine Klasseneinteilung yon P derart, daft /i~r a, b e K e ~, a ~ b stets

q~,b = {(a, b), (b, a)} w {(x, x) I x e P\{a, b}}

ein Automorphismus des metrischen IS (P, !~) ist, 8o gibt e8 8, q mit = !~=,q und ]constanten Einschrdnkungen 8[K /at alle K e ~.

B e w e i s . Es sei a, b e K E ~, a =~ b, 9 = ~ . b und u=< o= mit (3), (4). Wir definieren nun eine Stimmenverteilung 8' durch

Is(x) ffir x ~ P\{a, b}, 8'(x) =|�89 + 8(b)) flu: x e { a , b }

13"

196 Giinter Picker~

und haben dalm fiir alle K _c p

{a,b} ~ K oder (a,b} c_ P \ K :~ 9 K = K , s ' ( K ) ----8(K),

a e K , b C K ~ ~ K : ( K \ { a } ) k J { b } , 8 ' (K)

= s (K) - -8 (a ) + �89 ~-s(b)),

also in jedem Fal l s' (K) ---- �89 + 8(q~K)).

Da ~ Automorphismus yon (P, ~ ) ist, folgt daxaus us' =< us, os ~_ o s , ,

also

0 < os - - us --<_ os, - - ~t,,.

W e nde t man nun dieses yon s zu s' f i ihrende Verfallren bei fes tem K ~ ~ for tgesetzt an mid zwar jeweils fiir a, b e K, a ~= b mi t

Js(b)--s(a)l >= Js(y)--8(x)J ftir alle x, y e K ,

ausgehend yon einem s (~ mi t us~o ~ < o#~, so en t s teh t eine Folge

(8(n))n=0, 1 . . . . m a t

0 < %o) - - u#~ ~ %,~ - - %(,~ (n = 1, 2 . . . . ) (v)

u n d

f~r (n ---- O, 1 , . . . )

un = rain s(nJK, vn = m a x s(n)K.

Die mono ton fallende Folge ( v . - u.).=o, ~ . . . . erweist sich nun als Null- folge: Zu u = u , , v ---- v, mi t u < v setzt m a n d ---- ~ (v - - u) und n i m m t o . B . d . A .

I { x e K [ u < s(-,(x) < u + d } l < J { x e K I v - - d < s , - , (x) < v } l

an; wegen

u < u ' , v - - d < v ' = > u + d - - - - � 8 9 1 8 9

gibt es dalm m > n mi t s(~)K c [u -4- d, v], also u + d ~ u~ , v~ < v und daher

v , . - -u , . <= ~(v . - -u . ) .

Wegen der Nullfolgeneigenschaft gibt es n mi t

1 (s) v. - - u . < ~ (%0, - - u,,o,).

Weil wegen s(")K __ [us, v.] anch ~ s ( " ) ( K ) e [u,~, v,~] ist, gilt fiir die durch

[ s("~(x) ftir x e P \ K , =/;_

( I / ~ J

Bemerkungen zu metrischen Abstimmungssystemen 197

definierte Stimmenverteilung 8" nach (7), (8)

[8(~)(x)--s*(x)[<2--~--pl(%,.,--u,.)) fiiralle x e P .

Nach dem Approximationssatz (mit s (~) start s) gibt es also q* mit ---- !~8.,q.. Dabei ist s*lK konstant und s* I P \ K : 8 ~ ) I P k K

-~ 8(~ Daher laBt sich dieses Verfahren nacheinander fox alle K e ~ anwenden, wobei schliel~lich s, q mit den verlangten Eigenschaften entstehen.

3. Ein metrisches IS (P, !~) mit konstanter Stimmenverteilung 1

(wegen (N) also s(x)=J-P-II fOx alle x e P) kann offenbax durch die natOxliche Zahl (~= 0)

k : m i n { I g I I k e!~}

beschrieben werden:

~ i ~ = { g l g c _ P , [g[ ~ k};

ferner gilt dafiir mit v = [P[ nach (3), (4)

k k - - 1 Os ~ - - , ~s - ~ - ' - - , v v

so dab genau im Falle v < 2k ein AS vorliegt. Neuerdings werden in der Hochschulgesetzgebung solche AS dadurch modifiziert, da~ man die Belange einer Teilmenge P' (C P) besonders beriicksichtigt und dazu mit einer nattirlichen Zahl k' und

O) k' <=v' = IP'I, ~' ~

die Menge der Gewinnkoalitionen als

( lo) !~ -={KIK c p, IKI ~ k , IKc~P' I ~ k ' }

bestimmt. Bei P ' C P und natiirlichen Zahlen k, k' ( ~ O) mit k ~ v = I P ] und (9) liefert (10) offenbax stets ein IS (P, ~ ) , und man stellt leicht lest, dal~ dieses genau sogar ein AS ist, wenn v ~ 2k oder v ' ~ 2k' gilt.

Wir untersuchen nun im folgenden, warm (10) ein metrisches IS liefert. Setzt man

1 fOx So(X) = V

so gilt offenbar mit (10)

(10

x e P, So(X)= fOx x e P \ P ' ,

198 G~inter Pickert

und man erh~t

~ $ 0 , V"'~ �9

Fiir K _c p, ]K] _~ k ergibt sich

I g n P ' l = l K l + I P ' l - - I K u P ' l ~ k + r

so dab in (10) im l~alle k + v ' - - v ~ k' die le~zte Bedingung tiber- flttssig wird:

(13) v - - k __< v' - - ~' ~ ~ = ~ .o ,~ .

Wegen (12), (13) diirfen wir im folgenden

(14) k' < k , v - - k > v ' - - k ' ( ~ _ O )

voraussetzen.

Naeh (10) wird mit ~ = { P', P \ P'} die Voraussetzung des Symmetrie- satzes erftillt. Ist (P, ~ ) metrisch, so gibt es daher eine Stimmen- verteilung s mit (3), (4), u~ < o, mad reelle Zahlen w, w' e [0, 1] mit

(15) s(x) = { ww' ftirfiir xeP\P',x~p,

und

(16) w ( v - v') q- w' v' = 1.

Zur Bereehnung yon o8 bestimmen wit zuerst die (bez. der Inklusion) mirdmalen Gewinnkoalitionen. Offenbar ist K( _~ P) im l~alle

(17) Ig l = k, IP' c~ g I > k'

eine solehe. Bei I g l > 2, l e ' n K I _~ r besagt die Minimaliti~t yon K abet

I P' n (K\{x}) I < k' f'ur jedes x e K

und damit K c p ' , I e ' n K I = k', was abet wegen k' ~ k < I K I un- mSglich isr Somit beschreibt (17) gerade die minimalen K(e !~), und man erhi~lt wegen (15), (14)

(18) o8 <= ( k - k')w + k' w'

sowie im Falle w ~_ w' sogar

(18') 0, = (k - - k')w + k'w'.

Nach (1O) haben die K ~ !~ entweder die Eigensehaf~ ]K I < k oder abet die Eigenschaft [K] ~ k, IP' n g I < k'. Im zweiten Fall nirnmr s(g)

Bemerkungert zu metrischen Abstimmungssystemen 199

offenbar sein Maximum fiir [P' (~ K I = k' - - 1, I ( P \ P ' ) t~ K I = v - - v' an (wegen (14) ist tats~chlich I t ' - -1 + v - - v ' ~ k) , so dab sich nach (15)

u, = max {(v - - v ' ) w + (k' - - 1)w', m}

~ t m = max (8 (K) I K -~ P, I K l = k - 1} er#bt . ~, < o, besag* d~her

(19) ( v - - v ' ) w + ( k ' - - l ) w ' < o , , m < o , .

Wegen (18) liefert der erste Tell yon (19)

(20) ((v - - k) - - (v' - - ~'))w < w',

wegen (14) insbesondere

(20') w < w'.

Wegen (20') gilt (18'), und (20) ist daher gleiehwertig mit dem ersten Teil yon (19). Nach (16), (20') erhglt man nun

falls k - 1 m - - ~ , __[vw + ( k - - l - - v ' ) w falls k - - l > v ' .

Somit wird der zweite Teil yon (19) wegen (18') zu

( k - - k ' - - l ) w ' < ( k - - k ' ) w , falls k - - 1 ~_v', (v' - - k')w' < (v' - - k' + 1)w, falls k - - 1 > v'.

Daher besagt (19), also u, < o, (wegen (20') is* w' > Ol)

|k-r-~_ t w ) k - - k ' , falls k - - l ~ _ v ,

(21) (,., - - k) - - ( r - - k ' ) > ~ > | , , ' - - k ' ( ~ - - - - ~ T - I ' falls k - - l > v ' .

Zusammen mit (16) ist (21) offenbar genau dazm dutch Zahlen w' [0, 1] erftillbar, wenn W,

[k_-r~! 1 ) k - - k , , falls k ~ l _ ~ v ,

(V l ~ ) - (V ' I ~ ' ) > / ~ v ' - - ( -- / v - - k ' + l ' falls k - - l > v ' .

Das forint man leieht um zu

( k - - k ' - - l ) ( ( v - - k ) - - ( v ' - - k ' ) - - l ) < 1, falls k - - 1 ~ v ' ,

(v' - - k ' ) ( ( v - - k) - - (v' - - k ' ) - - l ) < 1, falls k - - 1 > v ' .

Da die hier links auftretenden Faktoren samtlich nichmegative ganze Zahlen sind, kann eine dieser Ungleichungen nur dana bestehen, wenn einer der Faktoren = 0 ist. Damit erhalten wir insgesamt den

200 Giinter Piekert

Satz 1. Das durch (10) beschriebene IS (P, !~) ist abgesehen yon den in (12), (13) angegebenen Fallen genau dann metrisch, wenn eine der [olgenden Bedingungen er/fdlt ist :

a) v - - k = v ' - - k ' + 1,

b) k - - - - F + 1 ,

e) v' = F .

Diese drei Bedingungen schliel3en sich gegenseitig nicht aus; sie sind sogar (genau) im Fa l l ev ~ 3, k ---- v - - 1, v' ---- k' = v - - 2 s/imtlich er- fiillt. Bedingung c) besagt K _ P ' ffir alle K e ~ : Jedes Element yon P' besitzt Vetorecht. So ist ja auch das (nicht durch Stimmenverteilung und Mehrheitsquotienten besehriebene) AS im Sicherheitsrat der Ver- einten Nationen metrisch.

Far die Bestimmung der Stimmenverh/~ltnisse w liefert (21) in den W t

drei F/~llen:

: 1 falls k - 1 < v', w k - - k "

a) 1 > ~ r > 1 falls k - - 1 > v ' , v - - k '

1 w b) v__v, l > ~ > O ,

1 w c) ~--~-X > ~ - > o.

Die minimalen Gewinnkoalitionen des durch (10) gegebenen IS (P, !~) haben naeh (17) si~mtlieh dieselbe Elementeanzahl k. Das legt die Frage nahe, unter welchen Bedingungen far v, k, v', k' die •enge ~t~ o dieser minimalen Gewinnkoalitionen eine taktisvhe Konfiguration (P, ~o) liefert. Zur Beantwortung mfissen wir far x e P

r~ = [{K l x e K e !~o} I

untersuehen. Da ~----{P', P \ P ' } die Voraussetzungen des Symmetrie- satzes erfiillt, also ?a,b sowohl ftir {a, b} _~ P ' wie ftir (a, b} c p \ p ' ein Automorphismus yon (P, ~t~) und damit yon (P, !l~0) ist, gibt es jeden- falls Zahlen r, r' mit

r ffir x e P \ P', r' far x ~ P ' ;

genau im Fall r' = r ist (P, ~o) eine taktisehe Konfiguration. Zur Be- st immung yon r' - - r = r b - - r~ (far a ~ P \ P ' , b E P') verwenden wit die im Symmetriesatz erkl/~rte Permutation ~0----~a,b yon P und die Mengen

9 A = { K l a e g e ~ o }, ! ~ = { K i b e K e ~ i ~ o }

Bemerkungen zu metrischen Abstimmtmgssystemen 201

mit ]gX [ = r~ = r, ! ~ t -= r~ = r' sowie die durch

~ ( K ) = q K Ftir alle K c p

definierte involutorische Permutat ion ~ der Potenzmenge yon P. Wegen ] P ' n q J K ] > l P ' n K l > k ' fiir K z ~ hat man nach (17) ~ und daher

(22)

Wir beweisen nun

(23) K e ~ \ ~ p ~ .r I P ' n K [ = k ' , a~iK, K e ~ .

Da fiir K e ~ o wegen (17) I P ' n K ] # k ' dasselbe besagt wie ]P' n K 1 > k', geniigt dazu offenbar der Nachweis tier folgenden Be- ziehungen:

a e K e ~ ~ K e v29~ ,

K e ~ , I P ' n K l > k ' ~ K e ~ 9 ~ ,

a~.Kc~pg~ ~ IP' n K I > k'.

Zur ersten: Bei a e K E ~ ist {a, b} c K ~ 9~ und daher

K -= q K = ~(K) r ~9~.

Zur zweiten: Aus K E ~ ergibt sich a e ~K und I ~ g l = I K I = k, ferner I p ' n ~ K ] > ! P ' n g l - - l > k ' wegen I P ' n K l > k ' und somit nach (17) ~(K) ---- ~0K e 9X und daher K = ~v(v2(K)) e v29~,

Zur drit ten: Aus K e~gX ergibt sich ~K = ~(K)eg~ und wegen aCK, b e K ( e ~ c _ ~ ) hat man K=(qJK\{a})u{b} und daher P ' n K = (P' n ~0K) w {b}, also

]P' n K I-=lP' n ~ g [ + l > k ' - 4 - l > k ' .

~ach (23) ruff nun

K --> ((P' n K) \ {b}, K\P')

eine Bijektion von ~\~9~ auf das cartesische Produkt der Menge der (k' - - 1)-elementigen Teilmengen von P' \(b} und der Menge der (k - - k')- elementigen Teilmengen yon P\(P' u {a)) hervor. Daher ergibt (22)

k- -k ' "

Daraus nun erhalt man wegen (13)

202 Giinter Pickert, Bemerkungen zu metrischen Abstimmungssystemen

Satz 2. Die minima~n Gewinnkoalitionen des dutch (10) gegebenen I S (P, ~ ) Bind genau dann die Bl6cke einer taktischen Konfiguration, wenn v - - k ~_ v' - - k' gilt und damit die minimalen qewinnIcoalltionen gerade die s5mtlichen k-elementigen Teilmengen yon P sind.

Literatur

[1] E. BURGER, Einfiihrung in die Theorie der Spiele. Berlin 19668. [2] A. NEU~AmR, Inklusions- und Abstimmungssysteme. Math. Zeltschr. 141

(1975) 147--158. [3] G. PXO~RT, Abstimmungssysteme und taktische Konilgurationen. Erscheint

in Colloquio internazionalo sulle Teorie Combinatorie, Atti dei Convegni Lincei, Roma 1975.

Eingegangen am 25. 4. 1975