When Can Limited Randomness Be Used in Repeated Games? View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-06-09

AUTHORS

Pavel Hubáček, Moni Naor, Jonathan Ullman

ABSTRACT

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist. More... »

PAGES

722-746

References to SciGraph publications

  • 2007-01-01. Algorithms for Playing Games with Limited Randomness in ALGORITHMS – ESA 2007
  • 1987-09. Nash equilibria of finitely repeated games in INTERNATIONAL JOURNAL OF GAME THEORY
  • 2000-08-11. A Cryptographic Solution to a Game Theoretic Problem in ADVANCES IN CRYPTOLOGY — CRYPTO 2000
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-016-9690-4

    DOI

    http://dx.doi.org/10.1007/s00224-016-9690-4

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1040671468


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0805", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Distributed Computing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel", 
              "id": "http://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hub\u00e1\u010dek", 
            "givenName": "Pavel", 
            "id": "sg:person.016153011375.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016153011375.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel", 
              "id": "http://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Naor", 
            "givenName": "Moni", 
            "id": "sg:person.07776170271.83", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Northeastern University College of Computer and Information Science, 02115, Boston, MA, USA", 
              "id": "http://www.grid.ac/institutes/grid.261112.7", 
              "name": [
                "Northeastern University College of Computer and Information Science, 02115, Boston, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ullman", 
            "givenName": "Jonathan", 
            "id": "sg:person.015402574613.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402574613.10"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01756291", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004391712", 
              "https://doi.org/10.1007/bf01756291"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44598-6_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002949083", 
              "https://doi.org/10.1007/3-540-44598-6_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75520-3_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017105472", 
              "https://doi.org/10.1007/978-3-540-75520-3_30"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-06-09", 
        "datePublishedReg": "2016-06-09", 
        "description": "The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have \u03a9(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on \u201crandom-like\u201d sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then \u03a9(n) random bits remain necessary for equilibria to exist.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-016-9690-4", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "59"
          }
        ], 
        "keywords": [
          "two-player", 
          "zero-sum game", 
          "random bits", 
          "Nash equilibrium", 
          "pseudorandom generators", 
          "exact Nash equilibrium", 
          "true random bits", 
          "cryptographic pseudorandom generators", 
          "limited randomness", 
          "approximate Nash equilibria", 
          "random-like sequence", 
          "classical game theory", 
          "single instance", 
          "game theory", 
          "bits", 
          "class of games", 
          "constant number", 
          "game", 
          "normal form games", 
          "form games", 
          "Repeated Games", 
          "large class", 
          "randomness", 
          "version", 
          "pure strategies", 
          "players", 
          "small number", 
          "finite normal form games", 
          "access", 
          "generator", 
          "instances", 
          "class", 
          "strategies", 
          "number", 
          "work", 
          "sequence", 
          "time", 
          "results", 
          "stage", 
          "central result", 
          "practice", 
          "humans", 
          "theory", 
          "contrast", 
          "equilibrium", 
          "enough random bits"
        ], 
        "name": "When Can Limited Randomness Be Used in Repeated Games?", 
        "pagination": "722-746", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040671468"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-016-9690-4"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-016-9690-4", 
          "https://app.dimensions.ai/details/publication/pub.1040671468"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:40", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_697.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-016-9690-4"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9690-4'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9690-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9690-4'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9690-4'


     

    This table displays all metadata directly associated to this object as RDF triples.

    145 TRIPLES      22 PREDICATES      77 URIs      63 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-016-9690-4 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author Na0d08cdf8a3947d897dbb342241f6976
    7 schema:citation sg:pub.10.1007/3-540-44598-6_7
    8 sg:pub.10.1007/978-3-540-75520-3_30
    9 sg:pub.10.1007/bf01756291
    10 schema:datePublished 2016-06-09
    11 schema:datePublishedReg 2016-06-09
    12 schema:description The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.
    13 schema:genre article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree true
    16 schema:isPartOf N1585f1b056334270b36888788af0a795
    17 N1be83f32f8254122b347d21cbcbf4cc0
    18 sg:journal.1052098
    19 schema:keywords Nash equilibrium
    20 Repeated Games
    21 access
    22 approximate Nash equilibria
    23 bits
    24 central result
    25 class
    26 class of games
    27 classical game theory
    28 constant number
    29 contrast
    30 cryptographic pseudorandom generators
    31 enough random bits
    32 equilibrium
    33 exact Nash equilibrium
    34 finite normal form games
    35 form games
    36 game
    37 game theory
    38 generator
    39 humans
    40 instances
    41 large class
    42 limited randomness
    43 normal form games
    44 number
    45 players
    46 practice
    47 pseudorandom generators
    48 pure strategies
    49 random bits
    50 random-like sequence
    51 randomness
    52 results
    53 sequence
    54 single instance
    55 small number
    56 stage
    57 strategies
    58 theory
    59 time
    60 true random bits
    61 two-player
    62 version
    63 work
    64 zero-sum game
    65 schema:name When Can Limited Randomness Be Used in Repeated Games?
    66 schema:pagination 722-746
    67 schema:productId N274e990547fd4fa5a22cfae069ed6844
    68 N8194409753394d849310673ce8dfc69c
    69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040671468
    70 https://doi.org/10.1007/s00224-016-9690-4
    71 schema:sdDatePublished 2022-01-01T18:40
    72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    73 schema:sdPublisher Nf3e59f307ed94445b4adbe8e7a28fca9
    74 schema:url https://doi.org/10.1007/s00224-016-9690-4
    75 sgo:license sg:explorer/license/
    76 sgo:sdDataset articles
    77 rdf:type schema:ScholarlyArticle
    78 N1585f1b056334270b36888788af0a795 schema:issueNumber 4
    79 rdf:type schema:PublicationIssue
    80 N1be83f32f8254122b347d21cbcbf4cc0 schema:volumeNumber 59
    81 rdf:type schema:PublicationVolume
    82 N274e990547fd4fa5a22cfae069ed6844 schema:name doi
    83 schema:value 10.1007/s00224-016-9690-4
    84 rdf:type schema:PropertyValue
    85 N302f8161b68e4b969672648d2ef707dc rdf:first sg:person.07776170271.83
    86 rdf:rest N5c6b979763c04f758760e9d442109a50
    87 N5c6b979763c04f758760e9d442109a50 rdf:first sg:person.015402574613.10
    88 rdf:rest rdf:nil
    89 N8194409753394d849310673ce8dfc69c schema:name dimensions_id
    90 schema:value pub.1040671468
    91 rdf:type schema:PropertyValue
    92 Na0d08cdf8a3947d897dbb342241f6976 rdf:first sg:person.016153011375.19
    93 rdf:rest N302f8161b68e4b969672648d2ef707dc
    94 Nf3e59f307ed94445b4adbe8e7a28fca9 schema:name Springer Nature - SN SciGraph project
    95 rdf:type schema:Organization
    96 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Mathematical Sciences
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Applied Mathematics
    101 rdf:type schema:DefinedTerm
    102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Information and Computing Sciences
    104 rdf:type schema:DefinedTerm
    105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Computation Theory and Mathematics
    107 rdf:type schema:DefinedTerm
    108 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Distributed Computing
    110 rdf:type schema:DefinedTerm
    111 sg:journal.1052098 schema:issn 1432-4350
    112 1433-0490
    113 schema:name Theory of Computing Systems
    114 schema:publisher Springer Nature
    115 rdf:type schema:Periodical
    116 sg:person.015402574613.10 schema:affiliation grid-institutes:grid.261112.7
    117 schema:familyName Ullman
    118 schema:givenName Jonathan
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402574613.10
    120 rdf:type schema:Person
    121 sg:person.016153011375.19 schema:affiliation grid-institutes:grid.13992.30
    122 schema:familyName Hubáček
    123 schema:givenName Pavel
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016153011375.19
    125 rdf:type schema:Person
    126 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
    127 schema:familyName Naor
    128 schema:givenName Moni
    129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
    130 rdf:type schema:Person
    131 sg:pub.10.1007/3-540-44598-6_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002949083
    132 https://doi.org/10.1007/3-540-44598-6_7
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-540-75520-3_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017105472
    135 https://doi.org/10.1007/978-3-540-75520-3_30
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf01756291 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004391712
    138 https://doi.org/10.1007/bf01756291
    139 rdf:type schema:CreativeWork
    140 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel
    141 schema:name Department of Computer Science and Applied Mathematics,, Weizmann Institute of Science, 76100, Rehovot, Israel
    142 rdf:type schema:Organization
    143 grid-institutes:grid.261112.7 schema:alternateName Northeastern University College of Computer and Information Science, 02115, Boston, MA, USA
    144 schema:name Northeastern University College of Computer and Information Science, 02115, Boston, MA, USA
    145 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...