Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Yuyu Chen , Ming-Yang Kao , Hsueh-I. Lu

ABSTRACT

In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of multipleobject auctions where a bidding algorithm consists of an initial bid sequence and an algorithm for randomly permuting the sequence. We are especially concerned with situations where some bidders know the bidding algorithms of others. For the case of only two bidders, we give an optimal bidding algorithm for the disadvantaged bidder. Our result generalizes previous work by allowing the bidders to have unequal budgets. One might naturally anticipate that the optimal expected numbers of objects won by the bidders would be proportional to their budgets. Surprisingly, this is not true. Our new algorithm runs in optimal O(n) time in a straightforward manner. The case with more than two bidders is open. More... »

PAGES

84-95

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-40996-3_8

DOI

http://dx.doi.org/10.1007/3-540-40996-3_8

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Yale University, 06520, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.47100.32", 
          "name": [
            "Department of Computer Science, Yale University, 06520, New Haven, CT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Yuyu", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Yale University, 06520, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.47100.32", 
          "name": [
            "Department of Computer Science, Yale University, 06520, New Haven, CT, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.506928.0", 
          "name": [
            "Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I.", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of multipleobject auctions where a bidding algorithm consists of an initial bid sequence and an algorithm for randomly permuting the sequence. We are especially concerned with situations where some bidders know the bidding algorithms of others. For the case of only two bidders, we give an optimal bidding algorithm for the disadvantaged bidder. Our result generalizes previous work by allowing the bidders to have unequal budgets. One might naturally anticipate that the optimal expected numbers of objects won by the bidders would be proportional to their budgets. Surprisingly, this is not true. Our new algorithm runs in optimal O(n) time in a straightforward manner. The case with more than two bidders is open.", 
    "editor": [
      {
        "familyName": "Goos", 
        "givenName": "Gerhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Hartmanis", 
        "givenName": "Juris", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "D. T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Teng", 
        "givenName": "Shang-Hua", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-40996-3_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41255-7", 
        "978-3-540-40996-0"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "multiple object auctions", 
      "optimal bidding algorithm", 
      "bidding algorithm", 
      "special class", 
      "number of objects", 
      "straightforward manner", 
      "algorithm runs", 
      "algorithm", 
      "previous work", 
      "auctions", 
      "objects", 
      "class", 
      "new algorithm runs", 
      "bidders", 
      "cases", 
      "sequence", 
      "number", 
      "budget", 
      "work", 
      "results", 
      "run", 
      "situation", 
      "time", 
      "manner", 
      "paper"
    ], 
    "name": "Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets", 
    "pagination": "84-95", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051769570"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-40996-3_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-40996-3_8", 
      "https://app.dimensions.ai/details/publication/pub.1051769570"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_7.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-40996-3_8"
  }
]
 

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/3-540-40996-3_8'

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/3-540-40996-3_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-40996-3_8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-40996-3_8'


 

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

121 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-40996-3_8 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N35ca84fdbe4541c1b8c69b995c7c793b
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of multipleobject auctions where a bidding algorithm consists of an initial bid sequence and an algorithm for randomly permuting the sequence. We are especially concerned with situations where some bidders know the bidding algorithms of others. For the case of only two bidders, we give an optimal bidding algorithm for the disadvantaged bidder. Our result generalizes previous work by allowing the bidders to have unequal budgets. One might naturally anticipate that the optimal expected numbers of objects won by the bidders would be proportional to their budgets. Surprisingly, this is not true. Our new algorithm runs in optimal O(n) time in a straightforward manner. The case with more than two bidders is open.
7 schema:editor Nbfc98109f7854e8a841df5f6e5c60d35
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na51e1391651e465388bbf0be346fcf95
12 schema:keywords algorithm
13 algorithm runs
14 auctions
15 bidders
16 bidding algorithm
17 budget
18 cases
19 class
20 manner
21 multiple object auctions
22 new algorithm runs
23 number
24 number of objects
25 objects
26 optimal bidding algorithm
27 paper
28 previous work
29 results
30 run
31 sequence
32 situation
33 special class
34 straightforward manner
35 time
36 work
37 schema:name Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets
38 schema:pagination 84-95
39 schema:productId Nd2d6a420b6db4e1889c6811dd1da749a
40 Ne8a65233ecc448e5a1f58d78ae5f4bf9
41 schema:publisher N075ade452b744e73827caf6000d031f5
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051769570
43 https://doi.org/10.1007/3-540-40996-3_8
44 schema:sdDatePublished 2022-05-10T10:54
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N2aefe95c32014125bdcc316b08edbcb4
47 schema:url https://doi.org/10.1007/3-540-40996-3_8
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N0609866872bf42cf8b180291f0bfb96e rdf:first sg:person.011536202643.55
52 rdf:rest N23a2162f19614b3a8a2558d84c755d00
53 N075ade452b744e73827caf6000d031f5 schema:name Springer Nature
54 rdf:type schema:Organisation
55 N0e4eeb7ff5444a07884428fdca1c4546 schema:familyName Lee
56 schema:givenName D. T.
57 rdf:type schema:Person
58 N23a2162f19614b3a8a2558d84c755d00 rdf:first sg:person.013345515575.46
59 rdf:rest rdf:nil
60 N261b89ce3e7a49de8e63bd987ed5cdc8 schema:familyName Hartmanis
61 schema:givenName Juris
62 rdf:type schema:Person
63 N2aefe95c32014125bdcc316b08edbcb4 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N2d60ffa49b674a6cb6930357495da9f7 rdf:first N3d74d2e0c2094813a57858809299812a
66 rdf:rest rdf:nil
67 N35ca84fdbe4541c1b8c69b995c7c793b rdf:first Ne9d14b8d830e420c843704dae0bf61ea
68 rdf:rest N0609866872bf42cf8b180291f0bfb96e
69 N3d74d2e0c2094813a57858809299812a schema:familyName Teng
70 schema:givenName Shang-Hua
71 rdf:type schema:Person
72 N6305118251fb4ccaa07e053ad20e67e2 schema:familyName van Leeuwen
73 schema:givenName Jan
74 rdf:type schema:Person
75 Na51e1391651e465388bbf0be346fcf95 schema:isbn 978-3-540-40996-0
76 978-3-540-41255-7
77 schema:name Algorithms and Computation
78 rdf:type schema:Book
79 Nbcb6f8f266c84d01a3ea26613221ab7e rdf:first N0e4eeb7ff5444a07884428fdca1c4546
80 rdf:rest N2d60ffa49b674a6cb6930357495da9f7
81 Nbfc98109f7854e8a841df5f6e5c60d35 rdf:first Nf43d706edede4e109d5bab5272a577fa
82 rdf:rest Nd0713867c69c48a093580aa967879e3b
83 Nd0713867c69c48a093580aa967879e3b rdf:first N261b89ce3e7a49de8e63bd987ed5cdc8
84 rdf:rest Ne09de105a9b949158c286e9521a936d0
85 Nd2d6a420b6db4e1889c6811dd1da749a schema:name doi
86 schema:value 10.1007/3-540-40996-3_8
87 rdf:type schema:PropertyValue
88 Ne09de105a9b949158c286e9521a936d0 rdf:first N6305118251fb4ccaa07e053ad20e67e2
89 rdf:rest Nbcb6f8f266c84d01a3ea26613221ab7e
90 Ne8a65233ecc448e5a1f58d78ae5f4bf9 schema:name dimensions_id
91 schema:value pub.1051769570
92 rdf:type schema:PropertyValue
93 Ne9d14b8d830e420c843704dae0bf61ea schema:affiliation grid-institutes:grid.47100.32
94 schema:familyName Chen
95 schema:givenName Yuyu
96 rdf:type schema:Person
97 Nf43d706edede4e109d5bab5272a577fa schema:familyName Goos
98 schema:givenName Gerhard
99 rdf:type schema:Person
100 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
101 schema:name Mathematical Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
104 schema:name Applied Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.011536202643.55 schema:affiliation grid-institutes:grid.47100.32
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.013345515575.46 schema:affiliation grid-institutes:grid.506928.0
112 schema:familyName Lu
113 schema:givenName Hsueh-I.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
115 rdf:type schema:Person
116 grid-institutes:grid.47100.32 schema:alternateName Department of Computer Science, Yale University, 06520, New Haven, CT, USA
117 schema:name Department of Computer Science, Yale University, 06520, New Haven, CT, USA
118 rdf:type schema:Organization
119 grid-institutes:grid.506928.0 schema:alternateName Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.
120 schema:name Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.
121 rdf:type schema:Organization
 




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


...