View in EDS

Prior-free multi-unit auctions with ordered bidders.

Saved in:
Bibliographic Details
Title: Prior-free multi-unit auctions with ordered bidders.
Authors: Bhattacharya, Sayan1 (AUTHOR) S.Bhattacharya@warwick.ac.uk, Koutsoupias, Elias1,2 (AUTHOR) elias@cs.ox.ac.uk, Kulkarni, Janardhan1,3 (AUTHOR) Jakul@microsoft.com, Leonardi, Stefano1,4 (AUTHOR) leonardi@dis.uniroma1.it, Roughgarden, Tim1,5 (AUTHOR) tr@cs.columbia.edu, Xu, Xiaoming6 (AUTHOR) xiaomingnatexu@gmail.com
Source: Theoretical Computer Science. Dec2020, Vol. 846, p160-171. 12p.
Subjects: Auctions, Bidders, Linear orderings
Abstract: Prior-free auctions are robust auctions that assume no distribution over bidders' valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders. Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden (STOC'08) to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F (2) , so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders' valuations, such an auction still provides a quantifiable input-by-input performance guarantee. In this paper, we design a simple O (1) -competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O (1) -competitive prior-free auction to multi-unit settings with limited supply. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 146711816
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Prior-free multi-unit auctions with ordered bidders.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bhattacharya%2C+Sayan%22">Bhattacharya, Sayan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> S.Bhattacharya@warwick.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Koutsoupias%2C+Elias%22">Koutsoupias, Elias</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> elias@cs.ox.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Kulkarni%2C+Janardhan%22">Kulkarni, Janardhan</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> Jakul@microsoft.com</i><br /><searchLink fieldCode="AR" term="%22Leonardi%2C+Stefano%22">Leonardi, Stefano</searchLink><relatesTo>1,4</relatesTo> (AUTHOR)<i> leonardi@dis.uniroma1.it</i><br /><searchLink fieldCode="AR" term="%22Roughgarden%2C+Tim%22">Roughgarden, Tim</searchLink><relatesTo>1,5</relatesTo> (AUTHOR)<i> tr@cs.columbia.edu</i><br /><searchLink fieldCode="AR" term="%22Xu%2C+Xiaoming%22">Xu, Xiaoming</searchLink><relatesTo>6</relatesTo> (AUTHOR)<i> xiaomingnatexu@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Dec2020, Vol. 846, p160-171. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Auctions%22">Auctions</searchLink><br /><searchLink fieldCode="DE" term="%22Bidders%22">Bidders</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+orderings%22">Linear orderings</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Prior-free auctions are robust auctions that assume no distribution over bidders' valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders. Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden (STOC'08) to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F (2) , so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders' valuations, such an auction still provides a quantifiable input-by-input performance guarantee. In this paper, we design a simple O (1) -competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O (1) -competitive prior-free auction to multi-unit settings with limited supply. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=146711816
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2020.09.030
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 160
    Subjects:
      – SubjectFull: Auctions
        Type: general
      – SubjectFull: Bidders
        Type: general
      – SubjectFull: Linear orderings
        Type: general
    Titles:
      – TitleFull: Prior-free multi-unit auctions with ordered bidders.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bhattacharya, Sayan
      – PersonEntity:
          Name:
            NameFull: Koutsoupias, Elias
      – PersonEntity:
          Name:
            NameFull: Kulkarni, Janardhan
      – PersonEntity:
          Name:
            NameFull: Leonardi, Stefano
      – PersonEntity:
          Name:
            NameFull: Roughgarden, Tim
      – PersonEntity:
          Name:
            NameFull: Xu, Xiaoming
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 18
              M: 12
              Text: Dec2020
              Type: published
              Y: 2020
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 846
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1