A Pre-processing Approach for Fast and Stable Allocations on Approximation-based Pricing for Multi-unit Combinatorial Auctions
Abstract
In this paper, some discussions about a pre-processing approach of fast approximation on stable pricing and allocation of resources in a combinatorial auction are presented. On the discussions, an approximate auction which has VCG-like pricing mechanism is used which considers the situation when a cancellation of winner bid(s) could be occurred after its completion of winner determination. An analysis about stable approximate pricing mechanisms against cancellation of a winner after its winner determination is also presented, where a single-unit non-combinatorial reserve price bidding on a combinatorial auction is employed on it. The pricing algorithms employ a kind of approximate allocation and pricing algorithms that are capable of handling multi-unit auctions with reserve price biddings. We consider a scenario on the allocation of electricity power usage rights while considering electricity generation costs on the power suppliers as well as external conditions such as violations of regulations done by some bidders outside the auction mechanism. An experimental analysis is presented on the scenario and the presented algorithms efficiently produced approximation allocations that are necessary in the pricing phase, while keeping the same level of stability in the case of single-winner cancellation scenario.
References
B. An, V. Lesser, D. Irwin, and M. Zink. Automated negotiation with decommitment for dynamic resource allocation in cloud computing. In Proc. International Conference on Autonomous Agents and Multiagent Systems(AAMAS 2010), volume 1, pages 981–988, 2010.
Ruggiero Cavallo. Incentive compatible two-tiered resource allocation without money. In Proc. the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2014), pages 1313–1320, 2014.
Florin Constantin, Jon Feldman, S. Muthukrishnan, and Martin Pal. An online mechanism for ad slot reservations with cancellations. In Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA2009), pages 1265–1274, 2009.
Peter Cramton, Yoav Shoham, and Richard Steinberg. Combinatorial Auctions. The MIT Press, 2006.
Sven de Vries and Rakesh V. Vohra. Combinatorial auctions: A survey. INFORMS Journal on Computing, 15(3):284–309, 2003.
Benjamin Edelman, Michael Ostorvsky, and Michael Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242–259, 2007.
Naoki Fukuta. A mobile agent approach for p2p-based semantic file retrieval. Journal of Information Processing, 20(3):607–613, 2012.
Naoki Fukuta. An approach to VCG-like approximate allocation and pricing for large-scale multi-unit combinatorial auctions. Journal of Information Processing, 21(1):9–15, 2013.
Naoki Fukuta. An approximation approach for large-scale multi-unit combinatorial auctions with reserve-price biddings. In Proc. The 2nd International Conference on Smart Computing and Artificial Intelligence(ICSCAI2014), pages 487–492, 2014.
Naoki Fukuta. A preliminary analysis of allocation stability on approximationbased pricing for multi-unit combinatorial auctions – a single-winner cancellation scenario. In Proc. KICSS2015 International Workshop on Collective Intelligence and Crowd / Social Computing, pages 236–246, Phuket, Thailand, 2015.
Naoki Fukuta. Toward efficient approximation for large-scale multi-unit combinatorial auctions with reserve-price bidding. IEICE Transactions on Information Systems, J98-D(6):948–961, Jun. 2015. (In Japanese.).
Naoki Fukuta. Toward fast approximation of stable allocation and pricing on combinatorial auctions. In Proc. of 1st IEEE International Conference on Agents(ICA2016), pages 74–77, Sep. 2016.
Naoki Fukuta and Takayuki Ito. Towards better approximation of winner determination for combinatorial auctions with large number of bids. In Proc. of The 2006 WIC/IEEE/ACM International Conference on Intelligent Agent Technology(IAT2006), pages 618–621, 2006.
Naoki Fukuta and Takayuki Ito. Fine-grained efficient resource allocation using approximated combinatorial auctions–a parallel greedy winner approximation for large-scale problems. Web Intelligence and Agent Systems: An International Journal, 7(1):43–63, 2009.
Naoki Fukuta and Takayuki Ito. An experimental analysis of biased parallel greedy approximation for combinatorial auctions. International Journal of Intelligent Information and Database Systems, 4(5):487–508, 2010.
Holger H. Hoos and Craig Boutilier. Solving combinatorial auctions using stochastic local search. In Proc. of 17th National Conference on Artificial Intelligence (AAAI2000), pages 22–29, 2000.
Takafumi Ishikawa and Naoki Fukuta. A prototype system for federated cloudbased resource allocation by automated negotiations using strategy changes. In Proc. the Sixth International Workshop on Agent-based Complex Automated Negotiations (ACAN2013), 2013.
Takayuki Ito, Yuma Imi, Takanori Ito, and Eizo Hideshima. COLLAGREE: A faciliator-mediated large-scale consensus support system. In Proc. of the International Conference on Collective Intelligence 2014, 2014.
Takayuki Ito and David C. Parkes. Instantiating the contingent bids model of truthful interdependent value auctions. In Proc. of the International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS2006), pages 1151–1158, 2006.
Ron Lavi and Noam Nisan. Competitive analysis of incentive compatible on-line auctions. In Proc. of the 2nd ACM conference on Electronic commerce(EC2000), pages 233–241. ACM, 2000.
Daniel Lehmann, Liadian Ita O’Callaghan, and Yoav Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. Journal of the ACM, 49:577–602, 2002.
Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combinatorial auction algorithms. In Proc. of ACM Conference on Electronic Commerce (EC2000), pages 66–76, 2000.
John McMillan. Selling spectrum rights. The Journal of Economic Perspectives, 8:145–162, 1994.
Noam Nisan and Amir Ronen. Computationally feasible VCG mechanisms. In Proc. of ACM Conference on Electronic Commerce, pages 242–252, 2000.
Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008.
T. Todo, A. Iwasaki, M. Yokoo, and Y. Sakurai. Characterizing false-nameproof allocation rules in combinatorial auctions. In Proc. 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2009), 2009.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8–37, 1961.
Makoto Yokoo. The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In Proc. of the 18th International Joint Conference on Artificial Intelligence, pages 733–739, 2003.
Edo Zurel and Noam Nisan. An efficient approximate allocation algorithm for combinatorial auctions. In Proc. of the Third ACM Conference on Electronic Commerce (EC2001), pages 125–136, 2001.
