Double groupoid: Difference between revisions

Revision as of 06:05, 20 January 2014

Consider a game of three players, I,II and III, facing, respectively, the strategies {T,B}, {L,R}, and {l,r}. Without further constraints, 3*2³=24 utility values would be required to describe such a game.
	L, l	L, r	R, l	R, r
T	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor
B	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor
For each strategy profile, the utility of the first player is listed first (Template:Fontcolor), and is followed by the utilities of the second player (Template:Fontcolor) and the third player (Template:Fontcolor).

In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of $n$ players, each facing $s$ strategies, requires listing $n s^{n}$ utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n^[1] (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008^[2]). 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Types of succinct games

Graphical games

Say that each player's utility depends only on his own action and the action of one other player - for instance, I depends on II, II on III and III on I. Representing such a game would require only three 2x2 utility tables, containing in all only 12 utility values.

	L	R
T	Template:Fontcolor	Template:Fontcolor
B	Template:Fontcolor	Template:Fontcolor

	l	r
L	Template:Fontcolor	Template:Fontcolor
R	Template:Fontcolor	Template:Fontcolor

	T	B
l	Template:Fontcolor	Template:Fontcolor
r	Template:Fontcolor	Template:Fontcolor

Graphical games are games in which the utilities of each player depends on the actions of very few other players. If $d$ is the greatest number of players by whose actions any single player is affected (that is, it is the indegree of the game graph), the number of utility values needed to describe the game is $n s^{d + 1}$ , which, for a small $d$ is a considerable improvement.

It has been shown that any normal form game is reducible to a graphical game with all degrees bounded by three and with two strategies for each player.^[3] Unlike normal form games, the problem of finding a pure Nash equilibrium in graphical games (if one exists) is NP-complete.^[4] The problem of finding a (possibly mixed) Nash equilibrium in a graphical game is PPAD-complete.^[5] Finding a correlated equilibrium of a graphical game can be done in polynomial time, and for a graph with a bounded treewidth, this is also true for finding an optimal correlated equilibrium.^[2] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Sparse games

When most of the utilities are 0, as below, it is easy to come up with a succinct representation.
	L, l	L, r	R, l	R, r
T	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor
B	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor

Sparse games are those where most of the utilities are zero. Graphical games may be seen as a special case of sparse games.

For a two player game, a sparse game may be defined as a game in which each row and column of the two payoff (utility) matrices has at most a constant number of non-zero entries. It has been shown that finding a Nash equilibrium in such a sparse game is PPAD-hard, and that there does not exist a fully polynomial-time approximation scheme unless PPAD is in P.^[6] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Symmetric games

Suppose all three players are identical (we'll color them all Template:Fontcolor), and face the strategy set {T,B}. Let #TP and #BP be the number of a player's peers who've chosen T and B, respectively. Describing this game requires only 6 utility values.

	#TP=2 #BP=0	#TP=1 #BP=1	#TP=0 #BP=2
T	Template:Fontcolor	Template:Fontcolor	Template:Fontcolor
B	Template:Fontcolor	Template:Fontcolor	Template:Fontcolor

In symmetric games all players are identical, so in evaluating the utility of a combination of strategies, all that matters is how many of the $n$ players play each of the $s$ strategies. Thus, describing such a game requires giving only $s (\binom{n + s - 2}{s - 1})$ utility values.

In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although a symmetric pure Nash equilibrium may not exist.^[7] The problem of finding a pure Nash equilibrium in a symmetric game (with possibly more than two players) with a constant number of actions is in AC⁰; however, when the number of actions grows with the number of players (even linearly) the problem is NP-complete.^[8] In any symmetric game there exists a symmetric equilibrium. Given a symmetric game of n players facing k strategies, a symmetric equilibrium may be found in polynomial time if k= $O (\log n / \log \log n)$ .^[9] Finding a correlated equilibrium in symmetric games may be done in polynomial time.^[2] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Anonymous games

If players were different but did not distinguish between other players we would need to list 18 utility values to represent the game - one table such as that given for "symmetric games" above for each player.

	#TP=2 #BP=0	#TP=1 #BP=1	#TP=0 #BP=2
T	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor
B	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor

In anonymous games, players have different utilities but do not distinguish between other players (for instance, having to choose between "go to cinema" and "go to bar" while caring only how crowded will each place be, not who'll they meet there). In such a game a player's utility again depends on how many of his peers choose which strategy, and his own, so $s n (\binom{n + s - 2}{s - 1})$ utility values are required.

If the number of actions grows with the number of players, finding a pure Nash equilibrium in an anonymous game is NP-hard.^[8] An optimal correlated equilibrium of an anonymous game may be found in polynomial time.^[2] When the number of strategies is 2, there is a known PTAS for finding an ε-approximate Nash equilibrium.^[10] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Polymatrix games

If the game in question was a polymatrix game, describing it would require 24 utility values. For simplicity, let us examine only the utilities of player I (we would need two more such tables for each of the other players).

	L	R
T	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor
B	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor

	l	r
T	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor
B	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor

	l	r
L	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor
R	Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor

If strategy profile (B,R,l) was chosen, player I's utility would be 9+8=17, player II's utility would be 1+2=3, and player III's utility would be 6+4=10.

In a polymatrix game (also known as a multimatrix game), there is a utility matrix for every pair of players (i,j), denoting a component of player i's utility. Player i's final utility is the sum of all such components. The number of utilities values required to represent such a game is $O (n^{2} * s^{2})$ .

Polymatrix games always have at least one mixed Nash equilibrium.^[11] The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete.^[5] Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.^[2] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Circuit games

Let us now equate the players' various strategies with the Boolean values "0" and "1", and let X stand for player I's choice, Y for player II's choice and Z for player III's choice. Let us assign each player a circuit: Player I: X ∧ (Y ∨ Z) Player II: X ⨁ Y ⨁ Z Player III: X ∨ Y These describe the utility table below.
	0, 0	0, 1	1, 0	1, 1
0	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor
1	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor	Template:Fontcolor, Template:Fontcolor, Template:Fontcolor

The most flexible of way of representing a succinct game is by representing each player by a polynomial-time bounded Turing machine, which takes as its input the actions of all players and outputs the player's utility. Such a Turing machine is equivalent to a Boolean circuit, and it is this representation, known as circuit games, that we will consider.

Computing the value of a 2-player zero-sum circuit game is an EXP-complete problem,^[12] and approximating the value of such a game up to a multiplicative factor is known to be in PSPACE.^[13] Determining whether a pure Nash equilibrium exists is a $Σ_{2}^{P}$ -complete problem (see Polynomial hierarchy).^[14] 50 year old Petroleum Engineer Kull from Dawson Creek, spends time with interests such as house brewing, property developers in singapore condo launch and camping. Discovers the beauty in planing a trip to places around the entire world, recently only coming back from .

Other representations

Many other types of succinct game exist (many having to do with allocation of resources). Examples include congestion games, network congestion games, scheduling games, local effect games, facility location games, action-graph games, hypergraphical games and more.

Summary of complexities of finding equilibria

Below is a table of some known complexity results for finding certain classes of equilibria in several game representations. "NE" stands for "Nash equilibrium", and "CE" for "correlated equilibrium". n is the number of players and s is the number of strategies each player faces (we're assuming all players face the same number of strategies). In graphical games, d is the maximum indegree of the game graph. For references, see main article text.

Representation	Size (O(...))	Pure NE	Mixed NE	CE	Optimal CE
Normal form game	$n s^{n}$	Linear	PPAD-complete	P	P
Graphical game	$n s^{d + 1}$	NP-complete	PPAD-complete	P	NP-hard
Symmetric game	$s (\binom{n + s - 1}{s - 1})$	NP-complete	PPAD-complete	P	P
Anonymous game	$s n (\binom{n + s - 1}{s - 1})$	NP-hard		P	P
Polymatrix game	$n^{2} * s^{2}$		PPAD-complete	P	NP-hard
Circuit game		$Σ_{2}^{P}$ -complete
Congestion game		PLS-complete		P	NP-hard

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

External links

Algorithmic Game Theory: The Computational Complexity of Pure Nash

Earlier than you decide whether stainless steel cookware is worth buying, lets first discuss what stainless steel cookware is. Chrome steel is manufactured from an alloy, or a mix of metals. Mostly, basic iron with chromium, nickel or another minor metals. The chromium supplies rust safety and gives your cookware durability. The nickel supplies rust safety as effectively, and adds a elegant look. Most properly made chrome steel cookware has copper or aluminum added to the bottom of the pan or pot. That is performed to increases the ability of the pot or pan to conduct heat.
The perfect stainless-steel cookware is the principle category, but nonetheless it is divided into several subcategories primarily based on the standard and the value range. It can be confusing to choose the best chrome steel cookware out of the classes that may meet your necessities. That is where we took a step ahead to explain you all the data that will be useful for you to understand how to choose one of the best stainless steel cookware. The most effective chrome steel cookware set is manufactured from cheap to expensive and high quality constructed pots and pans.
You can find magnetic chrome steel in the layer on the outside of some quality pieces of stainless steel. This is to make it suitable with induction stovetops, which involve the use of a quickly charging electromagnetic area to warmth cookware. Excessive-quality stainless-steel, like All-Clad , makes use of three layers of steel—the austenite layer of metal on the within, ferrite steel on the skin, and a layer of aluminum sandwiched between the 2 for optimum warmth conductivity (metal alone does not conduct heat evenly). Lesser-quality stainless steel is usually just one layer of austenitic chrome steel.
Aesthetically talking, stainless steel is a smart alternative should you prefer to display or hang pots or pans. The clean, crisp look of all stainless-steel kitchenware can remodel a mishmash of cookware into a classy décor assertion. Chrome steel kettles, such as the Cuisinart Tea Kettle will mix particular person kitchenware into a cohesive and nice entity. Take into account purchasing stainless-steel utensils as well. Already acquired a stunning stainless-steel cookware collection? The Cuisinart Chef’s Assortment stainless pot rack is perhaps the of completion for a kitchen, liberating up house and making those pots and pans readily accessible. Get the stainless-steel cookware of your culinary desires at Macy’s!
Arduous-anodized aluminum cookware is likely one of the hottest varieties of materials, despite the fact that many people don't quite perceive the construction. Onerous-anodized aluminum is plain aluminum that has been processed in a collection of chemical baths charged with an electric present. The result's a fabric that has the same superior heat conductivity as aluminum but is non-reactive with acidic foods, such as tomatoes, and twice as exhausting as stainless-steel. Two drawbacks to laborious-anodized cookware are that it is not dishwasher-protected and, because it is not magnetic, it is not going to work with induction vary tops.
The enamel over steel technique creates a bit that has the warmth distribution of carbon steel and a non-reactive, low-stick floor. Such pots are much lighter than most different pots of similar measurement, are cheaper to make than stainless-steel pots, and don't have the rust and reactivity problems with cast iron or carbon steel. citation wanted Enamel over metal is ideal for big stockpots and for other giant pans used largely for water-based cooking. Because of its mild weight and simple cleanup, enamel over metal is also common for cookware used while camping. For more about stainless steel cookware reviews look at our web site. Clad aluminium or copper edit
Distinctive specialty cookware pieces served a la carte to go with any cookware set are constructed of a sturdy Stainless Steel with a brushed exterior end. Designed with an impact bonded, aluminum disk encapsulated base which distributes warmth quickly and evenly to allow precise temperature control. Handles are riveted for durability and performance. The New Specialty Cookware is compatible for all range sorts including induction. Along with the multi use operate, another distinctive characteristic is bottom to prime interior volume markings in both quarts and metric measurement; and every bit comes with a tempered glass lid, oven safe to 350°F.
Whether or not you're a cooking enthusiasts, knowledgeable chef or just cooking for your family you already know the importance of having a totally stocked kitchen. Not solely do you need the appropriate substances, however you additionally need the proper tools to get the job done. In any sort of fundamental cooking training lesson, you will learn that stainless steel is your new greatest friend with regards to kitchen cookware. What you will also study is that high quality cooking tools does not often come at a discounted price. Because of this, it is very important take good care of your cookware! Listed below are some fundamentals for chrome steel care.
To fight the uneven heating downside, most stainless steel pans are laminations of aluminum or copper on the underside to spread the heat around, and stainless steel inside the pan to provide a cooking floor that is impervious to no matter you would possibly put inside. In my expertise, this stainless-steel floor continues to be too sticky to fry on, and should you ever burn it you get a everlasting bother spot. However, sometimes a stainless steel cooking floor turns out to be useful when you can't use aluminum (see under) so I maintain some around. Choose one thing with a fairly thick aluminum layer on the underside.
Effectively, until you’re a metals professional and go inspect the factory where the steel is made to see whether or not their manufacturing process creates a pure austenite with out corrosive materials fashioned, you’re not going to know for certain whether or not the craftsmanship of your stainless is of the best quality. I believe your finest guess is to easily purchase excessive-quality stainless-steel from the beginning, from a brand with a status for good quality. But, I think I have discovered one way which you could determine if the stainless cookware you have already got is doubtlessly reactive.

↑ Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2007
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2008
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Goldberg2006
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Gottlob2005
↑ ^5.0 ^5.1 Cite error: Invalid <ref> tag; no text was provided for refs named Daskalakis2006
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Chen2006
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Cheng2004
↑ ^8.0 ^8.1 Cite error: Invalid <ref> tag; no text was provided for refs named Brandt2009
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2005
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Daskalakis2007
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Howson1972
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Feigenbaum1995
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Fortnow2005
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Schoenebeck2006

[Papadimitriou2007-1] Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2007

[Papadimitriou2008-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2008

[Goldberg2006-3] Cite error: Invalid <ref> tag; no text was provided for refs named Goldberg2006

[Gottlob2005-4] Cite error: Invalid <ref> tag; no text was provided for refs named Gottlob2005

[Daskalakis2006-5] 5.0 ^5.1 Cite error: Invalid <ref> tag; no text was provided for refs named Daskalakis2006

[Chen2006-6] Cite error: Invalid <ref> tag; no text was provided for refs named Chen2006

[Cheng2004-7] Cite error: Invalid <ref> tag; no text was provided for refs named Cheng2004

[Brandt2009-8] 8.0 ^8.1 Cite error: Invalid <ref> tag; no text was provided for refs named Brandt2009

[Papadimitriou2005-9] Cite error: Invalid <ref> tag; no text was provided for refs named Papadimitriou2005

[Daskalakis2007-10] Cite error: Invalid <ref> tag; no text was provided for refs named Daskalakis2007

[Howson1972-11] Cite error: Invalid <ref> tag; no text was provided for refs named Howson1972

[Feigenbaum1995-12] Cite error: Invalid <ref> tag; no text was provided for refs named Feigenbaum1995

[Fortnow2005-13] Cite error: Invalid <ref> tag; no text was provided for refs named Fortnow2005

[Schoenebeck2006-14] Cite error: Invalid <ref> tag; no text was provided for refs named Schoenebeck2006

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Double groupoid: Difference between revisions

Revision as of 06:05, 20 January 2014

Contents

Types of succinct games

Graphical games

Sparse games

Symmetric games

Anonymous games

Polymatrix games

Circuit games

Other representations

Summary of complexities of finding equilibria

Notes

External links

Navigation menu

@@ Line 1: / Line 1: @@
-These fuzzies may be a small annoyance, but they can make your gym seem unkempt. Normal pedaling motion disengages the brake cane, allowing for normal pedaling. As a result of this various protective gear manufacturers have also ventured into production of improved design of padded shorts. Alison Addy is the author of many articles on subjects like mountain bike crashes and published at. When shopping for different bike accessories, parts, or whatever it is you are looking for, being a smart shopper is always in order. <br><br>
+{|align="right" border="1" cellpadding="3" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|colspan="5"|Consider a game of three players, I,II and III, facing, respectively, the strategies {T,B}, {L,R}, and {l,r}. Without further constraints, 3*2<sup>3</sup>=24 utility values would be required to describe such a game.
+|-
+|
+!align="center"|''L'', ''l''
+!align="center"|''L'', ''r''
+!align="center"|''R'', ''l''
+!align="center"|''R'', ''r''
+|-
+!align="center"|''T''
+|align="center"|{{fontcolor|red|4}}, {{fontcolor|green|6}}, {{fontcolor|blue|2}}
+|align="center"|{{fontcolor|red|5}}, {{fontcolor|green|5}}, {{fontcolor|blue|5}}
+|align="center"|{{fontcolor|red|8}}, {{fontcolor|green|1}}, {{fontcolor|blue|7}}
+|align="center"|{{fontcolor|red|1}}, {{fontcolor|green|4}}, {{fontcolor|blue|9}}
+|-
+!align="center"|''B''
+|align="center"|{{fontcolor|red|8}}, {{fontcolor|green|6}}, {{fontcolor|blue|6}}
+|align="center"|{{fontcolor|red|7}}, {{fontcolor|green|4}}, {{fontcolor|blue|7}}
+|align="center"|{{fontcolor|red|9}}, {{fontcolor|green|6}}, {{fontcolor|blue|5}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|3}}, {{fontcolor|blue|0}}
+|-
+|colspan="5"|''For each strategy profile, the utility of the first player is listed first ({{fontcolor|red|red}}), and is followed by the utilities of the second player ({{fontcolor|green|green}}) and the third player ({{fontcolor|blue|blue}}).''
+|}
-If you have any sort of questions relating to where and how you can make use of [http://games.k5kaa.com/profile/882817/EmPaten.html Here is your mountain bike sizing.], you can call us at the page. If you reverse breathe it means that you are trying to fill up something that is deflating. 3 width are versatile, and can be used on low mountain trails and the alpencross. From free shipping on all the bikes across the US, the Road Bike Outlet makes consumers happy anywhere within 1 to 6 days. Ten miles back to the truck is a long walk when pushing 200 pounds of meat on a bike. Titanium is very light and gives you an advantage and is usually used in racing bicycles. <br><br>Some also use the liner as a size aid, for example BMX helmets can come as one-size, with optional liner kits to change the helmets size. *	Numbness - Impingement of small nerve branches between the second and third or third and fourth toes can cause swelling that results in numbness, tingling, or burning, or sharp shooting pains into the toes. Please remember the stem lengths can impact just how reactive the bike is. Another way to classify brakes is by mounting style. These are stable forks whose weights are directly in proportion to their durability. <br><br>I would wake up at 3 o'clock in the morning to make calls to America. He just stood there looking at the view from the top-his view and perspective changed by a few seconds and a climb up a little mountain. If the metal tubing below the paint has become exposed, then touch this up with a dab of enamel paint, using a very fine brush. " I want us to be able to chase one another around the room, have pillow fights, and wrestle. Within 2 weeks of breathing exercises, the warm up period disappeared. <br><br>If you are just out there to like your journey or to get from position to put efficiently, an ebike electric mountain bike, electric mountain bike, electric bikes for sale is the great excess boost to your experience that will permit you go farther, more time and have much more electrical power above the course of your ride, letting you to appreciate the journey a little extra. It's usually best to buy from your bike store to begin with, as they can help you fit the bike and give you advice. And the cyclist may certainly sense the distinction. Many of these trails and stunts are so dangerous that signs are up because of the potential of a serious injury or even death. From there you can connect to the west switchback trail simply call "Switchbacks" or "The Old Switchbacks".
+In algorithmic [[game theory]], a '''succinct game''' or a '''succinctly representable game''' is a game which may be represented in a size much smaller than its [[Normal-form game|normal form]] representation. Without placing constraints on player utilities, describing a game of <math>n</math> players, each facing <math>s</math> [[strategy (game theory)|strategies]], requires listing <math>ns^n</math> utility values. Even trivial algorithms are capable of finding a [[Nash equilibrium]] in a time [[time complexity#Polynomial time|polynomial]] in the length of such a large input. A succinct game is of ''polynomial type'' if in a game represented by a string of length ''n'' the number of players, as well as the number of strategies of each player, is bounded by a polynomial in ''n''<ref name="Papadimitriou2007"/> (a formal definition, describing succinct games as a [[computational problem]], is given by Papadimitriou & Roughgarden 2008<ref name="Papadimitriou2008"/>).
+{{Clear}}
+==Types of succinct games==
+===Graphical games===
+{|align="right" border="1" cellpadding="3" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|Say that each player's utility depends only on his own action and the action of one other player - for instance, I depends on II, II on III and III on I. Representing such a game would require only three 2x2 utility tables, containing in all only 12 utility values.
+    <div style="text-align:center;">
+        {|border="1" cellpadding="3" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''L''
+            !align="center"|''R''
+            |-
+            !align="center"|''T''
+            |align="center"|{{fontcolor|red|9}}
+            |align="center"|{{fontcolor|red|8}}
+            |-
+            !align="center"|''B''
+            |align="center"|{{fontcolor|red|3}}
+            |align="center"|{{fontcolor|red|4}}
+        |}
+        {|border="1" cellpadding="3" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''l''
+            !align="center"|''r''
+            |-
+            !align="center"|''L''
+            |align="center"|{{fontcolor|green|6}}
+            |align="center"|{{fontcolor|green|8}}
+            |-
+            !align="center"|''R''
+            |align="center"|{{fontcolor|green|1}}
+            |align="center"|{{fontcolor|green|3}}
+        |}
+        {|border="1" cellpadding="3" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''T''
+            !align="center"|''B''
+            |-
+            !align="center"|''l''
+            |align="center"|{{fontcolor|blue|4}}
+            |align="center"|{{fontcolor|blue|4}}
+            |-
+            !align="center"|''r''
+            |align="center"|{{fontcolor|blue|5}}
+            |align="center"|{{fontcolor|blue|7}}
+        |}
+    </div>
+|}
+[[Graphical game (game theory)|Graphical game]]s are games in which the utilities of each player depends on the actions of very few other players. If <math>d</math> is the greatest number of players by whose actions any single player is affected (that is, it is the [[Indegree#Indegree and outdegree|indegree]] of the game graph), the number of utility values needed to describe the game is <math>ns^{d+1}</math>, which, for a small <math>d</math> is a considerable improvement.
+It has been shown that any normal form game is [[reduction (complexity)|reducible]] to a graphical game with all degrees bounded by three and with two strategies for each player.<ref name="Goldberg2006"/> Unlike normal form games, the problem of finding a pure Nash equilibrium in graphical games (if one exists) is [[NP-complete]].<ref name="Gottlob2005"/> The problem of finding a (possibly mixed) Nash equilibrium in a graphical game is [[PPAD (complexity)|PPAD]]-complete.<ref name="Daskalakis2006"/> Finding a [[correlated equilibrium]] of a graphical game can be done in polynomial time, and for a graph with a bounded [[treewidth]], this is also true for finding an ''optimal'' correlated equilibrium.<ref name="Papadimitriou2008"/>
+{{Clear}}
+===Sparse games===
+{|align="right" border="1" cellpadding="4" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|colspan="5"|When most of the utilities are 0, as below, it is easy to come up with a succinct representation.
+|-
+|
+!align="center"|''L'', ''l''
+!align="center"|''L'', ''r''
+!align="center"|''R'', ''l''
+!align="center"|''R'', ''r''
+|-
+!align="center"|''T''
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|2}}, {{fontcolor|green|0}}, {{fontcolor|blue|1}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|7}}, {{fontcolor|blue|0}}
+|-
+!align="center"|''B''
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|2}}, {{fontcolor|green|0}}, {{fontcolor|blue|3}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|}
+[[Sparse game]]s are those where most of the utilities are zero. Graphical games may be seen as a special case of sparse games.
+For a two player game, a sparse game may be defined as a game in which each row and column of the two payoff (utility) matrices has at most a constant number of non-zero entries. It has been shown that finding a Nash equilibrium in such a sparse game is PPAD-hard, and that there does not exist a fully [[polynomial-time approximation scheme]] unless PPAD is in [[P (complexity)|P]].<ref name="Chen2006"/>
+{{Clear}}
+===Symmetric games===
+{|align="right" border="1" cellpadding="3" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|Suppose all three players are identical (we'll color them all {{fontcolor|purple|purple}}), and face the strategy set {T,B}. Let #TP and #BP be the number of a player's peers who've chosen T and B, respectively. Describing this game requires only 6 utility values.
+    <div style="text-align:center;">
+        {|border="1" cellpadding="3" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|#TP=2<br/>#BP=0
+            !align="center"|#TP=1<br/>#BP=1
+            !align="center"|#TP=0<br/>#BP=2
+            |-
+            !align="center"|''T''
+            |align="center"|{{fontcolor|purple|5}}
+            |align="center"|{{fontcolor|purple|2}}
+            |align="center"|{{fontcolor|purple|2}}
+            |-
+            !align="center"|''B''
+            |align="center"|{{fontcolor|purple|1}}
+            |align="center"|{{fontcolor|purple|7}}
+            |align="center"|{{fontcolor|purple|2}}
+        |}
+    </div>
+|}
+In [[symmetric game]]s all players are identical, so in evaluating the utility of a combination of strategies, all that matters is how many of the <math>n</math> players play each of the <math>s</math> strategies. Thus, describing such a game requires giving only <math>s\tbinom{n+s-2}{s-1}</math> utility values.
+In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although a ''symmetric'' pure Nash equilibrium may not exist.<ref name="Cheng2004"/> The problem of finding a pure Nash equilibrium in a symmetric game (with possibly more than two players) with a constant number of actions is in [[AC0|AC<sup>0</sup>]]; however, when the number of actions grows with the number of players (even linearly) the problem is NP-complete.<ref name="Brandt2009"/> In any symmetric game there exists a [[symmetric equilibrium]]. Given a symmetric game of ''n'' players facing ''k'' strategies, a symmetric equilibrium may be found in polynomial time if k=<math>O(\log n/\log \log n)</math>.<ref name="Papadimitriou2005"/> Finding a correlated equilibrium in symmetric games may be done in polynomial time.<ref name="Papadimitriou2008"/>
+{{Clear}}
+===Anonymous games===
+{|align="right" border="1" cellpadding="3" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|If players were different but did not distinguish between other players we would need to list 18 utility values to represent the game - one table such as that given for "symmetric games" above for each player.
+    <div style="text-align:center;">
+        {|border="1" cellpadding="3" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|#TP=2<br/>#BP=0
+            !align="center"|#TP=1<br/>#BP=1
+            !align="center"|#TP=0<br/>#BP=2
+            |-
+            !align="center"|''T''
+            |align="center"|{{fontcolor|red|8}}, {{fontcolor|green|8}}, {{fontcolor|blue|2}}
+            |align="center"|{{fontcolor|red|2}}, {{fontcolor|green|9}}, {{fontcolor|blue|5}}
+            |align="center"|{{fontcolor|red|4}}, {{fontcolor|green|1}}, {{fontcolor|blue|4}}
+            |-
+            !align="center"|''B''
+            |align="center"|{{fontcolor|red|6}}, {{fontcolor|green|1}}, {{fontcolor|blue|3}}
+            |align="center"|{{fontcolor|red|2}}, {{fontcolor|green|2}}, {{fontcolor|blue|1}}
+            |align="center"|{{fontcolor|red|7}}, {{fontcolor|green|0}}, {{fontcolor|blue|6}}
+        |}
+    </div>
+|}
+In [[anonymous game]]s, players have different utilities but do not distinguish between other players (for instance, having to choose between "go to cinema" and "go to bar" while caring only how crowded will each place be, not who'll they meet there). In such a game a player's utility again depends on how many of his peers choose which strategy, and his own, so <math>sn\tbinom{n+s-2}{s-1}</math> utility values are required.
+If the number of actions grows with the number of players, finding a pure Nash equilibrium in an anonymous game is [[NP-hard]].<ref name="Brandt2009"/> An optimal correlated equilibrium of an anonymous game may be found in polynomial time.<ref name="Papadimitriou2008"/> When the number of strategies is 2, there is a known [[polynomial-time approximation scheme|PTAS]] for finding an [[epsilon-equilibrium|ε-approximate Nash equilibrium]].<ref name="Daskalakis2007"/>
+{{Clear}}
+===Polymatrix games===
+{|align="right" border="1" cellpadding="3" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|If the game in question was a polymatrix game, describing it would require 24 utility values. For simplicity, let us examine only the utilities of player I (we would need two more such tables for each of the other players).
+    <div style="text-align:center;">
+        {|border="1" cellpadding="2" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''L''
+            !align="center"|''R''
+            |-
+            !align="center"|''T''
+            |align="center"|{{fontcolor|red|4}}, {{fontcolor|green|6}}
+            |align="center"|{{fontcolor|red|8}}, {{fontcolor|green|7}}
+            |-
+            !align="center"|''B''
+            |align="center"|{{fontcolor|red|3}}, {{fontcolor|green|7}}
+            |align="center"|{{fontcolor|red|9}}, {{fontcolor|green|1}}
+        |}
+        {|border="1" cellpadding="2" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''l''
+            !align="center"|''r''
+            |-
+            !align="center"|''T''
+            |align="center"|{{fontcolor|red|7}}, {{fontcolor|blue|7}}
+            |align="center"|{{fontcolor|red|1}}, {{fontcolor|blue|6}}
+            |-
+            !align="center"|''B''
+            |align="center"|{{fontcolor|red|8}}, {{fontcolor|blue|6}}
+            |align="center"|{{fontcolor|red|6}}, {{fontcolor|blue|4}}
+        |}
+        {|border="1" cellpadding="2" cellspacing="0" style="margin:0.5em; border:1px #aaa solid; border-collapse:collapse; display:inline-table;"
+            |
+            !align="center"|''l''
+            !align="center"|''r''
+            |-
+            !align="center"|''L''
+            |align="center"|{{fontcolor|green|2}}, {{fontcolor|blue|9}}
+            |align="center"|{{fontcolor|green|3}}, {{fontcolor|blue|3}}
+            |-
+            !align="center"|''R''
+            |align="center"|{{fontcolor|green|2}}, {{fontcolor|blue|4}}
+            |align="center"|{{fontcolor|green|1}}, {{fontcolor|blue|5}}
+        |}
+    </div>
+If strategy profile (B,R,l) was chosen, player I's utility would be 9+8=17, player II's utility would be 1+2=3, and player III's utility would be 6+4=10.
+|}
+In a [[polymatrix game]] (also known as a ''multimatrix game''), there is a utility matrix for every pair of players ''(i,j)'', denoting a component of player i's utility. Player i's final utility is the sum of all such components. The number of utilities values required to represent such a game is <math>O(n^2*s^2)</math>.
+Polymatrix games always have at least one mixed Nash equilibrium.<ref name="Howson1972"/> The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete.<ref name="Daskalakis2006"/> Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.<ref name="Papadimitriou2008"/>
+{{Clear}}
+===Circuit games===
+{|align="right" border="1" cellpadding="4" cellspacing="0" width="230px" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%;"
+|colspan="5"|Let us now equate the players' various strategies with the Boolean values "0" and "1", and let X stand for player I's choice, Y for player II's choice and Z for player III's choice. Let us assign each player a circuit:
+<div style="margin-left:10px;">
+Player I: X ∧ (Y ∨ Z)<br/>
+Player II: X ⨁ Y ⨁ Z''<br/> <!--xor'd-->
+Player III: X ∨ Y
+</div>
+These describe the utility table below.
+|-
+|
+!align="center"|''0'', ''0''
+!align="center"|''0'', ''1''
+!align="center"|''1'', ''0''
+!align="center"|''1'', ''1''
+|-
+!align="center"|''0''
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|1}}, {{fontcolor|blue|0}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|1}}, {{fontcolor|blue|1}}
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|0}}, {{fontcolor|blue|1}}
+|-
+!align="center"|''1''
+|align="center"|{{fontcolor|red|0}}, {{fontcolor|green|1}}, {{fontcolor|blue|1}}
+|align="center"|{{fontcolor|red|1}}, {{fontcolor|green|0}}, {{fontcolor|blue|1}}
+|align="center"|{{fontcolor|red|1}}, {{fontcolor|green|0}}, {{fontcolor|blue|1}}
+|align="center"|{{fontcolor|red|1}}, {{fontcolor|green|1}}, {{fontcolor|blue|1}}
+|}
+The most flexible of way of representing a succinct game is by representing each player by a polynomial-time bounded [[Turing machine]], which takes as its input the actions of all players and outputs the player's utility. Such a Turing machine is equivalent to a [[Boolean circuit]]<!--https://www.cs.princeton.edu/~chazelle/pubs/UnboundedHardwEquivDetTuring.pdf ?-->, and it is this representation, known as [[circuit game]]s, that we will consider.
+Computing the value of a 2-player [[zero-sum]] circuit game is an [[EXPTIME|EXP]]-complete problem,<ref name="Feigenbaum1995"/> and approximating the value of such a game up to a multiplicative factor is known to be in [[PSPACE]].<ref name="Fortnow2005"/> Determining whether a pure Nash equilibrium exists is a <math>\Sigma_2^{\rm P}</math>-complete problem (see [[Polynomial hierarchy]]).<ref name="Schoenebeck2006"/>
+{{Clear}}
+===Other representations===
+Many other types of succinct game exist (many having to do with allocation of resources). Examples include [[congestion game]]s, [[network congestion game]]s, [[scheduling game]]s, [[local effect game]]s, [[facility location game]]s, [[action-graph game]]s, [[hypergraphical game]]s and more.
+==Summary of complexities of finding equilibria==
+Below is a table of some known complexity results for finding certain classes of equilibria in several game representations. "NE" stands for "Nash equilibrium", and "CE" for "correlated equilibrium". ''n'' is the number of players and ''s'' is the number of strategies each player faces (we're assuming all players face the same number of strategies). In graphical games, ''d'' is the maximum indegree of the game graph. For references, see main article text.
+{|class="wikitable" style="width:100%;"
+!Representation         !! Size (''O(...)'')                    !! Pure NE                              !! Mixed NE         !! CE               !! Optimal CE
+|-
+|Normal form game       || <math>ns^n</math>                    || Linear                               || PPAD-complete    || P                || P
+|-
+|Graphical game         || <math>ns^{d+1}</math>                || NP-complete                          || PPAD-complete    || P                || NP-hard
+|-
+|Symmetric game         || <math>s\tbinom{n+s-1}{s-1}</math>    || NP-complete                          || PPAD-complete    || P                || P
+|-
+|Anonymous game         || <math>sn\tbinom{n+s-1}{s-1}</math>   || NP-hard                              ||                  || P                || P
+|-
+|Polymatrix game        || <math>n^2*s^2</math>                 ||                                      || PPAD-complete    || P                || NP-hard
+|-
+|Circuit game           ||                                      || <math>\Sigma_2^{\rm P}</math>-complete                          ||                  ||                  ||
+|-
+|Congestion game        ||                                      || [[PLS (complexity)|PLS-complete]]    ||                  || P                || NP-hard
+|}
+<!--I strongly suggest editing this table in an external editor with line wrapping disabled.-->
+==Notes==
+{{Reflist|30em|refs=
+    <ref name="Papadimitriou2007">
+        {{Cite book
+        | last = Papadimitriou
+        | first = Christos H.
+        | editor1-first = Noam
+        | editor1-last  = Nisan
+        | editor2-first = Tim
+        | editor2-last  = Roughgarden
+        | editor3-first = Éva
+        | editor3-last  = Tardos
+        | editor4-first = Vijay V.
+        | editor4-last  = Vazirani
+        | title         = Algorithmic Game Theory
+        | publisher     = Cambridge University Press
+        | year          = 2007
+        | pages         = 29–52
+        | chapter       = The Complexity of Finding Nash Equilibria
+        | isbn          = 978-0-521-87282-9
+        }}
+</ref>
+    <ref name="Chen2006">
+        {{Cite book
+        | pages         = 262–273
+        | last1         = Chen
+        | first1        = Xi
+        | last2         = Deng
+        | first2        = Xiaotie
+        | last3         = Teng
+        | first3        = Shang-Hua
+        | title         = Internet and Network Economics
+        | chapter       = Sparse Games Are Hard
+        | accessdate    = 2010-01-24
+        | year          = 2006
+        | doi           = 10.1007/11944874_24
+        | isbn          = 978-3-540-68138-0
+        | chapterurl    = http://www.springerlink.com/content/v2603131200h23hq/
+        }}
+</ref>
+    <ref name="Gottlob2005">
+        {{Cite journal
+        | volume = 24
+        | issue = 195-220
+        | pages = 26–37
+        | last1 = Gottlob
+        | first1 = G.
+        | last2 = Greco
+        | first2 = G.
+        | last3 = Scarcello
+        | first3 = F.
+        | title = Pure Nash Equilibria: Hard and Easy Games
+        | journal = Journal of Artificial Intelligence Research
+        | year = 2005
+        }}
+</ref>
+    <ref name="Goldberg2006">
+        {{Cite conference
+        | publisher = ACM
+        | doi = 10.1145/1132516.1132526
+        | isbn = 1-59593-134-1
+        | pages = 61–70
+        | last1 = Goldberg
+        | first1 = Paul W.
+        | last2 = Papadimitriou
+        | first2 = Christos H.
+        | title = Reducibility Among Equilibrium Problems
+        | booktitle = Proceedings of the thirty-eighth annual ACM symposium on Theory of computing
+        | location = Seattle, WA, USA
+        | accessdate = 2010-01-25
+        | year = 2006
+        | url = http://portal.acm.org/citation.cfm?id=1132516.1132526
+        }}
+</ref>
+    <ref name="Howson1972">
+        {{Cite journal
+        | issn = 0025-1909
+        | volume = 18
+        | issue = 5
+        | pages = 312–318
+        | last = Howson
+        | first = Joseph T.
+        | title = Equilibria of Polymatrix Games
+        | journal = Management Science|date=January 1972
+        | jstor = 2634798
+        }}
+</ref>
+    <ref name="Papadimitriou2008">
+        {{Cite journal
+        | doi = 10.1145/1379759.1379762
+        | volume = 55
+        | issue = 3
+        | pages = 1–29
+        | last1 = Papadimitriou
+        | first1 = Christos H.
+        | last2 = Roughgarden
+        | first2 = Tim
+        | title = Computing Correlated Equilibria in Multi-Player Games
+        | journal = J. ACM
+        | accessdate = 2010-01-23
+        | year = 2008
+        | url = http://portal.acm.org/citation.cfm?id=1379759.1379762
+        }}
+</ref>
+    <ref name="Cheng2004">
+        {{Cite conference
+        | conference = AAMAS-04 Workshop on Game Theory and Decision Theory
+        | last1 = Cheng
+        | first1 = Shih-Fen
+        | last2 = Reeves
+        | first2 = Daniel M.
+        | last3 = Vorobeychik
+        | first3 = Yevgeniy
+        | last4 = Wellman
+        | first4 = Michael P.
+        | title = Notes on Equilibria in Symmetric Games
+        | year = 2004
+        }}
+</ref>
+    <ref name="Papadimitriou2005">
+        {{Cite conference
+        | publisher = Society for Industrial and Applied Mathematics
+        | isbn = 0-89871-585-7
+        | pages = 82–91
+        | last1 = Papadimitriou
+        | first1 = Christos H.
+        | last2 = Roughgarden
+        | first2 = Tim
+        | title = Computing equilibria in multi-player games
+        | booktitle = Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms
+        | location = Vancouver, British Columbia
+        | accessdate = 2010-01-25
+        | year = 2005
+        | url = http://portal.acm.org/citation.cfm?id=1070432.1070444
+        }}
+</ref>
+    <ref name="Daskalakis2007">
+        {{Cite arxiv
+        | last1 = Daskalakis
+        | first1 = Constantinos
+        | last2 = Papadimitriou
+        | first2 = Christos H.
+        | eprint = 0710.5582
+        | class = cs
+        | title = Computing Equilibria in Anonymous Games
+        | year = 2007
+        | version = v1
+        | accessdate = 2010-01-25
+        }}
+</ref>
+    <ref name="Daskalakis2006">
+        {{Cite book
+        | pages = 513–524
+        | last1 = Daskalakis
+        | first1 = Constantinos
+        | last2 = Fabrikant
+        | first2 = Alex
+        | last3 = Papadimitriou
+        | first3 = Christos H.
+        | title = Automata, Languages and Programming
+        | chapter = The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games| year = 2006
+        | doi = 10.1007/11786986_45
+        }}
+</ref>
+    <ref name="Feigenbaum1995">
+        {{Cite conference
+        | publisher = Certer for Discrete Mathematics \&amp; Theoretical Computer Science
+        | last1 = Feigenbaum
+        | first1 = Joan
+        | last2 = Koller
+        | first2 = Daphne
+        | last3 = Shor
+        | first3 = Peter
+        | title = A Game-Theoretic Classification of Interactive Complexity Classes
+        | accessdate = 2010-01-25
+        | year = 1995
+        | url = http://portal.acm.org/citation.cfm?id=868345
+        }}
+</ref>
+    <ref name="Schoenebeck2006">
+        {{Cite conference
+        | publisher = ACM
+        | doi = 10.1145/1134707.1134737
+        | isbn = 1-59593-236-4
+        | pages = 270–279
+        | last1 = Schoenebeck
+        | first1 = Grant
+        | last2 = Vadhan
+        | first2 = Salil
+        | title = The computational complexity of nash equilibria in concisely represented games
+        | booktitle = Proceedings of the 7th ACM conference on Electronic commerce
+        | location = Ann Arbor, Michigan, USA
+        | accessdate = 2010-01-25
+        | year = 2006
+        | url = http://portal.acm.org/citation.cfm?id=1134707.1134737
+        }}
+</ref>
+    <ref name="Fortnow2005">
+        {{Cite conference
+        | publisher = IEEE Computer Society
+        | isbn = 0-7695-2364-1
+        | pages = 323–332
+        | last1 = Fortnow
+        | first1 = Lance
+        | last2 = Impagliazzo
+        | first2 = Russell
+        | last3 = Kabanets
+        | first3 = Valentine
+        | last4 = Umans
+        | first4 = Christopher
+        | title = On the Complexity of Succinct Zero-Sum Games
+        | booktitle = Proceedings of the 20th Annual IEEE Conference on Computational Complexity
+        | accessdate = 2010-01-23
+        | year = 2005
+        | url = http://portal.acm.org/citation.cfm?id=1068661
+        }}
+</ref>
+    <ref name="Brandt2009">
+        {{Cite journal
+        | volume = 75
+        | issue = 3
+        | pages = 163–177
+        | last1 = Brandt
+        | first1 = Felix
+        | last2 = Fischer
+        | first2 = Felix
+        | last3 = Holzer
+        | first3 = Markus
+        | title = Symmetries and the Complexity of Pure Nash Equilibrium
+        | journal = J. Comput. Syst. Sci.
+        | accessdate = 2010-01-31
+        | year = 2009
+        | url = http://portal.acm.org/citation.cfm?id=1501295
+        }}
+</ref>
+}}
+==External links==
+* [http://agtb.wordpress.com/2009/11/19/the-computational-complexity-of-pure-nash/ Algorithmic Game Theory: The Computational Complexity of Pure Nash]
+{{Game theory}}
+[[Category:Game theory]]

Double groupoid: Difference between revisions

Revision as of 06:05, 20 January 2014

Types of succinct games

Graphical games

Sparse games

Symmetric games

Anonymous games

Polymatrix games

Circuit games

Other representations

Summary of complexities of finding equilibria

Notes

External links

Navigation menu

Search