Article Preview
Top1. Introduction
One of the recent trends in the development of auction mechanisms is combinatorial auctions. In combinatorial auctions, bidders can place bids on a combination of goods according to personal preferences rather than just individual items. It is beneficial to adopt combinatorial auction model if complementarities exist between the items to be auctioned. There are many well-known combinatorial auction examples, including the auctioning of Federal Communications Commission's radio spectrum licenses, the sales of airport time slots, allocation of delivery routes, carpool and trading goods (de Vries & Vohra 2003; Rassenti et al. 1982; Zhang, et al. 2019; Hsieh & Guo 2019; Hsieh et al. 2019). For example, application of combinatorial auctions in carpooling systems can be found in (Hsieh et al. 2019). Combinatorial double auctions also provide an efficient mechanism to trade goods in an electronic marketplace (Hsieh & Guo 2019). Combinatorial auctions have been extensively studied (Abrache et al. 2004; Catalán et al. 2009; Harsha et al. 2010; Leskelä et al. 2007; Meeus et al. 2009; Özer & Özturan 2009; Perugini et al. 2005; Sandholm, 2000; Yang et al. 2009). An excellent survey on combinatorial auctions can be found in the papers of de Vries & Vohra (2003) and Pekeč & Rothkopf (2003).
Combinatorial auctions can improve the efficiency of trading goods between buyers and sellers. However, the winner determination problem (WDP) is notoriously difficult to solve from a computational point of view (Rothkopf et al., 1998), (Xia et al., 2005) due to the exponential growth of the number of combinations. The combinatorial auction problem can be modelled as a set packing problem (SPP) (Andersson et al., 2000), (Fujishima, 1999), (Hoos and Boutilier, 2000), (Vemuganti, 1998), (Xia et al., 2005) . Sandholm mentioned that determining the winners so as to maximize revenue in combinatorial auction is NP-complete (Sandholm, 1999), (Sandholm, 2000), (Sandholm, 2002). Many algorithms have been developed for combinatorial auction problems. Exact algorithms have been developed for the SPP problem, including iterative deepening A* search (Sandholm, 2000) and the direct application of available CPLEX IP solver (Andersson et al., 2000). Gonen and Lehmann proposed branch and bound heuristics for finding optimal solutions for multi-unit combinatorial auctions (Gonen and Lehmann, 2000). Jones and Koehler studied combinatorial auctions using rule-based bids (Jones and Koehler, 2002). In (Guo et al., 2005; Hsieh & Lin, 2012; Hsieh & Liao, 2015a; Hsieh & Liao, 2015b), the authors proposed a Lagrangian heuristic and a Lagrangian relaxation approach (Fisher, 2004) for combinatorial auctions and combinatorial reverse auctions, respectively.