Convergence to Equilibrium of Logit Dynamics for Strategic Games View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-09

AUTHORS

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, Giuseppe Persiano

ABSTRACT

We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise β describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter β. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in β and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with β. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in β. Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in β and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter. More... »

PAGES

110-142

References to SciGraph publications

  • 2013. Logit Dynamics with Concurrent Updates for Local Interaction Games in ALGORITHMS – ESA 2013
  • 2008. Asynchronous Best-Reply Dynamics in INTERNET AND NETWORK ECONOMICS
  • 2009. Adaptive Learning in Systems of Interacting Agents in INTERNET AND NETWORK ECONOMICS
  • 1998. Trilogy of Couplings and General Formulas for Lower Bound of Spectral Gap in PROBABILITY TOWARDS 2000
  • 2009. On the Inefficiency Ratio of Stable Equilibria in Congestion Games in INTERNET AND NETWORK ECONOMICS
  • 2005-03. Glauber dynamics on trees and hyperbolic graphs in PROBABILITY THEORY AND RELATED FIELDS
  • 2010. Mixing Time and Stationary Expected Social Welfare of Logit Dynamics in ALGORITHMIC GAME THEORY
  • 1999. Lectures on Glauber Dynamics for Discrete Spin Models in LECTURES ON PROBABILITY THEORY AND STATISTICS
  • 2010-07. Atomic Congestion Games: Fast, Myopic and Concurrent in THEORY OF COMPUTING SYSTEMS
  • 2012-10. Dynamics in network interaction games in DISTRIBUTED COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-015-0025-7

    DOI

    http://dx.doi.org/10.1007/s00453-015-0025-7

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Salerno", 
              "id": "https://www.grid.ac/institutes/grid.11780.3f", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 di Salerno, Via Ponte don Melillo, Fisciano, SA, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Auletta", 
            "givenName": "Vincenzo", 
            "id": "sg:person.016327521101.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Salerno", 
              "id": "https://www.grid.ac/institutes/grid.11780.3f", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 di Salerno, Via Ponte don Melillo, Fisciano, SA, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ferraioli", 
            "givenName": "Diodato", 
            "id": "sg:person.013375000576.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013375000576.36"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Rome Tor Vergata", 
              "id": "https://www.grid.ac/institutes/grid.6530.0", 
              "name": [
                "Dipartimento di Ingegneria dell\u2019Impresa \u201cM. Lucertini\u201d, Universit\u00e0 di Roma \u201cTor Vergata\u201d, Via della Ricerca Scientifica, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pasquale", 
            "givenName": "Francesco", 
            "id": "sg:person.010366026047.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire d'Informatique Algorithmique: Fondements et Applications", 
              "id": "https://www.grid.ac/institutes/grid.462842.e", 
              "name": [
                "LIAFA, B\u00e2timent Sophie Germain, Universit\u00e9 Paris Diderot, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Penna", 
            "givenName": "Paolo", 
            "id": "sg:person.013624103516.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Salerno", 
              "id": "https://www.grid.ac/institutes/grid.11780.3f", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 di Salerno, Via Ponte don Melillo, Fisciano, SA, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Persiano", 
            "givenName": "Giuseppe", 
            "id": "sg:person.013255374317.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-16170-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002237752", 
              "https://doi.org/10.1007/978-3-642-16170-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16170-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002237752", 
              "https://doi.org/10.1007/978-3-642-16170-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1582716.1582732", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004429168"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00440-004-0369-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019937826", 
              "https://doi.org/10.1007/s00440-004-0369-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00440-004-0369-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019937826", 
              "https://doi.org/10.1007/s00440-004-0369-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-009-9198-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020845378", 
              "https://doi.org/10.1007/s00224-009-9198-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-009-9198-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020845378", 
              "https://doi.org/10.1007/s00224-009-9198-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1989493.1989522", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027041176"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48115-7_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028683830", 
              "https://doi.org/10.1007/978-3-540-48115-7_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/game.1993.1023", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030783580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10841-9_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037569907", 
              "https://doi.org/10.1007/978-3-642-10841-9_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10841-9_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037569907", 
              "https://doi.org/10.1007/978-3-642-10841-9_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-40450-4_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038387322", 
              "https://doi.org/10.1007/978-3-642-40450-4_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-012-0171-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046963080", 
              "https://doi.org/10.1007/s00446-012-0171-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92185-1_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048926796", 
              "https://doi.org/10.1007/978-3-540-92185-1_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92185-1_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048926796", 
              "https://doi.org/10.1007/978-3-540-92185-1_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10841-9_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049236065", 
              "https://doi.org/10.1007/978-3-642-10841-9_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10841-9_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049236065", 
              "https://doi.org/10.1007/978-3-642-10841-9_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-2224-8_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051321427", 
              "https://doi.org/10.1007/978-1-4612-2224-8_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-2224-8_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051321427", 
              "https://doi.org/10.1007/978-1-4612-2224-8_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218077", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842176"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/070680199", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062850843"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/09-aap651", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064390633"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2951493", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1070145834"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.80", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801548"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1997.646111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093546754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/focs.2009.64", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095269626"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/mbk/058", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098774897"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511800481", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1108143530"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-09", 
        "datePublishedReg": "2016-09-01", 
        "description": "We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise \u03b2 describes the behavior of a complex system whose individual components act selfishly according to some partial (\u201cnoisy\u201d) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter \u03b2. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in \u03b2 and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with \u03b2. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in \u03b2. Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in \u03b2 and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-015-0025-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "76"
          }
        ], 
        "name": "Convergence to Equilibrium of Logit Dynamics for Strategic Games", 
        "pagination": "110-142", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b6f0dfa67ced7880a933362a20d70027aa271298c3239b33ba11dac196f6f73f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-015-0025-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1038404106"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-015-0025-7", 
          "https://app.dimensions.ai/details/publication/pub.1038404106"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T14:22", 
        "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_8660_00000591.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-015-0025-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/s00453-015-0025-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/s00453-015-0025-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0025-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0025-7'


     

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

    171 TRIPLES      21 PREDICATES      49 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-015-0025-7 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N0b3a5d4b5a554576b332352e798a2b5c
    4 schema:citation sg:pub.10.1007/978-1-4612-2224-8_7
    5 sg:pub.10.1007/978-3-540-48115-7_2
    6 sg:pub.10.1007/978-3-540-92185-1_59
    7 sg:pub.10.1007/978-3-642-10841-9_2
    8 sg:pub.10.1007/978-3-642-10841-9_54
    9 sg:pub.10.1007/978-3-642-16170-4_6
    10 sg:pub.10.1007/978-3-642-40450-4_7
    11 sg:pub.10.1007/s00224-009-9198-2
    12 sg:pub.10.1007/s00440-004-0369-4
    13 sg:pub.10.1007/s00446-012-0171-y
    14 https://doi.org/10.1006/game.1993.1023
    15 https://doi.org/10.1017/cbo9780511800481
    16 https://doi.org/10.1090/mbk/058
    17 https://doi.org/10.1109/focs.2009.64
    18 https://doi.org/10.1109/sfcs.1997.646111
    19 https://doi.org/10.1137/0218077
    20 https://doi.org/10.1137/070680199
    21 https://doi.org/10.1137/1.9781611973099.80
    22 https://doi.org/10.1145/1582716.1582732
    23 https://doi.org/10.1145/1989493.1989522
    24 https://doi.org/10.1214/09-aap651
    25 https://doi.org/10.2307/2951493
    26 schema:datePublished 2016-09
    27 schema:datePublishedReg 2016-09-01
    28 schema:description We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise β describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter β. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in β and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with β. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in β. Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in β and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.
    29 schema:genre research_article
    30 schema:inLanguage en
    31 schema:isAccessibleForFree false
    32 schema:isPartOf Na34b234a67af4b42959a8855bdd56898
    33 Nb917b7d3ff4442ecb84b464780122da5
    34 sg:journal.1047644
    35 schema:name Convergence to Equilibrium of Logit Dynamics for Strategic Games
    36 schema:pagination 110-142
    37 schema:productId Na427beeab78c49d78a717f0165227dd1
    38 Ndcdd1f03db494fe1b43b4840f8777996
    39 Nee1dae6704e74a75b27da6ba201b97d6
    40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038404106
    41 https://doi.org/10.1007/s00453-015-0025-7
    42 schema:sdDatePublished 2019-04-10T14:22
    43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    44 schema:sdPublisher N4605c2fb0e18417aaf0533515e08328b
    45 schema:url http://link.springer.com/10.1007%2Fs00453-015-0025-7
    46 sgo:license sg:explorer/license/
    47 sgo:sdDataset articles
    48 rdf:type schema:ScholarlyArticle
    49 N0b3a5d4b5a554576b332352e798a2b5c rdf:first sg:person.016327521101.60
    50 rdf:rest N5bf9c523d2504267b694a299bfc2b2f6
    51 N4605c2fb0e18417aaf0533515e08328b schema:name Springer Nature - SN SciGraph project
    52 rdf:type schema:Organization
    53 N5bf9c523d2504267b694a299bfc2b2f6 rdf:first sg:person.013375000576.36
    54 rdf:rest Nfc2ec4c165014e5d9936df03f0589d8c
    55 Na34b234a67af4b42959a8855bdd56898 schema:issueNumber 1
    56 rdf:type schema:PublicationIssue
    57 Na427beeab78c49d78a717f0165227dd1 schema:name dimensions_id
    58 schema:value pub.1038404106
    59 rdf:type schema:PropertyValue
    60 Nab6d5a77fb5248649aad3ac4c6d6ed94 rdf:first sg:person.013255374317.27
    61 rdf:rest rdf:nil
    62 Nb917b7d3ff4442ecb84b464780122da5 schema:volumeNumber 76
    63 rdf:type schema:PublicationVolume
    64 Nbfcf7b94876941efad53b109e9389bb8 rdf:first sg:person.013624103516.76
    65 rdf:rest Nab6d5a77fb5248649aad3ac4c6d6ed94
    66 Ndcdd1f03db494fe1b43b4840f8777996 schema:name doi
    67 schema:value 10.1007/s00453-015-0025-7
    68 rdf:type schema:PropertyValue
    69 Nee1dae6704e74a75b27da6ba201b97d6 schema:name readcube_id
    70 schema:value b6f0dfa67ced7880a933362a20d70027aa271298c3239b33ba11dac196f6f73f
    71 rdf:type schema:PropertyValue
    72 Nfc2ec4c165014e5d9936df03f0589d8c rdf:first sg:person.010366026047.55
    73 rdf:rest Nbfcf7b94876941efad53b109e9389bb8
    74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Information and Computing Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Artificial Intelligence and Image Processing
    79 rdf:type schema:DefinedTerm
    80 sg:journal.1047644 schema:issn 0178-4617
    81 1432-0541
    82 schema:name Algorithmica
    83 rdf:type schema:Periodical
    84 sg:person.010366026047.55 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
    85 schema:familyName Pasquale
    86 schema:givenName Francesco
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55
    88 rdf:type schema:Person
    89 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
    90 schema:familyName Persiano
    91 schema:givenName Giuseppe
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
    93 rdf:type schema:Person
    94 sg:person.013375000576.36 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
    95 schema:familyName Ferraioli
    96 schema:givenName Diodato
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013375000576.36
    98 rdf:type schema:Person
    99 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.462842.e
    100 schema:familyName Penna
    101 schema:givenName Paolo
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
    103 rdf:type schema:Person
    104 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
    105 schema:familyName Auletta
    106 schema:givenName Vincenzo
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
    108 rdf:type schema:Person
    109 sg:pub.10.1007/978-1-4612-2224-8_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051321427
    110 https://doi.org/10.1007/978-1-4612-2224-8_7
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-540-48115-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028683830
    113 https://doi.org/10.1007/978-3-540-48115-7_2
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-540-92185-1_59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048926796
    116 https://doi.org/10.1007/978-3-540-92185-1_59
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-642-10841-9_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049236065
    119 https://doi.org/10.1007/978-3-642-10841-9_2
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-10841-9_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037569907
    122 https://doi.org/10.1007/978-3-642-10841-9_54
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-642-16170-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002237752
    125 https://doi.org/10.1007/978-3-642-16170-4_6
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-642-40450-4_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038387322
    128 https://doi.org/10.1007/978-3-642-40450-4_7
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/s00224-009-9198-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020845378
    131 https://doi.org/10.1007/s00224-009-9198-2
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/s00440-004-0369-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019937826
    134 https://doi.org/10.1007/s00440-004-0369-4
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s00446-012-0171-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1046963080
    137 https://doi.org/10.1007/s00446-012-0171-y
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1006/game.1993.1023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030783580
    140 rdf:type schema:CreativeWork
    141 https://doi.org/10.1017/cbo9780511800481 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108143530
    142 rdf:type schema:CreativeWork
    143 https://doi.org/10.1090/mbk/058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098774897
    144 rdf:type schema:CreativeWork
    145 https://doi.org/10.1109/focs.2009.64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095269626
    146 rdf:type schema:CreativeWork
    147 https://doi.org/10.1109/sfcs.1997.646111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093546754
    148 rdf:type schema:CreativeWork
    149 https://doi.org/10.1137/0218077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842176
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1137/070680199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850843
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1137/1.9781611973099.80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801548
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1145/1582716.1582732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004429168
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1145/1989493.1989522 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027041176
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1214/09-aap651 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064390633
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.2307/2951493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070145834
    162 rdf:type schema:CreativeWork
    163 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
    164 schema:name Dipartimento di Informatica, Università di Salerno, Via Ponte don Melillo, Fisciano, SA, Italy
    165 rdf:type schema:Organization
    166 https://www.grid.ac/institutes/grid.462842.e schema:alternateName Laboratoire d'Informatique Algorithmique: Fondements et Applications
    167 schema:name LIAFA, Bâtiment Sophie Germain, Université Paris Diderot, Paris, France
    168 rdf:type schema:Organization
    169 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
    170 schema:name Dipartimento di Ingegneria dell’Impresa “M. Lucertini”, Università di Roma “Tor Vergata”, Via della Ricerca Scientifica, Rome, Italy
    171 rdf:type schema:Organization
     




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


    ...