Tesis sobre el tema "Computationnal social choice"

L'objectif de cette thèse est d'étudier les notions de diversité et d'équité dans le cadre de problèmes d'allocation de ressources où l'ensemble des agents est partitionné en un certain nombre de types.Ces problématiques ont de nombreuses applications, en premier lieu dans le problème qui a inspiré le modèle, l'immobilier de Singapour, mais également dans des problèmes plus divers telles que la répartition des élèves en écoles ou l'allocation des ressources médicales.Les travaux effectués se divisent en deux grands axes, le premier étudie les mécanismes d'allocations dans un contexte où les agents souhaitent se regrouper par types mais sont limités par des quotas de diversité, le deuxième étudie l'équité entre les types eux-mêmes.Dans le cadre du premier axe, nous considérons un modèle qui dispose, en plus d'une partition de l'ensemble des agents en un certain nombre de types, d'une partition de l'ensemble des ressources (ou objets) en un certains nombres de blocs, et de quotas de diversité entre ces types et ces blocs. Nous introduisons dans ce modèle une dynamique d'amélioration en autorisant les agents à effectuer des échanges de ressources bilatéraux. Cette dynamique introduit une notion de stabilité, où une allocation est stable si elle est invariante par cette dynamique.Nous étudions les propriétés de cette notion de stabilité, puis nous considérons deux mécanismes d'allocations. Le premier est le mécanisme de loterie, utilisé en situation réelle, qui consiste à ordonner les agents, puis leur laisser sélectionner leur objet favori chacun leur tour dans l'ordre. Le second, basé sur notre dynamique, consiste à partir d'une allocation quelconque et à appliquer des échanges améliorants jusqu'à atteindre une allocation stable. Nous présentons ensuite plusieurs séries d'expériences effectuées avec ces mécanismes et discutons de leurs résultats.Dans le cadre du deuxième axe, nous discutons de la notion d'équité, au travers de la notion d'envie. Nous posons 4 axiomes qui représentent des propriétés que l'on souhaite retrouver dans une notion d'envie, puis nous listons un certain nombre de définitions utilisées dans la littérature, et nous vérifions lesquelles vérifient quels axiomes.Cela fait, nous définissons nos propres notions d'envies, basées sur des comparaisons utilisant des sous-groupes, et nous les situons par rapport aux axiomes, puis nous discutons de leurs aspects computationnels. Nous explorons ensuite les différentes interprétations possibles du concept de monotonie.Nous introduisons une relaxation de nos notions d'envie, le degré d'envie, que nous montrons difficile à calculer. Nous présentons alors deux méthodes d'approximation. La première, plus efficace, repose sur une réduction à une variante du problème du sac à dos, la deuxième, théoriquement beaucoup plus longue, repose sur une succession d'échantillonnage par une chaîne de Markov.Si les résultats théoriques indiquent que cette deuxième méthode a une complexité beaucoup trop importante pour être utilisable en pratique, une série d'expérience suggère qu'elle serait en réalité bien plus rapide
The purpose of this thesis is to study the notions of fairness and diversity in resource allocation problems where the agent set is partitionned into types. These concepts have numberous applications, first among them being the Singapour housing allocation problem, which inspired our model. Other applications include allocating students to schools or medical resources to hospital.This work follow to main axis, the first one is about allocation mechanism within the context of a model with diversity constraints, while the second one is about equity between types of agents using the notion en envy.In the first part, we study a model for which, just as the agent set is partitionned into a set of types, the item set is partitionned into a set of blocks, and there are diversity quotas between these types and these blocks. We introduce a dynamic of individual improvement in which agents are allowed to improve their allocation by swapping their item with an other (willing) agent.This dynamic create a notion of stability, for which an allocation is stable if no pair of agent wish to swap their item. We then study the theoretical property of this notion of stability, before considering two different methods for generating allocation. The first one, the lotery mechanism, consists in ordering the set of agents, then allowing each one in turn to pick their favorite item. The second one relies on the dynamic we just introduced: we start from a random allocation, and we apply improving swap between agents until we reach a stable allocation. We then describe several series of experiments made using these mechanisms, and discuss their results.The second main contribution is about the notion of equity, which we consider through the lens of envy and envy-freeness. We define 4 axioms which stands for properties we consider to be critical to a relevant definition of envy. We then list the definitions of envy commonly used in the litterature, and we check whether or not they satisfy the axioms. We then define our own notions of envy, which relies on comparison using subgroups. We first study whether or not they satisfy the axioms, then their computationnal aspects. We then discuss the different possible interpretations of the concept of monotony.We then relax our notions of envy by defining the degree of envy,. However, we show that it is hard to compute, we thus bring forward two ways to approximate its computation. The first and most efficient one relies on a reduction to a variant of the knapsack problem, while the second one uses a succession of samples made using a Markov chain.While the theoretical complexity of this second method is very high, experimental results suggest convergence is in practice much faster

Cette thèse s'inscrit à la frontière entre deux domaines de recherche : le choix social computationnel et l'optimisation discrète, avec un accent sur l'ordonnancement. Le choix social computationnel est l'étude des processus de décision collective, de leurs propriétés mathématiques et computationnelles. Le but de ces processus est d'agréger un ensemble de préférences individuelles pour en déduire une solution "satisfaisante" pour la communauté. De nombreuses questions sont étudiées: qu'est-ce que "satisfaisante pour la communauté" signifie ? Est-ce la solution préférée par le plus grand nombre d'individus ? Est-ce une solution de compromis, appréciée par un grand nombre de participants et qui ne crée pas trop d'insatisfaction chez les autres ? Si oui, comment mesurer et exprimer ce compromis ? Comment le processus assure-t-il l'équité entre les votants et entre les candidats, dans le cas d'une élection par exemple ? Les participants ont-il intérêt à mentir ? Qu'en est-il des aspects computationnels ? Le processus peut-il être exécuté rapidement ? L'optimisation discrète est un domaine de recherche traitant de la résolution de problèmes complexes. Ces problèmes peuvent être extrêmement variés, de l'optimisation de tournées de véhicules pour le transport et la livraison de produits à la gestion de la production d'électricité dans une centrale. Le point commun de tous ces problèmes est d'avoir une structure composée (1) d'une fonction objectif, ou de plusieurs fonctions objectif, que l'on cherche à optimiser, cela peut être un coût à minimiser ou un indicateur de qualité à maximiser par exemple; (2) d'un ensemble de variables correspondant à des décisions, l'ensemble de ces décisions formant une solution au problème, ces décisions peuvent correspondre à l'utilisation ou non d'une source d'énergie, au passage ou non d'un camion à un entrepôt pour récupérer des biens par exemple; (3) un ensemble de contraintes sur les variables, il peut par exemple être impossible de faire tourner une machine pendant trop longtemps, car la machine a besoin de refroidir. A chaque solution correspond une valeur de la fonction objectif et notre but est de trouver la solution optimisant la fonction objectif. Parmi les problèmes d'optimisation discrète, les problèmes d'ordonnancement traitent de l'affectation de tâches à des machines. Les machines peuvent représenter des unités de calcul, des employés dans une entreprise, des salles de cours, dots Les tâches correspondent alors à des programmes informatiques, des travaux à effectuer (livraison, rédaction de rapport, dots) ou des enseignements. Une solution est alors une affectation de chaque tâche à une machine avec une fenêtre de temps correspondant à l'exécution de la tâche. Dans cette thèse on s'intéresse à des problèmes d'optimisation discrète, et notamment à des problèmes d'ordonnancement, dans lesquels plusieurs agents ont des préférences sur l'ensemble des solutions. Il s'agira alors de trouver des processus de décision qui tiennent compte de ces préférences pour trouver une solution satisfaisante. Il est également possible que ces préférences entrent en conflit avec un autre objectif, indépendant des votants, et qui concerne l'efficacité du système. Il faudra alors trouver un compromis entre satisfaction des agents et efficacité du système
This thesis focuses on several collective decision making problems, from multi agent scheduling to participatory budgeting. There are several agents, that can represent companies, citizens of a city, members of a research lab dots, for which a common solution has to be found. Such a solution can be a schedule of tasks of interest for the agents, a ranking of items that the agents have to sort or a selection of projects approved by the agents. Each agent has different interest over the possible solutions. This can be because the solution impacts directly the agents or because the agents express preferences over the possible solutions. Any solution can be evaluated thanks to different tools. We will mostly focus on fairness and efficiency. Fairness and efficiency can be formulated in different ways, depending on the context, from objective functions to binary properties. In all cases, our goal will be to find a solution that corresponds as much as possible to the interests or preferences of the agents. A solution is collectively satisfying if it is "close" to the preferences of the agents, according to some definition of closeness, or if the overall benefit of the agents is high. The solution should also be fair in the sense that no agent should be treated better than any other. We study different problems, especially scheduling problems, in which we have to find fair solution or fair decision making processes while guaranteeing some notion of efficiency

Le choix social repose sur l’étude de la prise de décision collective, où un ensemble d’individus doit convenir d’une solution commune en fonction des préférences de ses membres. Le problème revient à déterminer comment agréger les préférences de différents agents en une décision acceptable pour le groupe. Typiquement, les agents interagissent dans des processus de décision collective, notamment en collaborant ou en échangeant des informations. Il est communément supposé que tout agent est capable d’interagir avec n’importe quel autre. Or, cette hypothèse paraît irréaliste pour de nombreuses situations. On propose de relâcher cette hypothèse en considérant que la possibilité d’interaction est déterminée par un réseau social, représenté par un graphe sur les agents. Dans un tel contexte, on étudie deux problèmes de choix social : le vote stratégique et l’allocation de ressources. L’analyse se concentre sur deux types d’interaction : la collaboration entre les agents, et la collecte d’information. On s’intéresse à l’impact du réseau social, modélisant une possibilité de collaboration entre les agents ou une relation de visibilité, sur la résolution et les solutions de problèmes de vote et d’allocation de ressources. Nos travaux s’inscrivent dans le cadre du choix social computationnel, en utilisant pour ces questions des outils provenant de la théorie des jeux algorithmique et de la théorie de la complexité
Social choice is the study of collective decision making, where a set of agents must make a decision over a set of alternatives, according to their preferences. The question relies on how aggregating the preferences of the agents in order to end up with a decision that is commonly acceptable for the group. Typically, agents can interact by collaborating, or exchanging some information. It is usually assumed in computational social choice that every agent is able to interact with any other agent. However, this assumption looks unrealistic in many concrete situations. We propose to relax this assumption by considering that the possibility of interaction is given by a social network, represented by a graph over the agents.In this context, we study two particular problems of computational social choice: strategic voting and resource allocation of indivisible goods. The focus is on two types of interaction: collaboration and information gathering. We explore how the social network,modelingapossibilityofcollaboration or a visibility relation among the agents, can impact the resolution and the solution of voting and resource allocation problems. These questions are addressed via computational social choice by using tools from algorithmic game theory and computational complexity

Les règles de vote classiques supposent que les bulletins de vote des électeurs sont des ordres de préférence complets sur les candidats. Cependant, lorsque le nombre de candidats est suffisamment élevé, il est trop coûteux de demander aux électeurs de classer tous les candidats. Il y a donc un compromis à faire entre l’efficacité d’une méthode d’agrégation des préférences et la charge de communication qu’elle fait peser sur les électeurs.Dans cette thèse, nous abordons ce problème en suggérant de demander aux électeurs de ne classer que leurs k candidats préférés (où k peut varier selon les électeurs et/ou au cours du processus). On dit que de tels votes sont k- tronqués. Nous étudions la quantité d’information nécessaire pour déterminer le résultat de l’élection (de manière exacte ou approchée) à partir de bulletins tronqués selon différentes règles de vote et nous proposons et analysons différentes méthodes permettant un compromis entre précision du résultat et quantité de communication requise ; certaines ne requièrent qu’une seule phase de communication, alors que d’autres sont dynamiques
Classical voting rules assume that voters’ ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. There is therefore a trade-off between the efficiency of an aggregation method and the communication burden it places on voters.In this thesis, we address this problem by suggesting to ask voters to report only their k preferred candidates (where k may vary depending on the voters and/or during the process). The obtained ballots are then said to be k-truncated. We study the amount of information needed to determine the outcome of the election (exact or approximate) from truncated ballots with respect to different voting rules and we propose and analyze different methods allowing a compromise between the accuracy of the result and the amount of communication required; some require only one round of communication, while others are interactive

Cette thèse s'inscrit dans le contexte du Choix Social Computationnel. Il s'agit d'un domaine à l'intersection du Choix Social, de l'Informatique et de l'Intelligence Artificielle. Nous nous intéressons plus particulièrement au problème partage équitable de ressources indivisibles qui consiste à trouver une allocation équitable et efficace d'un ensemble d'objets à un ensemble d'agents. Tandis que la notion d'efficacité est communément traduite par l'exigence minimale de complétude (tous les objets doivent être alloués dans le but de ne gâcher aucun objet) ou la notion plus exigeante de Pareto-Optimalité (une allocation est dite Pareto-Optimale s'il n'existe pas une autre allocation telle que tous les agents sont au moins aussi contents et un agent est strictement plus content), plusieurs notions ont été proposées pour définir l'équité. Une des mesures d'équité la plus importante est l'absence d'envie. Une allocation est dite sans envie ou envy-free si aucun agent n'aurait envie de changer ses objets contre ceux d'un autre agent. Cependant, il n'existe pas forcément d'allocation envy-free quand on est dans le cadre de ressources indivisibles. Afin de surmonter cette limitation, des relaxations ont été récemment proposées dans la littérature.Dans cette thèse, nous étudions tout d'abord une famille de procédures décentralisées basée sur des échanges d'objets entre agents. Nous analysons en particulier comment ces procédures se comportent et les propriétés désirables qu'elles montrent. Plus précisément, on étudie les séquences de choix sincères et les cycles d'échanges de ressources. Dans un second temps, nous proposons de nouvelles relaxations de la notion d'absence d'envie (et d'autres mesures d'équité) et les étudions en profondeur. La première relaxation a pour but d'équilibrer l'envie entre les agents (quand elle ne peut être évitée) et se base sur l'Ordered Weighted Average (OWA), un agrégateur habituellement utilisé dans le domaine de l'optimisation multicritère pour traduire l'équité. La deuxième relaxation se concentre sur l'approbation sociale de l'envie et se rapproche plus de la théorie du vote étant donné que les agents votent sur l'envie des autres agents. Nous examinons les aspects computationnels liés à ces nouvelles relaxations, leurs liens avec des notions d'équité et d'efficacité existantes avant de les tester expérimentalement
The work of this thesis is in the scope of Computational Social Choice. It is a field at the intersection of Social Choice, Computer Science and Artificial Intelligence. In particular, we study the problem of Fair Division of Indivisible Goods where the the objective is to find a fair and efficient allocation of a set of (valuable) objects among a set of agents. While efficiency is usually brought by the minimal requirement of completeness (all the objects have to be allocated in order not to waste anything), or the more demanding notion of Pareto-Optimality (an allocation is Pareto-Optimal if there is no allocation such that all the agents are not worse off and one agent is strictly better off), several notions have been proposed to define the fairness of an allocation.One of the most prominent fairness measures is called envy-freeness. An allocation is said to be envy-free if no agent would like to exchange her bundle of resources with another agent. However, envy-freeness is not guaranteed to exist when considering indivisible goods so various relaxations have been proposed recently in the literature to overcome this limitation.In this thesis, we first thoroughly study a family of decentralized allocation procedures related to exchanges of goods. We analyze how these procedures behave and the desirable properties they exhibit. More specifically, we study sequence of sincere choices and cycle exchanges of resources. We then propose new relaxations of the envy-freeness notion (and also of other fairness measures) and thoroughly study them. Our first relaxation aims at balancing the envy among the agents (when it cannot be avoided) and is based on the Order Weighted Average (OWA) aggregator usually used in multi-criteria optimisation to bring fairness. The second relaxation focuses on the social approval of the envy and is more related to voting theory, as it lets agents vote about the envy of the other agents. We investigate computational issues related to these new relaxations, their link with existing fairness and efficiency notions and we experimentally test them

In the past, the power of news dissemination was under a few people's control, like newspapers' editors and TV channels. Thanks to social networks, this power is in the hand of everyone now. Social networks became very popular as soon as they were launched, and many societies extensively welcomed them. They have provided an engaging environment so that people can share their moments with their relatives, friends, colleagues, and even their unseen friends (so-called virtual friends) as their `followers.' In this virtual world, people can also share their opinions with their followers by broadcasting a message. Diffusing information and news among the followers will affect them and slightly change their opinions. When a follower is influenced, she may shares/retweets/forwards the message to her own followers and cause more propagation. There are many shreds of evidence that a message shared by few people (even in some cases one person) has been watched by millions of users and went viral. Hence, social media is an inseparable part of our life that can provide many opportunities, e.g., teaching, entertainment, news, and give us the power of sharing our experiences. Researchers have shown that many people prefer to get news from social networks rather than related websites as they are speedy tool to provide news from everywhere. Therefore, social media is considered one of the most effective tools to manipulate the users' opinions, and it is an attractive means of election control for political campaigns/parties/candidates. As a real example, in the 2016 US presidential election, it has been shown that 92% of Americans saw and remembered pro-Trump fake news stories, 23% remembered pro-Clinton false news, and a very high portion of them believed the news. Moreover, the campaigns can use social influence in order to polarize the users such that a voter receives specific messages in support/oppose of a candidate/party and not all possible messages. These activities impair the integrity of the elections and our democracies because people should have access to all reliable news from different perspectives to make a fair judgment. In this thesis, we investigate the computational aspects of this problem and study different manipulators' strategies to understand how they work. Our goal is to prevent malicious activities as they have enough potential to cause drastic consequences for any society. We study different aspects of controlling elections utilizing social influence. First, we consider a multi-winner election control where some parties are running for an election, and more than one candidate will be selected as winners. There is a social network of voters and an attacker trying to bribe some users/voters to start a diffusion process and spread a message among them; her goal is to change the voters' opinion regarding a target party. In the constructive model, the attacker tries to maximize the number of winners in the target party, while in the destructive case, she wants to minimize it. In this model, we present some hardness results, approximation guarantee, and polynomial-time algorithms regarding different structures (e.g., graphs, trees, and arborescent), objective functions, diffusion models (e.g., linear threshold and independent cascade models), and different configurations of influencing voters. Second, we investigate a single-winner election control problem where the attacker does not know the exact voters' preference list; instead, she has/guesses a probability distribution over all candidates for each voter. In this case, we show that the problem is at least as hard to approximate as the Densest-k-subgraph problem, which is hard to approximate for some constant under the exponential time hypothesis. Then we consider a lightly relaxed version and present some hardness and constant factor approximation algorithms for some objective functions regarding both constructive and destructive models. We also examine some real-world social networks and experimentally show that our algorithm works well. Finally, we present a Stackelberg game variation for competitive election control where there are two players called attacker and defender. They have a budget and the number of their seed nodes should not exceed their budget. The attacker plays first and selects a set of seed nodes to start a diffusion and change the voters' opinion. She knows that the defender is aware of everything and plays afterward. When the attacker's diffusion process is finished, the defender selects her seed nodes to cancel the attacker's influence over the infected voters. Indeed, the attacker tries to maximize the number of infected voters after both diffusion processes, while the defender attempts to minimize it. For simplicity, we first investigate the influence maximization model of this problem and then extend it to the election control through social influence for a single-winner election control problem regarding plurality scoring rule under the independent cascade model. We show that the attacker's problem is $Sigma_2^p$-hard when the defender is able to find an optimal strategy. We also show the same hardness result regarding any approximation algorithm. Moreover, we show that the defender's problem is NP-hard to approximate within any factor $alpha geq 1$. Since the problems are inapproximable, we consider a relaxed version in which the defender selects her seed nodes based on a probability distribution over the nodes, and the attacker is aware of the distribution. In the relaxed model, we give a constant-factor approximation algorithm for the attacker's problem. We also simulate our results and show that the attacker can activate many voters even when the defender can find the optimal solution. Moreover, we show that the greedy influence maximization algorithm works very well for the defender.

Des agents devant prendre une décision collective sont souvent motivés par des buts individuels. Dans ces situations, deux aspects clés doivent être abordés : sélectionner une alternative gagnante à partir des voix des agents et s'assurer que les agents ne manipulent pas le résultat. Cette thèse étudie l'agrégation et la dimension stratégique des décisions collectives lorsque les agents utilisent un langage représenté de manière compacte. Nous étudions des langages de type logique : de la logique propositionnelle aux CP-nets généralisés, en passant par la logique temporelle linéaire (LTL). Notre principale contribution est l'introduction d'un cadre de vote sur les buts, dans lequel les agents soumettent des buts individuels exprimés comme des formules de la logique propositionnelle. Les fonctions d'agrégation classiques issues du vote, de l'agrégation de jugements et de la fusion de croyances sont adaptées et étudiées de manière axiomatique et computationnelle. Les propriétés axiomatiques connues dans la littérature sur la théorie du choix social sont généralisées à ce nouveau type d'entrée, ainsi que les problèmes de complexité visant à déterminer le résultat du vote. Une autre contribution importante est l'étude de l'agrégation des CP-nets généralisés, c'est-à-dire des CP-nets où la précondition de l'énoncé de préférence est une formule propositionnelle. Nous utilisons différents agrégateurs pour obtenir un classement collectif des résultats possibles. Grâce à cette thèse, deux axes de recherche sont ainsi reliés : l'agrégation des CP-nets classiques et la généralisation des CP-nets à des préconditions incomplètes. Nous contribuons également à l'étude du comportement stratégique dans des contextes de prise de décision collective et de théorie des jeux. Le cadre du vote basé sur les buts est de nouveau étudié sous l'hypothèse que les agents peuvent décider de mentir sur leur but s'ils obtiennent ainsi un meilleur résultat. L'accent est mis sur trois règles de vote majoritaires qui se révèlent manipulables. Par conséquent, nous étudions des restrictions à la fois sur le langage des buts et sur les stratégies des agents en vue d'obtenir des résultats de votes non manipulables. Nous présentons par ailleurs une extension stratégique d'un modèle récent de diffusion d'opinion sur des réseaux d'influence. Dans les jeux d'influence définis ici, les agents ont comme but des formules en LTL et ils peuvent choisir d'utiliser leur pouvoir d'influence pour s'assurer que leur but est atteint. Des solutions classiques telles que la stratégie gagnante sont étudiées pour les jeux d'influence, en relation avec la structure du réseau et les buts des agents. Enfin, nous introduisons une nouvelle classe de concurrent game structures (CGS) dans laquelle les agents peuvent avoir un contrôle partagé sur un ensemble de variables propositionnelles. De telles structures sont utilisées pour interpréter des formules de logique temporelle en temps alternés (ATL), grâce auxquelles on peut exprimer l'existence d'une stratégie gagnante pour un agent dans un jeu itéré (comme les jeux d'influence mentionnés ci-dessus). Le résultat principal montre qu'un CGS avec contrôle partagé peut être représenté comme un CGS avec contrôle exclusif. En conclusion, cette thèse contribue au domaine de la prise de décision collective en introduisant un nouveau cadre de vote basé sur des buts propositionnels. Elle présente une étude de l'agrégation des CP-nets généralisés et une extension d'un cadre de diffusion d'opinion avec des agents rationnels qui utilisent leur pouvoir d'influence. Une réduction du contrôle partagé à un contrôle exclusif dans les CGS pour l'interprétation des logiques du raisonnement stratégique est également proposée. Par le biais de langages logiques divers, les agents peuvent ainsi exprimer buts et préférences sur la décision à prendre, et les propriétés souhaitées pour le processus de décision peuvent en être garanties
Agents having to take a collective decision are often motivated by individual goals. In such scenarios, two key aspects need to be addressed. The first is defining how to select a winning alternative from the expressions of the agents. The second is making sure that agents will not manipulate the outcome. Agents should also be able to state their goals in a way that is expressive, yet not too burdensome. This dissertation studies the aggregation and the strategic component of multi-agent collective decisions where the agents use a compactly represented language. The languages we study are all related to logic: from propositional logic, to generalized CP-nets and linear temporal logic (LTL). Our main contribution is the introduction of the framework of goal-based voting, where agents submit individual goals expressed as formulas of propositional logic. Classical aggregation functions from voting, judgment aggregation, and belief merging are adapted to this setting and studied axiomatically and computationally. Desirable axiomatic properties known in the literature of social choice theory are generalized to this new type of propositional input, as well as the standard complexity problems aimed at determining the result. Another important contribution is the study of the aggregation of generalized CP-nets coming from multiple agents, i.e., CP-nets where the precondition of the preference statement is a propositional formula. We use different aggregators to obtain a collective ordering of the possible outcomes. Thanks to this thesis, two lines of research are thus bridged: the one on the aggregation of complete CP-nets, and the one on the generalization of CP-nets to incomplete preconditions. We also contribute to the study of strategic behavior in both collective decision-making and game-theoretic settings. The framework of goal-based voting is studied again under the assumption that agents can now decide to submit an untruthful goal if by doing so they can get a better outcome. The focus is on three majoritarian voting rules which are found to be manipulable. Therefore, we study restrictions on both the language of the goals and on the strategies allowed to the agents to discover islands of strategy-proofness. We also present a game-theoretic extension of a recent model of opinion diffusion over networks of influence. In the influence games defined here, agents hold goals expressed as formulas of LTL and they can choose whether to use their influence power to make sure that their goal is satisfied. Classical solution concepts such as weak dominance and winning strategy are studied for influence games, in relation to the structure of the network and the goals of the agents. Finally, we introduce a novel class of concurrent game structures (CGS) in which agents can have shared control over a set of propositional variables. Such structures are used for the interpretation of formulas of alternating-time temporal logic, thanks to which we can express the existence of a winning strategy for an agent in a repeated game (as, for instance, the influence games mentioned above). The main result shows by means of a clever construction that a CGS with shared control can be represented as a CGS with exclusive control. In conclusion, this thesis provides a valuable contribution to the field of collective decision-making by introducing a novel framework of voting based on individual propositional goals, it studies for the first time the aggregation of generalized CP-nets, it extends a framework of opinion diffusion by modelling rational agents who use their influence power as they see fit, and it provides a reduction of shared to exclusive control in CGS for the interpretation of logics of strategic reasoning. By using different logical languages, agents can thus express their goals and preferences over the decision to be taken, and desirable properties of the decision process can be ensured

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

In multi-agent systems agents often need to take a collective decision based on the preferences of individuals. A voting rule is used to decide which decision to take, mapping the agents' preferences over the possible candidate decisions into a winning decision for the collection of agents. In these kind of scenarios acting strategically can be seen in two opposite way. On one hand it may be desirable that agents do not have any incentive to act strategically. That is, to misreport their preferences in order to influence the result of the voting rule in their favor or acting on the structure of the election to change the outcome. On the other hand manipulation can be used to improve the quality of the outcome by enlarging the consensus of the winner. These two different scenarios are studied in this thesis. The first one by modeling and describing a natural form of control named ``replacement control'' and characterizing for several voting rules its computational complexity. The second scenario is studied in the form of iterative voting frameworks where individuals are allowed to change their preferences to change the outcome of the election. Computational social choice techniques can be used in very different scenarios. This work reports a first attempt to introduce the use of voting procedures in the field of sentiment analysis. In this area computer scientists extract the opinion of the community about a specific item. This opinion is extracted aggregating the opinion expressed by each individual which leaves a text in a blog or social network about the given item. We studied and proposed a new aggregation method which can improve performances of sentiment analysis, this new technique is a new variance of a well-known voting rule called Borda.
Nei sistemi multi agente spesso nasce la necessità di prendere decisioni collettive basate sulle preferenze dei singoli individui. A tal fine può essere utilizzata una regola di voto che, aggregando le preferenze dei singoli agenti, trovi una soluzione che rappresenti la collettività. In questi scenari la possibilità di agire in modo strategico può essere vista da due diversi e opposti punti di vista. Da una parte può essere desiderabile che gli agenti non abbiano alcun incentivo ad agire strategicamente, ovvero che gli agenti non abbiano incentivi a riportare in modo scorretto le proprie preferenze per influenzare il risultato dell'elezione a proprio favore, oppure che non agiscano sulla struttura del sistema elettorale stesso per cambiarne il risultato finale. D'altra parte l'azione strategica può essere utilizzata per migliorare la qualità del risultato o per incrementare il consenso del vincitore. Questi due diversi scenari sono studiati ed analizzati nella tesi. Il primo modellando e descrivendo una forma naturale di controllo chiamato "replacement control" descrivendo la complessità computazione di tale azione strategica per diverse regole di voto. Il secondo scenario è studiato nella forma dei sistemi di voto iterativi nei quali i singoli individui hanno la possibilità di cambiare le proprie preferenze al fine di influenzare il risultato dell'elezione. Le tecniche di Computational Social Choice inoltre possono essere usate in diverse situazioni. Il lavoro di tesi riporta un primo tentativo di introdurre l'uso di sistemi elettorali nel campo dell'analisi del sentimento. In questo contesto i ricercatori estraggono le opinioni della comunità riguardanti un particolare elemento di interesse. L'opinione collettiva è estratta aggregando le opinioni espresse dai singoli individui che discutono o parlano dell'elemento di interesse attraverso testi pubblicati in blog o social network. Il lavoro di tesi studia una nuova procedura di aggregazione proponendo una nuova variante di una regola di voto ben conosciuta qual è Borda. Tale nuova procedura di aggregazione migliora le performance dell'analisi del sentimento classica.

The three constituent chapters of this thesis tackle independent, self-contained research questions, all concerning welfare economics in general and its application to climate change policy in particular. Climate change is a policy problem for which the costs and benefits are distributed unequally across space and time, as well as one involving a high degree of uncertainty. Therefore, cost-benefit analysis of climate policy ought to be based on a welfare function that is sufficiently sophisticated to incorporate the three dimensions of aggregation: time, risk and space. Chapter 1 is an axiomatic treatment of a stylised model in which all three dimensions appear. The main result is a functional representation of the social welfare function for policy assessment in such situations. Chapter 2 is a numerical mitigation policy analysis. I modify William Nordhaus' RICE-2010 model by replacing his social welfare function with one that allows for different degrees of inequality aversion along the regional and inter-temporal dimension. I find that, holding the inter-temporal coefficient of inequality aversion fixed, performing the optimisation with a greater degree of regional inequality reduces the optimal carbon tax relative to treating the world as a single aggregate consumer. In Chapter 3 I analyse climate policy from the point of view of intergenerational transfers. I propose a system of transfers that allows future generations to compensate the current one for its mitigation effort and demonstrate the effects in an OLG model. When the marginal benefit to a - possibly distant - future generation is greater than the cost of compensating the current generation for its abatement effort, a Pareto improvement is possible by a combination of mitigation policy and transfer payments. I show that under very general assumptions the business-as-usual outcome is Pareto dominated by such policies and derive the conditions for the set of climate policies that are not dominated thus.

Simple games are a fundamental class of cooperative games. They have a huge relevance in several areas of computer science, social sciences and discrete applied mathematics. The algorithmic and computational complexity aspects of simple games have been gaining notoriety in the recent years. In this thesis we review different computational problems related to properties, parameters, and solution concepts of simple games. We consider different forms of representation of simple games, regular games and weighted games, and we analyze the computational complexity required to transform a game from one representation to another. We also analyze the complexity of several open problems under different forms of representation. In this scenario, we prove that the problem of deciding whether a simple game in minimal winning form is decisive (a problem that is associated to the duality problem of hypergraphs and monotone Boolean functions) can be solved in quasi-polynomial time, and that this problem can be polynomially reduced to the same problem but restricted to regular games in shift-minimal winning form. We also prove that the problem of deciding wheter a regular game is strong in shift-minimal winning form is coNP-complete. Further, for the width, one of the parameters of simple games, we prove that for simple games in minimal winning form it can be computed in polynomial time. Regardless of the form of representation, we also analyze counting and enumeration problems for several subfamilies of these games. We also introduce influence games, which are a new approach to study simple games based on a model of spread of influence in a social network, where influence spreads according to the linear threshold model. We show that influence games capture the whole class of simple games. Moreover, we study for influence games the complexity of the problems related to parameters, properties and solution concepts considered for simple games. We consider extremal cases with respect to demand of influence, and we show that, for these subfamilies, several problems become polynomial. We finish with some applications inspired on influence games. The first set of results concerns to the definition of collective choice models. For mediation systems, several of the problems of properties mentioned above are polynomial-time solvable. For influence systems, we prove that computing the satisfaction (a measure equivalent to the Rae index and similar to the Banzhaf value) is hard unless we consider some restrictions in the model. For OLFM systems, a generalization of OLF systems (van den Brink et al. 2011, 2012) we provide an axiomatization of satisfaction. The second set of results concerns to social network analysis. We define new centrality measures of social networks that we compare on real networks with some classical centrality measures.
Los juegos simples son una clase fundamental de juegos cooperativos, que tiene una enorme relevancia en diversas áreas de ciencias de la computación, ciencias sociales y matemáticas discretas aplicadas. En los últimos años, los distintos aspectos algorítmicos y de complejidad computacional de los juegos simples ha ido ganando notoriedad. En esta tesis revisamos los distintos problemas computacionales relacionados con propiedades, parámetros y conceptos de solución de juegos simples. Primero consideramos distintas formas de representación de juegos simples, juegos regulares y juegos de mayoría ponderada, y estudiamos la complejidad computacional requerida para transformar un juego desde una representación a otra. También analizamos la complejidad de varios problemas abiertos bajo diferentes formas de representación. En este sentido, demostramos que el problema de decidir si un juego simple en forma ganadora minimal es decisivo (un problema asociado al problema de dualidad de hipergrafos y funciones booleanas monótonas) puede resolverse en tiempo cuasi-polinomial, y que este problema puede reducirse polinomialmente al mismo problema pero restringido a juegos regulares en forma ganadora shift-minimal. También demostramos que el problema de decidir si un juego regular en forma ganadora shift-minimal es fuerte (strong) es coNP-completo. Adicionalmente, para juegos simples en forma ganadora minimal demostramos que el parámetro de anchura (width) puede computarse en tiempo polinomial. Independientemente de la forma de representación, también estudiamos problemas de enumeración y conteo para varias subfamilias de juegos simples. Luego introducimos los juegos de influencia, un nuevo enfoque para estudiar juegos simples basado en un modelo de dispersión de influencia en redes sociales, donde la influencia se dispersa de acuerdo con el modelo de umbral lineal (linear threshold model). Demostramos que los juegos de influencia abarcan la totalidad de la clase de los juegos simples. Para estos juegos también estudiamos la complejidad de los problemas relacionados con parámetros, propiedades y conceptos de solución considerados para los juegos simples. Además consideramos casos extremos con respecto a la demanda de influencia, y probamos que para ciertas subfamilias, varios de estos problemas se vuelven polinomiales. Finalmente estudiamos algunas aplicaciones inspiradas en los juegos de influencia. El primer conjunto de estos resultados tiene que ver con la definición de modelos de decisión colectiva. Para sistemas de mediación, varios de los problemas de propiedades mencionados anteriormente son polinomialmente resolubles. Para los sistemas de influencia, demostramos que computar la satisfacción (una medida equivalente al índice de Rae y similar al valor de Banzhaf) es difícil a menos que consideremos algunas restricciones en el modelo. Para los sistemas OLFM, una generalización de los sistemas OLF (van den Brink et al. 2011, 2012) proporcionamos una axiomatización para la medida de satisfacción. El segundo conjunto de resultados se refiere al análisis de redes sociales, y en particular con la definición de nuevas medidas de centralidad de redes sociales, que comparamos en redes reales con otras medidas de centralidad clásicas

Les systèmes multi-agents mettent en jeu des entités artificielles, conçues par des utilisateurs potentiellement différents, devant se coordonner pour atteindre leur but. La problématique générale est donc l'atteinte d'états "satisfaisants" en dépit de contraintes liées à la distribution des entités qui prennent part à la décision collective, et du caractère non nécessairement coopératifs de ces agents. Je discute de problèmes de vote dans le cas où les profils représentant les préférences des agents prenant part à la décision ne sont pas complètement spécifiés (à cause, par exemple, de la perte de messages du fait de la distribution, ou encore de l'impossibilité de spécifier parfaitement un profil portant sur un nombre rédhibitoire d'alternatives, comme dans le cas de domaines combinatoires). Les questions que nous abordons sont par exemple celles de la taille minimale nécessaire à encoder le profil partiel tout en restant capable de déterminer de manière certaine l'alternative choisie après complétion des votes, ou encore de la difficulté (algorithmique) liée à la détermination des alternatives que l'on peut exclure sans craindre de regretter ce choix plus tard, même si d'autres alternatives peuvent apparaîtrent. J'aborde également des procédures complètement décentralisées d'allocation de ressources. Ici on suppose que les agents débutent avec une allocation initiale et modifient de manière itérative cette allocation par le biais de contrats, c'est-à-dire de réallocation locale de ressources entre eux. En posant la contrainte que chacun de ces contrats doit être individuellement rationnel on se penche sur les garanties de convergence de tels systèmes vers de états efficaces et/ou équitables (au sens par exemple de l'égalitarisme ou l'absence d'envie). J'envisage enfin un processus de prise de décision collective plus délibératif, au sens où les agents peuvent échanger des arguments et contre-arguments, pour (éventuellement) modifier le point de vue des autres. Dans un premier temps je discute d'un cadre où les agents coopèrent en vue d'établir un diagnostic commun d'une situation, alors que les agents ne percoivent que localement leur environnement et ne disposent que de possibilités restreintes de communication. Chaque agent construit (sur la base d'informations partielles) une hypothèse qui pourra être par la suite réfutée par d'autres agents, nous sommes en présence d'un raisonnement de type non-monotone. Je présente enfin brièvement le cadre non-coopératif d'une argumentation multi-partite, où les agents peuvent avoir des opinions réellement contradictoires. Un protocole simple est proposé, qui contraint minimalement la pertinence des arguments échangés, et quelques phénomènes liés au comportement statégique des agents sont illustrés.

Cette thèse étudie des aspects structurels et algorithmiques des restrictions de domaines de préférences, en se focalisant sur les préférences unimodales et les préférences Euclidiennes. Dans la première partie de la thèse, nous introduisons d'abord une généralisation des préférences unimodales sur des graphes quelconques, en se focalisant sur des aspects algorithmiques, notamment le problème de reconnaissance. Dans un deuxième temps, nous nous intéressons aux préférences presque unimodales. Plus précisément, nous proposons une nouvelle métrique d'unimodalité approchée et nous étudions ses propriétés théoriques et computationnelles. La deuxième partie de la thèse est consacrée à l'étude des préférences d-Euclidiennes (où d est la dimension) par rapport à différentes normes. Nous proposons d'abord une heuristique de reconnaissance des préférences 2-Euclidiennes par rapport à la norme l_2, et étudions son efficacité en pratique. Enfin, nous étudions des aspects structurels des préférences 2-Euclidiennes par rapport à la norme l_1
This thesis studies structural and algorithmic aspects of preference domain restrictions, namely single-peaked preferences and Euclidean preferences. In the first part of the thesis, we first introduce a generalization of the notion of single-peakedness on an arbitrary graph. We focus, in particular, on algorithmic aspects, namely the problem of recognition. The notion of nearly single-peakedness is then studied. More precisely, we introduce a new metric of nearly single-peakedness, and we study its theoretical and computational properties. The second part of the thesis is devoted to the study of d-Euclidean preferences (where d is the dimension of the real space) with respect to different norms. We first propose a heuristic algorithm for recognizing 2-Euclidean preferences with respect to the l_2 norm, and study its practical efficiency in practice. Finally, we focus on structural aspects of 2-Euclidean preferences with respect to the l_1 norm

In my Ph.D. dissertation, I have studied problems arising in various aspects of preferences: preference modeling, preference learning, and preference reasoning, when preferences concern outcomes ranging over combinatorial domains. Preferences is a major research component in artificial intelligence (AI) and decision theory, and is closely related to the social choice theory considered by economists and political scientists. In my dissertation, I have exploited emerging connections between preferences in AI and social choice theory. Most of my research is on qualitative preference representations that extend and combine existing formalisms such as conditional preference nets, lexicographic preference trees, answer-set optimization programs, possibilistic logic, and conditional preference networks; on learning problems that aim at discovering qualitative preference models and predictive preference information from practical data; and on preference reasoning problems centered around qualitative preference optimization and aggregation methods. Applications of my research include recommender systems, decision support tools, multi-agent systems, and Internet trading and marketing platforms.

Humans are unique in their ability to flexibly and rapidly adapt their behaviour and select courses of action that lead to future reward. Several ‘component processes’ must be implemented by the human brain in order to facilitate this behaviour. This thesis examines two such components; (i) the neural substrates supporting action selection during value- guided choice using magnetoencephalography (MEG), and (ii) learning the value of environmental stimuli and other people’s actions using functional magnetic resonance imaging (fMRI). In both situations, it is helpful to formally model the underlying component process, as this generates predictions of trial-to-trial variability in the signal from a brain region involved in its implementation. In the case of value-guided action selection, a biophysically realistic implementation of a drift diffusion model is used. Using this model, it is predicted that there are specific times and frequency bands at which correlates of value are seen. Firstly, there are correlates of the overall value of the two presented options, and secondly the difference in value between the options. Both correlates should be observed in the local field potential, which is closely related to the signal measured using MEG. Importantly, the content of these predictions is quite distinct from the function of the model circuit, which is to transform inputs relating to the value of each option into a categorical decision. In the case of social learning, the same reinforcement learning model is used to track both the value of two stimuli that the subject can choose between, and the advice of a confederate who is playing alongside them. As the confederate advice is actually delivered by a computer, it is possible to keep prediction error and learning rate terms for stimuli and advice orthogonal to one another, and so look for neural correlates of both social and non-social learning in the same fMRI data. Correlates of intentional inference are found in a network of brain regions previously implicated in social cognition, notably the dorsomedial prefrontal cortex, the right temporoparietal junction, and the anterior cingulate gyrus.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.

Nei sistemi multi agente spesso nasce la necessità di prendere decisioni collettive basate sulle preferenze dei singoli individui. A tal fine può essere utilizzata una regola di voto che, aggregando le preferenze dei singoli agenti, trovi una soluzione che rappresenti la collettività. In questi scenari la possibilità di agire in modo strategico può essere vista da due diversi e opposti punti di vista. Da una parte può essere desiderabile che gli agenti non abbiano alcun incentivo ad agire strategicamente, ovvero che gli agenti non abbiano incentivi a riportare in modo scorretto le proprie preferenze per influenzare il risultato dell'elezione a proprio favore, oppure che non agiscano sulla struttura del sistema elettorale stesso per cambiarne il risultato finale. D'altra parte l'azione strategica può essere utilizzata per migliorare la qualità del risultato o per incrementare il consenso del vincitore. Questi due diversi scenari sono studiati ed analizzati nella tesi. Il primo modellando e descrivendo una forma naturale di controllo chiamato "replacement control" descrivendo la complessità computazione di tale azione strategica per diverse regole di voto. Il secondo scenario è studiato nella forma dei sistemi di voto iterativi nei quali i singoli individui hanno la possibilità di cambiare le proprie preferenze al fine di influenzare il risultato dell'elezione. Le tecniche di Computational Social Choice inoltre possono essere usate in diverse situazioni. Il lavoro di tesi riporta un primo tentativo di introdurre l'uso di sistemi elettorali nel campo dell'analisi del sentimento. In questo contesto i ricercatori estraggono le opinioni della comunità riguardanti un particolare elemento di interesse. L'opinione collettiva è estratta aggregando le opinioni espresse dai singoli individui che discutono o parlano dell'elemento di interesse attraverso testi pubblicati in blog o social network. Il lavoro di tesi studia una nuova procedura di aggregazione proponendo una nuova variante di una regola di voto ben conosciuta qual è Borda. Tale nuova procedura di aggregazione migliora le performance dell'analisi del sentimento classica.

Στο πλαίσιο της παρούσας διδακτορικής διατριβής μελετώνται υπολογιστικά ζητήματα που προκύπτουν από τη θεωρία της κοινωνικής επιλογής. Ένα από τα κύρια θέματα της θεωρίας αυτής είναι οι εκλογές. Τα προβλήματα που σχετίζονται με τις εκλογές ανήκουν στη θεωρία ψηφοφοριών όπου βασικό πρόβλημα είναι η εύρεση του νικητή των εκλογών όταν έχουμε ως δεδομένες τις προτιμήσεις των ψηφοφόρων. Στη βιβλιογραφία υπάρχουν αρκετοί κανόνες ψηφοφορίας βάσει των οποίων γίνεται ο υπολογισμός της κατάταξης μιας ψηφοφορίας και της ανάδειξης του νικητή. Η θεωρία των ψηφοφοριών αποτελεί ένα σημαντικό κλάδο της θεωρίας της κοινωνικής επιλογής με άμεσες εφαρμογές στην κοινωνία, καθώς οι κανόνες αυτοί εφαρμόζονται στην πράξη σε βουλευτικές, δημοτικές ή τοπικές εκλογές, καθώς επίσης και σε αρκετές επιτροπές σχετικές με την λήψη συλλογικών αποφάσεων. Στη συγκεκριμένη διατριβή μελετούμε πρώτα τους κανόνες ψηφοφορίας που πρότειναν ο Dodgson και ο Young, οι οποίοι είναι σχεδιασμένοι έτσι ώστε να εντοπίζουν τον υποψήφιο που είναι διαισθητικά πιο κοντά στο να είναι ο νικητής σύμφωνα με το κριτήριο του Condorcet. Σύμφωνα με το κριτήριο αυτό, νικητής θα πρέπει να είναι ο υποψήφιος που έχει την προτίμηση της πλειοψηφίας έναντι των άλλων υποψήφιων. Ωστόσο κάτι τέτοιο δεν μπορεί να υπολογιστεί πάντα, καθώς οι προτιμήσεις της πλειοψηφίας μπορεί να είναι κυκλικές. Για παράδειγμα σε μια εκλογή με 3 υποψηφίους, ο υποψήφιος a να προτιμάται σε σχέση με τον b, ο b να προτιμάται σε σχέση με τον c, αλλά ο c να προτιμάται σε σχέση με τον a. Στην περίπτωση αυτή δεν μπορεί να καθοριστεί ο νικητής των εκλογών σύμφωνα με το κριτήριο του Condorcet. Για το λόγο αυτό χρησιμοποιούμε τους κανόνες ψηφοφορίας που προτάθηκαν από τους Dodgson και Young, οι οποίοι παρέχουν μια διαφορετική έννοια εγγύτητας ενός υποψήφιου στο να αναδειχθεί νικητής κατά Condorcet. Οι συγκεκριμένοι κανόνες αποτελούν ένα σημαντικό κομμάτι της βιβλιογραφίας της θεωρίας της Κοινωνικής Επιλογής διότι διαισθητικά παρουσιάζουν υψηλή εγγύτητα με τον κανόνα του Condorcet. Πιο συγκεκριμένα και σύμφωνα με τον κανόνα του Dodgson ισχύουν τα εξής: δεδομένου ενός συνόλου προτιμήσεων των ψηφοφόρων, ο βαθμός ενός υποψηφίου ορίζεται ως ο ελάχιστος αριθμός των ανταλλαγών που πρέπει να γίνουν μεταξύ γειτονικών υποψηφίων στην κατάταξη των ψηφοφόρων έτσι ώστε ο συγκεκριμένος υποψήφιος να αναδειχθεί νικητής κατά Condorcet. Ο υποψήφιος που έχει τον ελάχιστο βαθμό Dodgson είναι νικητής κατά Dodgson. Αντίστοιχα, σύμφωνα με τον κανόνα του Young ο βαθμός ενός υποψηφίου είναι το μέγεθος του μεγαλύτερου υποσυνόλου ψηφοφόρων έτσι ώστε, αν ληφθούν υπόψη μόνο αυτά τα ψηφοδέλτια, ο συγκεκριμένος υποψήφιος να γίνεται νικητής κατά Condorcet. Ο υποψήφιος με το μέγιστο βαθμό Young είναι νικητής κατά Young. Δυστυχώς, ο υπολογισμός του βαθμού ενός δεδομένου υποψηφίου είναι δύσκολος είτε με τον κανόνα του Dodgson είτε με τον κανόνα του Young. Για αυτό το λόγο τα υπολογιστικά ζητήματα που προκύπτουν και μελετώνται στην παρούσα διατριβή αφορούν στην προσέγγιση των δυο αυτών κανόνων ψηφοφορίας. Πιο συγκεκριμένα παρουσιάζονται δύο αλγόριθμοι που προσεγγίζουν το βαθμό ενός υποψηφίου σύμφωνα με τον κανόνα του Dodgson: ένας άπληστος αλγόριθμος και ένας αλγόριθμος βασισμένος σε γραμμικό πρόγραμμα. Οι δυο αυτοί αλγόριθμοι έχουν λόγο προσέγγισης H_{m-1}, όπου m είναι ο αριθμός των υποψηφίων και H_{m-1} είναι ο (m-1)-ος αρμονικός αριθμός. Επίσης, αποδεικνύεται ότι δεν υπάρχει αλγόριθμος πολυωνυμικού χρόνου που να προσεγγίζει το βαθμό Dodgson κατά λογαριθμικό παράγοντα, εκτός εάν υπάρχουν για τα προβλήματα της κλάσης NP αλγόριθμοι ψευδο-πολυωνυμικού χρόνου. Παρότι διαισθητικά υπερέχει ο άπληστος αλγόριθμος, στη συγκεκριμένη διατριβή υποστηρίζουμε ότι ο αλγόριθμος που είναι βασισμένος σε γραμμικό πρόγραμμα έχει πλεονέκτημα από την οπτική της θεωρίας της κοινωνικής επιλογής. Επιπλέον, αποδεικνύεται ότι ο υπολογισμός κάθε λογικής προσέγγισης της κατάταξης που παράγεται από τον κανόνα Dodgson είναι ένα υπολογιστικά δύσκολο πρόβλημα, γεγονός που εξηγεί, από την πλευρά της θεωρίας της πολυπλοκότητας, το ότι έχουν παρατηρηθεί μεγάλες διαφορές κατά τη σύγκριση εκλογών Dodgson με απλούστερους κανόνες ψηφοφορίας που εμπεριέχονται στη βιβλιογραφία της θεωρίας της κοινωνικής επιλογής. Τέλος, αποδεικνύεται ότι το πρόβλημα υπολογισμού του βαθμού ενός υποψηφίου σύμφωνα με τον κανόνα του Young είναι επίσης υπολογιστικά δύσκολο. Αυτό οδηγεί σε ένα αποτέλεσμα μη προσεγγισιμότητας για την κατάταξη υποψηφίων σε μια εκλογή σύμφωνα με τον κανόνα του Young. Αν και ο κανόνας του Dodgson είναι ένας από τους πιο καλά μελετημένους κανόνες ψηφοφορίας, παρουσιάζει σοβαρές ελλείψεις, τόσο από υπολογιστικής άποψης --- είναι υπολογιστικά δύσκολο ακόμη και να προσεγγιστεί ο βαθμός Dodgson ενός υποψηφίου --- όσο και από την πλευρά της κοινωνικής επιλογής, καθώς αποτυγχάνει σε βασικές επιθυμητές ιδιότητές της, όπως είναι η μονοτονία και η ομοιογένεια. Ωστόσο, αυτό δεν αποκλείει την ύπαρξη προσεγγιστικών αλγορίθμων για τον κανόνα του Dodgson που είναι μονότονοι ή ομοιογενείς, οπότε τίθεται το ερώτημα ύπαρξης τέτοιων αλγόριθμων. Στη διατριβή αυτή δίνονται οριστικές απαντήσεις στα ερωτήματα αυτά. Παρουσιάζεται ένας μονότονος αλγόριθμος εκθετικού χρόνου που πετυχαίνει λόγο προσέγγισης του βαθμού Dodgson ίσο με 2 και το αποτέλεσμα συμπληρώνεται με ένα αυστηρό αντίστοιχο κάτω φράγμα. Παρουσιάζεται επίσης ένας μονότονος προσεγγιστικός αλγόριθμος πολυωνυμικού χρόνου με λόγο O(logm) (όπου m είναι ο αριθμός των υποψηφίων): και στην περίπτωση αυτή το αποτέλεσμα είναι βέλτιστο, λόγω ύπαρξης αντίστοιχου κάτω φράγματος. Επιπλέον, αποδεικνύεται ότι μια μικρή παραλλαγή σε ένα γνωστό κανόνα ψηφοφορίας δίνει ένα μονότονο, ομοιογενή, O(m logm)-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, με τον καλύτερο δυνατό λόγο προσέγγισης, ακόμη και αν αυτό που μας ενδιαφέρει είναι μόνο η ομοιογένεια. Τέλος, μελετώνται διάφορες πρόσθετες ιδιότητες κοινωνικής επιλογής, για τις οποίες δεν υπάρχει αλγόριθμος με λόγο προσέγγισης που να εξαρτάται μόνο από το m . Αυτά τα αποτελέσματα της προσεγγισιμότητας του κανόνα αυτού αποτελούν σημαντική προσφορά της διατριβής καθώς μπορούν να θεωρηθούν ως κανόνες που υπολογίζονται σε πολυωνυμικό χρόνο και πληρούν μάλιστα επιθυμητές κοινωνικές ιδιότητες, ενώ ταυτόχρονα διέπονται και από την φιλοσοφία του κανόνα που θέσπισε ο Dodgson. Ένα άλλο σημαντικό υπολογιστικό πρόβλημα με το οποίο ασχολείται η παρούσα διατριβή είναι αυτό της δωροδοκίας των εκλογών. Στο πρόβλημα της δωροδοκίας μπορεί κάποιος με δεδομένο ένα χρηματικό προϋπολογισμό να αλλάξει τις προτιμήσεις των ψηφοφόρων ώστε να αναδειχθεί νικητής των εκλογών ο υποψήφιος της αρεσκείας του. Στη συγκεκριμένη διατριβή μελετώνται κανόνες ψηφοφορίας που βασίζονται στη βαθμολόγηση των υποψηφίων. Πιο συγκεκριμένα μελετάται η τάξη των κανόνων ψηφοφορίας όπου κάθε ψηφοφόρος εκχωρεί κ βαθμούς στον υποψήφιο που προτιμά ως πρώτο, λ βαθμούς στον υποψήφιο που προτιμά ως δεύτερο και 0 βαθμούς σε όλους τους υπόλοιπους υποψηφίους. Αποδεικνύεται ότι για αυτήν την τάξη των κανόνων βαθμολόγησης η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Στους κανόνες που βασίζονται στην βαθμολόγηση των υποψηφίων περιλαμβάνονται αυτοί της πλειοψηφίας και της 2-έγκρισης όπου μια βέλτιστη στρατηγική δωροδοκίας μπορεί εύκολα να υπολογιστεί, καθώς επίσης και ο κανόνας της 3-έγκρισης όπου η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Λαμβάνοντας υπόψιν την πολυπλοκότητα αυτών των κανόνων εξάγεται το συμπέρασμα ότι οι κανόνες που μελετήθηκαν είναι εκ των πιο απλών που δεν είναι ευάλωτοι στη δωροδοκία.
In this PhD thesis we study computational problems arising from the theory of social choice. One main aspect of Computational Social Choice is voting theory. The most important problem of voting theory is the computation of the winner of the elections when we have as input the preferences of the voters. In the literature there are many voting rules according to which the computation of the winner of the elections is done. Voting theory is a seminal subject in the Computational Social Choice theory with applications in the society. Voting rules are widely used in government and municipal or local elections and also in committees for taking decisions. In this thesis we start by considering voting rules proposed by Dodgson and Young. These rules are both designed to find an alternative closest to being a Condorcet winner. According to the Condorcet criterion, the winner of the elections should be the one that the majority of the voters prefer in relation to every other candidate. Unfortunately, the preferences of the majority may be circular. For example, in an election with 3 candidates, candidate a is preferred to b by the majority and b is preferred in relation to c, but c is preferred to a. Then a Condorcet winner does not exist. Each of these voting rules provide a different notion of proximity of how close they are to Condorcet rule. In the Dodgson rule the score of a candidate, given a set of preferences, is the minimum number of exchanges between adjacent candidates in order for the specific candidate to become a Condorcet winner. The Dodgson winner is the candidate with the minimum Dodgson score. In the Young rule the score of a candidate is the size of the largest subset of voters, when taking in account only these votes, the specific candidate becomes a Condorcet winner. The Young winner is the candidate with the maximum Young score. The score of a given alternative is known to be hard to compute under either rule and so the computational problems that arise and we consider are related to the approximation of the voting rules proposed by Dodgson and Young. We put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of H_{m-1}, where m is the number of alternatives and H_{m-1} is the (m-1)st harmonic number. We also prove that there is no polynomial time algorithm that approximates the Dodgson score by (1/2-ε)lnm, unless problems in NP have quasi-polynomial time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Also, we show that the problem of calculating the Young score is NP-hard to approximate by any factor. This leads to an inapproximability result for the Young ranking. Although Dodgson's rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view --- it is NP-hard even to approximate the Dodgson score within sublogarithmic factors --- and from the social choice point of view --- it fails basic social choice desiderata such as monotonicity and homogeneity. However, this does not preclude the existence of approximation algorithms for Dodgson that are monotonic or homogeneous, and indeed it is natural to ask whether such algorithms exist. In this thesis we give definitive answers to these questions. We design a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(logm)-approximation algorithm (where m is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation on a known voting rule yields a monotonic, homogeneous, polynomial-time O(m logm)-approximation algorithm, and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity. We complete the picture by studying several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist. In this thesis we consider also the important computational problem of bribery in elections, where the winning candidate is computed using a scoring voting rule. In the bribery problem we have an external agent who wants to change the preferences of some voters to make his favorite candidate win the election given a budget. In this thesis we consider scoring voting rules where the voter gives to the first candidate κ points, λ points to his second most preferred candidate and zero points to all other candidates. We prove that for this class of rules bribery is a computationally hard problem. The class of scoring voting rules includes plurality and 2-approval for which an optimal bribing strategy can be computed efficiently as well as 3-approval which is hard to bribe. Concluding we derive that the class of rules we consider is one of the most simple scoring voting rules that are resistant to bribery.

The theory of fair division addresses the fundamental problem of dividing a set of resources among the participating agents in a satisfactory or meaningfully fair manner. This thesis examines the key computational challenges that arise in various settings of fair-division problems and complements the existential (and non-constructive) guarantees and various hardness results by way of developing efficient (approximation) algorithms and identifying computationally tractable instances. • Our work in fair cake division develops several algorithmic results for allocating a divisible resource (i.e., the cake) among a set of agents in a fair/economically efficient manner. While strong existence results and various hardness results exist in this setup, we develop a polynomial-time algorithm for dividing the cake in an approximately fair and efficient manner. Furthermore, we identify an encompassing property of agents’ value densities (over the cake)—the monotone likelihood ratio property (MLRP)—that enables us to prove strong algorithmic results for various notions of fairness and (economic) efficiency. • Our work in fair rent division develops a fully polynomial-time approximation scheme (FPTAS) for dividing a set of discrete resources (the rooms) and splitting the money (rents) among agents having general utility functions (continuous, monotone decreasing, and piecewise-linear), in a fair manner. Prior to our work, efficient algorithms for finding such solutions were known only for a specific set of utility functions. We com- plement the algorithmic results by proving that the fair rent division problem (under general utilities) lies in the intersection of the complexity classes, PPAD (Polynomial Parity Arguments on Directed graphs) and PLS (Polynomial Local Search). • Our work respectively addresses fair division of rent, cake (divisible), and discrete (in- divisible) goods in a partial information setting. We show that, for all these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation.
IBM Ph.D. Fellowship 2020

Matching problems arise in numerous practical settings. Fairness and efficiency are two desirable properties in most such real world scenarios. This dissertation work presents new approaches and models for capturing and solving fairness issues in different practical settings and develops algorithms to identify fair and/or efficient matchings. The thesis is organised into two logical parts: one-sided preferences and two-sided preferences. Part 1: One-Sided Preferences Fair and Efficient Delivery Motivated by the classical delivery problem, we introduce a novel model of fair division where delivery tasks must be fairly distributed among a set of agents. The delivery tasks are placed on the vertices of a given acyclic graph. The cost incurred by the agents is determined by the distance they travel from the hub where they start to service their assigned tasks. We study the existence of fair and efficient allocations of tasks to agents. We choose the fairness notions: EF1 and MMS and efficiency notions: Pareto optimality and Social optimality. We find that while all these notions can be satisfied independently, the only combination of fairness and efficiency that can always be guaranteed is MMS and PO. For the remaining combinations, we provide characterisations of the space of instances for which they can be achieved. We find that most of the relevant problems are NP-Hard. We provide an XP-algorithm which finds the different combinations of fairness and efficiency whenever they exist. Repeated Matchings We propose a novel repeated matching model where the valuations of agents may change with how often they have received an item in the past. We study achieving fairness and efficiency separately as well as in conjunctions in this setting. We find that optimizing for social welfare is NP-Hard for general valuations and tractable when the valuations are monotone with time. We also prove that maximizing for social welfare over the space of EF1 repeated matchings is NP-Hard. Further, we provide algorithms and non-existence results for EF1 and EFX repeated matchings in different settings. Part 2: Two Sided Preferences Fairness and Stability in Many-to-One Matchings We seek to optimize a fairness measure over the space of stable many-to-one matchings, motivated by a college admissions setting. With leximin optimality as the fairness notion, we first show the intractability of this problem. We identify a minimal set of assumptions that makes this problem solvable in polynomial time. This requires that the agents on either side have the same ordinal rankings over the agents on the other side and that these must be strict. We show that on relaxing to weak rankings, the problem becomes APX-Hard. When we remove the ranking assumption but maintain strict preferences, the problem is NP-Hard. Additionally, we show that the leximin optimal stable matching can be efficiently computed in the special case of two colleges. Incentive Compatibility in Stable Fractional Matchings We investigate the existence of incentive compatible mechanisms that find stable fractional matchings. We show, for general settings, that no incentive compatible mechanism can be stable. We characterise the space of instances that have a unique stable fractional matching. We prove for this set of instances that any stable matching mechanism will be incentive compatible
Tata Consultancy Services