From single static to multiple dynamic combinatorial auctions

We apply the Provisional Agreement Protocol (PAP) as a new approach to single static, single dynamic and multiple combinatorial auction problems, and empirically evaluate PAP. PAP benefits over one-shot auctions include: bidders not required to submit all bids and their dependencies; interaction with a changing environment during the auction can improve the solution; less communication when each bidder possesses many bids. PAP's backtracking may allow a better solution to be found than the first (greedy) solution, but can be detrimental with multiple auctions when bids (resources) are limited. With multiple auctions, dynamics and competition increases as resources becomes scarce. Therefore, PAP is likely to perform better when many resources are available, which is when auctions are useful anyway. PAP scales well, and applying PAP to a second domain shows its generality.