Potential games, path independence and Poisson’s binomial distribution View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-08

AUTHORS

Debapriya Sen

ABSTRACT

This paper provides a simple characterization of potential games in terms of path independence. Using this characterization we propose an algorithm to determine if a finite game is potential or not. We define the storage requirement for our algorithm and provide its upper bound. The number of equations required in this algorithm is lower or equal to the number obtained in the algorithms proposed in the recent literature. We also show that for games with same numbers of players and strategy profiles, the number of equations for our algorithm is maximum when all players have the same number of strategies. The key technique of this paper is to identify an associated Poisson’s binomial distribution with any finite game. This distribution enables us to derive explicit forms of the number of equations, storage requirement and related aspects. More... »

PAGES

125-146

References to SciGraph publications

  • 2011-02. An improved algorithm for detecting potential games in INTERNATIONAL JOURNAL OF GAME THEORY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00186-018-0631-7

    DOI

    http://dx.doi.org/10.1007/s00186-018-0631-7

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Ryerson University", 
              "id": "https://www.grid.ac/institutes/grid.68312.3e", 
              "name": [
                "Ryerson University, Toronto, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sen", 
            "givenName": "Debapriya", 
            "id": "sg:person.011044010275.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044010275.95"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1006/jcta.1997.2747", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001459329"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/506147.506153", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002416680"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00182-010-0233-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005038833", 
              "https://doi.org/10.1007/s00182-010-0233-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.geb.2005.12.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026828003"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/game.2000.0800", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036041095"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.geb.2009.05.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045787003"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/game.1996.0044", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048802310"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.geb.2010.01.008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050000139"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tac.2016.2525936", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061479958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tsmcb.2009.2017273", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061797064"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aoms/1177703287", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064400141"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aoms/1177728178", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064401313"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1257/aer.104.3.898", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064526219"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/moor.2015.0771", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064723961"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wcnc.2004.1311438", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094958409"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-08", 
        "datePublishedReg": "2018-08-01", 
        "description": "This paper provides a simple characterization of potential games in terms of path independence. Using this characterization we propose an algorithm to determine if a finite game is potential or not. We define the storage requirement for our algorithm and provide its upper bound. The number of equations required in this algorithm is lower or equal to the number obtained in the algorithms proposed in the recent literature. We also show that for games with same numbers of players and strategy profiles, the number of equations for our algorithm is maximum when all players have the same number of strategies. The key technique of this paper is to identify an associated Poisson\u2019s binomial distribution with any finite game. This distribution enables us to derive explicit forms of the number of equations, storage requirement and related aspects.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00186-018-0631-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1053187", 
            "issn": [
              "1432-2994", 
              "1432-5217"
            ], 
            "name": "Mathematical Methods of Operations Research", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "88"
          }
        ], 
        "name": "Potential games, path independence and Poisson\u2019s binomial distribution", 
        "pagination": "125-146", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5fce2588258f779d923071d90c528df84c053a1ad997bfab538a50193b9e4516"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00186-018-0631-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1100995982"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00186-018-0631-7", 
          "https://app.dimensions.ai/details/publication/pub.1100995982"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T22:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8690_00000484.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00186-018-0631-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/s00186-018-0631-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/s00186-018-0631-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00186-018-0631-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00186-018-0631-7'


     

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

    107 TRIPLES      21 PREDICATES      42 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00186-018-0631-7 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N6df5e142f06c437abce6058df0399fcd
    4 schema:citation sg:pub.10.1007/s00182-010-0233-y
    5 https://doi.org/10.1006/game.1996.0044
    6 https://doi.org/10.1006/game.2000.0800
    7 https://doi.org/10.1006/jcta.1997.2747
    8 https://doi.org/10.1016/j.geb.2005.12.006
    9 https://doi.org/10.1016/j.geb.2009.05.004
    10 https://doi.org/10.1016/j.geb.2010.01.008
    11 https://doi.org/10.1109/tac.2016.2525936
    12 https://doi.org/10.1109/tsmcb.2009.2017273
    13 https://doi.org/10.1109/wcnc.2004.1311438
    14 https://doi.org/10.1145/506147.506153
    15 https://doi.org/10.1214/aoms/1177703287
    16 https://doi.org/10.1214/aoms/1177728178
    17 https://doi.org/10.1257/aer.104.3.898
    18 https://doi.org/10.1287/moor.2015.0771
    19 schema:datePublished 2018-08
    20 schema:datePublishedReg 2018-08-01
    21 schema:description This paper provides a simple characterization of potential games in terms of path independence. Using this characterization we propose an algorithm to determine if a finite game is potential or not. We define the storage requirement for our algorithm and provide its upper bound. The number of equations required in this algorithm is lower or equal to the number obtained in the algorithms proposed in the recent literature. We also show that for games with same numbers of players and strategy profiles, the number of equations for our algorithm is maximum when all players have the same number of strategies. The key technique of this paper is to identify an associated Poisson’s binomial distribution with any finite game. This distribution enables us to derive explicit forms of the number of equations, storage requirement and related aspects.
    22 schema:genre research_article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree true
    25 schema:isPartOf N14a38d6825e94029afea0546b8e8c34a
    26 N37cc1520ee5146b284b791baf1a098e4
    27 sg:journal.1053187
    28 schema:name Potential games, path independence and Poisson’s binomial distribution
    29 schema:pagination 125-146
    30 schema:productId N2419019042274b7181eb2c995f0d279f
    31 N44ec2db6bebd43fb8948432dd058d7ae
    32 Nb043525bcb3b47edaadc595f4ab2c297
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100995982
    34 https://doi.org/10.1007/s00186-018-0631-7
    35 schema:sdDatePublished 2019-04-10T22:25
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nb11cb5bbda2442f7b50a48edee40c84d
    38 schema:url http://link.springer.com/10.1007/s00186-018-0631-7
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset articles
    41 rdf:type schema:ScholarlyArticle
    42 N14a38d6825e94029afea0546b8e8c34a schema:volumeNumber 88
    43 rdf:type schema:PublicationVolume
    44 N2419019042274b7181eb2c995f0d279f schema:name readcube_id
    45 schema:value 5fce2588258f779d923071d90c528df84c053a1ad997bfab538a50193b9e4516
    46 rdf:type schema:PropertyValue
    47 N37cc1520ee5146b284b791baf1a098e4 schema:issueNumber 1
    48 rdf:type schema:PublicationIssue
    49 N44ec2db6bebd43fb8948432dd058d7ae schema:name dimensions_id
    50 schema:value pub.1100995982
    51 rdf:type schema:PropertyValue
    52 N6df5e142f06c437abce6058df0399fcd rdf:first sg:person.011044010275.95
    53 rdf:rest rdf:nil
    54 Nb043525bcb3b47edaadc595f4ab2c297 schema:name doi
    55 schema:value 10.1007/s00186-018-0631-7
    56 rdf:type schema:PropertyValue
    57 Nb11cb5bbda2442f7b50a48edee40c84d schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Mathematical Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Pure Mathematics
    64 rdf:type schema:DefinedTerm
    65 sg:journal.1053187 schema:issn 1432-2994
    66 1432-5217
    67 schema:name Mathematical Methods of Operations Research
    68 rdf:type schema:Periodical
    69 sg:person.011044010275.95 schema:affiliation https://www.grid.ac/institutes/grid.68312.3e
    70 schema:familyName Sen
    71 schema:givenName Debapriya
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044010275.95
    73 rdf:type schema:Person
    74 sg:pub.10.1007/s00182-010-0233-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1005038833
    75 https://doi.org/10.1007/s00182-010-0233-y
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1006/game.1996.0044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048802310
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1006/game.2000.0800 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036041095
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1006/jcta.1997.2747 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001459329
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1016/j.geb.2005.12.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026828003
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/j.geb.2009.05.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045787003
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1016/j.geb.2010.01.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050000139
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1109/tac.2016.2525936 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061479958
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/tsmcb.2009.2017273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061797064
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1109/wcnc.2004.1311438 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094958409
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1145/506147.506153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002416680
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1214/aoms/1177703287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064400141
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1214/aoms/1177728178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064401313
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1257/aer.104.3.898 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064526219
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1287/moor.2015.0771 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064723961
    104 rdf:type schema:CreativeWork
    105 https://www.grid.ac/institutes/grid.68312.3e schema:alternateName Ryerson University
    106 schema:name Ryerson University, Toronto, ON, Canada
    107 rdf:type schema:Organization
     




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


    ...