IDEAS home Printed from https://ideas.repec.org/p/ete/kbiper/539977.html
   My bibliography  Save this paper

Winner determination in geometrical combinatorial auctions

Author

Listed:
  • Bart Vangerven
  • Dries Goossens
  • Frits Spieksma

Abstract

We consider auctions of items that can be arranged in rows. Examples of such a setting appear in allocating pieces of land for real estate development, or seats in a theater or stadium. The objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue (often referred to as the winner determination problem). We describe a dynamic programming algorithm which, for a k-row problem with connected and gap-free bids, solves the winner determination problem in polynomial time. We study the complexity for bids in a grid, complementing known results in literature. Additionally, we study variants of the geometrical winner determination setting. We provide a NP-hardness proof for the 2-row setting with gap-free bids. Finally, we extend this dynamic programming algorithm to solve the case where bidders submit connected, but not necessarily gap-free bids in a 2-row and a 3-row problem.

Suggested Citation

  • Bart Vangerven & Dries Goossens & Frits Spieksma, 2016. "Winner determination in geometrical combinatorial auctions," Working Papers of Department of Decision Sciences and Information Management, Leuven 539977, KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven.
    • Handle: RePEc:ete:kbiper:539977
    as

    Download full text from publisher

    File URL: https://lirias.kuleuven.be/retrieve/386445
    File Function: Winner determination in geometrical combinatorial auctions
    Download Restriction: no
    ---><---

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ete:kbiper:539977. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: library EBIB (email available below). General contact details of provider: https://feb.kuleuven.be/KBI .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.