Δημοκρατία ή … δικτατορία; – Το παράδοξο του Arrow

Παίρνοντας αφορμή από τις προσεχείς βουλευτικές εκλογές στην Κύπρο, επιστρέφω μετά από περισσότερο από ένα χρόνο απραξίας με ένα καινούργιο άρθρο.

Φυσικά εδώ θα ασχοληθούμε με μαθηματικά και όχι με την πολιτική. Θα παρουσιάσω λοιπόν ένα εκλογικό παράδοξο το οποίο ανακαλύφθηκε από τον οικονομολόγο Kenneth Arrow ο οποίος το 1972 τιμήθηκε και με το βραβείο Νόμπελ.

Οι βουλευτές μιας χώρας προσπαθούν να φτιάξουν ένα καινούργιο εκλογικό νόμο. Μετά από αρκετή ένταση και πάρα πολλές διαφωνίες αποφασίζουν να καλέσουν ένα μαθηματικό για να τους βοηθήσει στην δημιουργία μιας καινούργιας εκλογικής διαδικασίας.

1) Το πρώτο πράγμα που απαιτούν οι βουλευτές είναι να ληφθεί πρόνοια για οποιοδήποτε αριθμό υποψηφίων. Κάθε πολίτης θα δικαιούται να κατατάσσει τους εκάστοτε υποψηφίους με την σειρά προτίμησης του. Η εκλογική διαδικασία πρέπει να είναι τέτοια ώστε λαμβάνοντας υπόψη τις προτιμήσεις των ψηφοφόρων να βγάζει μια τελική σειρά κατάταξης όλων των υποψηφίων.

Ο μαθηματικός τους λέει ότι υπάρχει ένας πολύ απλός τρόπος για να γίνει η εκλογική διαδικασία. Να μην λαμβάνουν καθόλου υπόψη τις ψήφους και να γίνεται κλήρωση! Αυτό οδηγεί τους βουλευτές να βάλουν και ένα νέο όρο για την εκλογική διαδικασία.

2) Η διαδικασία πρέπει να είναι ντετερμινιστική. Αν επαναληφθεί η ψηφοφορία και όλοι δώσουν τις ίδιες ακριβώς ψήφους τότε η τελική κατάταξη πρέπει να είναι η ίδια.

Και πάλι ο μαθηματικός βρίσκει μια πολύ απλή εκλογική διαδικασία. Να κατατάσσονται οι υποψήφιοι αλφαβητικα! Αφού και αυτή η λύση θεωρείται απαράδεκτη οι βουλευτές θέτουν και ένα καινούργιο όρο.

3) Αν όλοι οι ψηφοφόροι προτιμούν τον υποψήφιο Α από τον υποψήφιο Β τότε πρέπει και στην τελική κατάταξη ο Α να λάβει ψηλότερη θέση από τον Β.

Οι βουλευτές εξακολουθούν να φοβούνται τι θα γίνει αν κάποιοι ψηφοφόροι προσπαθούν να βάζουν σε χαμηλή κατάταξη αντίπαλους υποψηφίους για να ευνοηθούν οι δικοί τους. Ο μαθηματικός προτείνει να μπει ο ακόλουθος όρος

4) Για κάθε δύο υποψηφίους Α και Β, η σχετική τους κατάταξη πρέπει να εξαρτάται μόνο από την σχετική τους κατάταξη στις προτιμήσεις των ψηφοφόρων. Δηλαδή αν επαναληφθεί η ψηφοφορία και κάθε ψηφοφόρος αλλάζει την ψήφο του αλλά προτιμά τον Α από τον Β αν και μόνο αν τον προτιμούσε και στην αρχική ψηφοφορία τότε και στο τελικό αποτέλεσμα ο Α είναι πιο ψηλά από τον Β αν και μόνο αν ήταν πιο ψηλά και στην αρχική ψηφοφορία.

Παρατηρεί επίσης ο μαθηματικός ότι ο όρος (2) δεν χρειάζεται πλέον αφού είναι συνέπεια του όρου (4).

Αφού δεν υπάρχουν ενστάσεις ο μαθηματικός ξεκινάει την προσπάθειά του για να φτιάξει μια εκλογική διαδικασία που να ικανοποιεί τους παραπάνω όρους. Μετά από λίγο καιρό επιστρέφει στην βουλή και τους ανακοινώνει ότι έχει καλά και κακά νέα. Τα καλά νέα είναι ότι έχει φτιάξει μια πολύ απλή εκλογική διαδικασία που ικανοποιεί τους παραπάνω όρους: Η τελική κατάταξη να είναι ότι ψηφίσει ο ίδιος! Μετά από το σχετικό πανδαιμόνιο μπαίνει και ένας πέμπτος όρος

(5) Απαγορεύεται η ύπαρξη δικτάτορα: Απαγορεύεται να υπάρχει συγκεκριμένο άτομο ώστε όπως και αν ψηφίσουν οι υπόλοιποι να λαμβάνεται μόνο η δική του ψήφος υπόψη.

Ο μαθηματικός όμως έχει ήδη μελετήσει και αυτό το ζήτημα και τους ανακοινώνει τα κακά νέα. «Κύριοι, αδυνατώ να φτιάξω μια τόσο δημοκρατική εκλογική διαδικασία. Μάλιστα δεν θα καταφέρετε να βρείτε κανένα που να μπορέσει να σας φτιάξει μια τέτοια διαδικασία διότι η ύπαρξή της είναι αδύνατη!»

Ας δούμε λοιπόν μια απόδειξη αυτού του ισχυρισμού:

Θα ονομάζουμε μια ομάδα ατόμων «κλίκα» αν υπάρχουν δύο υποψήφιοι Α και Β ώστε όταν όλα τα μέλη της κλίκας προτιμούν τον Α από τον Β, τότε στην τελική κατάταξη ο Α παίρνει πιο ψηλή θέση από τον Β. Για παράδειγμα, το σύνολο όλων των ψηφοφόρων είναι μια κλίκα. Αν μια κλίκα αποτελείται από μόνο ένα άτομο τότε θα ονομάζουμε αυτό το άτομο «ημιδικτάτορα». Η απόδειξη βασίζεται στους ακόλουθους δυο ισχυρισμούς:

α) Υπάρχει ένας ημιδικτάτορας.

β) Κάθε ημιδικτάτορας είναι δικτάτορας.

Για να αποδείξουμε το (α), παίρνουμε μια κλίκα με τον μικρότερο αριθμό ατόμων. Θα αποδείξουμε πως η κλίκα αποτελείται από ένα μόνο άτομο. Ας υποθέσουμε πως δεν ισχύει αυτό. Έστω Α,Β υποψήφιοι ώστε όποτε η κλίκα προτιμά τον Α από τον Β, τότε στην τελική κατάταξη ο Α είναι πάνω από τον Β, και έστω Γ ένας τρίτος υποψήφιος. Έστω ένα μέλος της κλίκας. Έστω λοιπόν ότι σε μια εκλογική διαδικασία έχουμε τις εξής προτιμήσεις:

– Ο x προτιμά τον Α από τον Β και τον Γ από τον Α. (Δηλαδή ψηφίζει Β<Α<Γ.)

– Κάθε μέλος του εκτός από τον ψηφίζει Γ<Β<Α.

– Κάθε άλλος ψηφοφόρος ψηφίζει Α<Γ<Β.

(Από την υπόθεση (4), αν έχουμε ακόμη περισσότερους υποψηφίους, η τελική κατάταξη των Α,Β,Γ δεν επηρεάζεται.)

Ποια είναι λοιπόν η σχετική κατάταξη των Α,Β,Γ; Σίγουρα θα έχουμε Β<Α αφού κάθε μέλος του προτιμά τον Α από τον Β. Αν Β<Γ τότε ο είναι ημιδικτάτορας αφού όλοι οι άλλοι προτιμάνε τον Β από τον Γ. Άρα μπορούμε να υποθέσουμε ότι στην τελική κατάταξη έχουμε Γ<Β<Α και άρα Γ<Α. Αλλά τότε το αποτελεί κλίκα αφού όποτε προτιμάει τον Α από τον Γ τότε στην τελική κατάταξη ο Α είναι πιο πάνω από τον Γ. Αυτό όμως είναι άτοπο αφού ήδη βρήκαμε κλίκα με λιγότερα άτομα από την .

Μένει να δείξουμε το (β). Έστω λοιπόν ένας ημιδικτάτορας και δυο υποψήφιοι Α και Β ώστε όταν ο προτιμάει τον Α από τον Β τότε και στην τελική κατάταξη ο Α είναι πάνω από τον Β. Θα γράφουμε ότι ο είναι (Α,Β)-δικτάτορας. Αρκεί (από το (4)) να δείξουμε ότι για κάθε δυο υποψηφίους Γ και Δ ο είναι (Γ,Δ)-δικτάτορας.

(β1) Για κάθε υποψήφιο Γ (διαφορετικό από τον Α), ο είναι (Α,Γ)-δικτάτορας: Πράγματι αν ο ψηφίσει Α>Β>Γ και όλοι οι άλλοι ψηφοφόροι ψηφίσουν Β>Γ>Α στην τελική κατάταξη πρέπει να έχουμε Α>Β (αφού ο είναι (Α,Β)-δικτάτορας) και Β>Γ (από το (3)) άρα και Α>Γ.

(β2) Για κάθε δυο υποψηφίους Γ και Δ (διαφορετικούς από τον Α), ο είναι (Γ,Δ)-δικτάτορας: Πράγματι αν ο ψηφίσει Γ>Α>Δ και όλοι οι άλλοι ψηφοφόροι ψηφίσουν Δ>Γ>Α στην τελική κατάταξη πρέπει να έχουμε Α>Δ (αφού ο είναι (Α,Δ)-δικτάτορας) και Γ>Α (από το (3)) άρα και Γ>Δ.

(β3) Δουλεύοντας με παρόμοιο τρόπο, βρίσκουμε ότι για κάθε δυο υποψηφίους Γ και Δ (διαφορετικούς από τον Β), ο είναι (Γ,Δ)-δικτάτορας.

(β4) Μένει να δείξουμε ότι ο είναι (Β,Α)-δικτάτορας. Πράγματι αν Γ ένας άλλος υποψήφιος, ο ψηφίσει Β>Γ>Α και όλοι οι άλλοι ψηφίσουν Γ>Α>Β τότε αφού ο είναι (Β,Γ)-δικτάτορας η τελική κατάταξη θα είναι Β>Γ>Α και άρα ο είναι (Β,Α)-δικτάτορας.

Πηγή: christofides