The Web Graph as an Equilibrium View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-12-10

AUTHORS

Georgios Kouroupas , Evangelos Markakis , Christos Papadimitriou , Vasileios Rigas , Martha Sideri

ABSTRACT

We present a game-theoretic model for the creation of content networks such as the worldwide web. The action space of a node in our model consists of choosing a set of outgoing links as well as click probabilities on these links. A node’s utility is then the product of the traffic through this node, captured by its PageRank in the Markov chain created by the strategy profile, times the quality of the node, a surrogate for the website’s utility per visit, such as repute or monetization potential. The latter depends on the intrinsic quality of the node’s content, as modified by the chosen outgoing links and probabilities. We only require that the quality be a concave function of the node’s strategy (the distribution over outgoing links), and we suggest a natural example of such a function. We prove that the resulting game always has a pure Nash equilibrium. Experiments suggest that these equilibria are not hard to compute, avoid the reciprocal equilibria of other such models, have characteristics broadly consistent with what we know about the worldwide web, and seem to have favorable price of anarchy. More... »

PAGES

203-215

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Informatics, Athens University of Economics and Business, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.16299.35", 
          "name": [
            "Department of Informatics, Athens University of Economics and Business, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kouroupas", 
        "givenName": "Georgios", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Informatics, Athens University of Economics and Business, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.16299.35", 
          "name": [
            "Department of Informatics, Athens University of Economics and Business, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Markakis", 
        "givenName": "Evangelos", 
        "id": "sg:person.014013771241.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of EECS, University of California - Berkeley, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Department of EECS, University of California - Berkeley, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Informatics, Athens University of Economics and Business, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.16299.35", 
          "name": [
            "Department of Informatics, Athens University of Economics and Business, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rigas", 
        "givenName": "Vasileios", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Informatics, Athens University of Economics and Business, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.16299.35", 
          "name": [
            "Department of Informatics, Athens University of Economics and Business, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sideri", 
        "givenName": "Martha", 
        "id": "sg:person.016347202663.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347202663.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-12-10", 
    "datePublishedReg": "2015-12-10", 
    "description": "We present a game-theoretic model for the creation of content networks such as the worldwide web. The action space of a node in our model consists of choosing a set of outgoing links as well as click probabilities on these links. A node\u2019s utility is then the product of the traffic through this node, captured by its PageRank in the Markov chain created by the strategy profile, times the quality of the node, a surrogate for the website\u2019s utility per visit, such as repute or monetization potential. The latter depends on the intrinsic quality of the node\u2019s content, as modified by the chosen outgoing links and probabilities. We only require that the quality be a concave function of the node\u2019s strategy (the distribution over outgoing links), and we suggest a natural example of such a function. We prove that the resulting game always has a pure Nash equilibrium. Experiments suggest that these equilibria are not hard to compute, avoid the reciprocal equilibria of other such models, have characteristics broadly consistent with what we know about the worldwide web, and seem to have favorable price of anarchy.", 
    "editor": [
      {
        "familyName": "Hoefer", 
        "givenName": "Martin", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48433-3_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48432-6", 
        "978-3-662-48433-3"
      ], 
      "name": "Algorithmic Game Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "outgoing links", 
      "pure Nash equilibria", 
      "Markov chain", 
      "action space", 
      "concave function", 
      "game-theoretic model", 
      "Nash equilibrium", 
      "such models", 
      "node strategy", 
      "strategy profile", 
      "node utility", 
      "natural examples", 
      "web graph", 
      "model", 
      "equilibrium", 
      "nodes", 
      "content networks", 
      "space", 
      "probability", 
      "graph", 
      "traffic", 
      "function", 
      "set", 
      "network", 
      "worldwide web", 
      "link", 
      "PageRank", 
      "game", 
      "prices", 
      "utility", 
      "monetization potential", 
      "node content", 
      "anarchy", 
      "strategies", 
      "surrogate", 
      "website utility", 
      "Web", 
      "chain", 
      "intrinsic quality", 
      "quality", 
      "experiments", 
      "favorable prices", 
      "clicks", 
      "characteristics", 
      "reciprocal equilibrium", 
      "creation", 
      "products", 
      "example", 
      "potential", 
      "profile", 
      "content", 
      "repute", 
      "visits"
    ], 
    "name": "The Web Graph as an Equilibrium", 
    "pagination": "203-215", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031523720"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48433-3_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48433-3_16", 
      "https://app.dimensions.ai/details/publication/pub.1031523720"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_341.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48433-3_16"
  }
]
 

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

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_16'

Turtle is a human-readable linked data format.

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

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_16'


 

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

142 TRIPLES      23 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48433-3_16 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nde0aeae7bf6c468ab8533d12a9145b0d
4 schema:datePublished 2015-12-10
5 schema:datePublishedReg 2015-12-10
6 schema:description We present a game-theoretic model for the creation of content networks such as the worldwide web. The action space of a node in our model consists of choosing a set of outgoing links as well as click probabilities on these links. A node’s utility is then the product of the traffic through this node, captured by its PageRank in the Markov chain created by the strategy profile, times the quality of the node, a surrogate for the website’s utility per visit, such as repute or monetization potential. The latter depends on the intrinsic quality of the node’s content, as modified by the chosen outgoing links and probabilities. We only require that the quality be a concave function of the node’s strategy (the distribution over outgoing links), and we suggest a natural example of such a function. We prove that the resulting game always has a pure Nash equilibrium. Experiments suggest that these equilibria are not hard to compute, avoid the reciprocal equilibria of other such models, have characteristics broadly consistent with what we know about the worldwide web, and seem to have favorable price of anarchy.
7 schema:editor N33a67cc563814d538cfcdd82c8bfb691
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N81cb6fa66bbd4ae4be144927e299edbf
12 schema:keywords Markov chain
13 Nash equilibrium
14 PageRank
15 Web
16 action space
17 anarchy
18 chain
19 characteristics
20 clicks
21 concave function
22 content
23 content networks
24 creation
25 equilibrium
26 example
27 experiments
28 favorable prices
29 function
30 game
31 game-theoretic model
32 graph
33 intrinsic quality
34 link
35 model
36 monetization potential
37 natural examples
38 network
39 node content
40 node strategy
41 node utility
42 nodes
43 outgoing links
44 potential
45 prices
46 probability
47 products
48 profile
49 pure Nash equilibria
50 quality
51 reciprocal equilibrium
52 repute
53 set
54 space
55 strategies
56 strategy profile
57 such models
58 surrogate
59 traffic
60 utility
61 visits
62 web graph
63 website utility
64 worldwide web
65 schema:name The Web Graph as an Equilibrium
66 schema:pagination 203-215
67 schema:productId N455b068df2f94de0be8777e57324655c
68 N912c94f062324e7d9541a69f5552115c
69 schema:publisher Nb092675555e04892b85e90ba9fac0ad0
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031523720
71 https://doi.org/10.1007/978-3-662-48433-3_16
72 schema:sdDatePublished 2021-12-01T20:05
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher Nc297ade19763432c99799ed524353b3e
75 schema:url https://doi.org/10.1007/978-3-662-48433-3_16
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N0d31a0eee1534ce6b41bedee5968acd7 rdf:first sg:person.014013771241.29
80 rdf:rest Nb2cdfc5217ad47dca9ffcee4ece6ae82
81 N116402c7276a49438fd29d0ec1bcf9f3 schema:affiliation grid-institutes:grid.16299.35
82 schema:familyName Kouroupas
83 schema:givenName Georgios
84 rdf:type schema:Person
85 N1bd3661ffef44b08b97018c4c13c511c rdf:first sg:person.016347202663.46
86 rdf:rest rdf:nil
87 N33a67cc563814d538cfcdd82c8bfb691 rdf:first Nf40b3741d8a64721af5bb5990a0e21a0
88 rdf:rest rdf:nil
89 N455b068df2f94de0be8777e57324655c schema:name dimensions_id
90 schema:value pub.1031523720
91 rdf:type schema:PropertyValue
92 N81cb6fa66bbd4ae4be144927e299edbf schema:isbn 978-3-662-48432-6
93 978-3-662-48433-3
94 schema:name Algorithmic Game Theory
95 rdf:type schema:Book
96 N8493b4e551364c4cbb1acdf7282b5576 schema:affiliation grid-institutes:grid.16299.35
97 schema:familyName Rigas
98 schema:givenName Vasileios
99 rdf:type schema:Person
100 N912c94f062324e7d9541a69f5552115c schema:name doi
101 schema:value 10.1007/978-3-662-48433-3_16
102 rdf:type schema:PropertyValue
103 Nb092675555e04892b85e90ba9fac0ad0 schema:name Springer Nature
104 rdf:type schema:Organisation
105 Nb2cdfc5217ad47dca9ffcee4ece6ae82 rdf:first sg:person.013233165465.63
106 rdf:rest Ne02d86962c2b48249ca27edcc8385e82
107 Nc297ade19763432c99799ed524353b3e schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 Nde0aeae7bf6c468ab8533d12a9145b0d rdf:first N116402c7276a49438fd29d0ec1bcf9f3
110 rdf:rest N0d31a0eee1534ce6b41bedee5968acd7
111 Ne02d86962c2b48249ca27edcc8385e82 rdf:first N8493b4e551364c4cbb1acdf7282b5576
112 rdf:rest N1bd3661ffef44b08b97018c4c13c511c
113 Nf40b3741d8a64721af5bb5990a0e21a0 schema:familyName Hoefer
114 schema:givenName Martin
115 rdf:type schema:Person
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
120 schema:name Information Systems
121 rdf:type schema:DefinedTerm
122 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
123 schema:familyName Papadimitriou
124 schema:givenName Christos
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
126 rdf:type schema:Person
127 sg:person.014013771241.29 schema:affiliation grid-institutes:grid.16299.35
128 schema:familyName Markakis
129 schema:givenName Evangelos
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29
131 rdf:type schema:Person
132 sg:person.016347202663.46 schema:affiliation grid-institutes:grid.16299.35
133 schema:familyName Sideri
134 schema:givenName Martha
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347202663.46
136 rdf:type schema:Person
137 grid-institutes:grid.16299.35 schema:alternateName Department of Informatics, Athens University of Economics and Business, Athens, Greece
138 schema:name Department of Informatics, Athens University of Economics and Business, Athens, Greece
139 rdf:type schema:Organization
140 grid-institutes:grid.47840.3f schema:alternateName Department of EECS, University of California - Berkeley, Berkeley, USA
141 schema:name Department of EECS, University of California - Berkeley, Berkeley, USA
142 rdf:type schema:Organization
 




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


...