Opportunity Cost Algorithms for Combinatorial Auctions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002

AUTHORS

Karhan Akcoglu , James Aspnes , Bhaskar DasGupta , Ming-Yang Kao

ABSTRACT

Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids. Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other. The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs. The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids. Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted. More... »

PAGES

455-479

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4757-3613-7_23

DOI

http://dx.doi.org/10.1007/978-1-4757-3613-7_23

DIMENSIONS

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


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": "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.47100.32", 
          "name": [
            "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Akcoglu", 
        "givenName": "Karhan", 
        "id": "sg:person.014075252501.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014075252501.66"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.47100.32", 
          "name": [
            "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aspnes", 
        "givenName": "James", 
        "id": "sg:person.07603052541.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07603052541.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.16753.36", 
          "name": [
            "Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "id": "sg:person.011536202643.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002", 
    "datePublishedReg": "2002-01-01", 
    "description": "Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids. Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other. The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs. The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids. Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.", 
    "editor": [
      {
        "familyName": "Kontoghiorghes", 
        "givenName": "Erricos John", 
        "type": "Person"
      }, 
      {
        "familyName": "Rustem", 
        "givenName": "Berc", 
        "type": "Person"
      }, 
      {
        "familyName": "Siokos", 
        "givenName": "Stavros", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4757-3613-7_23", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-1-4419-5230-1", 
        "978-1-4757-3613-7"
      ], 
      "name": "Computational Methods in Decision-Making, Economics and Finance", 
      "type": "Book"
    }, 
    "keywords": [
      "combinatorial auctions", 
      "approximation ratio", 
      "general algorithm", 
      "additional constraints", 
      "particular bidder", 
      "small constant", 
      "graph", 
      "node subset", 
      "interesting family", 
      "algorithm", 
      "structural properties", 
      "constraints", 
      "budget constraints", 
      "object graph", 
      "problem", 
      "extension", 
      "auctions", 
      "set", 
      "auctioneer", 
      "objects", 
      "bidders", 
      "subset", 
      "properties", 
      "constants", 
      "efficient processing", 
      "bid", 
      "prices", 
      "available goods", 
      "cost", 
      "size", 
      "processing", 
      "time", 
      "ratio", 
      "family", 
      "goods", 
      "opportunity cost", 
      "opportunities", 
      "conflict"
    ], 
    "name": "Opportunity Cost Algorithms for Combinatorial Auctions", 
    "pagination": "455-479", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017395482"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4757-3613-7_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4757-3613-7_23", 
      "https://app.dimensions.ai/details/publication/pub.1017395482"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_357.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-1-4757-3613-7_23"
  }
]
 

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-1-4757-3613-7_23'

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-1-4757-3613-7_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3613-7_23'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3613-7_23'


 

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

134 TRIPLES      22 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4757-3613-7_23 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N101190f8409f4a2d980ad7fe5b298343
4 schema:datePublished 2002
5 schema:datePublishedReg 2002-01-01
6 schema:description Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids. Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other. The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs. The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids. Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.
7 schema:editor Nf9e43e921e794ba484920d50d367835c
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N72049c2eba614e17851356f2a5fbfcbb
11 schema:keywords additional constraints
12 algorithm
13 approximation ratio
14 auctioneer
15 auctions
16 available goods
17 bid
18 bidders
19 budget constraints
20 combinatorial auctions
21 conflict
22 constants
23 constraints
24 cost
25 efficient processing
26 extension
27 family
28 general algorithm
29 goods
30 graph
31 interesting family
32 node subset
33 object graph
34 objects
35 opportunities
36 opportunity cost
37 particular bidder
38 prices
39 problem
40 processing
41 properties
42 ratio
43 set
44 size
45 small constant
46 structural properties
47 subset
48 time
49 schema:name Opportunity Cost Algorithms for Combinatorial Auctions
50 schema:pagination 455-479
51 schema:productId N6cc5c4fcb4644fbbb08cf6abea5534c1
52 Nf7410a40631b408c8b256737164cc995
53 schema:publisher N26510fd6cfc6494ca0424a6f53fcaf76
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017395482
55 https://doi.org/10.1007/978-1-4757-3613-7_23
56 schema:sdDatePublished 2022-12-01T06:51
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N47336d6b06e142b68af944a7510efcb7
59 schema:url https://doi.org/10.1007/978-1-4757-3613-7_23
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N08203dbfaabf4f5c88648e60ee90befc schema:familyName Kontoghiorghes
64 schema:givenName Erricos John
65 rdf:type schema:Person
66 N101190f8409f4a2d980ad7fe5b298343 rdf:first sg:person.014075252501.66
67 rdf:rest Nf9a2ea804f1b4fad9e06d18833fcccff
68 N26510fd6cfc6494ca0424a6f53fcaf76 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N371ef4b3466048b797b926efdee7602a rdf:first Nf77e98ac46bc47d2ab98458a09a4521c
71 rdf:rest Nb287fd72fbb147f29e58239fb75b0797
72 N47336d6b06e142b68af944a7510efcb7 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N61a8591d71864c27b045ce0f7e5a898e rdf:first sg:person.011536202643.55
75 rdf:rest rdf:nil
76 N6cc5c4fcb4644fbbb08cf6abea5534c1 schema:name dimensions_id
77 schema:value pub.1017395482
78 rdf:type schema:PropertyValue
79 N72049c2eba614e17851356f2a5fbfcbb schema:isbn 978-1-4419-5230-1
80 978-1-4757-3613-7
81 schema:name Computational Methods in Decision-Making, Economics and Finance
82 rdf:type schema:Book
83 N7f25b61740be4914a7040e4035664438 rdf:first sg:person.0763403270.10
84 rdf:rest N61a8591d71864c27b045ce0f7e5a898e
85 Nb287fd72fbb147f29e58239fb75b0797 rdf:first Nc498360c48584d9bbda169a4183b4ab7
86 rdf:rest rdf:nil
87 Nc498360c48584d9bbda169a4183b4ab7 schema:familyName Siokos
88 schema:givenName Stavros
89 rdf:type schema:Person
90 Nf7410a40631b408c8b256737164cc995 schema:name doi
91 schema:value 10.1007/978-1-4757-3613-7_23
92 rdf:type schema:PropertyValue
93 Nf77e98ac46bc47d2ab98458a09a4521c schema:familyName Rustem
94 schema:givenName Berc
95 rdf:type schema:Person
96 Nf9a2ea804f1b4fad9e06d18833fcccff rdf:first sg:person.07603052541.00
97 rdf:rest N7f25b61740be4914a7040e4035664438
98 Nf9e43e921e794ba484920d50d367835c rdf:first N08203dbfaabf4f5c88648e60ee90befc
99 rdf:rest N371ef4b3466048b797b926efdee7602a
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.011536202643.55 schema:affiliation grid-institutes:grid.16753.36
107 schema:familyName Kao
108 schema:givenName Ming-Yang
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55
110 rdf:type schema:Person
111 sg:person.014075252501.66 schema:affiliation grid-institutes:grid.47100.32
112 schema:familyName Akcoglu
113 schema:givenName Karhan
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014075252501.66
115 rdf:type schema:Person
116 sg:person.07603052541.00 schema:affiliation grid-institutes:grid.47100.32
117 schema:familyName Aspnes
118 schema:givenName James
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07603052541.00
120 rdf:type schema:Person
121 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
122 schema:familyName DasGupta
123 schema:givenName Bhaskar
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
125 rdf:type schema:Person
126 grid-institutes:grid.16753.36 schema:alternateName Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA
127 schema:name Department of Computer Science, Northwestern University, 60201, Evanston, IL, USA
128 rdf:type schema:Organization
129 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
130 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.47100.32 schema:alternateName Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA
133 schema:name Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA
134 rdf:type schema:Organization
 




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


...