Gotowa bibliografia na temat „Computational Social Choice Theory”

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.

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é<br>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

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.

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.<br>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