Abstract
This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises the well-studied gross substitutes demand to a multi-unit setting. Recent work by Baldwin and Klemperer shows that any such demand can be expressed in a natural way as a finite list of weighted bid vectors. A simplified version of this bidding language has been used by the Bank of England. Assuming access to a demand oracle, we provide an algorithm that computes the unique list of weighted bid vectors corresponding to a bidder’s demand preferences. In the special case where their demand can be expressed using positive bids only, we have an efficient algorithm that learns this list in linear time. We also show super-polynomial lower bounds on the query complexity of computing the list of bids in the general case where bids may be positive and negative. Our algorithms constitute the first systematic approach for bidders to construct a bid list corresponding to non-trivial demand, allowing them to participate in ‘product-mix’ auctions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In the banking context, the goods correspond to liquidity secured against alternative kinds of collateral. Commercial banks pay for liquidity ‘products’ by committing to interest rates. The values of the bids submitted by the commercial banks correspond to the interest rates they are willing to pay.
- 2.
Orthants in n-dimensional space generalise the notion of quadrants and octants in two- and three-dimensional space, respectively.
- 3.
Note that \(\mathcal {B}'\) is valid, as lists of positive bids are always valid. If \(\mathcal {B}\) consisted of positive and negative bids, removing a single positive bid might result in a bid list that is no longer valid, in which case the algorithm described in this section may fail and return points not corresponding to bid locations.
References
Baldwin, E., Goldberg, P.W., Klemperer, P., Lock, E.: Solving strong-substitutes product-mix auctions. ArXiv preprint (2019). http://arxiv.org/abs/1909.07313
Baldwin, E., Klemperer, P.: Implementing Walrasian equilibrium - the language of product-mix auctions (2019, in preparation)
Baldwin, E., Klemperer, P.: Understanding preferences: “demand types”, and the existence of equilibrium with indivisibilities. Econometrica 87(3), 867–932 (2019)
Blum, A., Jackson, J.C., Sandholm, T., Zinkevich, M.: Preference elicitation and query learning. J. Mach. Learn. Res. 5, 649–667 (2004)
Conen, W., Sandholm, T.: Preference elicitation in combinatorial auctions. In: Proceedings of the 3rd ACM-EC Conference, pp. 256–259 (2001)
Conen, W., Sandholm, T.: Differential-revelation VCG mechanisms for combinatorial auctions. In: Padget, J., Shehory, O., Parkes, D., Sadeh, N., Walsh, W.E. (eds.) AMEC 2002. LNCS (LNAI), vol. 2531, pp. 34–51. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36378-5_3
Conen, W., Sandholm, T.: Partial-revelation VCG mechanism for combinatorial auctions. In: Proceedings of the 18th National Conference on AI and 14th Conference on Innovative Applications of AI, pp. 367–372. AAAI Press/MIT Press (2002)
Goldberg, P.W., Lock, E., Marmolejo-Cossío, F.: Learning strong substitutes demand via queries. ArXiv preprint (2020). https://arxiv.org/abs/2005.01496
Hudson, B., Sandholm, T.: Effectiveness of query types and policies for preference elicitation in combinatorial auctions. In: Proceedings of the 3rd AAMAS Conference, vol 1, pp. 386–393. IEEE Computer Society (2004)
Klemperer, P.: A new auction for substitutes: central bank liquidity auctions, the U.S. TARP, and variable product-mix auctions (2008). https://www.nuffield.ox.ac.uk/economics/Papers/2008/substsauc.pdf, working paper
Klemperer, P.: The product-mix auction: a new auction design for differentiated goods. J. Eur. Econ. Assoc. 8(2–3), 526–536 (2010)
Klemperer, P.: Product-mix auctions, working paper 2018–W07 (2018). https://www.nuffield.ox.ac.uk/economics/Papers/2018/2018W07 productmix.pdf
Lahaie, S.M., Parkes, D.C.: Applying learning algorithms to preference elicitation. In: Proceedings of the 5th ACM-EC Conference, pp. 180–188 (2004)
Murota, K.: Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications Series, Society for Industrial and Applied Mathematics (2013)
Nisan, N.: Bidding and allocation in combinatorial auctions. In: Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 1–12 (2000)
Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Econ. Theory 129(1), 192–224 (2006)
Shioura, A.: Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discrete Appl. Math. 134(1), 303–316 (2004)
Shioura, A., Tamura, A.: Gross substitutes condition and discrete concavity for multi-unit valuations: a survey. J. Oper. Soc. Japan 58(1), 61–103 (2015)
Tamura, A.: Coordinatewise domain scaling algorithm for M-convex function minimization. Math. Program. 102(2), 339 (2004)
Zhang, H., Conitzer, V.: Learning the valuations of a \(k\)-demand agent (2020). Preprint at https://users.cs.duke.edu/~hrzhang/papers/k-demand.pdf
Zinkevich, M.A., Blum, A., Sandholm, T.: On polynomial-time preference elicitation with value queries. In: Proceedings of the 4th ACM-EC Conference, pp. 176–185 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Goldberg, P.W., Lock, E., Marmolejo-Cossío, F. (2020). Learning Strong Substitutes Demand via Queries. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)