Ontology type: schema:Chapter Open Access: True
2000
AUTHORSYuyu Chen , Ming-Yang Kao , Hsueh-I. Lu
ABSTRACTIn 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... »
PAGES84-95
Algorithms and Computation
ISBN
978-3-540-41255-7
978-3-540-40996-0
http://scigraph.springernature.com/pub.10.1007/3-540-40996-3_8
DOIhttp://dx.doi.org/10.1007/3-540-40996-3_8
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1051769570
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
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