The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

No description available.

Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...

Nous considérons des jeux de congestion sur des graphes. Dans les jeux non-atomiques, nous considérons un ensemble de joueurs infinitésimaux. Chaque joueur veut aller d'un sommet à un autre en choisissant une route de coût minimal. Le coût de chaque route dépend du nombre de joueur la choisissant. Dans les jeux atomiques divisibles, nous considérons un ensemble de joueurs ayant chacun une demande à transférer d'un sommet à un autre, en la subdivisant éventuellement sur plusieurs routes. Dans ces jeux, un équilibre de Nash est atteint lorsque chaque joueur a choisi une stratégie de coût minimal. L'existence d'un équilibre de Nash est assurée sous de faibles hypothèses. Les principaux sujets sont l'unicité, le calcul, l'efficacité et la sensibilité de l'équilibre de Nash. De nombreux résultats sont connus dans le cas où les joueurs sont tous impactés de la même façon par la congestion. Le but de cette thèse est de généraliser ces résultats au cas où les joueurs ont des fonctions de coût différentes. Nous obtenons des résultats sur l'unicité de l'équilibre dans les jeux non-atomiques. Nous donnons deux algorithmes capables de calculer un équilibre dans les jeux non-atomiques lorsque les fonctions de coût sont affines. Nous obtenons une borne sur le prix de l'anarchie pour certains jeux atomiques divisibles et prouvons qu'il n'est pas borné en général, même lorsque les fonctions sont affines. Enfin, nous prouvons des résultats sur la sensibilité de l'équilibre par rapport à la demande dans les jeux atomiques divisibles / We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.

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.

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.