Combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research. An earlier version of this paper appeared in 4OR 2, 1–33, 2004.     

Revenue deficiency under second-price auctions in a supply-chain setting

Consider a firm, called the buyer, that satisfies its demand over two periods by assigning both demands to a supplier via a second-price procurement auction; call this the Standard auction. In the hope of lowering its purchase cost, the firm is considering an alternative procedure in which it will also allow bids on each period individually, where there can be either one or two winners covering the two demands; call this the Multiple Winner auction. Choosing the Multiple Winner auction over the Standard auction can in fact result in a higher cost to the buyer. We provide a bound on how much greater the buyer’s cost can be in the Multiple Winner auction and show that this bound is tight. We then sharpen this bound for two scenarios that can arise when the buyer announces his demands close to the beginning of the demand horizon. Under a monotonicity condition, we achieve a further sharpening of the bound in one of the scenarios. Finally, this monotonicity condition allows us to generalize this bound to the T-period case in which bids are allowed on any subset of period demands.     

Electronic service matching: Failure of incentive compatibility in Vickrey auctions

We consider pricing schemes for matching customers and providers on double-sided markets for electronic services. While existing second-best solutions are incentive compatible, the associated payment functions are difficult to implement in real-world settings. Based on the Vickrey–Clarke–Groves (VCG) and the $k$-pricing mechanism, we propose two straightforward payment schemes that offer a practical alternative to the second-best solution. Our experiments provide evidence that the VCG payments fail to implement incentive compatibility. This failure is due to the interdependency of the participants’ utilities.     

Strategic bidding in continuous electricity auctions: an application to the Spanish electricity market

In this paper we introduce an asymmetric model of continuous electricity auctions with limited production capacity and bounded supply functions. The strategic bidding is studied with this model by means of an electricity market game. We prove that for every electricity market game with continuous cost functions a mixed-strategy Nash equilibrium always exists. In particular, we focus on the behavior of producers in the Spanish electricity market. We consider a very simple form for the Spanish electricity market: an oligopoly consisting just of independent hydro-electric power production units in a single wet period. We show that a pure-strategy Nash equilibrium for the Spanish electricity market game always exists.     

Take (smoothed) risks when you are young, not when you are old: How to get the best from your pension plan

Using stochastic modelling, we demonstrate that the best investmentstrategy for the accumulation phase of a defined contributionpension plan is one that limits the range of returns that arecredited to the plan member's account. In particular, we showthat with-profit accumulation programmes which make use of asmoothing fund to smooth out returns over time dominate unit-linkedaccumulation programmes. However, for the distribution phase,we show that it is hard in practice for an investment-linkeddistribution programme to beat the income and security providedby a standard annuity, although we again find that, by avoidingextremely poor outcomes, with-profit distribution programmesdominate unit-linked distribution programmes. Return smoothingby means of a smoothing fund is therefore a valuable featureof any long-term investment programme both during the accumulationand distribution phases.     

Quasi-maximum likelihood estimation in GARCH processes when some coefficients are equal to zero

The asymptotic distribution of the quasi-maximum likelihood (QML) estimator is established for generalized autoregressive conditional heteroskedastic (GARCH) processes, when the true parameter may have zero coefficients. This asymptotic distribution is the projection of a normal vector distribution onto a convex cone. The results are derived under mild conditions. For an important subclass of models, no moment condition is imposed on the GARCH process. The main practical implication of these results concerns the estimation of overidentified GARCH models.     

How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast

We present two randomized entropy-based algorithms for approximating quite general #P-complete counting problems, like the number of Hamiltonian cycles in a graph, the permanent, the number of self-avoiding walks and the satisfiability problem. In our algorithms we first cast the underlying counting problem into an associate rare-event probability estimation, and then apply dynamic importance sampling (IS) to estimate efficiently the desired counting quantity. We construct the IS distribution by using two different approaches: one based on the cross-entropy (CE) method and the other one on the stochastic version of the well known minimum entropy (MinxEnt) method. We also establish convergence of our algorithms and confidence intervals for some special settings and present supportive numerical results, which strongly suggest that both ones (CE and MinxEnt) have polynomial running time in the size of the problem.