Collective decisions with incomplete individual opinions

Abstract

In the modern world, people make decisions together every day: they participate in elections, boards of companies, juries of courts, and social activities amongst friends. Accurately capturing such fine-grained human behaviour is essential, not only for directly improving the choices made by people, but also for developing AI (multiagent) systems that work efficiently and safely with collective decisions. Social choice theory, a sub-area of (micro)economics, is concerned with the analysis of mechanisms that groups use to make decisions; its far-reaching themes transcend neighbouring disciplines, like political science, law, and artificial intelligence. The much younger field of computational social choice investigates problems traditionally studied in social choice theory with powerful tools from computer science. Much research to date in computational social choice has been resting on a rather stringent hypothesis—namely, that people are able to form concrete opinions about all issues at stake in a given decision problem (such opinions are called complete). But in recent years, people make decisions increasingly in online settings, where the abundance of available options often makes them prohibitively difficult to critically evaluate. This thesis concerns collective decisions where the agents may hold intrinsically incomplete opinions (that is, they may lack an opinion about some issues in question). For example, on a travel website where users rank hotels according to their experience and preferences, most people will not have an opinion about all offered listings. We need aggregation mechanisms that allow for incomplete inputs and produce reasonable collective outcomes. This thesis proposes such mechanisms in three contexts, where we care about (i) reaching a consensus between the diverse opinions of the group members for issues that are subjective in nature (like in the example about the travel website); (ii) avoiding skewed outcomes caused by the strategic behaviour of selfish agents (like in election problems); (iii) discovering the ground truth with respect to a number of objective issues (like in crowdsourcing experiments). First, how can we achieve a sufficiently good compromise for a group of agents with diverting opinions? One way, typically employed by the social choice community, suggests the use of axioms, i.e., properties of aggregation mechanisms that are normatively appealing. Such axioms are well-studied in the standard frameworks where completeness is assumed, but present numerous open questions when incompleteness comes into the picture. By restricting attention to different axioms, we obtain distinct mechanisms for collective choice—including mechanisms that weigh individual opinions relying on their size, mechanisms that assign scores to alternatives with respect to their position in the individual preferences, as well as mechanisms that are associated with given acceptance thresholds. The various axioms that we consider lead to different notions of compromise. Depending on those one finds compelling, one can argue for the use of the corresponding mechanisms that satisfy them. Second, under what mechanisms for collective decision making are the members of a group tempted to misrepresent their individual opinions in view of obtaining a better outcome for themselves? Agents that have the freedom to report incomplete opinions may lie in three ways: by hiding their sincere opinion; by inventing a new insincere opinion; or by reversing their sincere opinion. Such acts pose threats to our everyday life, bringing out the risk of obtaining non-representative, undemocratic collective decisions. In many cases, we show that it is possible to find mechanisms that are immune to this kind of strategic behaviour. However, we also prove impossibility results stating that strategic manipulation is, sometimes, inescapable. Furthermore, when agents are allowed to change their opinions in rounds, we examine whether—and how fast—relevant procedures of iterative decision making are guaranteed to terminate. Third, suppose you need to determine the correct answer to a question (e.g., whether a colleague should get promoted) that depends on two independent premises (e.g., whether the colleague is excellent at her work and whether she is a good team player). Will you ask the members of a group to each evaluate just one of those premises (which can be done with relatively high accuracy) or both (in which case their need to multitask will lower their accuracy)? In scenarios like this, we present an optimal mechanism for making collective decisions, we determine how many agents one should ask for how many of their opinions, and we provide an extensive analysis of strategic incentives that may arise from the point of view of the group members. In a nutshell, spanning across ample contexts motivated by real-world applications, this thesis discusses several promising ways for making collective decisions when individual opinions are expected to be incomplete.

Στον σύγχρονο κόσμο, οι άνθρωποι λαμβάνουν αποφάσεις από κοινού καθημερινά: συμμετέχουν σε εκλογές, συμβούλια εταιρειών, και δικαστικές επιτροπές. Η ακριβής καταγραφή αυτής της ανθρώπινης συμπεριφοράς είναι απαραίτητη, όχι μόνο για τη βελτίωση των επιλογών που κάνουν οι άνθρωποι, αλλά και για την ανάπτυξη συστημάτων τεχνητής νοημοσύνης που λειτουργούν αποτελεσματικά και με ασφάλεια στις συλλογικές αποφάσεις. Η θεωρία της κοινωνικής επιλογής, ένα υποπεδίο της (μικρο)οικονομίας, ασχολείται με την ανάλυση των μηχανισμών που χρησιμοποιούν οι ομάδες για να λαμβάνουν αποφάσεις· τα ευρύτατα θέματά της ξεπερνούν γειτονικές επιστήμες, όπως η πολιτική επιστήμη, το δίκαιο και η τεχνητή νοημοσύνη. Το πολύ νεότερο πεδίο της υπολογιστικής κοινωνικής επιλογής εξετάζει προβλήματα που παραδοσιακά μελετώνται στη θεωρία της κοινωνικής επιλογής με ισχυρά εργαλεία από την επιστήμη των υπολογιστών. Μέχρι σήμερα, πολλές έρευνες στην υπολογιστική κοινωνική επιλογή βασίζονται σε μια μάλλον αυστηρή υπόθεση—συγκεκριμένα, ότι οι άνθρωποι είναι ικανοί να σχηματίσουν σαφείς απόψεις για όλα τα ζητήματα που διακυβεύονται σε ένα δεδομένο πρόβλημα απόφασης (τέτοιες απόψεις ονομάζονται πλήρεις). Όμως, τα τελευταία χρόνια, οι άνθρωποι λαμβάνουν όλο και περισσότερες αποφάσεις σε διαδικτυακά περιβάλλοντα, όπου η αφθονία των διαθέσιμων επιλογών καθιστά συχνά την κριτική τους αξιολόγηση αδύνατη. Αυτή η διατριβή αφορά συλλογικές αποφάσεις στις οποίες οι πράκτορες μπορεί να έχουν εγγενώς ελλιπείς απόψεις (δηλαδή, μπορεί να μην έχουν άποψη για ορισμένα ζητήματα που τίθενται). Για παράδειγμα, σε έναν ιστότοπο ταξιδιών όπου οι χρήστες κατατάσσουν τα ξενοδοχεία σύμφωνα με την εμπειρία και τις προτιμήσεις τους, οι περισσότεροι άνθρωποι δεν θα έχουν άποψη για όλες τις προσφερόμενες καταχωρήσεις. Χρειαζόμαστε μηχανισμούς ψηφοφορίας που επιτρέπουν ελλιπείς εισόδους και παράγουν συνεπή συλλογικά αποτελέσματα. Αυτή η διατριβή προτείνει τέτοιους μηχανισμούς σε τρία πλαίσια, όπου μας ενδιαφέρει (i) να επιτευχθεί συναίνεση μεταξύ των διαφορετικών απόψεων των μελών της ομάδας για ζητήματα που είναι υποκειμενικής φύσης (όπως στο παράδειγμα του ιστότοπου ταξιδιών), (ii) να αποφευχθούν στρεβλωμένα αποτελέσματα που προκαλούνται από τη στρατηγική συμπεριφορά εγωιστικών πρακτόρων (όπως σε προβλήματα εκλογών), (iii) να ανακαλυφθεί η αλήθεια σε σχέση με έναν αριθμό αντικειμενικών ζητημάτων (όπως σε πειράματα). Πρώτον, πώς μπορούμε να επιτύχουμε έναν επαρκώς καλό συμβιβασμό για μια ομάδα πρακτόρων με διαφορετικές απόψεις; Ένας τρόπος, που συνήθως χρησιμοποιείται από την κοινότητα της κοινωνικής επιλογής, προτείνει τη χρήση αξιωμάτων, δηλαδή ιδιοτήτων των μηχανισμών συγκέντρωσης που είναι κανονιστικά ελκυστικές. Τέτοια αξιώματα είναι καλά μελετημένα στα τυπικά πλαίσια όπου υποτίθεται πληρότητα, αλλά παρουσιάζουν πολλά ανοικτά ερωτήματα όταν η έλλειψη πληρότητας εισέρχεται στο προσκήνιο. Περιορίζοντας την προσοχή σε διαφορετικά αξιώματα, αποκτούμε διακριτούς μηχανισμούς συλλογικής επιλογής—συμπεριλαμβανομένων μηχανισμών που ζυγίζουν τις ατομικές απόψεις βασιζόμενοι στο μέγεθός τους, μηχανισμών που αποδίδουν βαθμολογίες στις εναλλακτικές λύσεις σε σχέση με τη θέση τους στις ατομικές προτιμήσεις, καθώς και μηχανισμών που συνδέονται με δεδομένα όρια αποδοχής. Τα διάφορα αξιώματα που εξετάζουμε οδηγούν σε διαφορετικές έννοιες του συμβιβασμού. Ανάλογα με αυτά που θεωρεί κανείς πειστικά, μπορεί να υποστηρίξει τη χρήση των αντίστοιχων μηχανισμών που τα ικανοποιούν. Δεύτερον, υπό ποιους μηχανισμούς για τη λήψη συλλογικών αποφάσεων τα μέλη μιας ομάδας έχουν κίνητρο να παραποιήσουν τις ατομικές τους απόψεις με σκοπό να επιτύχουν ένα καλύτερο αποτέλεσμα για τον εαυτό τους; Οι πράκτορες που έχουν την ελευθερία να αναφέρουν ελλιπείς απόψεις μπορεί να προβούν σε ψέμματα με τρεις τρόπους: κρύβοντας την ειλικρινή τους άποψη, επινοώντας μια νέα μη ειλικρινή άποψη, ή αντιστρέφοντας την ειλικρινή τους άποψη. Τέτοιες πράξεις αποτελούν απειλές για την καθημερινή μας ζωή, φέρνοντας τον κίνδυνο να ληφθούν μη αντιπροσωπευτικές, μη δημοκρατικές συλλογικές αποφάσεις. Σε πολλές περιπτώσεις, δείχνουμε ότι είναι δυνατόν να βρεθούν μηχανισμοί που είναι άτρωτοι σε αυτό το είδος στρατηγικής συμπεριφοράς. Ωστόσο, αποδεικνύουμε επίσης αποτελέσματα του αδυνάτου που υποστηρίζουν ότι η στρατηγική χειραγώγηση είναι, μερικές φορές, αναπόφευκτη. Επιπλέον, όταν οι πράκτορες έχουν τη δυνατότητα να αλλάξουν τις απόψεις τους σε γύρους, εξετάζουμε εάν—και πόσο γρήγορα—οι σχετικές διαδικασίες επαναλαμβανόμενης λήψης αποφάσεων θα ολοκληρωθούν. Τρίτον, υποθέστε ότι χρειάζεται να καθορίσετε τη σωστή απάντηση σε ένα ερώτημα (π.χ., εάν ένας συνάδελφος πρέπει να προαχθεί) που εξαρτάται από δύο ανεξάρτητα αξιώματα (π.χ., εάν ο συνάδελφος είναι εξαιρετικός στη δουλειά της και εάν είναι καλή ομαδική παίκτρια). Θα ζητήσετε από τα μέλη μιας ομάδας να αξιολογήσουν το καθένα από αυτά τα αξιώματα (που μπορεί να γίνει με σχετικά υψηλή ακρίβεια) ή και τα δύο (οπότε η ανάγκη τους να κάνουν πολλαπλές εργασίες θα μειώσει την ακρίβειά τους); Σε σενάρια όπως αυτό, παρουσιάζουμε έναν βέλτιστο μηχανισμό για τη λήψη συλλογικών αποφάσεων, καθορίζουμε πόσους πράκτορες πρέπει να ρωτήσετε για πόσες από τις απόψεις τους και παρέχουμε μια εκτενή ανάλυση των στρατηγικών κινήτρων που μπορεί να προκύψουν από την οπτική των μελών της ομάδας. Εν συντομία, εξετάζοντας πολλά πλαίσια που είναι εμπνευσμένα από πραγματικές εφαρμογές, αυτή η διατριβή συζητά διάφορους υποσχόμενους τρόπους για τη λήψη συλλογικών αποφάσεων όταν οι ατομικές απόψεις αναμένεται να είναι ελλιπείς.