An Analysis of Allocation Stability on Approximation-Based Pricing for Multi-unit Combinatorial Auctions

In this paper, a discussion and an analysis about the stability on pricing and allocation of resources are presented. On the discussion, an approximate auction which has VCG-like pricing mechanism is used when cancellation of winner bid(s) after its winner determination is considered. An analysis about stable approximate pricing mechanisms against cancellation of a winner after its winner determination is also presented. In there, a single-unit non-combinatorial reserve price bidding on a multi-unit combinatorial auction could also be employed as well. The pricing algorithm employs an approximate allocation and pricing algorithm that is capable of handling multi-unit auctions with reserve price biddings. This type of auction is expected to be applied to a situation when we consider an allocation of electricity while considering electricity generation costs on the power suppliers in more realistic configurations, i.e., some bidders might be untrustful in their ability. Based on the experimental analysis, the algorithm effectively produces approximation allocations that are necessary in the pricing phase, as well as yielding better stability in the case of single-winner cancellation. It also behaves as an approximation of VCG(Vickrey-Clarke-Groves) mechanism satisfying budget balance condition and bidders' individual rationality without enforcing the single-minded bidders assumption.