Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-10-13

AUTHORS

Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta

ABSTRACT

We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1−1/e≃0.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING. More... »

PAGES

3-18

References to SciGraph publications

  • 2005. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions in INTERNET AND NETWORK ECONOMICS
  • 1994-06. The hardness of approximation: Gap location in COMPUTATIONAL COMPLEXITY
  • 2004. Auctions with Budget Constraints in ALGORITHM THEORY - SWAT 2004
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7

    DOI

    http://dx.doi.org/10.1007/s00453-007-9105-7

    DIMENSIONS

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


    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/14", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Economics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1402", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Economics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Georgia Institute of Technology, 30332, Atlanta, GA, USA", 
              "id": "http://www.grid.ac/institutes/grid.213917.f", 
              "name": [
                "Georgia Institute of Technology, 30332, Atlanta, GA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Khot", 
            "givenName": "Subhash", 
            "id": "sg:person.015757022753.38", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015757022753.38"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Telcordia Research, 07960, Morristown, NJ, USA", 
              "id": "http://www.grid.ac/institutes/None", 
              "name": [
                "Georgia Institute of Technology, 30332, Atlanta, GA, USA", 
                "Telcordia Research, 07960, Morristown, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lipton", 
            "givenName": "Richard J.", 
            "id": "sg:person.010133373171.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Dept. of Computer Science, University of Toronto, 10 King\u2019s College Road, M5S3G4, Toronto, ON, Canada", 
              "id": "http://www.grid.ac/institutes/grid.17063.33", 
              "name": [
                "Dept. of Computer Science, University of Toronto, 10 King\u2019s College Road, M5S3G4, Toronto, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Markakis", 
            "givenName": "Evangelos", 
            "id": "sg:person.014013771241.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.481551.c", 
              "name": [
                "IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mehta", 
            "givenName": "Aranyak", 
            "id": "sg:person.010106546671.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01202286", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026973980", 
              "https://doi.org/10.1007/bf01202286"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27810-8_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019890075", 
              "https://doi.org/10.1007/978-3-540-27810-8_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11600930_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037677693", 
              "https://doi.org/10.1007/11600930_10"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-10-13", 
        "datePublishedReg": "2007-10-13", 
        "description": "Abstract\nWe consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1\u22121/e\u22430.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-007-9105-7", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "52"
          }
        ], 
        "keywords": [
          "combinatorial auctions", 
          "maximum social welfare", 
          "set of goods", 
          "set of players", 
          "submodular utility functions", 
          "social welfare", 
          "utility function", 
          "auctions", 
          "allocation problem", 
          "monotone submodular function", 
          "players", 
          "welfare", 
          "goods", 
          "utility", 
          "submodular functions", 
          "set", 
          "inapproximability results", 
          "results", 
          "sum", 
          "setting", 
          "factors", 
          "problem", 
          "cases", 
          "reduction", 
          "function", 
          "system", 
          "approximation algorithm", 
          "time approximation algorithm", 
          "algorithm", 
          "polynomial-time approximation algorithm", 
          "NPs", 
          "proof system"
        ], 
        "name": "Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions", 
        "pagination": "3-18", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1027463644"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-007-9105-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-007-9105-7", 
          "https://app.dimensions.ai/details/publication/pub.1027463644"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:24", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_432.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-007-9105-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-007-9105-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-007-9105-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9105-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-007-9105-7'


     

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

    133 TRIPLES      22 PREDICATES      60 URIs      49 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-007-9105-7 schema:about anzsrc-for:14
    2 anzsrc-for:1402
    3 schema:author Nb2534cd8c1b64893b4824f37b034f94d
    4 schema:citation sg:pub.10.1007/11600930_10
    5 sg:pub.10.1007/978-3-540-27810-8_4
    6 sg:pub.10.1007/bf01202286
    7 schema:datePublished 2007-10-13
    8 schema:datePublishedReg 2007-10-13
    9 schema:description Abstract We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1−1/e≃0.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf Nb9ba09c116cd45d2b8d05d12bb808f0c
    14 Nf31d8621501242399197f562857cd508
    15 sg:journal.1047644
    16 schema:keywords NPs
    17 algorithm
    18 allocation problem
    19 approximation algorithm
    20 auctions
    21 cases
    22 combinatorial auctions
    23 factors
    24 function
    25 goods
    26 inapproximability results
    27 maximum social welfare
    28 monotone submodular function
    29 players
    30 polynomial-time approximation algorithm
    31 problem
    32 proof system
    33 reduction
    34 results
    35 set
    36 set of goods
    37 set of players
    38 setting
    39 social welfare
    40 submodular functions
    41 submodular utility functions
    42 sum
    43 system
    44 time approximation algorithm
    45 utility
    46 utility function
    47 welfare
    48 schema:name Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions
    49 schema:pagination 3-18
    50 schema:productId N011b80f912ea4ede963050cfa132ac2f
    51 N1da5defb8678453297401aaed362fa0a
    52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027463644
    53 https://doi.org/10.1007/s00453-007-9105-7
    54 schema:sdDatePublished 2022-05-20T07:24
    55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    56 schema:sdPublisher Ndbbad57412d94386aecef9f7b5a53764
    57 schema:url https://doi.org/10.1007/s00453-007-9105-7
    58 sgo:license sg:explorer/license/
    59 sgo:sdDataset articles
    60 rdf:type schema:ScholarlyArticle
    61 N011b80f912ea4ede963050cfa132ac2f schema:name dimensions_id
    62 schema:value pub.1027463644
    63 rdf:type schema:PropertyValue
    64 N1da5defb8678453297401aaed362fa0a schema:name doi
    65 schema:value 10.1007/s00453-007-9105-7
    66 rdf:type schema:PropertyValue
    67 N22d55eaa05734f819185dbae87de5af5 rdf:first sg:person.010133373171.27
    68 rdf:rest N670bc8d39c694830863bf64768399bf8
    69 N670bc8d39c694830863bf64768399bf8 rdf:first sg:person.014013771241.29
    70 rdf:rest Ndd93a5fcab5345909dfa02a47096dbca
    71 Nb2534cd8c1b64893b4824f37b034f94d rdf:first sg:person.015757022753.38
    72 rdf:rest N22d55eaa05734f819185dbae87de5af5
    73 Nb9ba09c116cd45d2b8d05d12bb808f0c schema:volumeNumber 52
    74 rdf:type schema:PublicationVolume
    75 Ndbbad57412d94386aecef9f7b5a53764 schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 Ndd93a5fcab5345909dfa02a47096dbca rdf:first sg:person.010106546671.08
    78 rdf:rest rdf:nil
    79 Nf31d8621501242399197f562857cd508 schema:issueNumber 1
    80 rdf:type schema:PublicationIssue
    81 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Economics
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Applied Economics
    86 rdf:type schema:DefinedTerm
    87 sg:journal.1047644 schema:issn 0178-4617
    88 1432-0541
    89 schema:name Algorithmica
    90 schema:publisher Springer Nature
    91 rdf:type schema:Periodical
    92 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.481551.c
    93 schema:familyName Mehta
    94 schema:givenName Aranyak
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
    96 rdf:type schema:Person
    97 sg:person.010133373171.27 schema:affiliation grid-institutes:None
    98 schema:familyName Lipton
    99 schema:givenName Richard J.
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27
    101 rdf:type schema:Person
    102 sg:person.014013771241.29 schema:affiliation grid-institutes:grid.17063.33
    103 schema:familyName Markakis
    104 schema:givenName Evangelos
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29
    106 rdf:type schema:Person
    107 sg:person.015757022753.38 schema:affiliation grid-institutes:grid.213917.f
    108 schema:familyName Khot
    109 schema:givenName Subhash
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015757022753.38
    111 rdf:type schema:Person
    112 sg:pub.10.1007/11600930_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037677693
    113 https://doi.org/10.1007/11600930_10
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-540-27810-8_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019890075
    116 https://doi.org/10.1007/978-3-540-27810-8_4
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/bf01202286 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026973980
    119 https://doi.org/10.1007/bf01202286
    120 rdf:type schema:CreativeWork
    121 grid-institutes:None schema:alternateName Telcordia Research, 07960, Morristown, NJ, USA
    122 schema:name Georgia Institute of Technology, 30332, Atlanta, GA, USA
    123 Telcordia Research, 07960, Morristown, NJ, USA
    124 rdf:type schema:Organization
    125 grid-institutes:grid.17063.33 schema:alternateName Dept. of Computer Science, University of Toronto, 10 King’s College Road, M5S3G4, Toronto, ON, Canada
    126 schema:name Dept. of Computer Science, University of Toronto, 10 King’s College Road, M5S3G4, Toronto, ON, Canada
    127 rdf:type schema:Organization
    128 grid-institutes:grid.213917.f schema:alternateName Georgia Institute of Technology, 30332, Atlanta, GA, USA
    129 schema:name Georgia Institute of Technology, 30332, Atlanta, GA, USA
    130 rdf:type schema:Organization
    131 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA
    132 schema:name IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA
    133 rdf:type schema:Organization
     




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


    ...