Potential game (original) (raw)
En théorie des jeux, un jeu de potentiel est un jeu où il existe une fonction globale décrivant les conséquences d'un changement de stratégie pour chaque joueur. Cette fonction est appelée fonction de potentiel. Ces jeux ont des propriétés intéressantes du point de vue des équilibre de Nash, et ont des applications, par exemple dans les (en) en théorie algorithmique des jeux, qui peuvent représenter le trafic routier.
| Property | Value |
|---|---|
| dbo:abstract | Ein Ordnungspotenzial oder eine Ordnungspotenzialfunktion ist in der Spieltheorie eine spezielle Funktion auf der Menge der eines Spiels. Durch diese Funktion werden die Strategiekombination nach ihrer Auszahlung an die Spieler angeordnet. Eine Strategiekombination besitzt dabei genau dann einen höheren Wert, wenn sie für jeden Spieler zu einer höheren Auszahlung führt. Indem man Ordnungspotenzialfunktion strenger an die Auszahlungsfunktionen bindet, erhält man die Spezialfälle des gewichteten Potenzials und des exakten Potenzials. Letzteres wird auch einfach nur als Potenzial oder Potenzialfunktion bezeichnet. Die meisten Spiele besitzen allerdings kein Ordnungpotenzial. Von wurden deshalb 1988 bzw. 1996 die folgenden Klassen von Spielen eingeführt: * Spiel mit Ordnungspotenzial * Spiel mit gewichtetem Potenzial * Spiel mit (exaktem) Potenzial Eine Potenzialfunktion wurde bei Spielen erstmals 1973 von eingesetzt, um zu zeigen, dass Auslastungsspiele ein Nash-Gleichgewicht in reinen Strategien besitzen. (de) In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and Lloyd Shapley. The properties of several types of potential games have since been studied. Games can be either ordinal or cardinal potential games. In cardinal games, the difference in individual payoffs for each player from individually changing one's strategy, other things equal, has to have the same value as the difference in values for the potential function. In ordinal games, only the signs of the differences have to be the same. The potential function is a useful tool to analyze equilibrium properties of games, since the incentives of all players are mapped into one function, and the set of pure Nash equilibria can be found by locating the local optima of the potential function. Convergence and finite-time convergence of an iterated game towards a Nash equilibrium can also be understood by studying the potential function. Potential games can be studied as repeated games with state so that every round played has a direct consequence on game's state in the next round. This approach has applications in distributed control such as distributed resource allocation, where players without a central correlation mechanism can cooperate to achieve a globally optimal resource distribution. (en) En théorie des jeux, un jeu de potentiel est un jeu où il existe une fonction globale décrivant les conséquences d'un changement de stratégie pour chaque joueur. Cette fonction est appelée fonction de potentiel. Ces jeux ont des propriétés intéressantes du point de vue des équilibre de Nash, et ont des applications, par exemple dans les (en) en théorie algorithmique des jeux, qui peuvent représenter le trafic routier. (fr) Un gioco a potenziale, o gioco con potenziale, è un gioco in cui l'incentivo per i giocatori per passare da una strategia ad un'altra può essere espresso con una singola , detta funzione potenziale, richiamando l'omonimo concetto fisico. Il concetto fu introdotto da e Lloyd Shapley nel 1996. Un gioco a potenziale è detto cardinale se la differenza di utilità ottenuta cambiando la strategia di un altro giocatore è uguale alla differenza di valore della funzione potenziale.Un gioco a potenziale è detto ordinale se solo il segno di tale differenza è lo stesso. La funzione potenziale si rivela uno strumento utile per analizzare gli equilibri di Nash di certi giochi, dato che gli incentivi di tutti i giocatori sono mappati in una singola funzione, e l'insieme degli equilibri di Nash si trova fra gli ottimi locali della funzione potenziale. I massimi della funzione potenziale sono equilibri di Nash, mentre l'inverso non è sempre vero. L'uso dei massimi della funzione potenziale permette di raffinare l'insieme degli equilibri di Nash. Come esempio, si consideri il seguente gioco in forma strategica: Essendo un gioco di puro coordinamento, un potenziale P è dato semplicemente dal payoff del giocatore I: P(T,L) = 1, P(T,R) = P(B,L) = P(B,R) = 0. La coppia di strategie (B,R) è un equilibrio di Nash, pur non massimizzando il potenziale P. (it) Потенциальная игра — это игра в нормальной форме, функции выигрыша в которой обладают особым свойством. При изменении игроком своих стратегий разность его выигрышей равна разности значений потенциальной функции. Это позволяет находить равновесие по Нэшу как решение некоторой оптимизационной задачи. Потенциальные игры были введены в рассмотрение Мондерером и Шепли. Потенциальная функция Рассмотрим игру лиц в нормальной форме , где — множество игроков, — множество стратегий и — функция выигрыша -го игрока, . Предположим, что существует функция , такая что для любого выполняется для произвольных и любых стратегий . Если такая функция существует, будем называть её потенциалом в игре , а саму игру — потенциальной. Равновесие в чистых стратегиях Пусть игра лиц допускает потенциал . Тогда равновесие по Нэшу в игре является равновесием по Нэшу в игре , и наоборот. Кроме того, в игре всегда существует, по крайней мере, одно равновесие в чистых стратегиях. Оптимальное решение Существование потенциала существенно облегчает нахождение равновесия по Нэшу. Выберем в качестве ситуацию в чистых стратегиях, которая доставляет максимум на множестве . Тогда в этой точке, для любого выполняется неравенство , в частности, и по каждому аргументу, то есть Отсюда вытекает, что равновесие по Нэшу в игре и, следовательно, в игре . Олигополия Курно Рассмотрим олигополию Курно, где функции выигрыша игроков имеют вид Эта игра также является потенциальной. Потенциалом является функция Глобальный максимум функции дает равновесие по Нэшу: Маршрутизация Важную роль потенциальные игры имеют в играх маршрутизации (congestion games), которые впервые были рассмотрены Розенталем. Свое название они получили из-за того, что функция выигрыша в них зависит лишь от числа игроков, выбравших одинаковые стратегии. В этих играх существует потенциал, максимум которого дает оптимальные маршруты в произвольной сети. (ru) 在賽局理論中，如果所有參與者改變策略的動機都可以使用稱為位勢函數的單一全局函數來表達，則稱該賽局為位勢賽局。這個概念起源於多夫·蒙德勒和劳埃德·沙普利1996 年的一篇論文。 此後研究了幾種類型的位勢賽局的特性。 賽局可以是序數或基數位勢賽局。在基數賽局中，在其他條件相同的情況下，每個玩家單獨改變策略的個體收益差異必須與位勢函數的值差異具有相同的值。 在序數賽局中，只要做到差異的符號相同就可以。 位勢函數是分析賽局平衡特性的有用工具，因為所有參與者的激勵被映射到一個函數中，並且可以通過定位勢函數的局部最優來找到純納許均衡的集合。 (zh) |
| dbo:wikiPageExternalLink | http://www.math.tau.ac.il/~mansour/course_games/scribe/lecture6.pdf http://www.huwdixon.org/SurfingEconomics/chapter8.pdf http://www.huwdixon.org/SurfingEconomics/index.html |
| dbo:wikiPageID | 9394324 (xsd:integer) |
| dbo:wikiPageLength | 8121 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1047364397 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nash_equilibrium dbr:Game_theory dbr:Congestion_game dbr:Battle_of_the_sexes_(game_theory) dbr:Lloyd_Shapley dbr:Payoff_matrix dbr:Stochastically_stable_equilibrium dbr:Strategy_(game_theory) dbc:Game_theory_game_classes dbr:Econophysics dbr:Externality dbr:Repeated_game |
| dbp:1d | –1 (en) |
| dbp:1u | +1 (en) |
| dbp:2l | +1 (en) |
| dbp:2r | –1 (en) |
| dbp:dl | –6 (en) –5, –4 (en) |
| dbp:dr | 2 (xsd:integer) 14 (xsd:integer) |
| dbp:name | (en) Fig. 1: Potential game example (en) Fig. 2: Battle of the sexes (en) Fig. 3: Battle of the sexes (en) |
| dbp:ul | 4 (xsd:integer) 52 (xsd:integer) |
| dbp:ur | 0 (xsd:integer) –1, –2 (en) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Math dbt:Reflist dbt:Microeconomics dbt:Payoff_matrix dbt:Game_theory dbt:Cite_Algorithmic_Game_Theory_2007 |
| dct:subject | dbc:Game_theory_game_classes |
| rdfs:comment | En théorie des jeux, un jeu de potentiel est un jeu où il existe une fonction globale décrivant les conséquences d'un changement de stratégie pour chaque joueur. Cette fonction est appelée fonction de potentiel. Ces jeux ont des propriétés intéressantes du point de vue des équilibre de Nash, et ont des applications, par exemple dans les (en) en théorie algorithmique des jeux, qui peuvent représenter le trafic routier. (fr) 在賽局理論中，如果所有參與者改變策略的動機都可以使用稱為位勢函數的單一全局函數來表達，則稱該賽局為位勢賽局。這個概念起源於多夫·蒙德勒和劳埃德·沙普利1996 年的一篇論文。 此後研究了幾種類型的位勢賽局的特性。 賽局可以是序數或基數位勢賽局。在基數賽局中，在其他條件相同的情況下，每個玩家單獨改變策略的個體收益差異必須與位勢函數的值差異具有相同的值。 在序數賽局中，只要做到差異的符號相同就可以。 位勢函數是分析賽局平衡特性的有用工具，因為所有參與者的激勵被映射到一個函數中，並且可以通過定位勢函數的局部最優來找到純納許均衡的集合。 (zh) Ein Ordnungspotenzial oder eine Ordnungspotenzialfunktion ist in der Spieltheorie eine spezielle Funktion auf der Menge der eines Spiels. Durch diese Funktion werden die Strategiekombination nach ihrer Auszahlung an die Spieler angeordnet. Eine Strategiekombination besitzt dabei genau dann einen höheren Wert, wenn sie für jeden Spieler zu einer höheren Auszahlung führt. Indem man Ordnungspotenzialfunktion strenger an die Auszahlungsfunktionen bindet, erhält man die Spezialfälle des gewichteten Potenzials und des exakten Potenzials. Letzteres wird auch einfach nur als Potenzial oder Potenzialfunktion bezeichnet. (de) In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and Lloyd Shapley. (en) Un gioco a potenziale, o gioco con potenziale, è un gioco in cui l'incentivo per i giocatori per passare da una strategia ad un'altra può essere espresso con una singola , detta funzione potenziale, richiamando l'omonimo concetto fisico. Il concetto fu introdotto da e Lloyd Shapley nel 1996. Un gioco a potenziale è detto cardinale se la differenza di utilità ottenuta cambiando la strategia di un altro giocatore è uguale alla differenza di valore della funzione potenziale.Un gioco a potenziale è detto ordinale se solo il segno di tale differenza è lo stesso. (it) Потенциальная игра — это игра в нормальной форме, функции выигрыша в которой обладают особым свойством. При изменении игроком своих стратегий разность его выигрышей равна разности значений потенциальной функции. Это позволяет находить равновесие по Нэшу как решение некоторой оптимизационной задачи. Потенциальные игры были введены в рассмотрение Мондерером и Шепли. Потенциальная функция Рассмотрим игру лиц в нормальной форме , где — множество игроков, — множество стратегий и — функция выигрыша -го игрока, . Предположим, что существует функция , такая что для любого выполняется Маршрутизация (ru) |
| rdfs:label | Potenzial (Spieltheorie) (de) Jeu de potentiel (fr) Gioco a potenziale (it) Potential game (en) Потенциальная игра (ru) 位勢賽局 (zh) |
| owl:sameAs | freebase:Potential game yago-res:Potential game wikidata:Potential game dbpedia-de:Potential game dbpedia-fa:Potential game dbpedia-fr:Potential game dbpedia-he:Potential game dbpedia-it:Potential game dbpedia-ru:Potential game dbpedia-zh:Potential game https://global.dbpedia.org/id/2fvo2 |
| prov:wasDerivedFrom | wikipedia-en:Potential_game?oldid=1047364397&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Potential_game |
| is dbo:knownFor of | dbr:Lloyd_Shapley |
| is dbo:wikiPageWikiLink of | dbr:Best_response dbr:Gibbs_measure dbr:Congestion_game dbr:Lloyd_Shapley dbr:Succinct_game dbr:Mean-field_game_theory dbr:Hedonic_game dbr:List_of_Nobel_Memorial_Prize_laureates_in_Economics dbr:Statistical_mechanics dbr:Econophysics dbr:Fictitious_play dbr:Facility_location_(competitive_game) dbr:Potential_function |
| is dbp:knownFor of | dbr:Lloyd_Shapley |
| is foaf:primaryTopic of | wikipedia-en:Potential_game |