Theory as an approach to generative composition and interactive computer music. Inspired by the notion of Performance Indeterminacy, software has been developed that attempts to simulate the interactions of improvising performers using a multi-agent system based on the ‘Iterated Prisoner’s Dilemma’. Composition activities and programming activities have formed a symbiotic relationship throughout the creation of the portfolio as each has constantly informed the other. Stylistically, the works presented fall into the experimental genre, although individually they address a wide range of aesthetic goals. The main contribution of this portfolio is a new approach to generative composition based on behavioural models, creating a sense of form bottom-up through modelling the social dynamics of music performance. Through this approach, the direct modelling of musical structures is avoided; instead larger scale forms emerge through the interactions of an ensemble of ‘improvising’ agents. This method offers a departure from previous complex systems work in the area of music, creating computer models of specific musical situations. Links between the Iterated Prisoner’s Dilemma and music are also established and combined with current music technologies. / Thesis(Ph.D.)- University of Adelaide, Elder Conservatorium of Music, 2008

Theory as an approach to generative composition and interactive computer music. Inspired by the notion of Performance Indeterminacy, software has been developed that attempts to simulate the interactions of improvising performers using a multi-agent system based on the ‘Iterated Prisoner’s Dilemma’. Composition activities and programming activities have formed a symbiotic relationship throughout the creation of the portfolio as each has constantly informed the other. Stylistically, the works presented fall into the experimental genre, although individually they address a wide range of aesthetic goals. The main contribution of this portfolio is a new approach to generative composition based on behavioural models, creating a sense of form bottom-up through modelling the social dynamics of music performance. Through this approach, the direct modelling of musical structures is avoided; instead larger scale forms emerge through the interactions of an ensemble of ‘improvising’ agents. This method offers a departure from previous complex systems work in the area of music, creating computer models of specific musical situations. Links between the Iterated Prisoner’s Dilemma and music are also established and combined with current music technologies. / Thesis(Ph.D.)- University of Adelaide, Elder Conservatorium of Music, 2008

Machine learning is increasingly involved in both our production and consumption of video. One symptom of this is the appearance of automated video editing applications. As this technology spreads rapidly to consumers, the need for substantive research about its social impact grows. To this end, this project maintains a focus on video editing as a microcosm of larger shifts in cultural objects co-authored by artificial intelligence. The window in which this research occurred (2010-2015) saw machine learning move increasingly into the public eye, and with it ethical concerns. What follows is, on the most abstract level, a discussion of why these ethical concerns are particularly urgent in the realm of the moving image. Algorithmic editing consists of software instructions to automate the creation of timelines of moving images. The criteria that this software uses to query a database is variable. Algorithmic authorship already exists in other media, but I will argue that the moving image is a separate case insofar as the raw material of text and music software can develop on its own. The performance of a trained actor can still not be generated by software. Thus, my focus is on the relationship between live embodied performance, and the subsequent algorithmic editing of that footage. This is a process that can employ other software like computer vision (to analyze the content of video) and predictive analytics (to guess what kind of automated film to make for a given user). How is performance altered when it has to communicate to human and non-human alike? The ritual of the iterative frame gives literal form to something that throughout human history has been a projection: the omniscient participant observer, more commonly known as the Divine. We experience black boxed software (AI's, specifically neural networks, which are intrinsically opaque) as functionally omniscient and tacitly allow it to edit more and more of life (e.g. filtering articles, playlists and even potential spouses). As long as it remains disembodied, we will continue to project the Divine on to the black box, causing cultural anxiety. In other words, predictive analytics alienate us from the source code of our cultural texts. The iterative frame then is a space in which these forces can be inscribed on the body, and hence narrated. The algorithmic editing of content is already taken for granted. The editing of moving images, in contrast, still requires a human hand. We need to understand the social power of moving image editing before it is delegated to automation. Practice Section: This project is practice-led, meaning that the portfolio of work was produced as it was being theorized. To underscore this, the portfolio comes at the end of the document. Video editors use artificial intelligence (AI) in a number of different applications, from deciding the sequencing of timelines to using facial and language detection to find actors in archives. This changes traditional production workflows on a number of levels. How can the single decision cut a between two frames of video speak to the larger epistemological shifts brought on by predictive analytics and Big Data (upon which they rely)? When predictive analytics begin modeling the world of moving images, how will our own understanding of the world change? In the practice-based section of this thesis, I explore how these shifts will change the way in which actors might approach performance. What does a gesture mean to AI and how will the editor decontextualize it? The set of a video shoot that will employ an element of AI in editing represents a move towards ritualization of production, summarized in the term the 'iterative frame'. The portfolio contains eight works that treat the set was taken as a microcosm of larger shifts in the production of culture. There is, I argue, metaphorical significance in the changing understanding of terms like 'continuity' and 'sync' on the AI-watched set. Theory Section In the theoretical section, the approach is broadly comparative. I contextualize the current dynamic by looking at previous shifts in technology that changed the relationship between production and post-production, notably the lightweight recording technology of the 1960s. This section also draws on debates in ethnographic filmmaking about the matching of film and ritual. In this body of literature, there is a focus on how participant observation can be formalized in film. Triangulating between event, participant observer and edit grammar in ethnographic filmmaking provides a useful analogy in understanding how AI as film editor might function in relation to contemporary production. Rituals occur in a frame that is dependent on a spatially/temporally separate observer. This dynamic also exists on sets bound for post-production involving AI, The convergence of film grammar and ritual grammar occurred in the 1960s under the banner of cinéma vérité in which the relationship between participant observer/ethnographer and the subject became most transparent. In Rouch and Morin's Chronicle of a Summer (1961), reflexivity became ritualized in the form of on-screen feedback sessions. The edit became transparent-the black box of cinema disappeared. Today as artificial intelligence enters the film production process this relationship begins to reverse-feedback, while it exists, becomes less transparent. The weight of the feedback ritual gets gradually shifted from presence and production to montage and post-production. Put differently, in cinéma vérité, the participant observer was most present in the frame. As participant observation gradually becomes shared with code it becomes more difficult to give it an embodied representation and thus its presence is felt more in the edit of the film. The relationship between the ritual actor and the participant observer (the algorithm) is completely mediated by the edit, a reassertion of the black box, where once it had been transparent. The crucible for looking at the relationship between algorithmic editing, participant observation and the black box is the subject in trance. In ritual trance the individual is subsumed by collective codes. Long before the advent of automated editing trance was an epistemological problem posed to film editing. In the iterative frame, for the first time, film grammar can echo ritual grammar and indeed become continuous with it. This occurs through removing the act of cutting from the causal world, and projecting this logic of post-production onto performance. Why does this occur? Ritual and specifically ritual trance is the moment when a culture gives embodied form to what it could not otherwise articulate. The trance of predictive analytics-the AI that increasingly choreographs our relationship to information-is the ineffable that finds form in the iterative frame. In the iterative frame a gesture never exists in a single instance, but in a potential state. The performers in this frame begin to understand themselves in terms of how automated indexing processes reconfigure their performance. To the extent that gestures are complicit with this mode of databasing they can be seen as votive toward the algorithmic. The practice section focuses on the poetics of this position. Chapter One focuses on cinéma vérité as a moment in which the relationship between production and post-production shifted as a function of more agile recording technology, allowing the participant observer to enter the frame. This shift becomes a lens to look at changes that AI might bring. Chapter Two treats the work of Pierre Huyghe as a 'liminal phase' in which a new relationship between production and post-production is explored. Finally, Chapter Three looks at a film in which actors perform with awareness that footage will be processed by an algorithmic edit. / The conclusion looks at the implications this way of relating to AI-especially commercial AI-through embodied performance could foster a more critical relationship to the proliferating black-boxed modes of production.

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.

Submitted by Maike Costa (maiksebas@gmail.com) on 2016-08-10T14:17:41Z No. of bitstreams: 1 arquivo total.pdf: 975005 bytes, checksum: 6f8194b9c0cb9c0bbd07b1d2b0ba4b9e (MD5) / Made available in DSpace on 2016-08-10T14:17:41Z (GMT). No. of bitstreams: 1 arquivo total.pdf: 975005 bytes, checksum: 6f8194b9c0cb9c0bbd07b1d2b0ba4b9e (MD5) Previous issue date: 2016-06-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The class of primitive recursive functions is not a formal version to the class of algorithmic functions, we study this special class of numerical functions due to the fact of that many of the functions known as algorithmic are primitive recursive. The approach on the class of primitive recursive functions aims to explore this special class of functions and from that, present solutions for the following problems: (1) given the class of primitive recursive derivations, is there an algorithm, that is, a mechanical procedure for recognizing primitive recursive derivations? (2) Is there a universal function for the class of primitive recursive functions? If so, is this function primitive recursive? (3) Are all the algorithmic functions primitive recursive? To provide solutions to these issues, we base on the hypothetical-deductive method and argue based on the works of Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), among others. We present the theory of Turing machines which is a formal version to the intuitive notion of algorithm, and after that the famous Church-Turing tesis which identifies the class of algorithmic functions with the class of Turing-computable functions. We display the class of primitive recursive functions and show that it is a subclass of Turing-computable functions. Having explored the class of primitive recursive functions we proved as results that there is a recognizer algorithm to the class of primitive recursive derivations; that there is a universal function to the class of primitive recursive functions which does not belong to this class; and that not every algorithmic function is primitive recursive. / A classe das funções recursivas primitivas não constitui uma versão formal para a classe das funções algorítmicas, estudamos esta classe especial de funções numéricas devido ao fato de que muitas das funções conhecidas como algorítmicas são recursivas primitivas. A abordagem acerca da classe das funções recursivas primitivas tem como objetivo explorar esta classe especial de funções e, a partir disto, apresentar soluções para os seguintes problemas: (1) dada a classe das derivações recursivas primitivas, há um algoritmo, ou seja, um procedimento mecânico, para reconhecer derivações recursivas primitivas? (2) Existe uma função universal para a classe das funções recursivas primitivas? Se sim, essa função é recursiva primitiva? (3) Toda função algorítmica é recursiva primitiva? Para apresentar soluções para estas questões, nos pautamos no método hipotético-dedutivo e argumentamos com base nos manuais de Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), entre outros. Apresentamos a teoria das máquinas de Turing, que constitui uma versão formal para a noção intuitiva de algoritmo, e, em seguida, a famosa tese de Church-Turing, a qual identifica a classe das funções algorítmicas com a classe das funções Turing-computáveis. Exibimos a classe das funções recursivas primitivas, e mostramos que a mesma constitui uma subclasse das funções Turing-computáveis. Tendo explorado a classe das funções recursivas primitivas, como resultados, provamos que existe um algoritmo reconhecedor para a classe das derivações recursivas primitivas; que existe uma função universal para a classe das funções recursivas primitivas a qual não pertence a esta classe; e que nem toda função algorítmica é recursiva primitiva.

Made available in DSpace on 2014-12-17T15:04:51Z (GMT). No. of bitstreams: 1 MariaCAB.pdf: 633984 bytes, checksum: 9739dba9dc013192725090e07643d0d7 (MD5) Previous issue date: 2008-08-08 / The current research had as main objective to analyze the possibility of knowledge elaboration/re-elaboration about ideas and algorithmic procedures related to basic operations by pupils of the 6th degree fundamental teaching in a significant learning process. This way the study had as basis a methodological intervention developed in a 6th degree class of a Fundamental Teaching Municipal School in the city of Jo?o Pessoa, PB. The research had as central steps the application of pre-tests (1 and 2); the execution of semi-structured interviews with the pupils involved in the theme deep studies; the elaboration and development of teaching activities, having as referential the significant learning and the application of a pre-test. The data collected in the pre-tests (1 and 2) showed a low level of the pupils comprehension about the contents related to the four operations. The answers to the post-test questions were analyzed mainly from the qualitative point of view based on the mathematic concepts comprehension theory proposed by Skemp (1980) having as complementary subsidy data collected through interviews. The analysis of the results obtained in the post-test showed that the major part of pupils reached a relational comprehension about the ideas and algorithmic procedures related to addition, subtraction, multiplication, and division. Such results showed us that the application of a teaching methodology that privileges the content comprehension, considering the pupils previous knowledge and the reflection about the action along the activities proposed, made possible the elaboration or re-elaboration of knowledge by pupils regarding to contents adopted as theme for our research / A presente pesquisa teve como principal objetivo analisar a possibilidade de elabora??o/reelabora??o de conhecimento acerca das id?ias e procedimentos algoritmos relativos ?s opera??es b?sicas, por alunos do 6? ano do Ensino Fundamental, em um processo de aprendizagem significativa. Para tanto, o estudo teve como base uma interven??o metodol?gica desenvolvida em uma turma do 6? ano de uma Escola da Rede Municipal de Ensino Fundamental da cidade de Jo?o Pessoa-PB. A pesquisa teve como etapas centrais a aplica??o de pr?-testes (1 e 2); a realiza??o de entrevistas semi-estruturadas com os alunos envolvidos nos estudos de aprofundamento do tema; a elabora??o e desenvolvimento de atividades de ensino, tendo como referencial a aprendizagem significativa, e a aplica??o de um p?s-teste. Os dados coletados nos pr?-testes (1 e 2) revelaram um baixo n?vel de compreens?o dos alunos acerca dos conte?dos relativos ?s quatro opera??es. As respostas ?s quest?es do p?s-teste foram analisadas principalmente do ponto de vista qualitativo, com base na teoria de compreens?o de conceitos matem?ticos, proposta por Skemp (1980), tendo como subs?dio, complementar dados coletados por meio de entrevistas. A an?lise dos resultados obtidos no p?s-teste revelou que a maior parte dos alunos atingiu uma compreens?o relacional acerca das id?ias e procedimentos algor?tmicos relativos ? adi??o, subtra??o, multiplica??o e divis?o. Tais resultados indicam que ? aplica??o de uma metodologia de ensino que privilegie a compreens?o dos conte?dos, considerando o conhecimento pr?vio dos alunos e a reflex?o sobre a a??o ao longo das atividades propostas, possibilitaram a elabora??o ou reelabora??o de conhecimento por parte dos alunos, pertinentes aos conte?dos adotados como tema para nossa pesquisa

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.

Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domains permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l‘analyse d’algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d’algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen. / In the present thesis, we try to compare the classical boolean complexity with the algebraic complexity, by studying problems related to polynomials. We consider the algebraic models from Valiant and from Blum, Shub and Smale (BSS). To study the algebraic complexity classes, one can start from results and open questions from the boolean case, and look at their translation in the algebraic context. The comparison of the results obtained in the two settings will then boost our understanding of both complexity theories. The first part follows this framework. By considering a polynomial canonically associated to a boolean formula, we get a link between boolean complexity issues on the formula and algebraic complexity problems on the polynomial. We studied the complexity of computing the polynomial in Valiant's model, as a function of the complexity of the boolean formula. We found algebraic counterparts to some boolean results. Along the way, we could also use some algebraic methods to improve boolean results, in particular by getting better counting reductions. Another motivation for algebraic models of computation is to offer an elegant framework to the study of numerical algorithms. The second part of this thesis follows this approach. We started from new algorithms for the search of approximate zeros of complex systems of n polynomials in n variables. Up to now, those were BSS machine algorithms. We studied the implementation of these algorithms on digital computers, and propose an algorithm using floating arithmetic for this problem.

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.