Dans cette thèse, nous avons étudié quelques problèmes qui émergent des interactions entre la théorie des jeux et la théorie des treillis. Nous avons introduit la nouvelle notion de jeu multicritère avec interactions entre critères et proposé comme solution pour ces jeux le concept d'équilibre de Choquet-Nash. Nous avons aussi étudié le calcul de la valeur de Shapley d'un jeu coopératif sur un treillis. Plusieurs algorithmes ont été proposés. Un cas polynomial a été mis en exergue : celui des jeux de graphe pondéré sur un produit de chaînes. Nous avons également introduit le modèle de jeu coopératif sur un ordre colore. / In this thesis, we have studied some problems that emerge from the interactions between game theory and lattice theory. We introduced the new notion of multi-criteria game with interactions between criteria and proposed as a solution for these games the concept of Choquet-Nash equilibrium. We studied the computation of the Shapley value of a cooperative game on a lattice. Several algorithms have been proposed for this purpose. A polynomial case was highlighted : that of weighted graph games on a product of chains. We have also introduced the notion of a cooperative game on a set-coloured poset.

AN ABSTRACT OF THE THESIS OF ISMAIL GUNEYDAS, for the Master of Science degree in Computer Science, presented on 5th November 2008, at Southern Illinois University Carbondale. TITLE: ACTOR POSITIONING IN WIRELESS SENSOR AND ACTOR NETWORKS USING MATCHING THEORY. MAJOR PROFESSOR: Dr. KEMAL AKKAYA In most of the Wireless sensor and actor network (WSAN) applications, the locations for the actors are determined autonomously by the collaboration of actors and/or sensors in order to eliminate human intervention as much as possible. Particularly, sensors can collaborate in a distributed manner and elect cluster-heads (CHs) among them which will be taking into account the distribution of the sensors within the region. In such cases, the actors can then move to such sensor locations (i.e., replace them as cluster-heads) as they have the ability to move by talking to nearby sensors/actors. Such movement, however, should be done wisely in order to minimize the total distance that will be traveled by the actors so that their lifetimes can be extended. Nevertheless, this may not be possible since not all the actor and CH locations will be known to each actor. In addition, the actors may not be reachable to each other and thus conflicts in assignments can easily occur. In this thesis, we propose an actor-CH location matching algorithm which will detect the CH locations and assign the actors to such locations in a distributed manner with the minimized travel distance. We adapt the Gale-Shapley (G-S) stable matching algorithm from Matching Theory in order to prevent conflicts and minimize the travel distance. In this matching algorithm, actors are regarded as men and CHs are regarded as women. First, we detect the CH locations through running a quorum-based search within the sensor network. Later, G-S is run on actor and CH locations. Once the locations are determined, each actor moves to that location. We evaluated the performance of our approach through simulation and have shown that our approach can produce results very close to the brute force approach.

nÃo hà / Esta pesquisa fez uma aplicaÃÃo do Valor de Shapley e do Ãndice de Poder de Shapley-Shubik no contexto da Teoria dos Jogos Cooperativos, com enfoque na repartiÃÃo da renda gerada nas bilheterias dos jogos do Campeonato Cearense de Futebol de 2010. Os dados foram coletados da pÃgina na internet da FederaÃÃo Cearense de Futebol-FCF, do blog Contexto Esportivo e do portal da transparÃncia do Tribunal de Contas do MunicÃpio-TCM. Aplicou-se o Valor de Shapley e o Ãndice de Poder de Shapley-Shubik para classificar os clubes de acordo com os ganhos de renda lÃquida obtidos nesta alocaÃÃo. Os resultados mostraram que a alocaÃÃo do Valor de Shapley à mais equitativa, de modo que clubes como QuixadÃ, Limoeiro e Boa Viagem, que obtiveram arrecadaÃÃo negativa pelo sistema de rateio atual da renda lÃquida, passaram a auferir renda lÃquida positiva com a alocaÃÃo do Valor de Shapley, de modo que pode-se dizer que estes clubes sÃo subsidiados com a repartiÃÃo de renda via valor de Shapley. Verificou-se que os clubes de maiores rendas lÃquidas obtiveram maiores valores para o Ãndice de Poder Shapley-Shubik, com exceÃÃo apenas do Fortaleza Esporte Clube. / This research is an application of the Shapley Value and the Power Index Shapley-Shubik as studied in the context of the Cooperative Game Theory. Specifically, this paper studied the distribution of net income generated at the box office of the FederaÃÃo Cearense de Futebol-FCF during the 2010 football championship. The data were collected from the website of FCF, as well as from the Contexto Esportivo blog, and from the ransparency portal of the Tribunal de Contas do MunicÃpio-TCM. The Shapley value and the power index Shapley-Shubik were applied to rank the football clubs participants according to the net income gains achieved in this allocation. The results revealed that the Shapley value application is more equal because the minor participants clubs like QuixadÃ, Limoeiro e Boa Viagem, with negative receipts from games in the previous status, get now positive ones from those techniques. The results from Power Index Shapley-Shubik show that the bigger the football club the bigger the net receipt from games, except to Fortaleza Esporte Clube.

Despite promotion by well-known economists and supporting economic theory, econometric analyses of voucher systems often find that they have been unsuccessful in improving traditional measures of educational success. This paper examines a possible explanation of this phenomenon by comparing the drivers of educational achievement and of school popularity by examining private school choice. The findings of this paper indicate that there is a disconnect between school success and school popularity, which adversely effects both the demand and supply-side benefits of voucher systems. Additionally, this paper reviews matching mechanisms that seek to efficiently match students with schools based on both student and school preferences.

Energy accounting determines how much a software process contributes to the total system energy consumption. It is the foundation for evaluating software and has been widely used by operating system based energy management. While various energy accounting policies have been tried, there is no known way to evaluate them directly simply because it is hard to track every hardware use by software in a heterogeneous multicore system like modern smartphones and tablets. This work provides the ground truth for energy accounting based on multi-player game theory and offers the first evaluation of existing energy accounting policies, revealing their important flaws. The proposed ground truth is based on Shapley value, a single value solution to multi-player games of which four axiomatic properties are natural and self-evident to energy accounting. This work further provides a utility optimization formulation of energy management and shows, surprisingly, that energy accounting does not matter for existing energy management solutions that control the energy use of a process by giving it an energy budget, or budget based energy management (BEM). This work shows an optimal energy management (OEM) framework can always outperform BEM. While OEM does not require any form of energy accounting, it is related to Shapley value in that both require the system energy consumption for all possible combination of processes under question. This work reports a prototype implementation of both Shapley value-based energy accounting and OEM based scheduling. Using this prototype and smartphone workload, this work experimentally demonstrates how erroneous existing energy accounting policies can be, show that existing BEM solutions are unnecessarily complicated yet underperforming by 20% compared to OEM.

The objective of this work is to develop a scheme to minimize a combination of power consumption and congestion delay in communication networks. I model the network as a set of parallel links, with flows that are able to divide their traffic among the links available to them. Power consumption at each link is concave and increasing in the load, with a non-zero intercept at the origin corresponding to idle power consumption. I believe it is possible to minimize the overall power consumption by possibly sharing links and shutting down the idle links, as long as it does not lead to significant congestion in the network. In this project, I focus on developing incentives for flows to choose the minimum cost solution. My solutions involve two elements - (i) a mypopic and selfish controller adopted by each source, which attempts to minimize cost seen by that flow, and (ii) a pricing scheme at each link whose objective is to provide appropriate signals to the controllers at the source. I use ideas drawn from population games to choose the set of source controllers, while I experiment with using marginal costs and weighted Shapley values for the pricing scheme. I show that the weighted Shapley value as a pricing scheme is superior to that of marginal cost pricing in some simple cases.

Made available in DSpace on 2014-06-12T17:16:32Z (GMT). No. of bitstreams: 2 arquivo558_1.pdf: 1430817 bytes, checksum: a4b16d2e9a8f62f0f5c40945bbb618fb (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Pode-se definir Capital Humano como os atributos que as pessoas têm ou adquirem que as tornam mais produtivas no contexto econômico. A despeito da dimensão do conceito, a literatura do crescimento econômico tem como praxe utilizar as variáveis de escolaridade para representar tal forma de capital. Utilizando um conceito de Capital Humano mais abrangente, que incorpora tanto aspectos qualitativos, quanto aspectos quantitativos da escolaridade, esse trabalho busca construir indicadores de pobreza educacional para as Unidades Federativas do Brasil. Pode-se dizer que existe pobreza educacional quando uma ou mais pessoas não atingem um nível mínimo necessário de escolaridade para os padrões da sociedade em questão, em outras palavras, esse conceito é análogo ao conceito de pobreza. Partindo da idéia que o estoque de Capital Humano é um dos componentes do bem-estar, combater a pobreza educacional é uma forma de aumentar o bem-estar de uma sociedade. Assim, os objetivos da tese são: construir um indicador de capital humano incorporando aspectos quantitativos e qualitativos da escolaridade, que segundo Schultz (1964) é o maior componente do investimento em capital humano; construir indicadores de pobreza educacional, buscando estudar as camadas inferiores da distribuição da educação; e por fim utilizar a abordagem do valor de Shapley para decompor a Pobreza Educacional por subgrupos (idade, sexo, raça), a fim de investigar quais os mais afetados em cada Unidade Federativa do Brasil. É importante ressaltar que o método de decomposição de Shapley generalizado por Shorrocks (1999) permite identificar a participação de cada subgrupo separadamente num procedimento de decomposição simultâneo, e que até a generalização proposta por Shorrocks (1999) não era possível separar a contribuição de cada subgrupo num procedimento desse tipo. De forma geral, os resultados encontrados apontam para o sucesso das políticas educacionais dos últimos anos que visavam aumentar o acesso à escolaridade, no entanto, percebe-se que as disparidades regionais relacionadas à escolaridade se mantiveram nos anos analisados (1996 e 2006)

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / No Brasil, a busca pela reduÃÃo das ineficiÃncias observadas na alocaÃÃo de vagas em instituiÃÃes de ensino superior via o tradicional vestibular levou à formulaÃÃo e implantaÃÃo de um mecanismo alternativo de seleÃÃo para admissÃo superior: o Sistema de SeleÃÃo Unificada (SISU), criado em 2010. O mecanismo, tecnicamente falando, à um algoritmo de matching com as seguintes caracterÃsticas: i) cada estudante que recebe oferta de matrÃcula decide por aceitar ou rejeitar a oferta recebida; ii) rejeiÃÃes de ofertas provocam a realizaÃÃo de novas propostas; e iii) propostas sÃo aceitas temporariamente, podendo cada oferta aceita ser âtrocadaâ por uma oferta considerada âmelhorâ. Ou seja, o SISU à um mecanismo semelhante ao Algoritmo Deferred Acceptance (Algoritmo Gale-Shapley) com os cursos propondo. Apesar da importÃncia do SISU, a literatura econÃmica sobre o tema à basicamente inexistente. Nesse sentido, a presente dissertaÃÃo buscou, à luz da teoria dos jogos, entender e caracterizar os incentivos propiciados pelo SISU atravÃs de dois mecanismos teÃricos desenvolvidos, o SISUα e o SISUβ. Ambos sÃo modelados como mecanismos de matching dinÃmicos. Caracterizamos estratÃgias nÃo dominadas para o SISUβ e o SISUα. Utilizando o SISUα como a melhor aproximaÃÃo disponÃvel para o SISU, concluÃmos que a introduÃÃo do SISU apresentou um importante avanÃo em relaÃÃo ao vestibular em termos de ganhos de eficiÃncia do matching entre alunos e cursos. / In Brazil, the quest for reducing observed inefficiencies in the allocation of seats in higher education institutions through traditional examination (Vestibular) led to the formulation and implementation of an alternative mechanism of selection: the Unified Selection System (SISU), created in 2010. Technically speaking, the mechanism is a matching algorithm with the following characteristics: i) each student who receives an offer decides to accept or reject the received offer; ii) rejections of offers prompt new proposals; iii) proposals are accepted temporarily, and each offer can be âreplacedâ by an offer considered âbetterâ. That is, the SISU is a mechanism similar to the Deferred Acceptance Algorithm (Gale-Shapley Algorithm). Despite the importance of SISU, the economic literature on the subject is basically nonexistent. In this sense, this dissertation sought, in light of game theory, to understand and characterize the incentives provided by SISU through two developed theoretical mechanisms, the SISUα and SISUβ. Both are modeled as dynamic matching mechanisms. We characterize undominated strategies for SISUβ and SISUα. Using SISUα as the best approximation available to SISU, we conclude that the introduction of SISU showed a significant improvement on Vestibular in terms of gains of efficiency from matching between students and courses.

We propose the use of methods based on the Shapley value to assess the fact that private returns to lower levels of educational attainment should incorporate prospective returns from higher attainment levels, since achieving primary education is a necessary condition to enter secondary and tertiary educational levels. We apply the proposed adjustment to a global dataset of private returns to different educational attainment levels and find that the corrected returns to education imply a large shift of returns from tertiary to primary schooling in countries at all income levels. (authors' abstract) / Series: Department of Economics Working Paper Series

Tout d'abord, nous traitons des jeux d'oligopole de Cournot sous forme caractéristique gamma. Nous montrons que ces jeux sont balancés lorsque les fonctions de profit individuel sont concave. Ensuite, lorsque les fonctions de coût individuel sont linéaires, la «valeur au prorata de Nash» appartient au cœur. Par la suite, nous étudions les jeux d'oligopole de Cournot sous forme d'intervalle gamma. Nous prouvons que le cœur intervalle (standard) est non-vide si et seulement si le jeu d'oligopole de Cournot sous forme caractéristique gamma associé à la meilleure (plus faible) capacité qu'obtient chaque coalition admet un cœur non vide. Ensuite, nous analysons les jeux d'oligopole de Stackelberg sous forme caractéristique gamma. Nous montrons que le cœur est égal à l'ensemble des imputations. Ensuite, nous donnons une condition nécessaire et suffisante, qui dépend de l'hétérogénéité des coûts marginaux, assurant la non-vacuité du cœur. Enfin, nous considérons les jeux d'oligopole de Bertrand. Nous prouvons que les jeux sous les formes caractéristiques alpha ou bêta satisfont à la propriété de convexité. Ensuite, nous prouvons que la valeur de partage égalitaire appartient au cœur des jeux sous forme caractéristique gamma et nous donnons une condition suffisante qui assure que ces jeux satisfont à la propriété de convexité. Nous prolongeons cette analyse en supposant que les coûts marginaux sont distincts. Si la constante de la demande est suffisamment petite, alors les jeux sous forme caractéristique bêta satisfont à la propriété de balancement total. Autrement, ces jeux satisfont à la propriété de convexité. / In the first essay, we study Cournot oligopoly TU-games in gamma-characteristic function form. First, we prove that if any individual profit function is concave, such games are balanced. Then, when the individual cost functions are linear, we provide a solution in the core, called NP(Nash Prorata) value. The second essay considers Cournot oligopoly interval game in gamma-set function form. The first (second) result states that the interval (standard) core is non empty if and only if the Cournot oligopoly TU-game associated with the best (worst) worth of every coalition in its worth interval admits a non-empty core. In the thirdessay, we focus on Stackelberg oligopoly TU-games in gamma-characteristic function form. First, we prove that the core is equal to the set of imputations. Th en, we provide a necessary and sufficient condition, depending on the heterogeneity of firms' marginal costs, under which the core is non-empty. In the fourth essay, we show that Bertrand oligopoly TU-games inalpha and beta-characteristic function forms are convex. Then, we prove that the equal division solution is in the core of Bertrand oligopoly TU-games in gamma-characteristic function form and we give a sufficient condition under which such games are convex. The fifth essay studies the case where the marginal costs are distinct. If the intercept of demand is sufficiently small then games in _beta-characteristic function form are totally balanced. Otherwise, these games are convex.