Advanced search
1 file | 2.78 MB Add to list

Combinatorial auctions : theory, experiments, and practice

Bart Vangerven (UGent)
(2017)
Author
Promoter
(UGent) and Frits Spieksma
Organization
Abstract
This doctoral dissertation contributes to theory, experiments, and practice in combinatorial auctions. Combinatorial auctions are multi-object auctions, that enable bidders to bid on packages of items. In Chapter 2, we theoretically investigate the classical winner determination problem in geometrical settings. Specifically, we consider combinatorial auctions of items that can be arranged in rows, and the objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue. Possible practical applications include allocating pieces of land for real estate development, or seats in a theater or stadium. We investigate several geometrical structures and bid shapes, and provide either a polynomial dynamic programming algorithm or an NP-hardness proof, filling in several gaps in academic literature. In Chapter 3, we combine theory with experiments, investigating coordination and threshold problems in combinatorial auctions. Bidders on small packages of items are unable to outbid provisionally winning bids on large packages alone; despite free-rider incentives, both coordination and cooperation are required. Coordination because smaller bidders need to bid on disjoint packages, and cooperation because more than one bidder is required to outbid a larger package bid. We propose indices quantifying both the coordination and the threshold problem, that can be used in providing feedback or generating valuations for laboratory experiments. Additionally, we develop coalitional feedback that is specifically aimed at helping bidders to overcome coordination and threshold problems. We test this in an experimental setting using human bidders, varying feedback from provisionally winning bids and prices, to winning and deadness levels, and coalitional feedback. We find that in situations where threshold problems are severe, coalitional feedback increases economic efficiency, but in easy or insurmountable threshold problems that is not always the case. Finally, in Chapter 4, we combine theory with practice. Scheduling a conference, based on preferences expressed by conference participants, can be seen as a combinatorial auction with public goods. In a situation with public goods, the utility of the final selected goods (presentations scheduled in parallel) are "consumed" by all bidders (conference participants). Constructing a good conference schedule is important: they are an essential part of academic research and require significant investments (e.g.\ time and money) from their participants. We provide computational complexity results, along with a combined approach of assigning talks to rooms and time slots, grouping talks into sessions, and deciding on an optimal itinerary for each participant. Our goal is to maximize attendance, considering the common practice of session hopping. On a secondary level, we accommodate presenters’ availabilities. This personalized conference scheduling approach has been applied to construct the schedule of the MathSport (2013), MAPSP (2015 and 2017) and ORBEL (2017) conferences.
Keywords
Combinatorial auction, computational complexity, coordination and threshold problems, laboratory experiments, conference scheduling

Downloads

  • Dissertation Bart Vangerven.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 2.78 MB

Citation

Please use this url to cite or link to this publication:

MLA
Vangerven, Bart. “Combinatorial Auctions : Theory, Experiments, and Practice.” 2017 : n. pag. Print.
APA
Vangerven, B. (2017). Combinatorial auctions : theory, experiments, and practice.
Chicago author-date
Vangerven, Bart. 2017. “Combinatorial Auctions : Theory, Experiments, and Practice.”
Chicago author-date (all authors)
Vangerven, Bart. 2017. “Combinatorial Auctions : Theory, Experiments, and Practice.”
Vancouver
1.
Vangerven B. Combinatorial auctions : theory, experiments, and practice. 2017.
IEEE
[1]
B. Vangerven, “Combinatorial auctions : theory, experiments, and practice,” 2017.
@phdthesis{8541000,
  abstract     = {{This doctoral dissertation contributes to theory, experiments, and practice in combinatorial auctions. Combinatorial auctions are multi-object auctions, that enable bidders to bid on packages of items.

In Chapter 2, we theoretically investigate the classical winner determination problem in geometrical settings. Specifically, we consider combinatorial auctions of items that can be arranged in rows, and the objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue. Possible practical applications include allocating pieces of land for real estate development, or seats in a theater or stadium. We investigate several geometrical structures and bid shapes, and provide either a polynomial dynamic programming algorithm or an NP-hardness proof, filling in several gaps in academic literature.

In Chapter 3, we combine theory with experiments, investigating coordination and threshold problems in combinatorial auctions. Bidders on small packages of items are unable to outbid provisionally winning bids on large packages alone; despite free-rider incentives, both coordination and cooperation are required. Coordination because smaller bidders need to bid on disjoint packages, and cooperation because more than one bidder is required to outbid a larger package bid. We propose indices quantifying both the coordination and the threshold problem, that can be used in providing feedback or generating valuations for laboratory experiments. Additionally, we develop coalitional feedback that is specifically aimed at helping bidders to overcome coordination and threshold problems. We test this in an experimental setting using human bidders, varying feedback from provisionally winning bids and prices, to winning and deadness levels, and coalitional feedback. We find that in situations where threshold problems are severe, coalitional feedback increases economic efficiency, but in easy or insurmountable threshold problems that is not always the case.

Finally, in Chapter 4, we combine theory with practice. Scheduling a conference, based on preferences expressed by conference participants, can be seen as a combinatorial auction with public goods. In a situation with public goods, the utility of the final selected goods (presentations scheduled in parallel) are "consumed" by all bidders (conference participants). Constructing a good conference schedule is important: they are an essential part of academic research and require significant investments (e.g.\ time and money) from their participants. We provide computational complexity results, along with a combined approach of assigning talks to rooms and time slots, grouping talks into sessions, and deciding on an optimal itinerary for each participant. Our goal is to maximize attendance, considering the common practice of session hopping. On a secondary level, we accommodate presenters’ availabilities. This personalized conference scheduling approach has been applied to construct the schedule of the MathSport (2013), MAPSP (2015 and 2017) and ORBEL (2017) conferences.}},
  author       = {{Vangerven, Bart}},
  keywords     = {{Combinatorial auction,computational complexity,coordination and threshold problems,laboratory experiments,conference scheduling}},
  language     = {{eng}},
  pages        = {{183}},
  school       = {{Ghent University}},
  title        = {{Combinatorial auctions : theory, experiments, and practice}},
  year         = {{2017}},
}