A Cryptographic Solution to a Game Theoretic Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000-08-11

AUTHORS

Yevgeniy Dodis , Shai Halevi , Tal Rabin

ABSTRACT

In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payo.s can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payo.s o.ered by mediator-assisted strategies. We answer this question a.rmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game.The main building block of our solution is an e.cient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games. More... »

PAGES

112-130

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44598-6_7

DOI

http://dx.doi.org/10.1007/3-540-44598-6_7

DIMENSIONS

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


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/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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratory for Computer Science, MIT, 545 Tech Square, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, MIT, 545 Tech Square, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dodis", 
        "givenName": "Yevgeniy", 
        "id": "sg:person.015074130645.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "id": "sg:person.015100320721.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015100320721.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-08-11", 
    "datePublishedReg": "2000-08-11", 
    "description": "In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of \u201cself-enforcing\u201d strategies making each player\u2019s strategy an optimal response to the other player\u2019s strategy. It is known that for many games the expected equilibrium payo.s can be much higher when a trusted third party (a \u201cmediator\u201d) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payo.s o.ered by mediator-assisted strategies. We answer this question a.rmatively provided the players are computationally bounded and can have free communication (so-called \u201ccheap talk\u201d) prior to playing the game.The main building block of our solution is an e.cient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games.", 
    "editor": [
      {
        "familyName": "Bellare", 
        "givenName": "Mihir", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44598-6_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67907-3", 
        "978-3-540-44598-2"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPTO 2000", 
      "type": "Book"
    }, 
    "keywords": [
      "cryptographic protocols", 
      "game-theoretic problem", 
      "zero-knowledge proofs", 
      "negligible error probability", 
      "cryptographic solutions", 
      "game-theoretic setting", 
      "game-theoretic solution concepts", 
      "main building blocks", 
      "theoretic problems", 
      "selection problem", 
      "list of pairs", 
      "third party", 
      "extensive form games", 
      "such games", 
      "players' strategies", 
      "constant number", 
      "strategic game", 
      "independent interest", 
      "game", 
      "solution concept", 
      "free communication", 
      "error probability", 
      "form games", 
      "cryptography", 
      "protocol", 
      "building blocks", 
      "Alice", 
      "players", 
      "Bob", 
      "communication", 
      "solution", 
      "moves", 
      "strategies", 
      "proof", 
      "concept", 
      "index I", 
      "parties", 
      "work", 
      "block", 
      "list", 
      "need", 
      "parallel", 
      "probability", 
      "pairs", 
      "interest", 
      "rounds", 
      "number", 
      "optimal response", 
      "setting", 
      "area", 
      "mechanism", 
      "interesting parallels", 
      "equilibrium", 
      "response", 
      "mediators", 
      "A.", 
      "problem"
    ], 
    "name": "A Cryptographic Solution to a Game Theoretic Problem", 
    "pagination": "112-130", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002949083"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44598-6_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44598-6_7", 
      "https://app.dimensions.ai/details/publication/pub.1002949083"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_260.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44598-6_7"
  }
]
 

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/3-540-44598-6_7'

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/3-540-44598-6_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44598-6_7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44598-6_7'


 

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

134 TRIPLES      23 PREDICATES      82 URIs      75 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44598-6_7 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Ne0a1ce76fd6d4dcaa4e358dec438def4
4 schema:datePublished 2000-08-11
5 schema:datePublishedReg 2000-08-11
6 schema:description In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payo.s can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payo.s o.ered by mediator-assisted strategies. We answer this question a.rmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game.The main building block of our solution is an e.cient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games.
7 schema:editor Nddbd3fb14c734232b274006a9f540bfb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N61de09f3ec48448cba66e22b9838ba42
12 schema:keywords A.
13 Alice
14 Bob
15 area
16 block
17 building blocks
18 communication
19 concept
20 constant number
21 cryptographic protocols
22 cryptographic solutions
23 cryptography
24 equilibrium
25 error probability
26 extensive form games
27 form games
28 free communication
29 game
30 game-theoretic problem
31 game-theoretic setting
32 game-theoretic solution concepts
33 independent interest
34 index I
35 interest
36 interesting parallels
37 list
38 list of pairs
39 main building blocks
40 mechanism
41 mediators
42 moves
43 need
44 negligible error probability
45 number
46 optimal response
47 pairs
48 parallel
49 parties
50 players
51 players' strategies
52 probability
53 problem
54 proof
55 protocol
56 response
57 rounds
58 selection problem
59 setting
60 solution
61 solution concept
62 strategic game
63 strategies
64 such games
65 theoretic problems
66 third party
67 work
68 zero-knowledge proofs
69 schema:name A Cryptographic Solution to a Game Theoretic Problem
70 schema:pagination 112-130
71 schema:productId N4d1606e10c7142699ad6269a989ea369
72 N5745212f3aec461fa951d65f64f9444e
73 schema:publisher Nd06311b75c0a4d9994c3d0cf0fd188c0
74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002949083
75 https://doi.org/10.1007/3-540-44598-6_7
76 schema:sdDatePublished 2022-05-10T10:44
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher N4e7f2d6e07b14c77b575190e70ec6e59
79 schema:url https://doi.org/10.1007/3-540-44598-6_7
80 sgo:license sg:explorer/license/
81 sgo:sdDataset chapters
82 rdf:type schema:Chapter
83 N1cf24b4d82a346b68421fba09883f0dc rdf:first sg:person.015473523512.58
84 rdf:rest rdf:nil
85 N44a7bd8a97f14e8e800ba774060cbe68 schema:familyName Bellare
86 schema:givenName Mihir
87 rdf:type schema:Person
88 N4d1606e10c7142699ad6269a989ea369 schema:name dimensions_id
89 schema:value pub.1002949083
90 rdf:type schema:PropertyValue
91 N4e7f2d6e07b14c77b575190e70ec6e59 schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 N5745212f3aec461fa951d65f64f9444e schema:name doi
94 schema:value 10.1007/3-540-44598-6_7
95 rdf:type schema:PropertyValue
96 N61de09f3ec48448cba66e22b9838ba42 schema:isbn 978-3-540-44598-2
97 978-3-540-67907-3
98 schema:name Advances in Cryptology — CRYPTO 2000
99 rdf:type schema:Book
100 Nd06311b75c0a4d9994c3d0cf0fd188c0 schema:name Springer Nature
101 rdf:type schema:Organisation
102 Nd86a5b4b88124f159b264c6cd675b153 rdf:first sg:person.015100320721.93
103 rdf:rest N1cf24b4d82a346b68421fba09883f0dc
104 Nddbd3fb14c734232b274006a9f540bfb rdf:first N44a7bd8a97f14e8e800ba774060cbe68
105 rdf:rest rdf:nil
106 Ne0a1ce76fd6d4dcaa4e358dec438def4 rdf:first sg:person.015074130645.34
107 rdf:rest Nd86a5b4b88124f159b264c6cd675b153
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
112 schema:name Data Format
113 rdf:type schema:DefinedTerm
114 sg:person.015074130645.34 schema:affiliation grid-institutes:grid.116068.8
115 schema:familyName Dodis
116 schema:givenName Yevgeniy
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34
118 rdf:type schema:Person
119 sg:person.015100320721.93 schema:affiliation grid-institutes:grid.481554.9
120 schema:familyName Halevi
121 schema:givenName Shai
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015100320721.93
123 rdf:type schema:Person
124 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
125 schema:familyName Rabin
126 schema:givenName Tal
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
128 rdf:type schema:Person
129 grid-institutes:grid.116068.8 schema:alternateName Laboratory for Computer Science, MIT, 545 Tech Square, 02139, Cambridge, MA, USA
130 schema:name Laboratory for Computer Science, MIT, 545 Tech Square, 02139, Cambridge, MA, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA
133 schema:name IBM T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, New York, USA
134 rdf:type schema:Organization
 




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


...