The complexity of two-person zero-sum games in extensive form
| ISSN: |
0899-8256
|
|---|---|
| Source: |
Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
|
| Topics: |
Mathematics
Economics
|
| Type of Medium: |
Electronic Resource
|
| URL: |
| _version_ | 1798292092128067586 |
|---|---|
| autor | Koller, D. Megiddo, N. |
| autorsonst | Koller, D. Megiddo, N. |
| book_url | http://dx.doi.org/10.1016/0899-8256(92)90035-Q |
| datenlieferant | nat_lic_papers |
| fussnote | This paper investigates the complexity of finding max-min strategies for finite two-person zero-sum games in the extensive form. The problem of determining whether a player with imperfect recall can guarantee himself a certain payoff is shown to be NP-hard. When both players have imperfect recall, this problem is even harder. Moreover, the max-min behavior strategy of such a player may use irrational numbers. Thus, for games with imperfect recall, computing the max-min strategy or the value of the game is a hard problem. For a game with perfect recall, we present an algorithm for computing a max-min behavior strategy, which runs in time polynomial in the size of the game tree. Journal of Economic Literature Classification Number: 026. |
| hauptsatz | hsatz_simple |
| identnr | NLZ184744555 |
| issn | 0899-8256 |
| journal_name | Games and Economic Behavior |
| materialart | 1 |
| package_name | Elsevier |
| publikationsort | Amsterdam |
| publisher | Elsevier |
| reference | 4 (1992), S. 528-552 |
| search_space | articles |
| shingle_author_1 | Koller, D. Megiddo, N. |
| shingle_author_2 | Koller, D. Megiddo, N. |
| shingle_author_3 | Koller, D. Megiddo, N. |
| shingle_author_4 | Koller, D. Megiddo, N. |
| shingle_catch_all_1 | Koller, D. Megiddo, N. The complexity of two-person zero-sum games in extensive form 0899-8256 08998256 Elsevier |
| shingle_catch_all_2 | Koller, D. Megiddo, N. The complexity of two-person zero-sum games in extensive form 0899-8256 08998256 Elsevier |
| shingle_catch_all_3 | Koller, D. Megiddo, N. The complexity of two-person zero-sum games in extensive form 0899-8256 08998256 Elsevier |
| shingle_catch_all_4 | Koller, D. Megiddo, N. The complexity of two-person zero-sum games in extensive form 0899-8256 08998256 Elsevier |
| shingle_title_1 | The complexity of two-person zero-sum games in extensive form |
| shingle_title_2 | The complexity of two-person zero-sum games in extensive form |
| shingle_title_3 | The complexity of two-person zero-sum games in extensive form |
| shingle_title_4 | The complexity of two-person zero-sum games in extensive form |
| sigel_instance_filter | dkfz geomar wilbert ipn albert fhp |
| source_archive | Elsevier Journal Backfiles on ScienceDirect 1907 - 2002 |
| timestamp | 2024-05-06T08:43:01.113Z |
| titel | The complexity of two-person zero-sum games in extensive form |
| titel_suche | The complexity of two-person zero-sum games in extensive form This paper investigates the complexity of finding max-min strategies for finite two-person zero-sum games in the extensive form. The problem of determining whether a player with imperfect recall can guarantee himself a certain payoff is shown to be NP-hard. When both players have imperfect recall, this problem is even harder. Moreover, the max-min behavior strategy of such a player may use irrational numbers. Thus, for games with imperfect recall, computing the max-min strategy or the value of the game is a hard problem. For a game with perfect recall, we present an algorithm for computing a max-min behavior strategy, which runs in time polynomial in the size of the game tree. Journal of Economic Literature Classification Number: 026. |
| topic | SA-SP Q |
| uid | nat_lic_papers_NLZ184744555 |