Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGAL. / In this thesis, we give some new results about the average size of convex hulls made of points chosen in a convex body. This size is known when the points are chosen uniformly (and independently) in a convex polytope or in a "smooth" enough convex body. This average size is also known if the points are independently chosen according to a centered Gaussian distribution. In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and a upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2. The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases. In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in C++ and integrated in the CGAL library.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

Esta tesis tiene dos objetivos principales. El primero es proponer métodos multivariantes para el estudio de las desigualdades socioeconómicas en la mortalidad en áreas pequeñas. El segundo es estudiar estas desigualdades en la práctica en varias ciudades españolas. En consecuencia, se han realizado cuatro estudios diferentes: dos de ellos más metodológicos y los otros dos más aplicados al estudio de las desigualdades. El primer estudio metodológico propone usar Análisis Factorial Bayesiano para el cálculo de índices de privación. Además, en este estudio se concluye que ignorar la variabilidad en la estimación del índice puede conducir a un sesgo cuando las áreas se agrupan según cuantiles del índice. En el segundo estudio se ha reformulado el modelo SANOVA de modo que es posible introducir una covariable dentro de este modelo. Asimismo, dicha reformulación permite la descomposición de la varianza de los patrones estudiados como suma de varianzas de todas las componentes del modelo. Finalmente, los estudios restantes evidencian la existencia de desigualdades socioeconómicas en la mortalidad total y en la mortalidad por las principales causas específicas en once ciudades españolas. Además, para las enfermedades isquémicas del corazón estas desigualdades parecen aumentar ligeramente en el tiempo. / This thesis has two main objectives. The first is to propose multivariate methods for the study of socioeconomic inequalities in mortality in small areas. The second is to study socioeconomic inequalities in mortality in small areas of several Spanish cities. Four different studies were conducted to attain these objectives: two of them focussed on the methodological aspects and the other two being empirical studies focussed on the study of inequalities. The first methodological study proposes the Bayesian factor analysis to calculate a deprivation index. Additionally, this study concludes that ignoring the uncertainty obtained in the estimation of the index may result in a misclassification bias when the areas are grouped according to quantiles of the index. In the second methodological study the SANOVA model has been reformulated enabling the introduction of a covariate in the model. Also, this reformulation permits the decomposition of the variance of the studied patterns into the sum of variances of all the model components. Finally, the other studies show the existence of socioeconomic inequalities in total mortality and mortality by specific causes in eleven major Spanish cities. In addition, for ischemic heart disease these inequalities appear to increase slightly over time.