Página 1 dos resultados de 1404 itens digitais encontrados em 0.063 segundos

The stability of the equilibrium outcomes in the admission games induced by stable matching rules

SOTOMAYOR, Marilda
Fonte: SPRINGER HEIDELBERG Publicador: SPRINGER HEIDELBERG
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
57.571943%
A stable matching rule is used as the outcome function for the Admission game where colleges behave straightforwardly and the students` strategies are given by their preferences over the colleges. We show that the college-optimal stable matching rule implements the set of stable matchings via the Nash equilibrium (NE) concept. For any other stable matching rule the strategic behavior of the students may lead to outcomes that are not stable under the true preferences. We then introduce uncertainty about the matching selected and prove that the natural solution concept is that of NE in the strong sense. A general result shows that the random stable matching rule, as well as any stable matching rule, implements the set of stable matchings via NE in the strong sense. Precise answers are given to the strategic questions raised.

Sobre teoremas de equilíbrio de Nash; On Nash equilibrium theorems

Monis, Thais Fernanda Mendes
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 27/08/2010 Português
Relevância na Pesquisa
68.243203%
Nesse trabalho, aplicando métodos da Topologia Algébrica, nós obtivemos novas versões do teorema de equilíbrio de Nash. Nós definimos um conceito de equilíbrio local para jogos não cooperativos, o chamado equilíbrio local fraco, e demonstramos sua existência quando os espaços de estratégia são variedades diferenciáveis e as funções payoff são continuamente diferenciáveis. Nós demonstramos a ineficiência do equilíbrio local fraco no sentido de Pareto; In this work, applying methods of Algebraic Topology, we obtain new versions of the Nash equilibrium theorem. We define a concept of local equilibrium for non-cooperative games, the socalled weak local equilibrium, and we prove its existence when the spaces of strategies are differentiable manifolds and the payoff functions are continuously differentiable. We prove the ineffciency of weak local equilibrium in the Pareto sense

Weak local Nash equilibrium

Biasi, Carlos; Monis, Thaís Fernanda Mendes
Fonte: Universidade Estadual Paulista Publicador: Universidade Estadual Paulista
Tipo: Artigo de Revista Científica Formato: 409-419
Português
Relevância na Pesquisa
68.051895%
In this paper, we consider a concept of local Nash equilibrium for non-cooperative games - the so-called weak local Nash equilibrium. We prove its existence for a significantly more general class of sets of strategies than compact convex sets. The theorems on existence of the weak local equilibrium presented here are applications of Brouwer and Lefschetz fixed point theorems. © 2013 Juliusz Schauder Centre for Nonlinear Studies Nicolaus Copernicus University.

Tempo de convergencia para o equilibrio de Nash nos jogos empacotamento de itens e balanceamento de carga; Convergence time to the Nash equilibrium in packing and load balancing games

Andre Luis Vignatti
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 18/03/2010 Português
Relevância na Pesquisa
48.339814%
Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a escolha egoísta de estratégias pelas entidades pode ou não levar a um estado estável do sistema, chamado de equilíbrio de Nash. Dependendo das condições definidas pelo modelo utilizado, devemos embutir certas regras para as entidades, contanto que as entidades tenham incentivo de utilizá-las e que, além disso, façam com que o sistema alcance um equilíbrio de Nash. Os principais resultados desta tese são relativos ao tempo de convergência para o equilíbrio de Nash, ou seja, buscamos saber quantas vezes os agentes mudam suas estratégias até alcançarem o equilíbrio de Nash, seja agindo de maneira completamente egoísta ou seguindo certas regras. Para o jogo de empacotamento de itens, apresentamos limitantes teóricos para o tempo de convergência, olhando ambos os casos de atualizações seqüenciais ou simultâneas das estratégias. Para o jogo de balanceamento de carga consideramos um modelo distribuído assíncrono com entidades heterogêneas...

GENERALIZED NASH EQUILIBRIUM PROBLEMS - RECENT ADVANCES AND CHALLENGES

Fischer,Andreas; Herrich,Markus; Schönefeld,Klaus
Fonte: Sociedade Brasileira de Pesquisa Operacional Publicador: Sociedade Brasileira de Pesquisa Operacional
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/12/2014 Português
Relevância na Pesquisa
68.180596%
Generalized Nash equilibrium problems have become very important as a modeling tool during the last decades. The aim of this survey paper is twofold. It summarizes recent advances in the research on computational methods for generalized Nash equilibrium problems and points out current challenges. The focus of this survey is on algorithms and their convergence properties. Therefore, we also present reformulations of the generalized Nash equilibrium problem, results on error bounds and properties of the solution set of the equilibrium problems.

Games of capacities : a (close) look to Nash Equilibria

Romero-Medina, Antonio; Triossi, Matteo
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Trabalho em Andamento Formato: application/pdf
Publicado em /07/2007 Português
Relevância na Pesquisa
57.76831%
The paper studies two games of capacity manipulation in hospital-intern markets. The focus is on the stability of Nash equilibrium outcomes. We provide minimal necessary and sufficient conditions guaranteeing the existence of pure strategy Nash Equilibria and the stability of outcomes.

Games with capacity manipulation : incentives and Nash equilibria

Romero-Medina, Antonio; Triossi, Matteo
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/draft; info:eu-repo/semantics/workingPaper Formato: application/pdf
Publicado em 19/08/2011 Português
Relevância na Pesquisa
57.64034%
Studying the interaction between preference and capacity manipulation in matching markets, we prove that acyclicity is a necessary and sufficient condition that guarantees the stability of a Nash equilibrium and the strategy-proofness of truthful capacity revelation under the hospital-optimal and intern-optimal stable rules. We then introduce generalized capacity manipulations games where hospitals move first and state their capacities, and interns are subsequently assigned to hospitals using a sequential mechanism. In this setting, we first consider stable revelation mechanisms and introduce conditions guaranteeing the stability of the outcome. Next, we prove that every stable non-revelation mechanism leads to unstable allocations, unless restrictions on the preferences of the agents are introduced

Endogenous Mechanisms and Nash Equilibrium in Competitive Contracting

Page, Frank H. Jr.; Monteiro, Paulo K.
Fonte: Center for Applied Economics and Policy Research Publicador: Center for Applied Economics and Policy Research
Tipo: Trabalho em Andamento Formato: 317713 bytes; application/pdf
Português
Relevância na Pesquisa
68.19035%
We model strategic competition in a market with asymmetric information as a noncooperative game in which each firm competes for the business of a buyer of unknown type by offering the buyer a catalog of products and prices. The timing in our model is Stackelberg: in the first stage, given the distribution of buyer types known to all firms and the deducible, type-dependent best responses of the agent, firms simultaneously and noncooperatively choose their catalog offers. In the second stage the buyer, knowing his type, chooses a single firm and product-price pair from that firm's catalog. By backward induction, this Stackelberg game with asymmetric information reduces to a game over catalogs with payoff indeterminacies. In particular, due to ties within catalogs and/or across catalogs, corresponding to any catalog profile offered by firms there may be multiple possible expected firm payoffs, all consistent with the rational optimizing behavior of the agent for each of his types. The resolution of these indeterminacies depends on the tie-breaking mechanism which emerges in the market. Because each tie-breaking mechanism induces a particular game over catalogs, a reasonable candidate would be a tie-breaking mechanism which supports a Nash equilibrium in the corresponding catalog game. We call such a mechanism an endogenous Nash mechanism. The fundamental question we address in this paper is...

On the Evolutionary Selection of Sets of Nash Equilibria

BALKENBORG, Dieter; SCHLAG, Karl H.
Fonte: Academic Press Inc Elsevier Science Publicador: Academic Press Inc Elsevier Science
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
58.09391%
It is well established for evolutionary dynamics in asymmetric games that a pure strategy combination is asymptotically stable if and only if it is a strict Nash equilibrium. We use an extension of the notion of a strict Nash equilibrium to sets of strategy combinations called 'strict equilibrium set' and show the following. For a large class of evolutionary dynamics, including all monotone regular selection dynamics, every asymptotically stable set of rest points that contains a pure strategy combination in each of its connected components is a strict equilibrium set. A converse statement holds for two-person games, for convex sets and for the standard replicator dynamic. (c) 2005 Elsevier Inc. All rights reserved.

Penalty methods for the solution of generalized Nash equilibrium problems and hemivariational inequalities with VI constraints

LAMPARIELLO, LORENZO
Fonte: La Sapienza Universidade de Roma Publicador: La Sapienza Universidade de Roma
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
67.77989%
In this thesis we propose penalty methods for the solution of Generalized Nash Equilibrium Problems (GNEPs) and we consider centralized and distributed algorithms for the solution of Hemivariational Inequalities (HVIs) where the feasible set is given by the intersection of a closed convex set with the solution set of a lower-level monotone Variational Inequality (VI).

O equilíbrio de Nash como uma solução para o conflito entre eficiência e custo na escolha de sistemas de tratamento de esgoto sanitário com o auxílio de um modelo de tomada de decisão; The Nash equilibrium as a solution to the conflict between efficiency and cost in the choice of systems for sanitary sewage treatment using a decision making model

LEONETI, Alexandre Bevilacqua; OLIVEIRA, Sonia Valle Walter Borges de; OLIVEIRA, Marcio Mattos Borges de
Fonte: ABES Publicador: ABES
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
68.339814%
A escolha de estações de tratamento de esgoto pode, dentre outras coisas, envolver um conflito entre a eficiência e o custo, pois para o menor custo possível esta escolha também deverá satisfazer várias exigências ambientais. Para auxiliar na escolha de uma estação de menor custo, um modelo baseado em técnicas de tomada de decisão foi desenvolvido por Oliveira (2004). Todavia, se não forem levados em consideração os outros critérios envolvidos, a interação entre os tomadores de decisão e suas respectivas estratégias podem fazer com que a escolha do sistema de tratamento não seja a mais adequada. Para estes casos, o equilíbrio de Nash pode oferece uma solução, construída com base na interação entre os jogadores, a qual poderia satisfazer razoavelmente os interesses conflitantes. Desta forma, o objetivo desta pesquisa foi, com base nos dados de saída do modelo de Oliveira (2004), encontrar o equilíbrio de Nash para propor uma solução para o conflito entre a eficiência e o custo nas escolhas do sistema de tratamento de esgoto sanitário. A comparação entre os diferentes resultados alcançados, quando apenas considerado o critério de menor custo ou de maior eficiência, demonstrou que a adoção do equilíbrio de Nash pode ser uma alternativa viável para solucionar o conflito entre a eficiência e o custo nas escolhas das estações de tratamento de esgoto sanitário.; The choice of sewage treatment plants may...

Local Nash Equilibrium in Social Networks

Zhang, Yichao; Aziz-Alaoui, M. A.; Bertelle, Cyrille; Guan, Jihong
Fonte: Nature Publishing Group Publicador: Nature Publishing Group
Tipo: Artigo de Revista Científica
Publicado em 29/08/2014 Português
Relevância na Pesquisa
48.29983%
Nash equilibrium is widely present in various social disputes. As of now, in structured static populations, such as social networks, regular, and random graphs, the discussions on Nash equilibrium are quite limited. In a relatively stable static gaming network, a rational individual has to comprehensively consider all his/her opponents' strategies before they adopt a unified strategy. In this scenario, a new strategy equilibrium emerges in the system. We define this equilibrium as a local Nash equilibrium. In this paper, we present an explicit definition of the local Nash equilibrium for the two-strategy games in structured populations. Based on the definition, we investigate the condition that a system reaches the evolutionary stable state when the individuals play the Prisoner's dilemma and snow-drift game. The local Nash equilibrium provides a way to judge whether a gaming structured population reaches the evolutionary stable state on one hand. On the other hand, it can be used to predict whether cooperators can survive in a system long before the system reaches its evolutionary stable state for the Prisoner's dilemma game. Our work therefore provides a theoretical framework for understanding the evolutionary stable state in the gaming populations with static structures.

Inapproximability of NP-Complete Variants of Nash Equilibrium

Austrin, Per; Braverman, Mark; Chlamtac, Eden
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/04/2011 Português
Relevância na Pesquisa
48.538037%
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size $O(\log n)$ in the random graph $G(n,1/2)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than $\eta$ (for any $\eta>0$, even when the best Nash equilibrium has value $1-\eta$)...

Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications

Lou, Youcheng; Hong, Yiguang; Xie, Lihua; Shi, Guodong; Johansson, Karl Henrik
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.322305%
In this paper, we investigate a distributed Nash equilibrium computation problem for a time-varying multi-agent network consisting of two subnetworks, where the two subnetworks share the same objective function. We first propose a subgradient-based distributed algorithm with heterogeneous stepsizes to compute a Nash equilibrium of a zero-sum game. We then prove that the proposed algorithm can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs with homogenous stepsizes. Moreover, we demonstrate that for weighted-unbalanced graphs a Nash equilibrium may not be achieved with homogenous stepsizes unless certain conditions on the objective function hold. We show that there always exist heterogeneous stepsizes for the proposed algorithm to guarantee that a Nash equilibrium can be achieved for UJSC digraphs. Finally, in two standard weight-unbalanced cases, we verify the convergence to a Nash equilibrium by adaptively updating the stepsizes along with the arc weights in the proposed algorithm.

A Constructive Generalization of Nash Equilibrium

Huang, Xiaofei
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/01/2009 Português
Relevância na Pesquisa
48.33623%
In a society of multiple individuals, if everybody is only interested in maximizing his own payoff, will there exist any equilibrium for the society? John Nash proved more than 50 years ago that an equilibrium always exists such that nobody would benefit from unilaterally changing his strategy. Nash Equilibrium is a central concept in game theory, which offers the mathematical foundation for social science and economy. However, the original definition is declarative without including a solution to find them. It has been found later that it is computationally difficult to find a Nash equilibrium. Furthermore, a Nash equilibrium may be unstable, sensitive to the smallest variation of payoff functions. Making the situation worse, a society with selfish individuals can have an enormous number of equilibria, making it extremely hard to find out the global optimal one. This paper offers a constructive generalization of Nash equilibrium to cover the case when the selfishness of individuals are reduced to lower levels in a controllable way. It shows that the society has one and only one equilibrium when the selfishness is reduced to a certain level. When every individual follows the iterative, soft-decision optimization process presented in this paper...

Inapproximability of Nash Equilibrium

Rubinstein, Aviad
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.319814%
We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative $\epsilon$-Nash equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen, Deng, and Teng [CDT'09], and for approximate competitive equilibrium from equal incomes with indivisible goods.; Comment: Fourth revision includes a new corollary for $\epsilon$-relative Nash equilibrium in two-player games, as well as new figures. Second revision includes new corollaries for Bayesian Nash equilibrium in two-player incomplete information games and for market equilibrium in a non-monotone market. arXiv admin note: text overlap with arXiv:1405.0524

Teaching Nash Equilibrium and Dominance: A Classroom Experiment on the Beauty Contest

Alba Fernández, Virtudes; Brañas-Garza, Pablo; Jiménez Jiménez, Francisca; Rodero, Javier
Fonte: Conselho Superior de Investigações Científicas Publicador: Conselho Superior de Investigações Científicas
Tipo: Documento de trabajo
Português
Relevância na Pesquisa
67.86576%
The aim of this investigation is to show how the use of classroom experiments may be a good pedagogical tool to teach the Nash equilibrium (NE) concept. For our purposes, the basic game is a repeated version of the Beauty Contest Game (BCG), a simple guessing game in which repetition lets students react to other players’ choices and converge iteratively to the equilibrium solution. We perform this experiment with undergraduate students with no previous training in game theory. After four rounds, we observe a clear decreasing tendency in the average submitted number in all groups. Thus, our findings prove that by playing a repeated BCG, students quickly learn how to reach the NE solution.; The authors gratefully acknowledge the financial support provided by the University of Jaén R+D program (# 20210/148).

An undominated Nash equilibrium for voting by committees with exit

Massó, Jordi; Neme, Alejandro; Berga, Dolors; Bergantiños Cid, Gustavo
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: info:eu-repo/semantics/article; info:eu-repo/semantics/submittedVersion Formato: application/pdf
Publicado em //2007 Português
Relevância na Pesquisa
67.77989%
We consider the problem of a society whose members choose, with a voting by committees, a subset of new members from a given set of candidates. After knowing the elected candidates, former members may decide either stay or exit the society. We analyze the voting behavior of members who take into account the effect of their votes not only on the elected candidates, but also on the final composition of the society. For additive and monotonic preferences with dichotomous bads we construct a strategy profile that is an undominated pure strategy Nash equilibrium of the induced voting game.

A Note on the Existence of Nash Equilibrium in Games with Discontinuous Payoffs

Gatti, J. Rupert J.
Fonte: Universidade de Cambridge Publicador: Universidade de Cambridge
Formato: 221336 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
67.86576%
This paper generalises the approach taken by Dasgupta & Maskin (1986) and Simon (1989) and provides necessary and sufficient conditions for the existence of pure and mixed strategy Nash equilibrium in games with continuous strategy spaces and discontinuous payoff functions. The conditions can be applied widely, and examples for existence of pure strategy and monotonic equilibria in First-Price auctions are provided. The conditions are also appropriate for ensuring that computer generated equilibrium solutions can be extended to continuous strategy spaces.

Finding Pure Nash Equilibrium for the Resource-Constrained Project Scheduling Problem

De Ita Luna,Guillermo; Zacarias-Flores,Fernando; Altamirano-Robles,L. Carlos
Fonte: Centro de Investigación en computación, IPN Publicador: Centro de Investigación en computación, IPN
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/03/2015 Português
Relevância na Pesquisa
68.138584%
The paper focuses on solving the Resource-Constrained Project Scheduling (RCPS) problem with a method based on intelligent agents. Parallelism for performing the tasks is allowed. Common and limited resources are available to all agents. The agents are non-cooperative and compete with each other for the use of common resources, thereby forming instances of RCPS problem. We analyze the global joint interaction of scheduling via a congestion network and seek to arrive at stable assignments of scheduling. For this class of network, stable assignments of scheduling correspond to a pure Nash equilibrium, and we show that in this case there is a guarantee of obtaining a pure Nash equilibrium in polynomial time complexity. The pure Nash equilibrium point for this congestion network will be a local optimum in the neighborhood structure of the projects, where no project can improve its completion time without negatively affecting the completion time of the total system. In our case, each state of the neighborhood represents an instance of the RCPS problem, and for solving such problem, we apply a novel greedy heuristic. It has a polynomial time complexity and works similar to the well-knowing heuristic NEH.