×

Compact bidding languages and supplier selection for markets with economies of scale and scope. (English) Zbl 1218.91052

Summary: Combinatorial auctions have been used in procurement markets with economies of scope. Preference elicitation is already a problem in single-unit combinatorial auctions, but it becomes prohibitive even for small instances of multi-unit combinatorial auctions, as suppliers cannot be expected to enumerate a sufficient number of bids that would allow an auctioneer to find the efficient allocation. Auction design for markets with economies of scale and scope are much less well understood. They require more compact and yet expressive bidding languages, and the supplier selection typically is a hard computational problem. In this paper, we propose a compact bidding language to express the characteristics of a supplier’s cost function in markets with economies of scale and scope. Bidders in these auctions can specify various discounts and markups on overall spend on all items or selected item sets, and specify complex conditions for these pricing rules. We propose an optimization formulation to solve the resulting supplier selection problem and provide an extensive experimental evaluation. We also discuss the impact of different language features on the computational effort, on total spend, and the knowledge representation of the bids. Interestingly, while in most settings volume discount bids can lead to significant cost savings, some types of volume discount bids can be worse than split-award auctions in simple settings.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models

Software:

Knapsack
Full Text: DOI

References:

[1] Abrache, J.; Bourbeau, B.; Crainic, T. G.; Gendreau, M., A new bidding framework for combinatorial e-auctions, Comput. Oper. Res., 31, 8, 1177-1203 (2004) · Zbl 1073.91575
[2] Andersson, A., Tenhunen, M., Ygge, F. 2000. Integer programming for combinatorial auction winner determination. In: Fourth International Conference on Multiagent Systems (ICMAS).; Andersson, A., Tenhunen, M., Ygge, F. 2000. Integer programming for combinatorial auction winner determination. In: Fourth International Conference on Multiagent Systems (ICMAS).
[3] Anton, J.; Yao, D. A., Coordination in split award auctions, Q. J. Econ., 107, 681-707 (1992) · Zbl 0825.90302
[4] Anton, J., Brusco, S., Lopomo, G. 2009. Coordination in split award auctions with uncertain scale economies: Theory and data. Technical report, Duke University.; Anton, J., Brusco, S., Lopomo, G. 2009. Coordination in split award auctions with uncertain scale economies: Theory and data. Technical report, Duke University. · Zbl 1229.91137
[5] Baumol, W. J., Microtheory: Applications and Origins (1987), MIT Press: MIT Press Cambridge, MA, USA
[6] Benisch, M., Sadeh, N., Sandholm, T. 2008. A theory of expressiveness in mechanisms. In: 23rd AAAI Conference on Artificial Intelligence.; Benisch, M., Sadeh, N., Sandholm, T. 2008. A theory of expressiveness in mechanisms. In: 23rd AAAI Conference on Artificial Intelligence.
[7] Bichler, M.; Davenport, A.; Hohner, G.; Kalagnanam, J., Industrial procurement auctions, (Cramton, P.; Shoham, Y.; Steinberg, R., Combinatorial Auctions (2006), MIT Press)
[8] Boutilier, C., Hoos, H.H. 2001. Bidding languages for combinatorial auctions. In: 17th International Joint Conference on Artificial Intelligence (IJCAI) 2001, Washington, USA, pp. 1211-1217.; Boutilier, C., Hoos, H.H. 2001. Bidding languages for combinatorial auctions. In: 17th International Joint Conference on Artificial Intelligence (IJCAI) 2001, Washington, USA, pp. 1211-1217.
[9] Chaudhry, S.; Forst, F.; Zydiak, J. L., Vendor selection with price breaks, Euro. J. Oper. Res., 70, 52-66 (1993) · Zbl 0800.90115
[10] Crama, Y.; Pascual, R.; Torres, A., Optimal procurement decisions in the presence of total quantity discounts and alternative product recipes, Euro. J. Oper. Res., 159, 364-378 (2004) · Zbl 1065.90047
[11] Cramton, P.; Shoham, Y.; Steinberg, R., Introduction to combinatorial auctions, (Cramton, P.; Shoham, Y.; Steinberg, R., Combinatorial Auctions (2006), MIT Press: MIT Press Cambridge, MA) · Zbl 1194.91018
[12] Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A., Complexity and expressive power of logic programming, ACM Comput. Surveys, 33, 374-425 (2001)
[13] Davenport, A., Kalagnanam, J. 2000. Price negotiations for procurement of direct inputs. In: IMA Hot Topics Workshop: Mathematics of the Internet: E-Auction and Markets, vol. 127. Minneapolis, USA, pp. 27-44.; Davenport, A., Kalagnanam, J. 2000. Price negotiations for procurement of direct inputs. In: IMA Hot Topics Workshop: Mathematics of the Internet: E-Auction and Markets, vol. 127. Minneapolis, USA, pp. 27-44. · Zbl 1003.91026
[14] de Vries, S.; Vohra, R., Combinatorial auctions: a survey, INFORMS J. Comput., 15, 3, 284-309 (2003) · Zbl 1238.91003
[15] Eso, M., Ghosh, S., Kalagnanam, J., Ladanyi, L. 2001. Bid evaluation in procurement auctions with piece-wise linear supplycurves. Technical report rc22219, IBM T.J. Watson Research Center.; Eso, M., Ghosh, S., Kalagnanam, J., Ladanyi, L. 2001. Bid evaluation in procurement auctions with piece-wise linear supplycurves. Technical report rc22219, IBM T.J. Watson Research Center.
[16] Evans, D.; Heckman, J., A test for subadditivity of the cost function with an application to the bell system, Amer. Eco. Rev., 74, 4, 615-623 (1984)
[17] Gallien, J.; Wein, L., A smart market for industrial procurement with capacity constraints, Manag. Sci., 51, 76-91 (2005) · Zbl 1232.91300
[18] Gartner, May 2008. Magic quadrant for sourcing application suites. Technical report, Gartner Consulting.; Gartner, May 2008. Magic quadrant for sourcing application suites. Technical report, Gartner Consulting.
[19] Giunipero, L., Carter, P., Fearon, H. 2009. The role of optimization in strategic sourcing. Technical report, CAPS Research.; Giunipero, L., Carter, P., Fearon, H. 2009. The role of optimization in strategic sourcing. Technical report, CAPS Research.
[20] Goossens, D. R.; Maas, A. J.T.; Spieksma, F.; van de Klundert, J. J., Exact algorithms for procurement problems under a total quantity discount structure, Euro. J. Oper. Res., 178, 603-626 (2007) · Zbl 1107.90043
[21] Guzelsoy, M.; Ralphs, T., Duality for mixed-integer linear programs, Inter. J. Oper. Res., 4, 118-137 (2007) · Zbl 1160.90600
[22] Hohner, G.; Rich, J.; Ng, E.; Reid, G.; Davenport, A.; Kalagnanam, J.; Lee, H.; An, C., Combinatorial and quantity discount procurement auctions with mutual benefits at mars, incorporated, Interfaces, 33, 1, 23-35 (2003)
[23] Hooker, J.N. 2009. A principled approach to mixed integer/linear problem formulation. In: INFORMS Computing Society Conference. pp. 79-100.; Hooker, J.N. 2009. A principled approach to mixed integer/linear problem formulation. In: INFORMS Computing Society Conference. pp. 79-100.
[24] Jucker, J. V.; Rosenblatt, M. J., Single period inventory models with demand uncertainty and quantity discounts: Behavioral implications and a new solution procedure, Nav. Res. Logist. Q., 32, 4, 537-550 (1985) · Zbl 0597.90024
[25] Katz, P.; Sadrian, A.; Tendrick, P., Telephone companies analyze price quotations with bellcore’s pdss software, Interfaces, 24, 50-63 (1994)
[26] Lee, H. L.; Rosenblatt, M. J., A generalized quantity discount pricing model to increase supplier’s profit, Manage. Sci., 32, 1177-1188 (1986) · Zbl 0605.90022
[27] Leyton-Brown, K.; Nudelman, E.; Shoham, Y., Empirical hardness models: methodology and a case study on combinatorial auctions, J. ACM, 56, 1-52 (2009) · Zbl 1325.68110
[28] Munson, C. L.; Rosenblatt, M. J., Theories and realities of quantity discounts: an exploratory study, Prod. Oper. Manage., 7, 4, 352-369 (1998)
[29] Nisan, N., Bidding languages, (Cramton, P.; Shoham, Y.; Steinberg, R., Combinatorial Auctions (2006), MIT Press: MIT Press Cambridge, MA)
[30] Nisan, N., Segal, I. 2001. The communication complexity of efficient allocation problems. In: DIMACS workshop on Computational Issues in Game Theory and Mechanism Design. Minneapolis, MI.; Nisan, N., Segal, I. 2001. The communication complexity of efficient allocation problems. In: DIMACS workshop on Computational Issues in Game Theory and Mechanism Design. Minneapolis, MI.
[31] (Papadimitriou, C. H., Computational Complexity (1993), Addison Wesley) · Zbl 0557.68033
[32] Perry, M.; Sakovics, J., Auctions for split-award contracts, J. Ind. Econ., 51, 215-242 (2003)
[33] Sandholm, T. 2008. Expressiveness in mechanisms and its relation to efficiency: Our experience from \(40 billion of combinatorial multi-attribute auctions, and recent theory. In: Proceedings of the 2nd International Workshop on Computational Social Choice.; Sandholm, T. 2008. Expressiveness in mechanisms and its relation to efficiency: Our experience from \)40 billion of combinatorial multi-attribute auctions, and recent theory. In: Proceedings of the 2nd International Workshop on Computational Social Choice.
[34] Silverson, R.; Peterson, E. A., Decision Systems for Inventory Management and Production Planning (1979), John Wiler and Sons: John Wiler and Sons New York
[35] Stewart, K. G., Non-jointness and scope economies in the multiproduct symmetric generalized mcfadden cost function, J. Prod. Anal., 32, 3, 161-171 (2009)
[36] van de Klundert, J.; Kuipers, J.; Spieksma, F.; Winkels, M., Selecting telecommunication carriers to obtain volume discounts, Interfaces, 35, 124-132 (2005)
[37] Williams, H. P., Duality in mathematics and linear and integer programming, J. Optim. Theor. Appl., 90, 257-278 (1996) · Zbl 0866.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.