Choix social, théorème de la flèche et problèmes ouverts?

22

Ces derniers mois, j'ai commencé à m'exprimer sur le choix social, le théorème de la flèche et les résultats associés.

Après avoir lu les résultats séminaux, je me suis demandé ce qui se passe avec les préférences d'ordre partiel, la réponse est dans l'article de Pini et al. : Agrégation de préférences partiellement ordonnées: résultats d'impossibilité et de possibilité . Ensuite, je me suis demandé s'il était possible de trouver une caractérisation des fonctions de choix social admissibles. Et encore une fois quelqu'un l'a fait ( Caractérisation complète des fonctions satisfaisant aux conditions du théorème d'Arrow par Mossel et Tamuz). Je ne donnerai pas une liste complète, mais je peux penser à tous les problèmes liés au choix social où tout a été résolu au cours des 5 dernières années :(

Alors, savez-vous s'il existe une enquête sur ce qui a été fait récemment sur le terrain et ce qui n'a pas été fait?

Une autre question est: êtes-vous conscient de la complexité et des problèmes liés aux choix sociaux (par exemple, la complexité de trouver le plus grand sous-ensemble d'utilisateurs qui sont compatibles pour au moins une fonction de choix social, ou ce genre de question).

Sylvain Peyronnet
la source

Réponses:

18

Votre question est très bien synchronisée, car le dernier numéro du CACM contient un article qui fait exactement cela: http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections /texte intégral

En bref, Conitzer, Tovey et d'autres ont beaucoup travaillé sur la dureté réelle, à la fois dans le pire des cas et selon les hypothèses de distribution, de la fissuration des mécanismes de vote qui sont en principe cassables via le théorème d'Arrow.

Suresh Venkat
la source
1
J'accepte celui-ci parce que c'est le plus voté, mais toutes les réponses m'ont intéressé. Merci à tous!
Sylvain Peyronnet
12

De nombreux problèmes de complexité sont liés à de nombreux sujets qui se posent dans ce que l'on a appelé la théorie du choix social. Il s'agit notamment de la complexité de décider qui est le vainqueur lorsqu'une méthode particulière est utilisée pour fusionner les bulletins de vote d'un certain type en un choix pour la société. Il y a aussi des problèmes de complexité à essayer de trouver un moyen de voter stratégiquement (plutôt que d'utiliser ses véritables préférences) lorsque des informations peuvent être disponibles sur les préférences d'autres votants lorsqu'une méthode particulière est utilisée dans l'espoir d'obtenir un meilleur résultat pour une personne en particulier. ou un groupe de personnes. La complexité se pose également dans la conception de systèmes de vote en ligne «sûrs».

Il s'agit d'une énorme littérature sur le choix social, mais quelques bons livres pour commencer pour ceux qui seraient intéressés seraient:

Donald Saari, Decisions and Elections, Cambridge U. Press, 2001.

Donald Saari, Disposing Dictators, Demystifying Voting Paradoxes, Cambridge U. Press, 2008.

Alan Taylor, Social Choice and the Mathematics of Manipulation, Cambridge U. Press, 2005.

Joseph Malkevitch
la source
9

Il y a eu de nombreux développements récents sur les aspects informatiques du choix social. Le site Web suivant donne de nombreux conseils sur la littérature pertinente:

http://www.illc.uva.nl/COMSOC/

Ha
la source
7

Le théorème d'Arrow est un théorème classique. Trouver un problème ouvert n'est pas facile non plus pour les théoriciens du choix social (ou du moins pour moi).

Mon conseil général aux étudiants qui étudient l'économie est le suivant: "éloignez-vous du théorème, à moins que vous ne puissiez relier votre contribution à certaines idées récentes (par exemple, les axiomes qui ont été proposés récemment, les solutions qui ont été étudiées un peu et les hypothèses comportementales à la mode). . Essayez de trouver un problème sans rapport avec le théorème d'Arrow. Il y en a beaucoup, même dans la théorie du choix social. " Ce n'est qu'après avoir eu une idée générale du type de problème que vous souhaitez résoudre que vous pouvez consulter le Handbook of Social Choice and Welfare .

Les problèmes informatiques pourraient être l'une de ces idées "récentes". Bien que l'étude de la complexité (des règles ou de la manipulation ou de la solution, etc.) soit la principale préoccupation des informaticiens (comme suggéré par d'autres), il existe des documents de sortie (tels que Mihara, 1997, Arrow's Theorem et Turing Computability , Economic Theory 10: 257-276) qui étudie le problème (fondamental?) De la calculabilité dans le cadre d'Arrow. ;-)

Permettez-moi de commenter les deux problèmes que vous avez suggérés.

  1. Je ne sais pas si les théoriciens du choix social ont négligé de considérer les ordres partiels. S'ils l'ont fait, ils l'ont fait probablement parce que la "partialité" peut s'exprimer par des préférences strictes (comme nous le faisons dans Kumabe et Mihara, Théorie de l'agrégation des préférences sans acyclicité: le noyau sans insatisfaction de la majorité, Games and Economic Behavior , sous presse). (Dans ce cas, mieux vaut oublier la préférence faible R ou la définir différemment [afin qu'elle ne devienne pas complète]: En définissant xRy [x est faiblement préféré à y] ssi non yPx [pas y est préféré à x], nous avons P est asymétrique si R est complet !)

  2. Certains auteurs ne le sont pas, mais je suppose que la plupart des théoriciens du choix social sont assez prudents pour ne pas prétendre que toute fonction dictatoriale de bien-être social satisfait à l'IIA. Par exemple, je dis (Mihara, 1997) qu'au sein des fonctions de protection sociale satisfaisant à l'AII , une règle est dictatoriale si elle satisfait à une certaine condition. Ils savaient donc que le problème était ouvert, mais n'étaient probablement pas intéressés à classer davantage les fonctions dictatoriales. (Peut-être que Mossel et Tamuz peuvent commenter les errata d'Armstrong cités par Mihara. Il identifie une séquence de dictateurs ou d'ultrafiltres.) Cela suggère une autre stratégie de recherche (que je ne peux pas recommander): essayer de trouver un problème qui n'intéressait pas les théoriciens des choix sociaux.

H. Reiju Mihara
la source