On a Network Generalization of the Minmax Theorem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Constantinos Daskalakis , Christos H. Papadimitriou

ABSTRACT

We consider graphical games in which the edges are zero-sum games between the endpoints/players; the payoff of a player is the sum of the payoffs from each incident edge. Such games are arguably very broad and useful models of networked economic interactions. We give a simple reduction of such games to two-person zero-sum games; as a corollary, a mixed Nash equilibrium can be computed efficiently by solving a linear program and rounding off the results. Our results render polynomially efficient, and simplify considerably, the approach in [3]. More... »

PAGES

423-434

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-642-02929-5
978-3-642-02930-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02930-1_35

DOI

http://dx.doi.org/10.1007/978-3-642-02930-1_35

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research New England, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Daskalakis", 
        "givenName": "Constantinos", 
        "id": "sg:person.0621125744.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621125744.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "U.C. Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "U.C. Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We consider graphical games in which the edges are zero-sum games between the endpoints/players; the payoff of a player is the sum of the payoffs from each incident edge. Such games are arguably very broad and useful models of networked economic interactions. We give a simple reduction of such games to two-person zero-sum games; as a corollary, a mixed Nash equilibrium can be computed efficiently by solving a linear program and rounding off the results. Our results render polynomially efficient, and simplify considerably, the approach in [3].", 
    "editor": [
      {
        "familyName": "Albers", 
        "givenName": "Susanne", 
        "type": "Person"
      }, 
      {
        "familyName": "Marchetti-Spaccamela", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Matias", 
        "givenName": "Yossi", 
        "type": "Person"
      }, 
      {
        "familyName": "Nikoletseas", 
        "givenName": "Sotiris", 
        "type": "Person"
      }, 
      {
        "familyName": "Thomas", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02930-1_35", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02929-5", 
        "978-3-642-02930-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "zero-sum game", 
      "two-person", 
      "mixed Nash equilibrium", 
      "such games", 
      "linear program", 
      "minmax theorem", 
      "graphical games", 
      "Nash equilibrium", 
      "network generalization", 
      "incident edges", 
      "payoffs", 
      "theorem", 
      "generalization", 
      "game", 
      "corollary", 
      "simple reduction", 
      "sum", 
      "model", 
      "equilibrium", 
      "approach", 
      "edge", 
      "results", 
      "players", 
      "economic interactions", 
      "useful model", 
      "reduction", 
      "program", 
      "interaction", 
      "endpoints/players", 
      "networked economic interactions"
    ], 
    "name": "On a Network Generalization of the Minmax Theorem", 
    "pagination": "423-434", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009551474"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02930-1_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02930-1_35", 
      "https://app.dimensions.ai/details/publication/pub.1009551474"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_324.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-02930-1_35"
  }
]
 

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-642-02930-1_35'

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-642-02930-1_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02930-1_35'

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-642-02930-1_35'


 

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

120 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02930-1_35 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nd05f963fa5334a448362ff34c74909fc
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We consider graphical games in which the edges are zero-sum games between the endpoints/players; the payoff of a player is the sum of the payoffs from each incident edge. Such games are arguably very broad and useful models of networked economic interactions. We give a simple reduction of such games to two-person zero-sum games; as a corollary, a mixed Nash equilibrium can be computed efficiently by solving a linear program and rounding off the results. Our results render polynomially efficient, and simplify considerably, the approach in [3].
7 schema:editor N75fe80b968a84062a969bda4c5c356ba
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb03e225d1098477cad01d8eb7311ae89
12 schema:keywords Nash equilibrium
13 approach
14 corollary
15 economic interactions
16 edge
17 endpoints/players
18 equilibrium
19 game
20 generalization
21 graphical games
22 incident edges
23 interaction
24 linear program
25 minmax theorem
26 mixed Nash equilibrium
27 model
28 network generalization
29 networked economic interactions
30 payoffs
31 players
32 program
33 reduction
34 results
35 simple reduction
36 such games
37 sum
38 theorem
39 two-person
40 useful model
41 zero-sum game
42 schema:name On a Network Generalization of the Minmax Theorem
43 schema:pagination 423-434
44 schema:productId N54202bf9844840239115bebe2d42a934
45 Naa01deb2eb5b46ebb264aa944bd9faea
46 schema:publisher N1c508696087c440b9b9cc1b984caf8dd
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009551474
48 https://doi.org/10.1007/978-3-642-02930-1_35
49 schema:sdDatePublished 2021-11-01T18:55
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N97518cfdcb8946c8a81342ee5384f113
52 schema:url https://doi.org/10.1007/978-3-642-02930-1_35
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N112d2773a072414980808025307df6be rdf:first N90e56136d0bb4274b61967cb0529b4df
57 rdf:rest Ne6b5754a9cad4511a01d93757b001d23
58 N1c508696087c440b9b9cc1b984caf8dd schema:name Springer Nature
59 rdf:type schema:Organisation
60 N3eaaa83472014530a6f5da31c62011a0 rdf:first sg:person.013233165465.63
61 rdf:rest rdf:nil
62 N51f13f4ae4e34da7a9200796ed673be5 schema:familyName Marchetti-Spaccamela
63 schema:givenName Alberto
64 rdf:type schema:Person
65 N54202bf9844840239115bebe2d42a934 schema:name doi
66 schema:value 10.1007/978-3-642-02930-1_35
67 rdf:type schema:PropertyValue
68 N6280396fe37a4822be5a4eef4245a152 rdf:first N51f13f4ae4e34da7a9200796ed673be5
69 rdf:rest N92e1b98b5a444bf4b84d5916b240773e
70 N7090ab6899a94b1881e44fd9d3b170d4 schema:familyName Thomas
71 schema:givenName Wolfgang
72 rdf:type schema:Person
73 N75fe80b968a84062a969bda4c5c356ba rdf:first Nbb458f90306547d2916a209373d69620
74 rdf:rest N6280396fe37a4822be5a4eef4245a152
75 N90e56136d0bb4274b61967cb0529b4df schema:familyName Nikoletseas
76 schema:givenName Sotiris
77 rdf:type schema:Person
78 N92e1b98b5a444bf4b84d5916b240773e rdf:first Nbd00bbb715f54077b1ae4089c2147405
79 rdf:rest N112d2773a072414980808025307df6be
80 N97518cfdcb8946c8a81342ee5384f113 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Naa01deb2eb5b46ebb264aa944bd9faea schema:name dimensions_id
83 schema:value pub.1009551474
84 rdf:type schema:PropertyValue
85 Nb03e225d1098477cad01d8eb7311ae89 schema:isbn 978-3-642-02929-5
86 978-3-642-02930-1
87 schema:name Automata, Languages and Programming
88 rdf:type schema:Book
89 Nbb458f90306547d2916a209373d69620 schema:familyName Albers
90 schema:givenName Susanne
91 rdf:type schema:Person
92 Nbd00bbb715f54077b1ae4089c2147405 schema:familyName Matias
93 schema:givenName Yossi
94 rdf:type schema:Person
95 Nd05f963fa5334a448362ff34c74909fc rdf:first sg:person.0621125744.74
96 rdf:rest N3eaaa83472014530a6f5da31c62011a0
97 Ne6b5754a9cad4511a01d93757b001d23 rdf:first N7090ab6899a94b1881e44fd9d3b170d4
98 rdf:rest rdf:nil
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
103 schema:name Artificial Intelligence and Image Processing
104 rdf:type schema:DefinedTerm
105 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
106 schema:familyName Papadimitriou
107 schema:givenName Christos H.
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
109 rdf:type schema:Person
110 sg:person.0621125744.74 schema:affiliation grid-institutes:grid.419815.0
111 schema:familyName Daskalakis
112 schema:givenName Constantinos
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621125744.74
114 rdf:type schema:Person
115 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research New England, USA
116 schema:name Microsoft Research New England, USA
117 rdf:type schema:Organization
118 grid-institutes:grid.47840.3f schema:alternateName U.C. Berkeley, USA
119 schema:name U.C. Berkeley, USA
120 rdf:type schema:Organization
 




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


...