The complexity of eliminating dominated strategies
This paper deals with the computational complexity of some yes /no problems associated with sequential elimination of strategies using three domination relations: strong domination (strict inequalities), weak domination (weak inequalities), and domination (the asymmetric part of weak domination). Classification of various problems as polynomial or NP-complete seems to suggest that strong domination is a simple notion, whereas weak domination and domination are complicated ones.
To our knowledge, this item is not available for
download. To find whether it is available, there are three
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
|Date of creation:||Aug 1993|
|Publication status:||Published in Mathematics of Operations Research, INFORMS, 1993, Vol.18, n°3, pp. 553-565. <10.1287/moor.18.3.553>|
|Note:||View the original document on HAL open archive server: https://hal-hec.archives-ouvertes.fr/hal-00481372|
|Contact details of provider:|| Web page: https://hal.archives-ouvertes.fr/|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Gilboa, Itzhak & Zemel, Eitan, 1989.
"Nash and correlated equilibria: Some complexity considerations,"
Games and Economic Behavior,
Elsevier, vol. 1(1), pages 80-93, March.
- Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Itzhak Gilboa & Eitan Zemel, 1989. "Nash and Correlated Equilibria: Some Complexity Considerations," Post-Print hal-00753241, HAL.
- Bernheim, B Douglas, 1984. "Rationalizable Strategic Behavior," Econometrica, Econometric Society, vol. 52(4), pages 1007-1028, July.
- D. B. Bernheim, 2010. "Rationalizable Strategic Behavior," Levine's Working Paper Archive 514, David K. Levine.
- D. B. Bernheim, 2010. "Rationalizable Strategic Behavior," Levine's Working Paper Archive 661465000000000381, David K. Levine.
- Pearce, David G, 1984. "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica, Econometric Society, vol. 52(4), pages 1029-1050, July.
- Ben-porath, Elchanan, 1990. "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economic Behavior, Elsevier, vol. 2(1), pages 1-12, March.
- Gilboa, Itzhak, 1988. "The complexity of computing best-response automata in repeated games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 342-352, August.
- Itzhak Gilboa, 1988. "The Complexity of Computing Best-Response Automata in Repeated Games," Post-Print hal-00756286, HAL.
- Ehud Kalai & Eitan Zemel, 1988. "On The Order of Eliminating Dominated Strategies," Discussion Papers 789, Northwestern University, Center for Mathematical Studies in Economics and Management Science. Full references (including those not matched with items on IDEAS)