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": "2022-01-01T19:15", 
    "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/chapter/chapter_262.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 N3977a0f1a6ad4380967bc1622db6a9e6
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 Nf3dbb6530fa94187b334923e8767e90f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3bac4b636a1d469abec198186109ee5b
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 N52850846b2d2467ea3b0d33a6c99b562
45 Nddcc56d4c857428a8df4f41b4941cdd0
46 schema:publisher N611d91694404462f8ea7b5da03361d77
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 2022-01-01T19:15
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N21c2e046044143f1bb1494dc6a7f1576
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 N011bf7e2dafc4e09bfab6227c69bc463 schema:familyName Nikoletseas
57 schema:givenName Sotiris
58 rdf:type schema:Person
59 N21c2e046044143f1bb1494dc6a7f1576 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N274cd1adc7324db4b2003d9c1a1abcbe schema:familyName Marchetti-Spaccamela
62 schema:givenName Alberto
63 rdf:type schema:Person
64 N3977a0f1a6ad4380967bc1622db6a9e6 rdf:first sg:person.0621125744.74
65 rdf:rest N8edf936f5fb2458ab55cc6609786c26e
66 N3bac4b636a1d469abec198186109ee5b schema:isbn 978-3-642-02929-5
67 978-3-642-02930-1
68 schema:name Automata, Languages and Programming
69 rdf:type schema:Book
70 N52850846b2d2467ea3b0d33a6c99b562 schema:name dimensions_id
71 schema:value pub.1009551474
72 rdf:type schema:PropertyValue
73 N611d91694404462f8ea7b5da03361d77 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N88255b00045446cdbadcdfed043ad3d1 rdf:first N9da38a4db11a4e6e81c52cce0bc28dba
76 rdf:rest Nfc3e902b232e4058a38d5e54496529d0
77 N8edf936f5fb2458ab55cc6609786c26e rdf:first sg:person.013233165465.63
78 rdf:rest rdf:nil
79 N9da38a4db11a4e6e81c52cce0bc28dba schema:familyName Matias
80 schema:givenName Yossi
81 rdf:type schema:Person
82 Na18dc4103cd64439b79e0cc5e40093b6 rdf:first N274cd1adc7324db4b2003d9c1a1abcbe
83 rdf:rest N88255b00045446cdbadcdfed043ad3d1
84 Na95b508033ab42deac03f622582de8f9 schema:familyName Albers
85 schema:givenName Susanne
86 rdf:type schema:Person
87 Nddcc56d4c857428a8df4f41b4941cdd0 schema:name doi
88 schema:value 10.1007/978-3-642-02930-1_35
89 rdf:type schema:PropertyValue
90 Ndebb48c2b1704a8682062de5daca9cbe rdf:first Ne560d58b93554cafb3b788d9550e6a2c
91 rdf:rest rdf:nil
92 Ne560d58b93554cafb3b788d9550e6a2c schema:familyName Thomas
93 schema:givenName Wolfgang
94 rdf:type schema:Person
95 Nf3dbb6530fa94187b334923e8767e90f rdf:first Na95b508033ab42deac03f622582de8f9
96 rdf:rest Na18dc4103cd64439b79e0cc5e40093b6
97 Nfc3e902b232e4058a38d5e54496529d0 rdf:first N011bf7e2dafc4e09bfab6227c69bc463
98 rdf:rest Ndebb48c2b1704a8682062de5daca9cbe
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)


...