Coalition Structure Formation Using Anytime Dynamic Programming View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-08-10

AUTHORS

Narayan Changder , Animesh Dutta , Aditya K. Ghose

ABSTRACT

The optimal coalition structure generation is an important problem in multi-agent systems that remains difficult to solve. This paper presents a novel anytime dynamic programming algorithm to compute the optimal coalition structure. The proposed algorithm can be interrupted, and upon interruption, uses heuristic to select the largest valued coalition from each subproblem of size x and picks the rest of the unassigned agent from other subproblem of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n- x$$\end{document}, where n is the total number of agents. We compared the performance of our algorithm against the only existing proposal in the literature for the optimal coalition structure problem that uses anytime dynamic programming using 9 distinct datasets (each corresponding to a different distribution). The empirical evaluation shows that our algorithm always generates better or, at least, as good a solution as the previous anytime dynamic programming algorithm. More... »

PAGES

295-309

Book

TITLE

PRIMA 2016: Princiles and Practice of Multi-Agent Systems

ISBN

978-3-319-44831-2
978-3-319-44832-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-44832-9_18

DOI

http://dx.doi.org/10.1007/978-3-319-44832-9_18

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Institute of Technology, Durgapur, West Bengal, India", 
          "id": "http://www.grid.ac/institutes/grid.444419.8", 
          "name": [
            "National Institute of Technology, Durgapur, West Bengal, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Changder", 
        "givenName": "Narayan", 
        "id": "sg:person.010513662020.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010513662020.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Institute of Technology, Durgapur, West Bengal, India", 
          "id": "http://www.grid.ac/institutes/grid.444419.8", 
          "name": [
            "National Institute of Technology, Durgapur, West Bengal, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dutta", 
        "givenName": "Animesh", 
        "id": "sg:person.07562500567.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07562500567.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Wollongong, 2522, Wollongong, NSW, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1007.6", 
          "name": [
            "University of Wollongong, 2522, Wollongong, NSW, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ghose", 
        "givenName": "Aditya K.", 
        "id": "sg:person.015573517335.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015573517335.70"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-08-10", 
    "datePublishedReg": "2016-08-10", 
    "description": "The optimal coalition structure generation is an important problem in multi-agent systems that remains difficult to solve. This paper presents a novel anytime dynamic programming algorithm to compute the optimal coalition structure. The proposed algorithm can be interrupted, and upon interruption, uses heuristic to select the largest valued coalition from each subproblem of size x and picks the rest of the unassigned agent from other subproblem of size \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$n- x$$\\end{document}, where n is the total number of agents. We compared the performance of our algorithm against the only existing proposal in the literature for the optimal coalition structure problem that uses anytime dynamic programming using 9 distinct datasets (each corresponding to a different distribution). The empirical evaluation shows that our algorithm always generates better or, at least, as good a solution as the previous anytime dynamic programming algorithm.", 
    "editor": [
      {
        "familyName": "Baldoni", 
        "givenName": "Matteo", 
        "type": "Person"
      }, 
      {
        "familyName": "Chopra", 
        "givenName": "Amit K.", 
        "type": "Person"
      }, 
      {
        "familyName": "Son", 
        "givenName": "Tran Cao", 
        "type": "Person"
      }, 
      {
        "familyName": "Hirayama", 
        "givenName": "Katsutoshi", 
        "type": "Person"
      }, 
      {
        "familyName": "Torroni", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-44832-9_18", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-44831-2", 
        "978-3-319-44832-9"
      ], 
      "name": "PRIMA 2016: Princiles and Practice of Multi-Agent Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "dynamic programming algorithm", 
      "Optimal Coalition Structure Generation", 
      "programming algorithm", 
      "Coalition Structure Generation", 
      "multi-agent systems", 
      "dynamic programming", 
      "optimal coalition structure", 
      "coalition structure formation", 
      "empirical evaluation", 
      "distinct datasets", 
      "algorithm", 
      "important problem", 
      "structure generation", 
      "coalition structure", 
      "subproblems", 
      "programming", 
      "structure problem", 
      "dataset", 
      "proposal", 
      "performance", 
      "system", 
      "solution", 
      "generation", 
      "coalition", 
      "evaluation", 
      "number", 
      "agents", 
      "interruption", 
      "total number", 
      "size x", 
      "literature", 
      "structure", 
      "size", 
      "rest", 
      "structure formation", 
      "formation", 
      "problem", 
      "paper"
    ], 
    "name": "Coalition Structure Formation Using Anytime Dynamic Programming", 
    "pagination": "295-309", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022744675"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-44832-9_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-44832-9_18", 
      "https://app.dimensions.ai/details/publication/pub.1022744675"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_401.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-44832-9_18"
  }
]
 

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-319-44832-9_18'

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-319-44832-9_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44832-9_18'

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-319-44832-9_18'


 

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

134 TRIPLES      22 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-44832-9_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf2896307adf5419ea7a05155ca28eab8
4 schema:datePublished 2016-08-10
5 schema:datePublishedReg 2016-08-10
6 schema:description The optimal coalition structure generation is an important problem in multi-agent systems that remains difficult to solve. This paper presents a novel anytime dynamic programming algorithm to compute the optimal coalition structure. The proposed algorithm can be interrupted, and upon interruption, uses heuristic to select the largest valued coalition from each subproblem of size x and picks the rest of the unassigned agent from other subproblem of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n- x$$\end{document}, where n is the total number of agents. We compared the performance of our algorithm against the only existing proposal in the literature for the optimal coalition structure problem that uses anytime dynamic programming using 9 distinct datasets (each corresponding to a different distribution). The empirical evaluation shows that our algorithm always generates better or, at least, as good a solution as the previous anytime dynamic programming algorithm.
7 schema:editor N6c3ce70cf6f54c8f83636bd411d8fa25
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N8ac4bbc353234b9ca5058adc069620f6
11 schema:keywords Coalition Structure Generation
12 Optimal Coalition Structure Generation
13 agents
14 algorithm
15 coalition
16 coalition structure
17 coalition structure formation
18 dataset
19 distinct datasets
20 dynamic programming
21 dynamic programming algorithm
22 empirical evaluation
23 evaluation
24 formation
25 generation
26 important problem
27 interruption
28 literature
29 multi-agent systems
30 number
31 optimal coalition structure
32 paper
33 performance
34 problem
35 programming
36 programming algorithm
37 proposal
38 rest
39 size
40 size x
41 solution
42 structure
43 structure formation
44 structure generation
45 structure problem
46 subproblems
47 system
48 total number
49 schema:name Coalition Structure Formation Using Anytime Dynamic Programming
50 schema:pagination 295-309
51 schema:productId N8d631d26d71f49fa8b19e47613e21f81
52 Nee897aca30854369a0b12db1e2f1c795
53 schema:publisher Ne42f180665a240d2bb37573d79c16db5
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022744675
55 https://doi.org/10.1007/978-3-319-44832-9_18
56 schema:sdDatePublished 2022-11-24T21:17
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N530c003dc5b645f3a778391c312895ab
59 schema:url https://doi.org/10.1007/978-3-319-44832-9_18
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N043406b9d61e4a4b847720af4638ae65 schema:familyName Hirayama
64 schema:givenName Katsutoshi
65 rdf:type schema:Person
66 N2918fb0b76c34d74967df9caf4dce5b7 schema:familyName Baldoni
67 schema:givenName Matteo
68 rdf:type schema:Person
69 N530c003dc5b645f3a778391c312895ab schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N6c3ce70cf6f54c8f83636bd411d8fa25 rdf:first N2918fb0b76c34d74967df9caf4dce5b7
72 rdf:rest N7b764a42aba24dec8fd892269642ca81
73 N7b764a42aba24dec8fd892269642ca81 rdf:first Ne503f05b2315412ab436e903c2615cab
74 rdf:rest Nc910d97c49c543c5bbb72888e4f32d71
75 N7dc3ec6d3a5248088cafb35e64790aa0 rdf:first sg:person.07562500567.79
76 rdf:rest Ndd1b942f44454dc890c92d616578d481
77 N8ac4bbc353234b9ca5058adc069620f6 schema:isbn 978-3-319-44831-2
78 978-3-319-44832-9
79 schema:name PRIMA 2016: Princiles and Practice of Multi-Agent Systems
80 rdf:type schema:Book
81 N8d631d26d71f49fa8b19e47613e21f81 schema:name dimensions_id
82 schema:value pub.1022744675
83 rdf:type schema:PropertyValue
84 N90ec170f552f4f4e86f49078fa4c84f6 schema:familyName Son
85 schema:givenName Tran Cao
86 rdf:type schema:Person
87 Nc6026cbdf44f4fe59bbfc63d66af8a9c rdf:first N043406b9d61e4a4b847720af4638ae65
88 rdf:rest Ndea24d538dd1478a9280d4797169cac9
89 Nc910d97c49c543c5bbb72888e4f32d71 rdf:first N90ec170f552f4f4e86f49078fa4c84f6
90 rdf:rest Nc6026cbdf44f4fe59bbfc63d66af8a9c
91 Nd16f30df476a4952b8f6e76541305933 schema:familyName Torroni
92 schema:givenName Paolo
93 rdf:type schema:Person
94 Ndd1b942f44454dc890c92d616578d481 rdf:first sg:person.015573517335.70
95 rdf:rest rdf:nil
96 Ndea24d538dd1478a9280d4797169cac9 rdf:first Nd16f30df476a4952b8f6e76541305933
97 rdf:rest rdf:nil
98 Ne42f180665a240d2bb37573d79c16db5 schema:name Springer Nature
99 rdf:type schema:Organisation
100 Ne503f05b2315412ab436e903c2615cab schema:familyName Chopra
101 schema:givenName Amit K.
102 rdf:type schema:Person
103 Nee897aca30854369a0b12db1e2f1c795 schema:name doi
104 schema:value 10.1007/978-3-319-44832-9_18
105 rdf:type schema:PropertyValue
106 Nf2896307adf5419ea7a05155ca28eab8 rdf:first sg:person.010513662020.28
107 rdf:rest N7dc3ec6d3a5248088cafb35e64790aa0
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
112 schema:name Computation Theory and Mathematics
113 rdf:type schema:DefinedTerm
114 sg:person.010513662020.28 schema:affiliation grid-institutes:grid.444419.8
115 schema:familyName Changder
116 schema:givenName Narayan
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010513662020.28
118 rdf:type schema:Person
119 sg:person.015573517335.70 schema:affiliation grid-institutes:grid.1007.6
120 schema:familyName Ghose
121 schema:givenName Aditya K.
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015573517335.70
123 rdf:type schema:Person
124 sg:person.07562500567.79 schema:affiliation grid-institutes:grid.444419.8
125 schema:familyName Dutta
126 schema:givenName Animesh
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07562500567.79
128 rdf:type schema:Person
129 grid-institutes:grid.1007.6 schema:alternateName University of Wollongong, 2522, Wollongong, NSW, Australia
130 schema:name University of Wollongong, 2522, Wollongong, NSW, Australia
131 rdf:type schema:Organization
132 grid-institutes:grid.444419.8 schema:alternateName National Institute of Technology, Durgapur, West Bengal, India
133 schema:name National Institute of Technology, Durgapur, West Bengal, India
134 rdf:type schema:Organization
 




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


...