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


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

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

92-101

Book

TITLE

Internet and Network Economics

ISBN

978-3-540-30900-0
978-3-540-32293-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11600930_10

DOI

http://dx.doi.org/10.1007/11600930_10

DIMENSIONS

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


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": "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": "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": "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": "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": "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": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "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\u20131/e \u2243 0.632, unless P = NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.", 
    "editor": [
      {
        "familyName": "Deng", 
        "givenName": "Xiaotie", 
        "type": "Person"
      }, 
      {
        "familyName": "Ye", 
        "givenName": "Yinyu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11600930_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-30900-0", 
        "978-3-540-32293-1"
      ], 
      "name": "Internet and Network Economics", 
      "type": "Book"
    }, 
    "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", 
      "NPs", 
      "polynomial-time approximation algorithm", 
      "proof system"
    ], 
    "name": "Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions", 
    "pagination": "92-101", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037677693"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11600930_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11600930_10", 
      "https://app.dimensions.ai/details/publication/pub.1037677693"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "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/chapter/chapter_436.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11600930_10"
  }
]
 

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/11600930_10'

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/11600930_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11600930_10'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11600930_10'


 

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

118 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11600930_10 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author Naf50a6686203480288190257d9d5c890
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description 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.
7 schema:editor N2268da2505cf4330be35fe9fde423485
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nce31fcfe69aa4e93995cb43002687758
12 schema:keywords NPs
13 algorithm
14 allocation problem
15 approximation algorithm
16 auctions
17 cases
18 combinatorial auctions
19 factors
20 function
21 goods
22 inapproximability results
23 maximum social welfare
24 monotone submodular function
25 players
26 polynomial-time approximation algorithm
27 problem
28 proof system
29 reduction
30 results
31 set
32 set of goods
33 set of players
34 setting
35 social welfare
36 submodular functions
37 submodular utility functions
38 sum
39 system
40 time approximation algorithm
41 utility
42 utility function
43 welfare
44 schema:name Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions
45 schema:pagination 92-101
46 schema:productId N935d3fff11ee4cda8ea0df6a58f66ef3
47 N981712a78fdb45ac89ab75900d2210a6
48 schema:publisher Nc5de781d5d0c449098bb7e422613c143
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037677693
50 https://doi.org/10.1007/11600930_10
51 schema:sdDatePublished 2022-05-20T07:48
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N4398c14eff784b76ad3b175ff9b37aae
54 schema:url https://doi.org/10.1007/11600930_10
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N1804a9ed153e4ca8be5b436ed42ca8e1 rdf:first sg:person.014013771241.29
59 rdf:rest N324cce70243746839021a6315490d64f
60 N2268da2505cf4330be35fe9fde423485 rdf:first Nc755f9e0feda49fd8c764d7c942d76fe
61 rdf:rest N4aeb55a8afdb4cf3a3547e221fe6bc8a
62 N251038078db84cd2bf7dedd4f826384b rdf:first sg:person.010133373171.27
63 rdf:rest N1804a9ed153e4ca8be5b436ed42ca8e1
64 N324cce70243746839021a6315490d64f rdf:first sg:person.010106546671.08
65 rdf:rest rdf:nil
66 N4398c14eff784b76ad3b175ff9b37aae schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N441d908b4a3e4579ad00f3c835a67c20 schema:familyName Ye
69 schema:givenName Yinyu
70 rdf:type schema:Person
71 N4aeb55a8afdb4cf3a3547e221fe6bc8a rdf:first N441d908b4a3e4579ad00f3c835a67c20
72 rdf:rest rdf:nil
73 N935d3fff11ee4cda8ea0df6a58f66ef3 schema:name doi
74 schema:value 10.1007/11600930_10
75 rdf:type schema:PropertyValue
76 N981712a78fdb45ac89ab75900d2210a6 schema:name dimensions_id
77 schema:value pub.1037677693
78 rdf:type schema:PropertyValue
79 Naf50a6686203480288190257d9d5c890 rdf:first sg:person.015757022753.38
80 rdf:rest N251038078db84cd2bf7dedd4f826384b
81 Nc5de781d5d0c449098bb7e422613c143 schema:name Springer Nature
82 rdf:type schema:Organisation
83 Nc755f9e0feda49fd8c764d7c942d76fe schema:familyName Deng
84 schema:givenName Xiaotie
85 rdf:type schema:Person
86 Nce31fcfe69aa4e93995cb43002687758 schema:isbn 978-3-540-30900-0
87 978-3-540-32293-1
88 schema:name Internet and Network Economics
89 rdf:type schema:Book
90 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
91 schema:name Economics
92 rdf:type schema:DefinedTerm
93 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
94 schema:name Applied Economics
95 rdf:type schema:DefinedTerm
96 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.213917.f
97 schema:familyName Mehta
98 schema:givenName Aranyak
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
100 rdf:type schema:Person
101 sg:person.010133373171.27 schema:affiliation grid-institutes:grid.213917.f
102 schema:familyName Lipton
103 schema:givenName Richard J.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27
105 rdf:type schema:Person
106 sg:person.014013771241.29 schema:affiliation grid-institutes:grid.213917.f
107 schema:familyName Markakis
108 schema:givenName Evangelos
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29
110 rdf:type schema:Person
111 sg:person.015757022753.38 schema:affiliation grid-institutes:grid.213917.f
112 schema:familyName Khot
113 schema:givenName Subhash
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015757022753.38
115 rdf:type schema:Person
116 grid-institutes:grid.213917.f schema:alternateName Georgia Institute of Technology, 30332, Atlanta, GA, USA
117 schema:name Georgia Institute of Technology, 30332, Atlanta, GA, USA
118 rdf:type schema:Organization
 




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


...