When Can Limited Randomness Be Used in Repeated Games?

Ontology type: schema:Chapter      Open Access: True

Chapter Info

DATE

2015-12-10

AUTHORS 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n)$$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n)$$\end{document} random bits remain necessary for equilibria to exist. More... »

PAGES

259-271

Book

TITLE

Algorithmic Game Theory

ISBN

978-3-662-48432-6
978-3-662-48433-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_20

DOI

http://dx.doi.org/10.1007/978-3-662-48433-3_20

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/14",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Economics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1401",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Economic Theory",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Weizmann Institute of Science, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Weizmann Institute of Science, 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": "Weizmann Institute of Science, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Weizmann Institute of Science, 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": "Columbia University Department of Computer Science, New York, USA",
"id": "http://www.grid.ac/institutes/grid.21729.3f",
"name": [
"Columbia University Department of Computer Science, New York, 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"
}
],
"datePublished": "2015-12-10",
"datePublishedReg": "2015-12-10",
"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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varOmega (n)$$\\end{document} 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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varOmega (n)$$\\end{document} random bits remain necessary for equilibria to exist.",
"editor": [
{
"familyName": "Hoefer",
"givenName": "Martin",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-662-48433-3_20",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-662-48432-6",
"978-3-662-48433-3"
],
"name": "Algorithmic Game Theory",
"type": "Book"
},
"keywords": [
"two-player",
"zero-sum game",
"random bits",
"Nash equilibrium",
"pseudorandom generators",
"exact Nash equilibrium",
"true random bits",
"cryptographic pseudorandom generators",
"limited randomness",
"random-like sequence",
"approximate Nash equilibria",
"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",
"instances",
"generator",
"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": "259-271",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1007322399"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-662-48433-3_20"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-662-48433-3_20",
"https://app.dimensions.ai/details/publication/pub.1007322399"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:19",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_323.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-662-48433-3_20"
}
]

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/978-3-662-48433-3_20'

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/978-3-662-48433-3_20'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_20'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_20'

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

123 TRIPLES      23 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1401
3 schema:author Ne6a369fbe7e54b9abfeb09b46ee9b1b0
4 schema:datePublished 2015-12-10
5 schema:datePublishedReg 2015-12-10
6 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n)$$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n)$$\end{document} random bits remain necessary for equilibria to exist.
7 schema:editor Nc733acaa8f1e4a4d8f69bda7b288da21
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N300700eac2564180bdc582e47d45f881
12 schema:keywords Nash equilibrium
13 Repeated Games
14 access
15 approximate Nash equilibria
16 bits
17 central result
18 class
19 class of games
20 classical game theory
21 constant number
22 contrast
23 cryptographic pseudorandom generators
24 enough random bits
25 equilibrium
26 exact Nash equilibrium
27 finite normal form games
28 form games
29 game
30 game theory
31 generator
32 humans
33 instances
34 large class
35 limited randomness
36 normal form games
37 number
38 players
39 practice
40 pseudorandom generators
41 pure strategies
42 random bits
43 random-like sequence
44 randomness
45 results
46 sequence
47 single instance
48 small number
49 stage
50 strategies
51 theory
52 time
53 true random bits
54 two-player
55 version
56 work
57 zero-sum game
58 schema:name When Can Limited Randomness Be Used in Repeated Games?
59 schema:pagination 259-271
60 schema:productId N9d86e1b3ed6340d589e96e2c00ce0100
61 Ndc6302a9e6e74ec698355aedf12294e5
62 schema:publisher Na0d825c33886439f80f8fc9a280351b2
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007322399
64 https://doi.org/10.1007/978-3-662-48433-3_20
65 schema:sdDatePublished 2022-01-01T19:19
67 schema:sdPublisher N208083f0a9fc4bc5abfc59ef40a53b52
68 schema:url https://doi.org/10.1007/978-3-662-48433-3_20
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N09b1a9a4a1404291be98a2c0b87a5506 rdf:first sg:person.015402574613.10
73 rdf:rest rdf:nil
74 N208083f0a9fc4bc5abfc59ef40a53b52 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N300700eac2564180bdc582e47d45f881 schema:isbn 978-3-662-48432-6
77 978-3-662-48433-3
78 schema:name Algorithmic Game Theory
79 rdf:type schema:Book
80 N7072b751abc1454a9e8dd00c0b5c9823 schema:familyName Hoefer
81 schema:givenName Martin
82 rdf:type schema:Person
84 rdf:rest N09b1a9a4a1404291be98a2c0b87a5506
85 N9d86e1b3ed6340d589e96e2c00ce0100 schema:name doi
86 schema:value 10.1007/978-3-662-48433-3_20
87 rdf:type schema:PropertyValue
88 Na0d825c33886439f80f8fc9a280351b2 schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nc733acaa8f1e4a4d8f69bda7b288da21 rdf:first N7072b751abc1454a9e8dd00c0b5c9823
91 rdf:rest rdf:nil
92 Ndc6302a9e6e74ec698355aedf12294e5 schema:name dimensions_id
93 schema:value pub.1007322399
94 rdf:type schema:PropertyValue
95 Ne6a369fbe7e54b9abfeb09b46ee9b1b0 rdf:first sg:person.016153011375.19
97 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
98 schema:name Economics
99 rdf:type schema:DefinedTerm
100 anzsrc-for:1401 schema:inDefinedTermSet anzsrc-for:
101 schema:name Economic Theory
102 rdf:type schema:DefinedTerm
103 sg:person.015402574613.10 schema:affiliation grid-institutes:grid.21729.3f
104 schema:familyName Ullman
105 schema:givenName Jonathan
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402574613.10
107 rdf:type schema:Person
108 sg:person.016153011375.19 schema:affiliation grid-institutes:grid.13992.30
109 schema:familyName Hubáček
110 schema:givenName Pavel
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016153011375.19
112 rdf:type schema:Person
113 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
114 schema:familyName Naor
115 schema:givenName Moni
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
117 rdf:type schema:Person
118 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
119 schema:name Weizmann Institute of Science, Rehovot, Israel
120 rdf:type schema:Organization
121 grid-institutes:grid.21729.3f schema:alternateName Columbia University Department of Computer Science, New York, USA
122 schema:name Columbia University Department of Computer Science, New York, USA
123 rdf:type schema:Organization