Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions

References

• Anari N, Mai T, Gharan SO, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Proc. Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms (SIAM, Philadelphia), 2274–2290.Google Scholar
• Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290.Crossref, Google Scholar
• Ausubel LM (2006) An efficient dynamic auction for heterogeneous commodities. Amer. Econom. Rev. 96(3):602–629.Crossref, Google Scholar
• Baldwin E, Klemperer P (2019) Understanding preferences: “demand types”, and the existence of equilibrium with indivisibilities. Econometrica 87(3):867–932.Crossref, Google Scholar
• Baldwin E, Edhan O, Jagadeesan R, Klemperer P, Teytelboym A (2020) The equilibrium existence duality: Equilibrium with indivisibilities & income effects. Preprint, submitted June 30, https://arxiv.org/abs/2006.16939.Google Scholar
• Ball MO, Berardino F, Hansen M (2017) The use of auctions for allocating airport access rights. Transp. Res. Part A Policy Pract. 114:186–202.Crossref, Google Scholar
• Bard JF, Moore (1990) A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Statist. Comput. 11(2):281–292.Crossref, Google Scholar
• Benoit J-P, Krishna V (2001) Multiple-object auctions with budget constrained bidders. Rev. Econom. Stud. 68(1):155–179.Crossref, Google Scholar
• Bichler M, Goeree J (2016) Frontiers in spectrum auction design. Internat. J. Indust. Organ. 50:372–391.Crossref, Google Scholar
• Bichler M, Goeree J (2017) Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK).Google Scholar
• Bichler M, Waldherr S (2017) Core and pricing equilibria in combinatorial exchanges. Econom. Lett. 157:145–147.Crossref, Google Scholar
• Bichler M, Fichtl M, Schwarz G (2020) Walrasian equilibria from an optimiziation perspective: a guide to the literature. Naval Res. Logist. 68(4):496–513.Crossref, Google Scholar
• Bichler M, Fux V, Goeree J (2018) A matter of equality: Linear pricing in combinatorial exchanges. Inform. Systems Res. 29(4):779–1068.Link, Google Scholar
• Bichler M, Fux V, Goeree JK (2019) Designing combinatorial exchanges for the reallocation of resource rights. Proc. National Academy Sci. 116(3):786–791.Crossref, Google Scholar
• Bikhchandani S, Mamer JW (1997) Competitive equilibrium in an exchange economy with indivisibilities. J. Econom. Theory 74(2):385–413.Crossref, Google Scholar
• Bikhchandani S, Ostroy JM (2002) The package assignment model. J. Econom. Theory 107(2):377–406.Crossref, Google Scholar
• Bondareva ON (1963) Some applications of linear programming to the theory of cooperative games [in Russian]. Problemy Kibernetiki 10: 119–139.Google Scholar
• Borgs C, Chayes J, Immorlica N, Mahdian M, Saberi A (2005) Multi-unit auctions with budget-constrained bidders. Proc. 6th ACM Conf. Electronic Commerce (ACM), 44–51.Google Scholar
• Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540.Google Scholar
• Caplice C, Yossi S (2006) Combinatorial auctions for truckload transportation. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Boston), 21:539–571.Google Scholar
• Castelli L, Pellegrini P, Pesenti R (2011) Airport slot allocation in Europe: economic efficiency and fairness. Internat. J. Rev. Management 6(1-2):28–44.Google Scholar
• Che YK, Gale I (1998) Standard auctions with financially constrained bidders. Rev. Econom. Stud. 65(1):1–21.Crossref, Google Scholar
• Cole R, Gkatzelis V (2015) Approximating the nash social welfare with indivisible items. Proc. Forty-Seventh Annual ACM Symposium Theory Comput. 371–380.Google Scholar
• Cole R, Gkatzelis V (2018) Approximating the nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• Cole R, Devanur N, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, fisher markets, and nash social welfare. Proc. 2017 ACM Conf. Econom. Comput., 459–460.Google Scholar
• Colini-Baldeschi R, Henzinger M, Leonardi S, Starnberger M (2011) On multiple round sponsored search auctions with budgets. Preprint, submitted December 29, https://arxiv.org/abs/1112.6361.Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2017) Multiplicative pacing equilibria in auction markets. Preprint, submitted June 22, https://arxiv.org/abs/1706.07151.Google Scholar
• Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Sodomka E, Stier-Moses NE, Wilkens C (2018) Pacing equilibrium in first-price auction markets. Preprint, submitted November 17, https://arxiv.org/abs/1811.07166.Google Scholar
• Danilov V, Koshevoy G, Murota K (2001) Discrete convexity and equilibria in economies with indivisible goods and money. Math. Soc. Sci. 41(3):251–273.Crossref, Google Scholar
• Day R, Cramton P (2012) The quadratic core-selecting payment rule for combinatorial auctions. Oper. Res. 60:588–603.Link, Google Scholar
• Day R, Raghavan S (2007) Fair payments for efficient allocations in public sector combinatorial auctions. Management Sci. 53(9):1389–1406.Link, Google Scholar
• de Vries S, Schummer J, Vohra RV (2007) On ascending vickrey auctions for heterogeneous objects. J. Econom. Theory 132(1):95–118.Crossref, Google Scholar
• Debyser A (2016) Airports in the EU: Challenges ahead. Technical Report PE 583.820, European Parliamentary Research Service.Google Scholar
• Delgadillo A, Arroyo JM, Alguacil N (2010) Analysis of electric grid interdiction with line switching. IEEE Trans. Power Systems 25(2):633–641.Crossref, Google Scholar
• Dempe S (2002) Foundations of Bilevel Programming (Springer, New York).Google Scholar
• Dempe S (2003) Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optim. 52(3):333–359.Crossref, Google Scholar
• Dobzinski S, Lavi R, Nisan N (2008) Multi-unit auctions with budget limits. Foundations Comput. Sci., 2008. FOCS’08, IEEE 49th Annual IEEE Symposium (IEEE, Piscataway, NJ), 260–269.Google Scholar
• Dütting P, Henzinger M, Starnberger M (2016) Auctions for heterogeneous items and budget limits. ACM Trans. Econom. Comput. 4(1):4.Google Scholar
• Fan M, Stallaert J, Whinston AB (2003) Decentralized mechanism design for supply chain organizations using an auction market. Inform. Systems Res. 14(1):1–22.Link, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6):1615–1637.Link, Google Scholar
• Goetzendorff A, Bichler M, Shabalin P, Day RW (2015) Compact bid languages and core pricing in large multi-item auctions. Management Sci. 61(7):1684–1703.Link, Google Scholar
• Gul F, Stacchetti E (1999) Walrasian equilibrium with gross substitutes. J. Econom. Theory 87:95–124.Crossref, Google Scholar
• Guo Z, Koehler GJ, Whinston AB (2012) A computational analysis of bunding trading markets design for distributed resource allocation. Inform. Systems Res. 23(3-part-1):823–843.Link, Google Scholar
• Haylen A, Butcher L (2017) Airport slots. Technical report, House of Commons Briefing Paper No CBP 488.Google Scholar
• Janssen M, Karamychev VA, Kasberger B 2017. Budget Constraints in Combinatorial Clock Auctions (Cambridge University Press, Cambridge, UK), 318–337.Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kelso AS, Crawford VP (1982) Job matching, coalition formation, and gross substitute. Econometrica 50:1483–1504.Crossref, Google Scholar
• Kintali S (2008) Scarf is ppad-complete. Preprint, submitted December 9, https://arxiv.org/abs/0812.1601.Google Scholar
• Krishna V (2010) Auction Theory (Academic Press, San Diego).Google Scholar
• Lee E (2017) Apx-hardness of maximizing nash social welfare with indivisible items. Inform. Process. Lett. 122:17–20.Crossref, Google Scholar
• Lehmann D, Müller R, Sandholm T (2006) The winner determination problem. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Boston), 297–318.Google Scholar
• Leme RP (2017) Gross substitutability: An algorithmic survey. Games Econom. Behav. 106:294–316.Crossref, Google Scholar
• Leyton-Brown K, Pearson M, Shoham Y (2000) Toward a universal test suite for combinatorial auction algorithms. Proc. 2nd ACM Conf. Electronic Commerce. (ACM, New York), 66–76.Google Scholar
• Madani M, Van Vyve M (2015) Computationally efficient mip formulation and algorithms for european day-ahead electricity market auctions. Eur. J. Oper. Res. 242(2):580–593.Crossref, Google Scholar
• Martin A, Müller JC, Pokutta S (2014) Strict linear prices in non-convex european day-ahead electricity markets. Optim. Methods Software 29(1):189–221.Google Scholar
• Mas-Colell A, Whinston MD, Green JR (1995) Microeconomic Theory, vol. 1 (Oxford University Press, New York).Google Scholar
• Milgrom P (2007) Package auctions and exchanges. Econometrica 75(4):935–965.Crossref, Google Scholar
• Milgrom P, Strulovici B (2009) Substitute goods, auctions, and equilibrium. J. Econom. Theory 144(1):212–247.Crossref, Google Scholar
• Moore JT, Bard JF (1990) The mixed integer linear bilevel programming problem. Oper. Res. 38(5):911–921.Link, Google Scholar
• Nisan N, Bayer J, Chandra D, Franji T, Gardner R, Matias Y, Rhodes N, et al. (2009) Google’s auction for TV ads. Internat. Colloquium Automata, Languages, Programming (Springer, Berlin), 309–327.Google Scholar
• Pai MM, Vohra R (2014) Optimal auctions with financially constrained buyers. J. Econom. Theory 150:383–425.Crossref, Google Scholar
• Pekec A, Rothkopf MH (2003) Combinatorial auction design. Management Sci. 49(11):1485–1503.Link, Google Scholar
• Pellegrini P, Castelli L, Pesenti R (2012) Secondary trading of airport slots as a combinatorial exchange. Transportation Res., Part E Logist. Trans. Rev. 48(5):1009–1022.Crossref, Google Scholar
• Rassenti SJ, Smith VL, Bulfin RL (1982) A combinatorial auction mechanism for airport time slot allocation. Bell J. Econom. 13(2):402–417.Crossref, Google Scholar
• Roughgarden T, Talgam-Cohen I (2015) Why prices need algorithms. Proc. Sixteenth ACM Conf. Econom. Comput. (ACM, New York), 19–36.Google Scholar
• Sandholm T (2012) Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of sourcing. Vulkan N, Roth AE, Neeman Z, eds. The Handbook of Market Design (Oxford University Press, Oxford, UK).Google Scholar
• Sandholm T, Suri S, Gilpin A, Levine D (2002) Winner determination in combinatorial auction generalizations. Proc. First Internat. Joint Conf. Autobomous Agents Multiagent Systems: Part I (ACM, New York), 69–76.Google Scholar
• Scaparra MP, Church RL (2008) A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35(6):1905–1923.Crossref, Google Scholar
• Scarf HE (1967) The core of an n person game. Econometrica 35(1):50–69.Crossref, Google Scholar
• Schwind M, Gujo O, Vykoukal J (2009) A combinatorial intra-enterprise exchange for logistics services. Inform. Systems E-Bus. Management 7(4):447–471.Crossref, Google Scholar
• Shapley LS (1967) On balanced sets and cores. Naval Res. Logist. 14(4):453–460 (NRL).Crossref, Google Scholar
• Shapley LS, Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111–130.Crossref, Google Scholar
• Stockmeyer LJ (1976) The polynomial-time hierarchy. Theoret. Comput. Sci. 3(1):1–22.Crossref, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2017) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Programming Comput. 12:529–568.Crossref, Google Scholar
• Vazirani VV (2007) Combinatorial algorithms for market equilibria. Nisan N, Roughgarden T, Tardos E, Vazirani V, eds. Algorithmic Game Theory (Cambridge University Press, New York), 103–134.Google Scholar
• Vazirani VV, Yannakakis M (2011) Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58(3):10.Crossref, Google Scholar
• Von Stackelberg H (1934) Marktform und Gleichgewicht (Springer, Berlin and Vienna).Google Scholar
• Walsh WE, Wellman MP, Ygge F (2000) Combinatorial auctions for supply chain formation. Proceedings of the 2nd ACM Conference on Electronic Commerce. EC ’00 (ACM, New York), 260–269.Google Scholar
• Wu D, Chen X, Yang X, Wang H, Tan Q, Zhang X, Xu J, Gai K(2018) Budget constrained bidding by model-free reinforcement learning in display advertising. Proc. 27th ACM Internat. Conf. Inform. Knowledge Management, 1443–1451.Google Scholar
• Xu P, Wang L (2014) An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41:309–318.Crossref, Google Scholar
• Zeng B, An Y (2014) Solving bilevel mixed integer program by reformulations and decomposition. Optimization Online 1–34. Accessed August 14, 2021, http://www.optimization-online.org/DB_FILE/2014/07/4455.pdf.Google Scholar