Optimal Dynamic Pricing in Multi-Demand Combinatorial Markets

A Two-Step Approach to Optimal Dynamic Pricing in Multi-Demand Combinatorial Markets Presenter: Xinyue Xie (Cynthia) Joint work with Kanstantsin Pashkovich xinyue.xie@uwaterloo.ca kpashkovich@uwaterloo.ca University of Waterloo Department of Combinatorics and Optimization CAIMS 2022 Annual meeting, UBC Okanagan June 13th 16th, 2022

Overview What is a multi-demand combinatorial market? What is our goal? What is a dynamic pricing? Step 1: Compute the rough prices Step 2: Compute the fine prices Case 1: Markets with 4 buyers Case 2: Markets with 2 optimal allocations Case 3: Tri-demand markets

What is a multi-demand combinatorial market? A combinatorial market combinatorial marketconsists of : A set ? of ? heterogeneous and indivisible items A set ? of ? buyers buyers (aka. players Each buyer ? is ??-demand and has valuation function ??:2? 0. Buyers Buyers items players) a a b b c c d d Items Items valuation function 1 1 2 1 1 1 2 2 2 0 1 0 3 3 1 0 0 1 Multi Multi- -demand valuation functions demand valuation functions: for all ?, ?? = max{ ? ??? : ??, }. Assume Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. ? ? = ?? ?1 ?,? ?1 ?,?,? = ?1 ?,? = 3 = 3 ?=1

What is our goal? Perspective of the seller: Perspective of the seller: set prices ?:? >0 Perspective of the buyer: Perspective of the buyer: ?? ,? = ?? ?( ), for all ? a a b b c c d d 1 1 2 1 1 1 Buyers always pick a bundle that maximizes their utility bundle in demand in demand). utility (ie. A 2 2 2 0 1 0 3 3 1 0 0 1 Perspective of the society: Perspective of the society: Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. An allocation allocation is a vector ?? ? ? of disjoint subsets of ?. ?? = ? ???? There are two optimal allocations. ?1= ?,? , ? , ? ?2= ?,? , ? , ? Both yield ?? = 5. ?=1 social welfare is maximized. An allocation is optimal optimal when the social welfare Goal: Goal: Find an optimal pricing optimal pricing so that the self-interested buyers will pick the items in a way that simultaneously maximizes social welfare.

What is a dynamic pricing? Assumptions: Assumptions: Valuation functions are known known. The order of arrival of the buyers is unknown unknown. When the bundles in demand are not unique, the choice of the buyer is unknown unknown. Consequence: Consequence: Static pricing is insufficient. We need an (optimal) dynamic pricing dynamic pricing! After a buyer purchases a bundle, we can change the prices of the remaining items in the market before the next buyer arrives. Characterization of dynamic pricing: Characterization of dynamic pricing: For each player, every bundle in demand can be extended to an optimal allocation.

a a b b c c d d Legality definitions and theorem 1 1 2 1 1 1 2 2 2 0 1 0 Legal item: Legal item: An item ? is legal optimal allocation. legal for a player ? if ? is allocated to ? in some 3 3 1 0 0 1 Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. ?1= ?,? , ? , ? ?2= ?,? , ? , ? Legal bundle: Legal bundle: A bundle is legal item in is legal for ?. legal for a player ? if = ??and every Legal allocation: Legal allocation: An allocation ?? ? ? is legal legal bundle for ?. legal if for every player ?, ?? is a Legal items Legal items Legal bundles Legal bundles 1 1 a,b,c {a,b},{b,c},{a,c} Theorem: Theorem: (Berger, Eden, Feldman, 2020) An allocation is legal if and only if it is optimal. only if it is optimal. An allocation is legal if and 2 2 a,c {a},{c} 3 3 d {d} A legal bundle does NOT NOT necessarily extend to a legal allocation. Ex. {?,?} is legal for player 1, but it is not extendable. Characterization of dynamic pricing: Characterization of dynamic pricing: For each player, every bundle in demand is an extendable legal bundle. Reference: Ben Berger, Alon Eden, and Michal Feldman. On the Power and Limits of Dynamic Pricing in Combinatorial Markets. arXiv e-prints, page arXiv:2002.06863, February 2020.

How do we find an optimal dynamic pricing? Previous results: Previous results: (Berger, Eden, Feldman, 2020) Multi-demand markets with at most 3 players. (Cohen-Addad, Eden, Feldman, Fiat, 2016) Gross-substitutes markets with unique optimal allocation. (In fact, such markets admit optimal static pricings.) (B rczi, B rczi-Kov cs, Sz gi, 2021) Bi-demand markets. New results: New results: (Pashkovich, Xie, 2022) Multi-demand markets with 4 players. (Pashkovich, Xie, 2022) Multi-demand markets with 2 optimal allocations. (Pashkovich, Xie, 2022) Tri-demand markets.

A two-step approach Step 1: Step 1: Rough prices Rough prices - limit the choices of each player to their legal items. Step 2: Step 2: Fine prices Fine prices - further differentiate the legal items. Items with positive valuation Rough prices ??????? ??????? = ???? ?????? + ???? ?????? Legal items New results: New results: Fine prices (Pashkovich, Xie, 2022) Multi-demand markets with 4 players. Extendable legal bundle (Pashkovich, Xie, 2022) Multi-demand markets with 2 optimal allocations. (Pashkovich, Xie, 2022) Tri-demand markets.

2 2 a b - -1 1 Step 1:Rough prices - -1 1 0 0 2 2 - -1 1 1 1 0 0 1 1 1 1 Construct an auxiliary graph auxiliary graph ? = (?,?) such that for any player ? and for any items ?,?, whenever ? ? ?? and ? ?? ??, we have an edge ? ? in ? with weight ? ? ? = ??? ??(?). 1. 1 1 0 0 1 1 0 0 d c 1 1 1 1 An edge ? ? induced by player ? is in a 0-weight cycle if and only if ? ?? and ? ??. a a b b c c d d 1 1 2 1 1 1 2 2 2 0 1 0 3 3 1 0 0 1 For a player For a player ?, the utility has the following ordering. , the utility has the following ordering. ? ?? ?? Items that are only only legal to ? Items that are legal to ? and at least one other player Items in ??have the same utility. Items that are not not legal to ? > > Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. 1= ? ,?1= ?,? ,?1= {?}

2 2 a b - -1 1 Step 1:Rough prices - -1 1 0 0 2 2 - -1 1 1 1 0 0 1 1 1 1 Construct an auxiliary graph auxiliary graph ? = (?,?) such that for any player ? and for any items ?,?, whenever ? ? ?? and ? ?? ??, we have an edge ? ? in ? with weight ? ? ? = ??? ??(?). 1. 1 1 0 0 1 1 0 0 d c 1 1 An edge ? ? induced by player ? is in a 0-weight cycle if and only if ? ?? and ? ??. 1 1 a a b b c c d d not in a 0-weight cycle, decrease their weights 2. For the edges not by ?. . 1 1 2 1 1 1 2 2 2 0 1 0 3 3 1 0 0 1 For a player For a player ?, the utility has the following ordering. , the utility has the following ordering. ? ?? ?? Items that are only only legal to ? Items that are legal to ? and at least one other player Items in ??have the same utility. Items that are not not legal to ? > > Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. 1= ? ,?1= ?,? ,?1= {?}

1.8 1.8 a b - -0.2 0.2 - -1.2 1.2 Step 1:Rough prices - -1 1 - -0.2 0.2 1.8 1.8 0.2 0.2 0.8 0.8 - -1 1 s 0.8 0.8 - -0.2 0.2 1 1 0.8 0.8 1. Construct an auxiliary graph. 0.2 0.2 - -0.2 0.2 For the edges not in a 0-weight cycle, decrease their weights by ?. . 2. 1 1 0.2 0.2 - -0.2 0.2 d c Add a source vertex ?. For each item ?, add an edge ? ? and assign weight ?. 3. 0.8 0.8 0.8 0.8 (? = 0.2) ?. For each item ?, ??= ? ?,? , Return rough prices ? >0 where ?(?,?) is the weight of a min-weight path from ? to ?. a a b b c c d d 4. 1 1 2 1 1 1 2 2 2 0 1 0 3 3 1 0 0 1 For a player For a player ?, the utility has the following ordering. , the utility has the following ordering. ? 1.4 1.4 0.2 0.2 0.4 0.4 0.6 0.6 ?? ?? ? ?? 0.6 0.8 0.6 0.4 Items that are only only legal to ? Items that are legal to ? and at least one other player Items in ??have the same utility. Items that are not not legal to ? > > Ex. Buyer 1 is 2-demand. Buyers 2 and 3 are unit-demand. 1= ? ,?1= ?,? ,?1= {?}

Step 2:Fine prices For a player For a player ?, the utility has the following ordering. , the utility has the following ordering. ?? ?? ? Items that are only only legal to ? Items that are legal to ? and at least one other player Items in ??have the same utility. Items that are not not legal to ? > > All fine prices are less than = min ??? ??? :??? ??? 0,? ? . Assumption 1: every item is legal to at least two players. Assumption 2: No item is legal to all players.

Step 2:Fine prices For a player For a player ?, the utility has the following ordering. , the utility has the following ordering. ?1 ?2 ?1 ?2 ?? ?? ? Items that are only only legal to ? Items that are legal to ? and at least one other player Items in ??have the same utility. Items that are not not legal to ? > > ?3 ?3 Reallocation along the cycle ?? ?? ?? ?3 ?1 ? ? ?2 ?1 Pick an optimal allocation ?? ? ?. Construct a legality graph legality graph ? = (?,?) such that for any player ? and for any items ?,?, whenever ? ?? and ? ?? ??, we have an edge ? ? in ?. ?3 ?2 Every edge is in a cycle. Every vertex is in a cycle.

Step 2:Fine prices case 1: 4 players Goal: Goal: Find a removable set a removable set of items to assign highest/lowest prices. In a market with 4 players, there always exists an optimal allocation whose legality graph contains a removable set of either type I or type II. Removable set of type I Removable set of type I Removable set of type II Removable set of type II ?2 ?1 ?1 ?2 High price High price ?2 ?1 High price High price ?1 ?2 High price High price High price High price ?? Low price Low price ?? ?3 ?4 High price High price High price High price ?3 ?4 High price High price ?3 ?3

Step 2: Fine prices case 2: 2 optimal allocations Uniquely assigned even cycle Uniquely assigned even cycle Every item is in a uniquely assigned cycle uniquely assigned cycle, where the items are allocated to distinct players. High price High price Low price Low price ?1 ?2 ?2 ?1 In a uniquely assigned cycle, every player has either 0 legal items or 2 adjacent legal items. ?2? High price High price ?3 ?2? ?3 Suppose there is no u. a. even cycle remove all but one item in a u. a. odd cycle that item is legal to exactly one player in the remaining submarket. u. a. even cycle or u. a. odd cycle pair u. a. odd cycle pair. If we u. a. odd cycle from the market, then Low price Low price ?4 ?2? 1 ?4 ?2? 1 High price High price Low price Low price Uniquely assigned o Uniquely assigned odd cycle pair dd cycle pair High price High price Low price Low price Uniquely assigned odd cycle Uniquely assigned odd cycle ?2 ?1 Keep Keep ?? in the market the market in ?1 ?2 High price High price ?1 ?2 ?1 ?5 ?2 ?1 ?2 ?1 ?4 ?2 ?3 ?5 ?3 ?4 ?3 ?4 ?5 ?4 ?3 ?5 ?2?+1 Low price Low price ?3 ?2?+1 ?3 ?2 ?6 Low price Low price ?2 ?6 ?4 ?2? ?7 ?6 ?7 ?6 ?4 ?2? High price High price High price High price Low price Low price High price High price

Step 2: Fine prices case 3: Tri-demand Property (P) Property (P): an item ? is legal to a player ? in the submarket iff ? is legal to ? in the original market. Goal: Goal: In any submarket with property (P), for any item ?, there is a dynamic pricing with ? priced the lowest (i.e. a pricing fixed at x a pricing fixed at x). Submarket 1 Submarket 1 Buyers Buyers + Artificial unit-demand player ? whose legal items are exactly the items in ?1 that are legal to ?2. Items Items ?1 = ??+ 1 Items ?1 players ?1 ? ?1 ?1 ?1 ?2 = ?? 1 Items not legal to ?2 Items legal to ?2 ? ?2 To compute dynamic pricing fixed at ?? Find dynamic pricing in Submarket 1 (fixed at ?? if ?? ?1) Define ? = ?????? ?????? ???? ?? ?1 ????? ?? ?2 Find ?1,1,?1,2 ?1 such that ?? < ?1,1< ? < ?1,2 Find dynamic pricing in Submarket 2 fixed at ? or ?? (if ?? ?2) Recombine the pricings ?? < ?1,1< ? ?2< ?1,2 ?2 ?1 Any 1 item ? Submarket 2 Submarket 2 ?3 ?2 Items ?2= ? ?1 players ?2= ? ?1 No item is legal to ?1 ?4 ?3

Step 2: Fine prices case 3: Tri-demand Property (P) Property (P): an item ? is legal to a player ? in the submarket iff ? is legal to ? in the original market. Goal: Goal: In any submarket with property (P), for any item ?, there is a dynamic pricing with ? priced the lowest (i.e. a pricing fixed at x a pricing fixed at x). Submarket 1 Submarket 1 + Artificial bi bi- -demand whose legal items are exactly the items in ?1 that are legal to ?2. ?1 = ??+ 2 demand player ? Items ?1 players ?1 ? ?1 ?2 = ?? 2 Items not legal to ?2 Items legal to ?2 ? ?2 To compute dynamic pricing fixed at ?? Find dynamic pricing in Submarket 1 fixed at ?? ?? < ?1,1< ? < ?1,2< ? < ?1,3 ? = ?????? ?????? ???? ?? ?1 ????? ?? ?2 ? = 2?? ?????? ?????? ???? ?? ?1 ????? ?? ?2 Find dynamic pricing in Submarket 2 fixed at ? ? < ?2,1< ? < ?2,2 ?? < ?1,1< ? < ?2,1< ?1,2< ? < ?2,2< ?1,3 Any 2 2 items ?,? Submarket 2 Submarket 2 Items ?2= ? ?1 players ?2= ? ?1 No item is legal to ?1

Conclusion Rough prices can be computed for any multi-demand market. There exist algorithms for computing dynamic pricings in the following types of markets Multi-demand markets with 4 players. Multi-demand markets with 2 optimal allocations. Tri-demand markets. Open problem: Open problem: Are any of the presented techniques generalizable to markets with more players, more optimal allocations and/or markets with higher demand? Thank you!