Αλγοριθμική Θεωρία Παιγνίων — Ιούνιος 2021 (eClass)¶

Η μεταγραφή προέρχεται από τέσσερα στιγμιότυπα οθόνης της πλατφόρμας eClass (150876271…, 2.png, 151299478…, 150958747…). Κείμενο που λείπει από μία φωτογραφία σημειώνεται στο σημείο του.

150876271_256613462660536_3416621301526982318_n.png¶

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

Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 2 βαθμοί)

Στο παιχνίδι του σχήματος, υπολογίστε τις τιμές κέρδους (α) του παίκτη 1 στην κατάσταση ΒΓ, (β) του παίκτη 2 στην κατάσταση ΑΔ, και (γ) του παίκτη 1 στην κατάσταση ΒΔ ώστε το κόστος της ευστάθειας να είναι 3 και το κόστος της αναρχίας να είναι 4. Ως κοινωνικό κέρδος σε μια κατάσταση, θεωρήστε το άθροισμα των κερδών των δύο παικτών.

[Σχήμα: πίνακας κερδών 2×2. Στήλες: Α, Β (τίτλος «παίκτης 1»). Γραμμές: Γ, Δ (τίτλος «παίκτης 2»). Κελί ΑΓ: άνω δεξιά 2, κάτω αριστερά 0. Κελί ΒΓ: άνω δεξιά (α) ?, κάτω αριστερά 2. Κελί ΑΔ: άνω δεξιά 0, κάτω αριστερά (β) ?. Κελί ΒΔ: άνω δεξιά (γ) ?, κάτω αριστερά 2.]

[ ] (α) 4, (β) 2, (γ) 0
[ ] (α) 2, (β) 12, (γ) 1
[ ] (α) 1, (β) 9, (γ) 1
[ ] (α) 1, (β) 3, (γ) 1
[ ] Δεν γνωρίζω (αυτή η επιλογή δεν έχει αρνητική βαθμολογία)

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

2.png¶

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

Δίνεται το παρακάτω παιχνίδι δύο παικτών με δύο στρατηγικές ανά παίκτη. Σημειώστε ποιες από τις καταστάσεις είναι αμιγείς ισορροπίες.

[Σχήμα: πίνακας παιχνιδιού 2×2. Στήλες: Α, Β (τίτλος «παίκτης 1»). Γραμμές: Γ, Δ (τίτλος «παίκτης 2»). Κελί ΑΓ: άνω δεξιά 1, κάτω αριστερά 1. Κελί ΒΓ: άνω δεξιά 3, κάτω αριστερά 2. Κελί ΑΔ: άνω δεξιά 2, κάτω αριστερά 1. Κελί ΒΔ: άνω δεξιά 1, κάτω αριστερά 0.]

[ ] Η κατάσταση ΑΓ
[ ] Η κατάσταση ΒΓ
[ ] Η κατάσταση ΑΔ
[ ] Η κατάσταση ΒΔ

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

151299478_754095845237505_2297159199992491731_n.png¶

[Λείπει από τη φωτογραφία: η επικεφαλίδα και το κείμενο της Ερώτησης 1, καθώς και το πάνω μέρος του πίνακα κερδών· βλ. την αρχή της σύνοψης στο 150876271_256613462660536_3416621301526982318_n.png]

[Σχήμα: κάτω μέρος του πίνακα κερδών. Στην κάτω αριστερή γωνία του κελιού ΑΔ «? (β)», στην κάτω αριστερή γωνία του κελιού ΒΔ «2».]

[ ] (α) 4, (β) 2, (γ) 0
[ ] (α) 2, (β) 12, (γ) 1
[ ] (α) 1, (β) 9, (γ) 1
[ ] (α) 1, (β) 3, (γ) 1
[ ] Δεν γνωρίζω (αυτή η επιλογή δεν έχει αρνητική βαθμολογία)

Ερώτηση 2 (Ελεύθερου Κειμένου — 2 βαθμοί)

Θεωρήστε τον κανόνα της πλειοψηφίας με 3 υποψηφίους και 2 ψηφοφόρους, όπου οι ισοπαλίες επιλύονται με βάση την προτίμηση του δεύτερου ψηφοφόρου. Δώστε παράδειγμα που να δείχνει ότι ο κανόνας χειραγωγείται.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

150958747_4035260966536372_6874490204800044715_n.png¶

Άσκηση ελεύθερου κειμένου.

Ερώτηση 1 (Ελεύθερου Κειμένου — 2 βαθμοί)

Δώστε προφίλ προτιμήσεων με 3 υποψηφίους ώστε οι τελικές διατάξεις με βάση τους κανόνες της πλειοψηφίας, του Borda, και της δικτατορίας του πρώτου ψηφοφόρου να είναι c>b>a, b>a>c, και a>c>b, αντίστοιχα. Γράψτε το προφίλ με την προτίμηση του κάθε ψηφοφόρου ανά γραμμή.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2021-06¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Ερώτηση 1 (Πολλαπλής Επιλογής — 2 βαθμοί)¶

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή

Η σωστή επιλογή είναι η 2η: (α) 2, (β) 12, (γ) 1.

Με ζεύγη $(u_1,u_2)$ ο πίνακας γίνεται [ \begin{array}{c|cc} & A & B\\hline \Gamma & (2,0) & (\alpha,2)\ \Delta & (0,\beta) & (\gamma,2) \end{array} ] Για $\alpha=2,\ \beta=12,\ \gamma=1$: - Αμιγείς ισορροπίες Nash είναι οι $B\Gamma=(2,2)$ και $B\Delta=(1,2)$. - Κοινωνικά κέρδη: $W(B\Gamma)=4$, $W(B\Delta)=3$, ενώ το κοινωνικό μέγιστο είναι $W(A\Delta)=12$. Άρα [ \text{κόστος ευστάθειας}=\frac{12}{4}=3,\qquad \text{κόστος αναρχίας}=\frac{12}{3}=4. ] Επομένως τα ζητούμενα είναι $\alpha=2$, $\beta=12$, $\gamma=1$.

Ερώτηση 2 (Πολλαπλής Επιλογής — Πολλαπλές Απαντήσεις — 1 βαθμός)¶

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή

Ο πίνακας είναι [ \begin{array}{c|cc} & A & B\\hline \Gamma & (1,1) & (3,2)\ \Delta & (2,1) & (1,0) \end{array} ] Οι αμιγείς ισορροπίες Nash είναι: - $B\Gamma$: ο παίκτης 1 προτιμά $B$ από $A$ στη γραμμή $\Gamma$ ($3>1$), και ο παίκτης 2 προτιμά $\Gamma$ από $\Delta$ στη στήλη $B$ ($2>0$). - $A\Delta$: ο παίκτης 1 προτιμά $A$ από $B$ στη γραμμή $\Delta$ ($2>1$), ενώ ο παίκτης 2 είναι αδιάφορος στη στήλη $A$ ($1=1$)· άρα δεν έχει κερδοφόρα απόκλιση.

Άρα σωστές επιλογές είναι: Η κατάσταση $B\Gamma$ και Η κατάσταση $A\Delta$. Η $A\Delta$ είναι ασθενής ισορροπία Nash.

Ερώτηση 2 (Ελεύθερου Κειμένου — 2 βαθμοί)¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα 151299478_754095845237505_2297159199992491731_n.png η εκφώνηση διατυπώνεται επί λέξει: «Θεωρήστε τον κανόνα της πλειοψηφίας με 3 υποψηφίους και 2 ψηφοφόρους, όπου οι ισοπαλίες επιλύονται με βάση την προτίμηση του δεύτερου ψηφοφόρου. Δώστε παράδειγμα που να δείχνει ότι ο κανόνας χειραγωγείται.»

Μαθηματική Ανάλυση του Κανόνα¶

Έστω οι 3 υποψήφιοι $A = \{a, b, c\}$ και οι 2 ψηφοφόροι $N = \{1, 2\}$ με προτιμήσεις $\succ_1$ και $\succ_2$. Στον κανόνα της σχετικής πλειοψηφίας (plurality), κάθε ψηφοφόρος δίνει 1 ψήφο στον υποψήφιο της 1ης προτίμησής του ($\text{top}(\succ_i)$): 1. Αν $\text{top}(\succ_1) = \text{top}(\succ_2) = x$: Ο υποψήφιος $x$ λαμβάνει 2 ψήφους και οι υπόλοιποι 0. Νικητής είναι ο $x = \text{top}(\succ_2)$. 2. Αν $\text{top}(\succ_1) = x \ne y = \text{top}(\succ_2)$: Ο υποψήφιος $x$ λαμβάνει 1 ψήφο, ο $y$ λαμβάνει 1 ψήφο και ο τρίτος υποψήφιος $z$ λαμβάνει 0 ψήφους. Υπάρχει ισοπαλία μεταξύ $x$ και $y$ (1-1). Σύμφωνα με την εκφώνηση, η ισοπαλία επιλύεται με βάση την προτίμηση του 2ου ψηφοφόρου. Επειδή $y = \text{top}(\succ_2)$, ισχύει $y \succ_2 x$, οπότε νικητής αναδεικνύεται πάντα ο $y = \text{top}(\succ_2)$.

Συνεπώς, για κάθε δυνατό προφίλ προτιμήσεων, το αποτέλεσμα του κανόνα είναι πάντα και αποκλειστικά η 1η προτίμηση του 2ου ψηφοφόρου: $$f(\succ_1, \succ_2) = \text{top}(\succ_2)$$

Εξέταση Χειραγώγησης (Manipulation)¶

Κατά τον τυπικό ορισμό (Gibbard-Satterthwaite), ένας κανόνας κοινωνικής επιλογής $f$ είναι χειραγωγήσιμος από τον ψηφοφόρο $i$ αν υπάρχει προφίλ $\succ$ και ψευδής ψήφος $\succ'_i$ τέτοια ώστε $f(\succ'_i, \succ_{-i}) \succ_i f(\succ_i, \succ_{-i})$ (δηλαδή ο ψηφοφόρος $i$ να πετυχαίνει αυστηρά προτιμότερο αποτέλεσμα δηλώνοντας ψευδή προτίμηση): - Για τον ψηφοφόρο 2: Ο κανόνας εκλέγει ήδη τον πιο προτιμώμενο υποψήφιό του ($\text{top}(\succ_2)$). Οποιαδήποτε απόκλιση $\succ'_2$ μπορεί μόνο να εκλέξει υποψήφιο ίσης ή χειρότερης προτίμησης. Άρα ο ψηφοφόρος 2 δεν έχει κίνητρο απόκλισης. - Για τον ψηφοφόρο 1: Το αποτέλεσμα είναι ανεξάρτητο της ψήφου του (οποιαδήποτε ψήφος του 1 δίνει το ίδιο αποτέλεσμα $\text{top}(\succ_2)$). Άρα ο ψηφοφόρος 1 δεν μπορεί να επηρεάσει το αποτέλεσμα προς όφελός του.

Επομένως, ο κανόνας όπως ορίζεται είναι δικτατορία του 2ου ψηφοφόρου και συνεπώς είναι αποδεδειγμένα μη χειραγωγήσιμος (φιλαλήθης).

Σχόλιο & Τι πιθανόν ζητούσε ο εξεταστής¶

Η εκφώνηση περιέχει εγγενές σφάλμα σχεδιασμού (ζητά παράδειγμα χειραγώγησης για έναν κανόνα που μαθηματικά δεν χειραγωγείται). - Αν η ισοπαλία λυνόταν με προκαθορισμένη εξωτερική σειρά (π.χ. αλφαβητικά $a \succ b \succ c$) αντί για την προτίμηση του 2ου ψηφοφόρου, τότε θα υπήρχε χειραγώγηση: Πραγματικές προτιμήσεις: $\text{Ψηφοφόρος 1: } b \succ a \succ c$, $\text{Ψηφοφόρος 2: } c \succ a \succ b$. Ειλικρινής ψήφος: 1 ψήφος στο $b$, 1 ψήφος στο $c$. Ισοπαλία μεταξύ $b$ και $c$, νικάει το $b$ (αλφαβητικά). Αν ο ψηφοφόρος 2 αποκλίνει στρατηγικά και ψηφίσει $a$ αντί για $c$, τότε το $a$ παίρνει 1 ψήφο, το $b$ 1 ψήφο, και αλφαβητικά νικάει το $a$, το οποίο ο ψηφοφόρος 2 προτιμά από το $b$ ($a \succ_2 b$). - Με την ακριβή εκφώνηση όμως, η ορθή επιστημονική απάντηση είναι ότι δεν υπάρχει τέτοιο παράδειγμα, διότι ο κανόνας ταυτίζεται με δικτατορία του 2ου ψηφοφόρου.

Ερώτηση 1 (Ελεύθερου Κειμένου — 2 βαθμοί)¶

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή

Η σωστή επιλογή είναι η 2η: (α) 2, (β) 12, (γ) 1.

Με ζεύγη $(u_1,u_2)$ ο πίνακας γίνεται [ \begin{array}{c|cc} & A & B\\hline \Gamma & (2,0) & (\alpha,2)\ \Delta & (0,\beta) & (\gamma,2) \end{array} ] Για $\alpha=2,\ \beta=12,\ \gamma=1$: - Αμιγείς ισορροπίες Nash είναι οι $B\Gamma=(2,2)$ και $B\Delta=(1,2)$. - Κοινωνικά κέρδη: $W(B\Gamma)=4$, $W(B\Delta)=3$, ενώ το κοινωνικό μέγιστο είναι $W(A\Delta)=12$. Άρα [ \text{κόστος ευστάθειας}=\frac{12}{4}=3,\qquad \text{κόστος αναρχίας}=\frac{12}{3}=4. ] Επομένως τα ζητούμενα είναι $\alpha=2$, $\beta=12$, $\gamma=1$.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή