Ce travail structuré en deux parties, porte sur l'étude des interactions entre des agents. Nous nous intéressons à la représentation conceptuelle du cadre et de ses règles de fonctionnement, à la mesure du pouvoir ou capacité des agents à influencer l'aboutissement des interactions et à l'analyse des aboutissements qui peuvent être considérés comme meilleurs.Dans la première partie, nous considérons des agents qui visent un objectif commun dépendant des facteurs distincts. Par exemple, dans un jeu avec abstention (Felsenthal et Machover (1997)) ou plus généralement dans les (j,k)-jeux, de Freixas et Zwicker (2003), des votes de natures différentes peuvent compter favorablement au résultat. Comme modèle, nous développons les jeux multi-types dans lesquels chacun tient un rôle précis dans un groupe. Ce modèle est proche de celui de Bolger (1986) où les rôles ne sont pas comparables. Dans ce cadre, nous proposons des extensions des indices de Shapley-Shubik (1954) et Banzhaf (1965). En prenant en compte une structure de coalitions sur l'ensemble des agents, nous reprenons l'étude avec les indices d'Owen-Shapley (1977) et Owen-Banzhaf (1981).Dans la deuxième partie, nous utilisons les positions des joueurs dans l'espace multidimensionnel pour modéliser des liens entre eux. Les indices d'Owen (1971) et de Shapley (1977) s'appliquent à ce cadre. Nous montrons que le second généralise le premier puis, nous les généralisons. Le cœur (Plott (1967)), le Yolk (Miller (1980), McKelvey (1986)) et le Finagle (Wuffle et al. (1989)) sont trois concepts de solution spatiale. Le Yolk est une région hypersphérique dont le centre est souvent supposé unique (Scott et Grofman (1988), Tovey (1992)). Nous le généralisons et nous montrons que son unicité n'est vraie que dans un espace bidimensionnel. En admettant qu'on peut se tromper sur la localisation spatiale, nous proposons une généralisation du cœur similaire à celle proposée par Bräuninger (2007), des études comparatives avec le Yolk et le Finagle sont faites. / This work structured into two parts, focuses on the study of interactions among agents. We are interested in the conceptual framework and its operating rules, the measurement of power or ability of agents to influence the outcome of interactions and analysis of outcomes which can be considered to be the best.In the first part, we consider that there is a set of agents who have a common objective which depends on different factors. For example, in a game with abstention (Felsenthal et Machover (1997)) or more generally in the (j,k)-games of Freixas and Zwicker (2003), the votes of different natures can contribute positively to the result. We use the model of multi-types games in which each agent has a specific role in a group. This model is similar to that of Bolger (1986) in which the roles are not comparable. In this context, we extend the Shapley-Shubik (1954) and Banzhaf (1981) power indices. We reconsider the multi-types games with the Owen-Shapley (1977) and Owen-Banzhaf (1965) power indices through the lens of a coalition structures on the set of agents.In the second part, we use the player positions in a multidimensional space to model the links among them. The Owen (1971) and Shapley (1977) power indices are developed in this framework. We show that the second generalizes the first and we extend them. The core (Plott (1967)), the Yolk (Miller (1980), McKelvey (1986)) and the Finagle (Wuffle et al. (1989)) are three concepts of spatial solution. The Yolk is an hyperspherical region whose center is often assumed unique (Tovey (1992), Scott et Grofman (1988)). We generalize this concept and show that uniqueness is only true on the bidimensional space. We consider the situation in which the social planner has a partial knowledge on the spatial location of agents and propose a generalization of the core similar to one of Bräuninger (2007). Comparative studies with the olk and the Finagle are made.

Le développement et l’utilisation de systèmes complexes multi-utilisateurs, ou encore la mise en réseau de systèmes d’observation ou d’information pose des problèmes complexes de partage de ressources entre les utilisateurs. La particularité de ces systèmes, impliquant plusieurs utilisateurs humains ou entités organisationnelles est que le partage des ressources doit satisfaire les préférences souvent antagonistes des utilisateurs et répondre à des exigences d’équité. Ce travail de thèse a pour objet l’étude des problèmes de partage de ressources indivisibles entre des agents ayant des préférences complexes sur ces ressources.Nous nous intéressons plus particulièrement à la modélisation de problèmes de partage en univers risqué.En effet, dans de nombreux problèmes d’allocation de ressources réels, la part revenant réellement à chaque agent après le partage de la ressource dépend de facteurs exogènes. C’est le cas par exemple dans les systèmes d’observation (satellitaires, capteurs embarqués,...), dans lesquels la réalisation d’une requête donnée dépend non seulement des conditions climatiques sur le secteur à observer, mais aussi du bon fonctionnement du capteur, de l’absence de brouillage du signal, etc. L’introduction de risque dans les problèmes de partage implique la redéfinition des notions classiques de choix social (utilité, absence d’envie, ...), et l’agrégation collective des préférences des agents s’en trouve compliquée. Au cours de ce travail de thèse, nous nous sommes tout d’abord intéressés à l’étude de cette extension au risque du formalisme associé aux problèmes de partage classiques : nous proposons un modèle simple de problèmes de partages de biens indivisibles en présence de risque, toutefois assez général pour rester proche des applications réelles considérées, et nous introduisons une extension générale des méthodes d’évaluation non risquées pour de tels partages. La seconde partie de ce travail de thèse porte sur l’algorithmique associée à ces problèmes, dont la résolution est notablement complexifiée par la présence de ressources risquées. Pour plusieurs critères d’évaluation (choisis car visant à garantir une certaine équité des solutions qu’ils suggèrent), nous proposons des algorithmes de résolution exacte et approchée des problèmes de partage associés. / The development and use of complex multi-user systems, or the networking of observation ou information systems raises complex resource allocation problems. The particularity of these systems, which involve several human users or organisational entities, rests in the fact that the share of resources must satisfy the often conflicting preferences of users and comply with equity exigences. This thesis deals with the problem of fairly allocating indivisible goods to a set of agents having complex preferences over these goods.We are more particularly interested in the modeling of fair allocation problems in a risky setting. In numerous real-world resource allocation problems, the actual share each agent receives after the allocation often depends on exogenous factors. This is for instance the case with the observation systems (satellites, embedded sensons, etc.) where the realisation of a request not only depends on weather conditions over the observation area, but also on the potential sensor malfunction, on the absence of jamming of the signal, etc. Introducing the risk in allocation problems implies the redefinition of classical social choice notions such as utility or envy-freeness for instance, and the collective aggregation of agents preferences becomes more complicated. We have studied in this thesis the extension of allocation problem formalism to a risky setting : we present a simple model for risky indivisible goods allocation problems, yet general enough to encompass most of the real-world applications, and we introduce a general extension of risk-free evalution methods for such allocations. The second part of the work concerns the algorithmical issues related to theses problems, whose resolution is significantly complexified because of the risky setting. Forseveral evaluation criteria (selected for the equity of the solutions they suggest) we present both exact and approached resolution algorithms for the related allocation problems.

L'objet de cette thèse est l'étude des aspects algorithmiques du vote par approbation. Il s'agit principalement d'une étude théorique des enjeux computationnels soulevés par le vote par approbation dans des contextes de décisions variés. Cependant, j'étudie aussi des questions plus proches de la théorie classique du choix social et je conduis de brèves études expérimentales.Dans un premier temps, l'étude se porte sur une famille générale de règles de vote pour les élections de comités et les référendums multiples à l'aide du vote par approbation. Dans un second temps, je porte mon attention sur un contexte plus général, le vote par approbation sur domaines combinatoires en se basant sur des préférences conditionnelles. Finalement, je me place dans le cadre du vote avec préférences incomplètes pour étudier les problèmes de vainqueurs possibles et nécessaires dans le vote par approbation. / The subject of this thesis is the study of computational aspects of approval voting. Most of the works are theoretical results about computational issues raised by approval voting, in many different settings. However, I also study some questions that are more related to classical choice theory, and some problems are investigated through experimental analysis.Firstly, I study a general family of rules for approval voting in the context of committee elections and multiple referenda. Secondly, I focus on a more general setting, approval voting in combinatorial domains, based on conditional preferences. Finally, I consider approval voting in the context of incomplete preferences, to study the possible and necessary winner problems.

<p align="justify">Depuis 20 à 30 ans, l'aide multicritère à la décision est apparue. L'expansion de cette nouvelle discipline s'est marquée dans la littérature essentiellement par un foisonnement de nouvelles méthodes multicritères d'aide à la décision et par des applications de celles-ci à des problèmes "réels". Pour la plupart de ces méthodes, il n'y pas ou peu de fondements théoriques. Seul le bon sens a guidé les créateurs de ces méthodes.</p><p><p align="justify">Depuis une dizaine d'années, le besoin de bases théoriques solides se fait de plus en plus sentir. C'est dans cette perspective que nous avons réalisé le présent travail. Ceci étant dit, nous n'allons pas vraiment nous occuper de méthodes multicritères à la décision dans ce travail, mais seulement de fragments de méthodes. En effet, les méthodes multicritères d'aide à la décision peuvent généralement être décomposées en trois parties (outre la définition de l'ensemble des alternatives et le choix des critères):</p><p><p align="justify"><ol><li>Modélisation des préférences: pendant cette étape, les préférences du décideur sont modélisées le long de chaque critère.<p><li>Agrégation des préférences: un modèle global de préférences est construit au départ des modèles obtenus critère par critère à la fin de la phase précédente.<p><li>Exploitation des résultats de l'agrégation: du modèle global de préférences issu de la phase 2, on déduit un choix, un rangement, une partition, selon les besoins.</ol></p><p><p align="justify">Jusqu'à présent, à cause de la difficulté du problème, peu de méthodes ont été axiomatisées de bout en bout; la plupart des travaux ne s'intéressent qu'à une ou deux des trois étapes que nous venons de décrire.</p><p><p align="justify">Nous nous sommes intéressés à une méthode bien connue: la méthode de Borda. Elle accepte comme données de départ des relations binaires. Elle intervient donc après la phase de modélisation des préférences. Le résultat de cette méthode est un rangement. Elle effectue donc les opérations correspondant aux étapes 2 et 3. Dans la suite de ce travail nous appellerons méthode de rangement toute méthode effectuant les étapes 2 et 3 pour aboutir à un rangement. Etant donné que les méthodes de rangement, celle de Borda en particulier, sont utilisées également en choix social, nous puiserons abondamment dans le vocabulaire, les outils et les résultats du choix social. Les résultats présentés seront valides en choix social, mais nous nous sommes efforcés de les rendre aussi pertinents que possible en aide multicritère à la décision.</p><p><p align="justify">Dans le chapitre II, après quelques définitions et notations, nous présentons quelques méthodes de rangement classiques, y compris la méthode de Borda, et quelques résultats majeurs de la littérature. Nous généralisons une caractérisation des méthodes de scorage due à Myerson (1995).</p><p><p align="justify">Nous nous tournons ensuite vers les relations valuées. La raison en est la suivante: elles sont utilisées depuis longtemps dans plusieurs méthodes multicritères et, depuis peu, elles le sont aussi en choix social (p.ex. Banerjec 1994) car elles permettent de modéliser plus finement les préférences des décideurs confrontés à des informations incertaines, imprécises, contradictoires, lacunaires, Nous commençons donc le chapitre III par des notations et définitions relatives aux relations valuées.</p> <p align="justify">Ensuite, nous présentons quelques méthodes de rangement opérant au départ de relations valuées. C'est-à-dire des méthodes de rangement qui agissent non pas sur des relations nettes, mais sur des relations valuées et qui fournissent comme précédemment un rangement des alternatives. N'ayant trouvé dans la littérature aucune méthode de ce type, toutes celles que nous présentons sont neuves ou des généralisations de méthodes existantes; comme par exemple, les méthodes de scorage généralisées, que nous caractérisons en généralisant encore une fois le résultat de Myerson.</p><p><p align="justify">Nous présentons enfin ce que nous appelons la méthode de Borda généralisée, qui est une des généralisations possibles de la méthode de Borda au cas valué. Nous basant sur un article de Farkas et Nitzan (1979), nous montrons que contrairement à ce qui se passait dans le cas particulier envisagé par Farkas et Nitzan (agrégation d'ordres totaux), la méthode de Borda généralisée (et sa particularisation au cas net) n'est pas toujours équivalente à la méthode proximité à l'unanimité. Cette dernière méthode classe chaque alternative en fonction de l'importance des changements qu'il faudrait faire subir à un ensemble de relations pour que l’alternative considérée gagne à l'unanimité. Nous identifions quelques cas où l'équivalence est vraie.</p><p><p align="justify">Ensuite, nous reprenons un résultat de Debord (1987). Il s'agit d'une caractérisation de la méthode de Borda en tant que méthode de choix appliquée à des préordres totaux. Nous la généralisons de deux façons au cas de la méthode de Borda en tant que méthode de rangement appliquée à des relations valuées. Lorsqu'on applique la méthode de Borda, on est amené à calculer une fonction à valeurs réelles sur l'ensemble des alternatives.</p><p><p align="justify">La valeur prise par cette fonction pour une alternative s'appelle le score de Borda de cette alternative. Ensuite, on range les alternatives par ordre décroissant de leur score de Borda. La tentation est grande - et beaucoup y succombent (peut-être avec raison) d'utiliser le score de Borda non seulement pour calculer le rangement mais aussi pour estimer si l'écart entre deux alternatives est important ou non (voir par exemple Brans 1994). Cette approche n'a, à notre connaissance, jamais été étudiée d'un point de vue théorique. Nous présentons deux caractérisations de la méthode de Borda utilisée à cette fin.</p><p><p align="justify">Dans la dernière partie du chapitre III, nous abandonnons la démarche qui visait à caractériser une méthode par un ensemble de propriétés le plus petit possible. Nous comparons 12 méthodes sur base d'une vingtaine de propriétés. Les résultats de cette partie sont résumés dans quelques tableaux.</p><p><p align="justify">Ce travail aborde donc la méthode de Borda et sa généralisation au cas valué sous différents angles. Il livre une série de résultats qui, espérons-le, devraient permettre de mieux comprendre la méthode de Borda et peut-être de l'utiliser à meilleur escient. Toutefois, quoique notre objectif ait été de présenter des résultats pertinents en aide multicritère à la décision (et nous avons fait des progrès dans ce sens), il reste du chemin à faire. Nous sommes probablement encore trop proche du choix social. Ceci constitue donc une voie de recherche intéressante, de même que l'étude d'autres méthodes de rangement et l'étude de méthodes complètes d'aide multicritère à la décision: modélisation du problème (identification du ou des décideur(s), des alternatives et des critères), modélisation des préférences, agrégation des préférences et exploitation des résultats de l'agrégation.</p><p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished