A Lower Bound on the Competitive Ratio of Truthful Auctions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin , Michael Saks

ABSTRACT

We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal single price sale to at least two bidders. In this framework, we give a lower bound of 2.42 (an improvement from the bound of 2 given in [3]) on the competitive ratio of any truthful auction, one where each bidders best strategy is to declare the true maximum value an item is worth to them. This result contrasts with the 3.39 competitive ratio of the best known truthful auction [4]. More... »

PAGES

644-655

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_56

DOI

http://dx.doi.org/10.1007/978-3-540-24749-4_56

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goldberg", 
        "givenName": "Andrew V.", 
        "id": "sg:person.010430273565.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010430273565.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hartline", 
        "givenName": "Jason D.", 
        "id": "sg:person.01020477604.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01020477604.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Washington", 
          "id": "http://www.grid.ac/institutes/grid.34477.33", 
          "name": [
            "Computer Science Department, University of Washington"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karlin", 
        "givenName": "Anna R.", 
        "id": "sg:person.013176064675.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013176064675.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics\u2013Hill Center, Rutgers University, 110 Frelinghuysen Rd., 08854, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics\u2013Hill Center, Rutgers University, 110 Frelinghuysen Rd., 08854, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal single price sale to at least two bidders. In this framework, we give a lower bound of 2.42 (an improvement from the bound of 2 given in [3]) on the competitive ratio of any truthful auction, one where each bidders best strategy is to declare the true maximum value an item is worth to them. This result contrasts with the 3.39 competitive ratio of the best known truthful auction [4].", 
    "editor": [
      {
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Habib", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24749-4_56", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21236-2", 
        "978-3-540-24749-4"
      ], 
      "name": "STACS 2004", 
      "type": "Book"
    }, 
    "keywords": [
      "competitive ratio", 
      "truthful auction", 
      "auctions", 
      "competitive framework", 
      "maximum value", 
      "class", 
      "sealed-bid auction", 
      "framework", 
      "set", 
      "identical items", 
      "ratio", 
      "bidders", 
      "results", 
      "profit", 
      "values", 
      "best strategy", 
      "strategies", 
      "items", 
      "sales"
    ], 
    "name": "A Lower Bound on the Competitive Ratio of Truthful Auctions", 
    "pagination": "644-655", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047437615"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24749-4_56"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24749-4_56", 
      "https://app.dimensions.ai/details/publication/pub.1047437615"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_24.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24749-4_56"
  }
]
 

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-540-24749-4_56'

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-540-24749-4_56'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_56'

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-540-24749-4_56'


 

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

110 TRIPLES      22 PREDICATES      44 URIs      37 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24749-4_56 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N2e70415d56624ffe9657e17429346bf0
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal single price sale to at least two bidders. In this framework, we give a lower bound of 2.42 (an improvement from the bound of 2 given in [3]) on the competitive ratio of any truthful auction, one where each bidders best strategy is to declare the true maximum value an item is worth to them. This result contrasts with the 3.39 competitive ratio of the best known truthful auction [4].
7 schema:editor N97d8da3ada8f42e1bc575da22d650b9a
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N4181fd7f136f4848b4ebe72f7c274e8f
11 schema:keywords auctions
12 best strategy
13 bidders
14 class
15 competitive framework
16 competitive ratio
17 framework
18 identical items
19 items
20 maximum value
21 profit
22 ratio
23 results
24 sales
25 sealed-bid auction
26 set
27 strategies
28 truthful auction
29 values
30 schema:name A Lower Bound on the Competitive Ratio of Truthful Auctions
31 schema:pagination 644-655
32 schema:productId N28097615738447f2ac1abd5d7411dd7b
33 Nfe7b448255bf4b69b9a10e2bcaf9c4f7
34 schema:publisher N022834473bac4fd0b4272d3100f28e06
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047437615
36 https://doi.org/10.1007/978-3-540-24749-4_56
37 schema:sdDatePublished 2022-09-02T16:12
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N2b9efec8e3ef426fbc242cf3ba75471b
40 schema:url https://doi.org/10.1007/978-3-540-24749-4_56
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N022834473bac4fd0b4272d3100f28e06 schema:name Springer Nature
45 rdf:type schema:Organisation
46 N05db479055dc4a80b1e6e9770444f605 schema:familyName Habib
47 schema:givenName Michel
48 rdf:type schema:Person
49 N0639947c406b4aacbf6c1a371ed242a7 rdf:first N05db479055dc4a80b1e6e9770444f605
50 rdf:rest rdf:nil
51 N28097615738447f2ac1abd5d7411dd7b schema:name dimensions_id
52 schema:value pub.1047437615
53 rdf:type schema:PropertyValue
54 N2b9efec8e3ef426fbc242cf3ba75471b schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N2e70415d56624ffe9657e17429346bf0 rdf:first sg:person.010430273565.28
57 rdf:rest Nf0abb95f9fbf4b8ca95eaf333a9984e0
58 N4181fd7f136f4848b4ebe72f7c274e8f schema:isbn 978-3-540-21236-2
59 978-3-540-24749-4
60 schema:name STACS 2004
61 rdf:type schema:Book
62 N6d7cf652299b41eb8795ec5825d02295 rdf:first sg:person.011520224512.05
63 rdf:rest rdf:nil
64 N97d8da3ada8f42e1bc575da22d650b9a rdf:first Na955063631da41aa8ae6816129774c08
65 rdf:rest N0639947c406b4aacbf6c1a371ed242a7
66 Na955063631da41aa8ae6816129774c08 schema:familyName Diekert
67 schema:givenName Volker
68 rdf:type schema:Person
69 Nb8a06959d6fd4c5abee9c06eac89b5bb rdf:first sg:person.013176064675.47
70 rdf:rest N6d7cf652299b41eb8795ec5825d02295
71 Nf0abb95f9fbf4b8ca95eaf333a9984e0 rdf:first sg:person.01020477604.57
72 rdf:rest Nb8a06959d6fd4c5abee9c06eac89b5bb
73 Nfe7b448255bf4b69b9a10e2bcaf9c4f7 schema:name doi
74 schema:value 10.1007/978-3-540-24749-4_56
75 rdf:type schema:PropertyValue
76 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
77 schema:name Mathematical Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
80 schema:name Numerical and Computational Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.01020477604.57 schema:affiliation grid-institutes:grid.419815.0
83 schema:familyName Hartline
84 schema:givenName Jason D.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01020477604.57
86 rdf:type schema:Person
87 sg:person.010430273565.28 schema:affiliation grid-institutes:grid.419815.0
88 schema:familyName Goldberg
89 schema:givenName Andrew V.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010430273565.28
91 rdf:type schema:Person
92 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
93 schema:familyName Saks
94 schema:givenName Michael
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
96 rdf:type schema:Person
97 sg:person.013176064675.47 schema:affiliation grid-institutes:grid.34477.33
98 schema:familyName Karlin
99 schema:givenName Anna R.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013176064675.47
101 rdf:type schema:Person
102 grid-institutes:grid.34477.33 schema:alternateName Computer Science Department, University of Washington
103 schema:name Computer Science Department, University of Washington
104 rdf:type schema:Organization
105 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA
106 schema:name Microsoft Research, SVC/5, 1065 La Avenida, 94043, Mountain View, CA, USA
107 rdf:type schema:Organization
108 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics–Hill Center, Rutgers University, 110 Frelinghuysen Rd., 08854, Piscataway, NJ, USA
109 schema:name Department of Mathematics–Hill Center, Rutgers University, 110 Frelinghuysen Rd., 08854, Piscataway, NJ, USA
110 rdf:type schema:Organization
 




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


...