Cuando los miembros de una sociedad tienen que tomar una decisión sobre un conjunto de alternativas suelen usar ciertas reglas que tratan de alcanzar un acuerdo entre sus diferentes intereses. Estas reglas se suelen denominar mecanismos de votación, procedimientos de elección social o, simplemente, elecciones. Las reglas de votación definen escenarios en los que los miembros de la sociedad interaccionan y tratan de obtener el mejor resultado de acuerdo con sus preferencias. Esta tesis doctoral está dedicada al estudio de los incentivos estratégicos de los participantes (votantes y candidatos) en procesos de elección social.Nuestro análisis se centra en modelos generales en los que se admite que el resultado de la elección consista en un conjunto de alternativas. Aunque resulta natural suponer que sólo una alternativa será finalmente elegida, existen múltiples situaciones en las que este supuesto es sumamente restrictivo. Por ejemplo, podríamos considerar la elección como una etapa intermedia en el proceso de decisión. El objeto del proceso electoral sería reducir el número de alternativas entre las que la sociedad tendría que escoger. Con esta interpretación, nos centraríamos en situaciones en los que existe cierto grado de incertidumbre sobre la resolución final de la elección social.En esta tesis seguimos dos importantes ramas de la literatura de la teoría de la elección social, el estudio de reglas decisión social no manipulables y el análisis de los problemas de candidatura estratégica.En primer lugar, siguiendo el trabajo seminal de Dutta, Jackson y Le Breton (Econometrica, 2001) estudiamos los incentivos de los candidatos para entrar o abandonar la lucha electoral con la intención de afectar al resultado de la elección. Si los candidatos comparan conjuntos de candidatos de forma consistente con los postulados de la teoría de la utilidad esperada, cualquier regla de decisión unánime y no dictatorial provee a algún candidato con incentivos a abandonar su candidatura. Sin embargo, si los candidatos comparan los resultados de la elección de acuerdo con métodos menos sofisticados, sí que se pueden obtener resultados positivos.Seguidamente, pasamos a analizar los incentivos estratégicos de los candidatos en un entorno complementario: en el que el resultado de la elección es explícitamente probabilístico. En esta situación podemos caracterizar la familia de reglas de votación que nunca incentivan la salida de ningún candidato. Sorprendentemente, aunque la familia de dictadores aleatorios juega un papel central dentro de la caracterización, podemos probar que reglas de decisión más flexibles también satisfacen los requerimientos de estabilidad en las candidaturas.Finalmente, nos centramos en la posibilidad de construir reglas de decisión no manipulables cuando los votantes comparan conjuntos de alternativas de acuerdo con actitudes extremas ante el riesgo. En este contexto, analizamos la compatibilidad entre la condición de no manipulabilidad y otras condiciones de regularidad que han sido propuestas en la literatura como por ejemplo, Resolución Residual. Además, también presentamos los requerimientos en las preferencias de los votantes sobre conjuntos de alternativas que reducen la posibilidad de reglas de decisión no manipulables a reglas dictatoriales. / When a society has to make a choice from an array of alternatives, it usually relies on certain rules that try to reconcile the opposite interest of the members of the society. These rules define environments in which the agents interact and try to obtain the best outcome according to their preferences. This work is devoted to the study of the strategic incentives of the participants in the social decision processes.We analyse general frameworks in which the outcome of the social choice process can be multivalued. Even when it seems natural to assume that the result of an election as a singleton, there are many situation in which our assumption should not be precluded. For instance, we can consider the social decision process as an interim stage that narrows the social agenda. Another possibility is to consider the set of the possible equilibria that could eventually arise in the voting procedure as the outcome of the election.Our study focuses on two important branches of the literature, the study of strategy-proof social choice correspondences and the analysis of strategic candidacy in multivalued voting procedures.First, we study the possibility of constructing non-manipulable social choice correspondences when the voters have strict attitudes towards risk. We analyse the trade-off between strategy-proofness and some regularity conditions proposed in the literature like Residual Resoluteness. Moreover, we introduce necessary conditions for strategy-proof and onto social choice correspondences. We also present the requirements in voters' preferences over sets of alternatives that reduce the possibility of strategy-proof correspondences to dictatorial ones.Second, we study the incentives of candidates to enter or to exit elections in order to affect strategically the outcome of a voting correspondence. We show that, if candidates form their preferences over sets according to Expected Utility Theory and Bayesian Updating, every unanimous and non dictatorial voting correspondence violates candidate stability, at least a candidate has incentives to leave the ballot at one profile of preferences. We also analyse the implications of using other extension criteria to define candidate stability that open the door to positive results.Finally, we analyse the strategic incentives of the candidates to withdraw the election in probabilistic environments. We characterise the family of unanimous and candidate stable probabilistic voting procedures when the candidates are expected utility maximisers. Surprisingly, we show that there are rules that are not probabilistic combinations of single-valued candidate stable voting procedures (random dictatorships) that do not provide incentives to the candidates to withdraw the election.

This thesis presents three chapters. In Chapter 1, I propose a simple one-to-one matching model, where individuals on one side have private information that affects the preferences of the individuals on the other side. I show the existence of the stable and strategy-proof mechanism in this environment. I present an algorithm that defines this mechanism - the Serial Dictatorship algorithm with cutoffs. I also consider the concept of obvious strategy-proofness. I first consider the case where only preferences, but not experience levels, are sellers' private information. For this case, Serial Dictatorship with cutoffs elicits preferences in an obviously strategy-proof way. On the other hand, when only experience levels, but not preferences are private information, I show that there is no obviously strategy-proof and stable mechanism. A consequence of the latter result is that obvious strategy-proofness is incompatible with stability. Chapter 2 considers settings with rich private information - an agent's type may include private information other than just his preferences. In such settings, I identify a necessary condition for obviously strategy-proof implementation of social choice rules. I consider applications to strict preferences, matching and object allocation. The main assumption behind the obvious dominance is that agents might be cognitively limited and can not engage in contingent reasoning at all. This assumption is unreasonably weak compared to the standard assumption that agents can perfectly distinguish contingencies. In Chapter 3, I strengthen it slightly by assuming that agents are able to do at least some contingent reasoning. I define what it means for the strategy to be obviously dominant with respect to a partition of the state space. I call such strategies partition dominant strategies. A strategy is an almost obviously dominant if, for all possible partitions, but not for the coarsest, it can be identified as being partition dominant. My hypothesis is that even though some agents can not do state-by-state reasoning as rational players do, they are able to do at least some partitioning of the other player’s actions and regardless of how the partitioning is done, the agents can identify an almost obviously dominant strategy.

<p>Diss. Stockholm :  Stockholm School of Economics, 2012. Introduction together with 6 papers</p>

Στην εργασία αυτή ασχολούμαστε με θέματα κοινωνικής επιλογής και πιο συγκεκριμένα με συμβιβαστικές ψηφοφορίες στις οποίες κάθε ψηφοφόρος ψηφίζει ένα (πιθανόν κενό) σύνολο υποψηφίων και το αποτέλεσμα είναι ένα σύνολο υποψηφίων πλήθους k, για δεδομένο k (π.χ. εκλογή επιτροπής). Εξετάζουμε τον κανόνα minimax σε συμβιβαστικές ψηφοφορίες, στις οποίες το αποτέλεσμα αντιπροσωπεύει ένα συμβιβασμό μεταξύ των προτιμήσεων των ψηφοφόρων, με την έννοια ότι η μέγιστη απόσταση μεταξύ των προτιμήσεων οποιουδήποτε ψηφοφόρου και του αποτελέσματος είναι όσο το δυνατό μικρότερη. Αυτός ο κανόνας έχει δύο μειονεκτήματα. Πρώτον, ο υπολογισμός του αποτελέσματος που ελαχιστοποιεί τη μέγιστη απόσταση από κάθε ψηφοφόρο είναι ένα υπολογιστικά δύσκολο πρόβλημα και δεύτερον, οποιοσδήποτε αλγόριθμος που πάντα επιστρέφει ένα τέτοιο αποτέλεσμα, δίνει στους ψηφοφόρους κίνητρο να πουν ψέματα για την πραγματική τους προτίμηση, με σκοπό να βελτιώσουν την απόσταση τους από το τελικό αποτέλεσμα. Για να ξεπεράσουμε αυτά τα μειονεκτήματα χρησιμοποιούμε προσεγγιστικούς αλγορίθμους, δηλαδή αλγορίθμους που παράγουν αποτέλεσμα που αποδεδειγμένα προσεγγίζει την minimax απόσταση για κάθε δοσμένο στιγμιότυπο. Τέτοιοι αλγόριθμοι μπορούν να χρησιμοποιηθούν σαν εναλλακτικοί κανόνες ψηφοφορίας. Παρουσιάζουμε ένα 2-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, ο οποίος υπολογίζει το αποτέλεσμα στρογγυλοποιώντας ντετερμινιστικά τη λύση του χαλαρωμένου γραμμικού προγράμματος μέσω του οποίου εκφράζουμε το πρόβλημά μας. Ο καλύτερος προηγούμενος προσεγγιστικός αλγόριθμος επιτύγχανε λόγο απόδοσης 3 και συνεπώς το παραπάνω αποτέλεσμα αποτελεί σημαντική βελτίωση. Επιπλέον ασχολούμαστε με προσεγγιστικούς αλγορίθμους που είναι ανθεκτικοί σε χειραγώγηση είτε από μεμονωμένους ψηφοφόρους είτε από ομάδες ψηφοφόρων. Τέτοιοι αλγόριθμοι δεν προσφέρουν κίνητρο στους ψηφοφόρους να δηλώσουν ψευδώς τις προτιμήσεις τους με σκοπό να βελτιώσουν την απόστασή τους από το τελικό αποτέλεσμα. Μια τέτοια μελέτη εντάσσεται στα πλαίσια της έρευνας που γίνεται τα τελευταία χρόνια πάνω στο σχεδιασμό προσεγγιστικών αλγοριθμικών μηχανισμών χωρίς χρήματα. Συμπληρώνουμε προηγούμενα αποτελέσματα με νέα πάνω και κάτω φράγματα για strategyproof και group-strategyproof αλγορίθμους. / We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some fixed k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the preferences of the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. This study falls within the recently initiated line of research on approximate mechanism design without money. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24030号 / 情博第786号 / 新制||情||133(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)准教授 宮崎 修一, 教授 岡部 寿男, 教授 阿久津 達也, 教授 湊 真一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

In diese Dissertation, betrachte ich das Problem der Aufteilung der unteilbaren Objekte unter Agenten, ihren Vorlieben entsprechend, und die Transfers fehlen. In Kapitel 1 studiere ich den Kompromiss zwischen Fairness und Effizienz in der Klasse der strategy-proof Aufteilungsmechanismen. Das wichtigste Ergebnis ist, dass für die strategy-proof Mechanismen folgende Effizienz- und Fairness-Kriterien nicht miteinander vereinbar sind: (1) Ex-post-Effizienz und Neidfreiheit, (2) Ordnung-Effizienz und schwache Neidfreiheit und (3) Ordnung-Effizienz und gleiche-Teilung-untere-Grenze. In Kapitel 2 ist der Fokus auf zwei Darstellungen einer Zuteilung: als probabilistische Zuordnung und als Lotterie über deterministische Zuordnungen. Um die Gestaltung der praktischen Lotterie-Mechanismen zu erleichtern schlagen wir neue Werkzeuge für den Erhalt der stochastischen Verbesserungen bei Lotterien vor. Als Anwendungen schlagen wir Lotterie Mechanismen, die die weit verbreiteten Random serial dictatorship Mechanismus verbessern, und eine Lotterie-Darstellung seiner Konkurrent, die Probabilistic serial Mechanismus, vor. In Kapitel 3 schlage ich einen neuen Mechanismus vor, der Schüler an Grundschulen zuweist: Adaptive Acceptance (AA). AA sammelt von Neumann-Morgenstern Präferenzen von Studenten über Schulen und implementiert die Zuordnung unter Verwendung eines iterativen Verfahrens, das ähnlich der vorherrschenden Immediate Acceptance (IA) ist. AA verfügt über eine starke Kombination von Anreize und Effizienzeigenschaften im Vergleich zu IA und sein Rivale, Deferred Acceptance (DA). / I consider the problem of allocating indivisible objects among agents according to their preferences when transfers are absent. In Chapter 1, I study the tradeoff between fairness and efficiency in the class of strategy-proof allocation mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness and (3) ordinal efficiency and equal division lower bound. In Chapter 2, the focus is on two representations of an allocation when randomization is used: as a probabilistic assignment and as a lottery over deterministic assignments. To help facilitate the design of practical lottery mechanisms, we provide new tools for obtaining stochastic improvements in lotteries. As applications, we propose lottery mechanisms that improve upon the widely-used random serial dictatorship mechanism, and a lottery representation of its competitor, the probabilistic serial mechanism. In Chapter 3, I propose a new mechanism to assign students to primary schools: the Adaptive Acceptance rule (AA). AA collects von Neumann-Morgenstern utilities of students over schools and implements the assignment using an iterative procedure similar to the prevalent Immediate Acceptance rule (IA). AA enjoys a strong combination of incentive and efficiency properties compared to IA and its rival, the Deferred Acceptance rule (DA). In case of strict priorities, AA implements the student-optimal stable matching in dominant strategies, which dominates each equilibrium outcome of IA. In case of no priorities, AA is ex-post efficient while some equilibrium outcomes of IA are not; also, AA causes loss of ex-ante efficiency less often than DA. If, in addition, students have common ordinal preferences, AA is approximately strategy-proof and ex-ante dominates DA.

No description available.

This thesis consists of three independent papers. They are put in reverse chronological order according to when they were initiated. The first paper, which is a joint work with Özgür Evren, extends the standard rational choice framework with the option to postpone the act of selecting an alternative. In that paper, we propose an axiomatic model of choice over risky prospects that restricts the classical rationality axioms solely to those instances in which the decision maker does not defer. The cardinal approach we follow allows us to identify the preference relation of the decision maker over lotteries, even if the choice data is very scarce due to deferral. Moreover, we also derive the value of deferring choice from a given set of options, which turns out to be an affine utility function over choice sets. At each choice situation, the decision maker compares the utility of each available alternative with that of deferral so as to decide on opting for an alternative immediately. The second paper is a model of status quo bias with choice avoidance. It describes the choice behavior of an otherwise standard decision maker whose choices are affected by the presence of a status quo alternative. The status quo emerges as a temporary choice, which may be reversed upon arrival of new (introspective or objective) information, or upon finding new alternatives. The third paper considers the network formation problem from a matching perspective. In that paper, agents want to link with each other and each has preferences over the subsets of others. We consider various solution concepts regarding the stability of a matching between the agents, establish relations between these concepts under several preference restrictions, and provide sufficient conditions for these solutions to be nonempty. / Diss. Stockholm : Handelshögskolan i Stockholm, 2011