# twoprice_equilibrium__57f180f3.pdf Two-Price Equilibrium Michal Feldman, Galia Shabtai, Aner Wolfenfeld Tel Aviv University michal.feldman@cs.tau.ac.il, galiashabtai@gmail.com, anerwolf@gmail.com Walrasian equilibrium is a prominent market equilibrium notion, but rarely exists in markets with indivisible items. We introduce a new market equilibrium notion, called two-price equilibrium (2PE). A 2PE is a relaxation of Walrasian equilibrium, where instead of a single price per item, every item has two prices: one for the item s owner and a (possibly) higher one for all other buyers. Thus, a 2PE is given by a tuple (S, ˆp, ˇp) of an allocation S and two price vectors ˆp, ˇp, where every buyer i is maximally happy with her bundle Si, given prices ˇp for items in Si and prices ˆp for all other items. 2PE generalizes previous market equilibrium notions, such as conditional equilibrium, and is related to relaxed equilibrium notions like endowment equilibrium. We define the discrepancy of a 2PE a measure of distance from Walrasian equilibrium as the sum of differences ˆpj ˇpj over all items (normalized by social welfare). We show that the social welfare degrades gracefully with the discrepancy; namely, the social welfare of a 2PE with discrepancy d is at least a fraction 1 d+1 of the optimal welfare. We use this to establish welfare guarantees for markets with subadditive valuations over identical items. In particular, we show that every such market admits a 2PE with at least 1/7 of the optimal welfare. This is in contrast to Walrasian equilibrium or conditional equilibrium which may not even exist. Our techniques provide new insights regarding valuation functions over identical items, which we also use to characterize instances that admit a WE. 1 Introduction We consider a combinatorial market setting with m items and n buyers. Every buyer i has a valuation function, vi : 2[m] R+, which maps every subset of items to a nonnegative real number. A valuation profile is given by a vector v = (v1, . . . , vn). As standard, we assume that valuation functions are monotone and normalized, i.e., for every S T [m], vi(S) vi(T) and vi( ) = 0 for every i. An allocation is a partition of the items among the buyers; i.e., a vector S = (S1, . . . , Sn) of disjoint sets, where Si denotes the bundle allocated to buyer i. The social welfare (SW) of an allocation S under valuation profile v is the sum of the buyers valuations for their bundles, that is, SW(S, v) = P i [n] vi(Si). The optimal (welfaremaximizing) allocation is denoted by OPT(v). Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Suppose every item j has some price pj R+. Given a vector of prices p1, . . . , pm, and an allocation S, the (quasilinear) utility of buyer i is ui(Si, p) = vi(Si) P j Si pj. Walrasian equilibrium (WE) is a classical and appealing market equilibrium notion that dates back to the 70 s (Walras (1874)). In a WE, despite competition among buyers, every buyer is maximally happy with her bundle and the market clears. That is, a WE is given by a tuple (S, p) satisfying: (i) Utility maximization: ui(Si, p) ui(T, p) for every bundle T [m], and (ii) Market clearance: all items are sold. Moreover, by the first welfare theorem (Bikhchandani and Mamer (1997)), any allocation supported in a WE has optimal social welfare. This appealing notion, however, comes with a serious downside, namely, it rarely exists in markets. In particular, it is known to exist for a strict subclass of submodular valuations, known as gross substitutes (Kelso and Crawford (1982)), and in some precise technical sense, gross substitutes is a maximal class for WE existence (Gul and Stacchetti (1999)). As a result, different relaxations of WE have been introduced and studied. A notable one is the notion of conditional equilibrium (CE) (Fu, Kleinberg, and Lavi (2012)), which is a tuple (S, p) satisfying: (i) individual rationality: ui(Si, p) 0, (ii) outward stability: ui(Si, p) ui(T Si, p) for every bundle T [m] and (iii) market clearance (all items are sold). That is, the difference between a WE and a CE is that it only requires that buyers do not wish to add items to their bundle, whereas a WE requires that buyers don t wish to change their bundle with any other bundle. A CE is guaranteed to exist for every market with submodular valuations (or even a superclass of submodular, called XOS). In addition, the CE notion admits an approximate version of the first welfare theorem; namely, any allocation supported in a CE has social welfare of at least half of the optimal social welfare. However, the notion of CE has its limitations it may not exist even in a market with two subadditive buyers (see Example 3.2). Two-price equilibrium. We introduce a new notion of equilibrium that is based on the idea that an item may be assigned more than a single price. Indeed, item prices often have different prices based on different buyer characteristics, such as location, time, and history. The new notion, termed two-price equilibrium (2PE), uti- The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) lizes two prices per item. A 2PE is a relaxation of Walrasian equilibrium, and generalizes other WE relaxations (e.g., conditional equilibrium). Like WE, it is a tuple of allocation and prices that clears the market (every buyer is maximally happy and all items are sold). However, in contrast to WE, where every item has a single price, 2PE specifies two prices for each item: one price for the item s owner and (a possibly higher) one for all other buyers. The utility maximization condition then states that every buyer is maximally happy with her bundle, given that she pays the low price for items in her possession, and the high price for all other items. Formally, a 2PE is given by a tuple (S, ˆp, ˇp) where ˆp, ˇp R[m] are the high and low prices, respectively (ˆpj ˇpj for every item j), and where (i) Utility maximization: vi(Si) P j Si ˇpj vi(T) P j T Si ˇpj P j T \Si ˆpj for every bundle T [m], and (ii) all items are sold. We note that Condition (i) of 2PE can be also written as vi(Si) P j Si\T ˇpj vi(T) P j T \Si ˆpj for every bundle T [m]. A 2PE for which ˆpj = ˇpj for every item j is a Walrasian equilibrium. Furthermore, one can show that (S, p) is a conditional equilibrium iff (S, p, 0) is a 2PE (see Proposition 3.3). The 2PE notion is related to other relaxations of WE, such as the endowment equilibrium ((Babaioff, Dobzinski, and Oren 2018), (Ezra, Feldman, and Friedler 2019)), named after the endowment effect, discovered by Nobel laureate Richard Thaler ((Kahneman, Knetsch, and Thaler 1990), (Kahneman, Knetsch, and Thaler 1991), (Knetsch, Tang, and Thaler 2001)), stating that buyers tend to inflate the value of items they own. Moreover, as we show in Section 3.1, 2PE is also related to Nash equilibria of simultaneous item auctions a simple auction format that attracted much research in the last decade ((Bhawalkar and Roughgarden 2011), (Christodoulou, Kov acs, and Schapira 2016), (Feldman et al. 2013), (Feldman and Shabtai 2020), (Christodoulou et al. 2016), (Cai and Papadimitriou 2014)). Clearly, a 2PE is guaranteed to exist for every market instance. Moreover, every allocation can be supported in a 2PE. Indeed, for every allocation S, the tuple (S, ˆp, ˇp) where ˆpj = and ˇpj = 0 for every item j is a 2PE. Thus, arbitrarily bad allocations can be supported in a 2PE. This is in stark contrast to Walrasian equilibrium or conditional equilibrium, where supported allocations have optimal welfare (for WE (Bikhchandani and Mamer 1997)) or at least half of the optimal welfare (for CE (Fu, Kleinberg, and Lavi 2012)). Moreover, 2PE s in which the high and low prices of items admit a large difference seem to be far from the notion of Walrasian equilibrium. To study 2PE s that are close to WE, we define a new metric, called the discrepancy of a 2PE, defined as the sum of price differences over all items, P j [m] (ˆpj ˇpj), normalized by the social welfare. The discrepancy of a 2PE can be viewed as a measure of the distance between a given 2PE and a Walrasian equilibrium. Indeed, a 2PE with discrepancy 0 is a WE. Thus, every 2PE with discrepancy 0 has optimal welfare. We then ask whether there are instances that do not admit WE, or WE relaxations (such as CE), but do admit 2PE with low discrepancy and high welfare. A particularly interesting class of valuations is the class of subadditive valuations where v(S)+v(T) v(S T) for every sets S, T [m]. This is a natural class of valuations, known to be the frontier of complement-free valuations (Lehmann, Lehmann, and Nisan 2006). Markets with subadditive valuations may not admit any WE or CE, even in cases where all the items are identical. The following question arises: Question: Do markets with subadditive valuations admit 2PE s with low discrepancy and high welfare? 1.1 Our Results We first show that the social welfare of a 2PE degrades gracefully with its discrepancy. Namely, the social welfare of a 2PE with discrepancy d is at least a fraction 1 d+1 of the optimal social welfare. Armed with this welfare guarantee, our goal is to show the existence of 2PE s with low discrepancy. We establish such results for markets with subadditive valuations over identical items. It should be noted that the problem of efficiently allocating identical items among multiple buyers has played a starring role in classical and algorithmic mechanism design. Identical item settings are of particular interest in our context, where a WE is guaranteed to exist for submodular valuations, but beyond submodular, even simple instances may not admit a WE, or even a relaxed equilibrium notion, such as conditional euilibrium. We first establish a low discrepancy result for markets with 2 identical subadditive valuations over identical items. Theorem 1: (see Theorem 7.1) Every market with 2 identical subadditive valuations over identical items admits a 2PE with discrepancy of at most 2, thus welfare of at least 1/3 of the optimal welfare. Moreover, we show an instance with 2 identical subadditive valuations, where the minimum discrepancy for any 2PE is 1.3895 (see Theorem 7.2). For an arbitrary number of identical valuations over identical items we show the following: Theorem 2: (see Theorem 7.3) Every market with (any number of) identical subadditive valuations over identical items admits a 2PE with discrepancy of at most 2.5, thus welfare of at least 2/7 of the optimal welfare. Our main result establishes a constant factor guarantee for markets with heterogeneous subadditve valuations over identical items. Main Theorem: (see Theorem 8.1) Every market with (any number of) subadditive valuations over identical items admits a 2PE with discrepancy of at most 6, thus welfare of at least 1/7 of the optimal welfare. Furthermore, we find an interesting connection between 2PE and pure Nash equilibria (PNE) of simultaneous item auctions (Christodoulou, Kov acs, and Schapira 2008). In these auctions every bidder submits a bid for every item, and items are sold simultaneously, each one in a separate auction given its own bids. For example, a simultaneous second price auction (S2PA) is one where every item is sold in a 2nd price auction. We show a correspondence between 2PEs of a market and PNE of S2PA for the corresponding market (see Proposi- tion 3.5). Similar correspondences have been shown for WE and PNE of simultaneous first price auctions (Hassidim et al. 2011) and for conditional equilibria and PNE of S2PA under the no-overbidding assumption (Fu, Kleinberg, and Lavi 2012). Combined with our welfare guarantees for 2PEs in markets with subadditive valuations over identical items, this correspondence implies that S2PA for such markets admit PNE (without no-overbidding) with a constant fraction of the optimal welfare. Note that S2PAs for such markets do not necessarily admit PNE with no-overbidding (Bhawalkar and Roughgarden 2011). To obtain our results, we provide new tools for the analysis of valuation functions over identical items. Using these tools, we also establish a necessary and sufficient condition for the existence of WE given an arbitrary valuation profile over identical items (see Theorem 9.1). Due to space limitations, most proofs are deferred to the full version (Feldman, Shabtai, and Wolfenfeld 2021). Open Problems: Our model and results constitute a first step in the analysis of 2PE, and leave some open problems for future work. Most immediately, it would be interesting to close the gaps between the upper and lower bounds on the discrepancy of the markets we study. In addition, it would be interesting to conduct a similar analysis for markets with heterogeneous items. Specifically, do markets with subadditive valuations over heterogeneous items admit a 2PE with constant discrepancy? (This is true for XOS valuations.) If the answer to this question is affirmative, then it implies that every S2PA admits a PNE with constant approximation to the optimal welfare. Finally, in Section 3.1 we show that every PNE of a S2PA has a corresponding 2PE with the same allocation (see Proposition 3.5). Feldman and Shabtai (2020) establish bounds on the price of anarchy of S2PA under a no underbidding assumption for different valuation classes. It would be interesting to study whether a PNE satisfying no underbidding corresponds to a 2PE with bounded discrepancy. 1.2 Additional Related Work Our work belongs to the line of research proposing relaxed market equilibrium notions that exist quite broadly and gives good welfare guarantees. Obvious examples include the conditional equilibrium notion of Fu, Kleinberg, and Lavi (2012) discussed above and the combinatorial Walrasian equilibrium notion introduced by Feldman, Gravin, and Lucier (2013). Fu, Kleinberg, and Lavi (2012) show that a market admits a conditional equilibrium if and only if a S2PA for the corresponding market admits a PNE with no overbidding. A related notion is local equilibrium, introduced by Lehmann (2018), which generalizes conditional equilibrium by relaxing individual rationality and outward stability. The endowment equilibrium notion was proposed by Babaioff, Dobzinski, and Oren (2018) to capture the endowment effect discovered by (Kahneman, Knetsch, and Thaler 1990). Babaioff, Dobzinski, and Oren (2018) showed that every market with submodular valuations admits an endowment equilibrium with at least a half of the optimal wel- fare. Ezra, Feldman, and Friedler (2019) introduced a general framework that captures a wide range of formulations for the endowment effect, and showed that stronger endowment effects can lead to existence of endowment equilibrium also in XOS markets. We show conditions under which one can transform an endowment equilibrium to a 2PE and vice versa. Ezra et al. (2020) provide welfare guarantees via pricing for markets with identical items. 2 Preliminaries Recall that we consider a combinatorial market setting with n buyers and m items, where every buyer has a valuation function that maps every subset of items into a real number. In this paper we consider mainly valuations over identical items, where vi : [m] R+, specifies the value of buyer i for every number of items between 0 and m. Such valuations are also called symmetric valuations. We consider the following valuation classes1. Unit demand: there exist a value a, s.t. v(k) = a for every 0 < k m Additive: there exist a value a, s.t. v(k) = a k for every 0 < k m Submodular: v(k) v(k 1) v(k+1) v(k) for every 0 < k m XOS: v(k) k t v(t) for any 0 < k < t m Subadditive: v(k)+v(t) v(k+t) for any 0 < k, t m s.t. k + t m 2.1 Walrasian Equilibrium and Relaxations In this section we present the definitions of Walrasian equilibrium and conditional equilibrium (for general valuations). Definition 2.1 (Walrasian equilibrium (WE) (Walras 1874)). A pair (S, p) of an allocation S = (S1, . . . , Sn) and item prices p = (p1, . . . , pm), is a Walrasian equilibrium if: 1. Utility maximization: Every buyer receives an allocation that maximizes her utility given the item prices, i.e., vi(Si) P j Si pj vi(T) P j T pj for every i [n] and bundle T [m]. 2. Market clearance: All items are allocated.2 Through the rest of this paper we focus attention on WE in which all items are allocated since if there is an unallocated item with price 0, we can allocate it to an arbitrary buyer. Clearly, the new allocation together with the same price vector, is also a WE. Definition 2.2 (Conditional equilibrium (CE) (Fu, Kleinberg, and Lavi 2012)). A pair (S, p) of an allocation S = (S1, . . . , Sn) and item prices p = (p1, . . . , pm), is a Conditional equilibrium if: 1The definitions of these valuation classes for heterogeneous items appear in the full version. 2More precisely, if an item j is not allocated, then pj = 0. One can easily verify that every such unallocated item can be allocated to an arbitrary buyer, and the resulting allocation, together with the original price vector, is also a Walrasian equilibrium. For simplicity of presentation, we assume throughout the paper that all items are allocated. 1. Individual rationality: Every buyer has a non-negative utility, i.e., vi(Si) P j Si pj 0 for every i [n]. 2. Outward stability: No buyer wishes to add items to her bundle, i.e., vi(Si) P j Si pj vi(Si T) P j Si T pj for every i [n] and bundle T [m]. 3. Market clearance: All items are allocated. An additional interesting relaxation of WE that attracted some attention recently is the notion of endowment equilibrium (Babaioff, Dobzinski, and Oren 2018; Ezra, Feldman, and Friedler 2019), called after the endowment effect (Kahneman, Knetsch, and Thaler 1990, 1991; Knetsch, Tang, and Thaler 2001). An endowment equilibrium is a Walrasian equilibrium with respect to endowed valuations, which inflate the value of items owned by the buyer. In the full version we discuss the relation between an endowment equilibrium and 2PE. 3 Two-Price Equilibrium (2PE) In this section we introduce a new equilibrium notion termed Two Price Equilibrium (2PE). As we shall see, 2PE generalizes some market equilibrium notions considered in the literature. A 2PE resembles a Walrasian equilibrium, but instead of one price per item, it has two prices per item: high and low. It requires that every buyer receives the bundle that maximizes her utility, given that she pays the low price on items in her bundle, and would have to pay the high price for items not in her bundle. The formal definition follow. Definition 3.1 (Two Price Equilibrium (2PE)). Given a valuation profile v, a triplet, (S, ˆp, ˇp), of an allocation S, and high and low price vectors ˆp, ˇp, s.t. ˆpj ˇpj 0 for every item j [m], is called a two price equilibrium (2PE) if the following hold: 1. Utility maximization: For every bundle T [m] and every buyer i [n]: j Si\T ˇpj vi(T) X j T \Si ˆpj (1) 2. Market clearance: All items are allocated. 2PE generalizes both Walrasian equilibrium and conditional equilibrium. We next present a market that admits no Walrasian equilibrium nor conditional equilibrium, and yet, the optimal allocation can be supported in a 2PE. Example 3.2. Consider a market with 2 buyers and an item set M = {x, y, z, w}. Suppose buyer 1 has the following subadditive valuations 0 S = 1 1 |S| 3 2 S = M and buyer 2 has a unit-demand valuation, where v2(S) = 0.9 for every non-empty bundle. We claim that this market has no conditional equilibrium (CE). To see this, consider two cases. Case 1: all items are allocated to buyer 1. For this allocation to be supported by a CE, pj 0.9 for every item j. However, this violates individual rationality for buyer 1. Case 2: buyer 2 receives a non-empty bundle. To satisfy individual rationality, the sum of prices in buyer 2 s bundle cannot exceed 0.9. This, however, violates outward stability for buyer 1. We conclude that no CE exists for this market. The optimal allocation gives all items to buyer 1. One can verify that this allocation is supported by a 2PE with ˆpj = 0.9 and ˇpj = 1 3 for every item j. Indeed, buyer 1 is maximally happy with the grand bundle, since dropping any item (or both) would give her a lower utility. Similarly, buyer 2 cannot increase her utility, since in order to obtain any item j, she would need to pay ˆpj = 0.9, for a utility of 0. Relation between 2PE and other market equilibrium notions. Clearly, every 2PE in which ˆpj = ˇpj for every item j is a WE. That is, for every valuation profile v, (S, p) is a WE if and only if (S, p, p) is a 2PE for v. The following proposition shows that CE is a special case of 2PE as well. Proposition 3.3. For every valuation profile v, (S, p) is a CE if and only if (S, p, 0) is a 2PE. In the full version we show a strong connection between endowment equilibrium and 2PE; namely, we show how a 2PE can be transformed into an endowment equilibrium and vice versa. 3.1 Relation Between 2PE and Simultaneous Second Price Auctions A simultaneous second price auction (S2PA) is a simple auction format, where, despite the complex valuations of the bidders, every bidder submits a bid on every item, and every item is sold separately in a 2nd price auction; i.e., every item is sold to the biider who submitted the highest bid for that item, and the winner pays the second highest bid for that item. A bid profile in a S2PE is denoted by b = (b1, . . . , bn), where bi = (bi1, . . . , bim) is the bid vector of bidder i; bij being bidder i s bid on item j, for j = 1, . . . , m. Let Si(b) denotes the set of items won by buyer i, and let S(b) = (S1(b), . . . , Sn(b)) denote the obtained allocation. Finally, let pj(b) denote the price paid by the winner of item j (i.e., the second highest bid on item j). A S2PA is not a truthful auction, and its performance is often measured in equilibrium. A bid profile is said to be a pure Nash equilibrium in a S2PA if the following holds. Definition 3.4. A bid profile b in a S2PA is a pure Nash equilibrium (PNE) if for any i [n] and for any b i, vi(Si(b)) P j Si(b) pj(b) vi(Si(b i, b i) P j Si(b i,b i) pj(b i, b i). The following proposition shows that a pure Nash equilibrium of S2PA corresponds to a 2PE of the corresponding market. Proposition 3.5. Consider a valuation profile v. The triplet (S, ˆp, ˇp) is a 2PE for v if and only if there exists a bid profile, b, which is a PNE of the S2PA for v (under some tie breaking rule), such that S(b) = S, and for every item j, ˆpj = maxk [n]bkj and ˇpj = max2k [n]bkj. 4 Discrepancy Factor of 2PE The main difference between a two-price equilibrium and a Walrasian equilibrium is the use of two prices per item (high price ˆpj and low price ˇpj) rather than a single price. This makes the notion of 2PE similar in spirit to WE. Namely, prices are still almost anonymous (in contrast to other approaches where prices are buyer-dependent, see, e.g., (Hartline and Roughgarden 2009)), and every buyer is maximally happy with her bundle. The closer the two prices ˆpj and ˇpj are together, the better the 2PE resembles a WE. Indeed, in the extreme case, where ˆpj = ˇpj for every item j, the two notions coincide. Consequently, a natural measure of distances of a 2PE from WE is the sum of price differences over all items. We further normalize the sum of price differences by the social welfare of the allocation, so that the discrepancy is independent of the units used (e.g., USD vs. Euros)3. This motivate us to define the discrepancy as follows. Definition 4.1 (Discrepancy). The discrepancy of a 2PE (S, ˆp, ˇp) under valuation profile v is D(S, ˆp, ˇp) = P j [m](ˆpj ˇpj) SW(S, v) (2) Low discrepancy is a desired property; a 2PE with low discrepancy is closer in spirit to WE in both fairness and simplicity. As we shall soon show, low discrepancy also implies high efficiency. The 2PE notion is appealing from an existence perspective; indeed, every allocation S can be supported in a 2PE by setting ˆpj = , ˇpj = 0 for every item j. However, from a welfare maximization perspective, no guarantee can be given. This is in stark contrast to WE (where, by the 1st welfare theorem, every allocation supported in a WE has optimal welfare), and to weaker equilibrium notions, such as conditional equilibrium (where every allocation supported in a CE gives at least half of the optimal welfare (Fu, Kleinberg, and Lavi 2012)). In contrast, an allocation supported in a 2PE may have an arbitrarily low welfare. The following proposition shows that the social welfare of a 2PE degrades gracefully with its discrepancy. Proposition 4.2. (low discrepancy implies high welfare) Let (S, ˆp, ˇp) be a 2PE for valuation v with discrepancy d. Then, SW(S, v) 1 1+d OPT(v). We also define the discrepancy of an allocation S as the discrepancy of the smallest-discrepancy 2PE supporting S. Definition 4.3. Given valuation profile v, the discrepancy of an allocation S is defined as D(S) = min(S,ˆp,ˇp) 2P ED(S, ˆp, ˇp) 3Formally, suppose (S, ˆp, ˇp) is a 2PE with respect to valuation profile v, and let v be a valuation profile such that v i(T) = c vi(T) for every buyer i and bundle T and some constant c R+. Clearly, (S, c ˆp, c ˇp) is a 2PE w.r.t. v , which has the same discrepancy as that of (S, ˆp, ˇp). For all reasons mentioned above, it is desirable to identify allocations with low discrepancy. Clearly, if S is supported by a WE, then D(S) = 0. Indeed, every allocation supported by a WE has optimal welfare. It is also known that every allocation supported by a conditional equilibrium has at least a half of the optimal welfare (Fu, Kleinberg, and Lavi 2012). The following proposition shows that the discrepancy of every such allocation is at most 1. Together with Proposition 4.2, it gives an alternative proof to the welfare guarantee of a conditional equilibrium. Proposition 4.4. Let S be an allocation that is supported by a conditional equilibrium. Then, D(S) 1. Moreover, this is tight. It is shown in (Christodoulou, Kov acs, and Schapira 2008) that for any XOS valuation profile, the optimal allocation is supported by a S2PA PNE with no-overbidding. By (Fu, Kleinberg, and Lavi 2012), every S2PA PNE with nooverbidding can be transformed into a CE that preserves the same allocation. It then follows by Proposition 4.4 that the discrepancy of the optimal allocation in every XOS valuation profile is at most 1. In the full version we show that for any general valuation profile, every welfare-maximizing allocation has a discrepancy of at most m. Notably, there exist markets that admit neither Walrasian equilibrium, nor conditional equilibrium, and yet, the optimal allocation is supported by a 2PE with small discrepancy. For example, the market in Example 3.2 admits no Walrasian equilibrium, nor conditional equilibrium, and yet, the optimal allocation, S , is supported in a 2PE with discrepancy D(S , ˆp, ˇp) = 3.6 4 5 Geometric Properties of Valuations over Identical Items In this section we introduce new geometric properties of valuations over identical items, which prove useful in establishing upper bounds on the discrepancy of 2PE in such markets. Hereafter, we refer to a valuation over identical items as a symmetric valuation. Definition 5.1 (max-forward-slope ( )). Given a symmetric valuation v, and some 0 k < m, and 1 r m k, the (k, r)-max-forward-slope is defined as v(k, r) = max l=1,2,...,r v(k + l) v(k) We say that l realizes v(k, r), if l is the minimum index s.t. v(k, r) = v(k+l ) v(k) l . In addition, we use v(k) to denote v(k, m k), and refer to v(k) as the k-maxforward-slope. The sorted vector of the max-forward slopes is defined by s v(k). That is, s v(k) s v(k + 1) for every 0 k < m 1. Definition 5.2 (min-backward-slope ( )). Given a symmetric valuation v, and some 0 k < m, and 1 r m k, the (k, r)-min-backward-slope is defined as v(k, r) = min l=1,2,...,r v(k) v(k l) We say that l realizes v(k, r), if l is the minimum index s.t. v(k, r) = v(k) v(k l ) l . In addition, we use v(k) to denote v(k, k), and refer to v(k) as the k-minbackward-slope. Submodular closure: Given a symmetric valuation v, the minimal submodular valuation that (point-wise) upper bounds it is called the submodular closure (SM-closure) of v. The SM-closure of a function is known to be unique (see, e.g., Ezra et al. (2020)); Given a symmetric valuation function v : [m] R+, we define the following: Let v : [m] R+ be the SM-closure of v, and let Iv be the set of indices k [m] for which v(k) = v(k), i.e., the set of points in which the v and v intersect. We refer to Iv as the set of intersection indices. For 0 l < |Iv| 1, let Tl be the right triangle between two adjacent intersecting indices, il and il+1, with vertices (il, v(il)), (il+1, v(il)) and (il+1, v(il+1)). Let αl = v(il+1) v(il) il+1 il be the slope of the triangle Tl. If v(il+1) = v(il), then Tl is a degenerated triangle (a line), with slope αl = 0. Let Tv = T0, T1, . . . , T|Iv| 2 be the set of all right triangles of v. For every 0 l < |Iv| 1, and every il k < il+1, we say that k Tl. In what follows we present some useful lemmas and theorems regarding symmetric valuation functions. The complete proofs, as well as additional observations, appear in the full version. The following lemma gives a lower bound on v(k) as a function of the max-forward-slopes of v up to k. Lemma 5.3. For every symmetric subadditive valuation function v, and 0 < k m, v(k) k min0 k c v(m) m ; otherwise, we say that k is c good. The following lemma establishes an upper bound on the number of c bad numbers in [m 1]. Lemma 5.7. For every symmetric valuation v, for every c 1, there are at most m (c 1) c m 1 c bad integers in {0, 1, . . . , m 1}. 6 Properties of 2PEs with Identical Items In this section we present some properties of 2PEs in markets with identical items. We first define 2PE with uniform prices: Definition 6.1 (2PE with uniform prices (U-2PE)). A triplet (S, ˆp, ˇp) is a 2PE with uniform prices (U-2PE) for valuation profile v, if it is a 2PE for v and for every buyer i [n], every items j, j Si, ˆpj = ˆpj and ˇpj = ˇpj . Let ˆp(i) and ˇp(i) denote these prices, respectively. The following proposition shows that for studying the discrepancy in markets with identical items it is without loss of generality to restrict attention to U-2PEs. Proposition 6.2. If (S, ˆp, ˇp) is a 2PE for some symmetric valuation profile v, then there exists a U-2PE (S, ˆp , ˇp ) s.t. D(S, ˆp , ˇp ) = D(S, ˆp, ˇp). The proof of Proposition 6.2 follows by an iterative invocation of the following lemma for every buyer i [n]. Lemma 6.3. Let (S, ˆp, ˇp) be a 2PE for some symmetric valuation profile v. Let l be some buyer. Let ˇp j = 1 |Sl| P t Sl ˇpt and ˆp j = 1 |Sl| P t Sl ˆpt for every item j Sl and ˇp j = ˇpj and ˆp j = ˆpj for every item j / Sl. Then: (S, ˆp, ˇp ) is a 2PE. (S, ˆp , ˇp) is a 2PE. D(S, ˆp, ˇp ) = D(S, ˆp , ˇp) = D(S, ˆp, ˇp) The following proposition gives necessary and sufficient conditions for the utility maximization property of a U-2PE. Proposition 6.4. Consider a symmetric valuation profile v and a triplet (S, ˆp, ˇp), s.t. for every item j [m], ˇpj ˆpj and for every buyer i [n] and every items j, j Si, ˆpj = ˆpj and ˇpj = ˇpj . Then, the following conditions are necessary and sufficient for utility maximization of a U-2PE: 1. ˇp(i) mini [n] ˆp(i ), for every i [n]. 2. ˇp(i) vi(|Si|), for every i [n]. 3. P i =i |T Si | ˆp(i ) vi(|T|) vi(|Si|), for every i [n] and every T [m] s.t. T Si. Given Proposition 6.4, we can now specify simple sufficient conditions for U-2PE in market with identical items. Proposition 6.5. Consider a symmetric valuation profile v and let (S, ˆp, ˇp) be a triplet satisfying the following conditions for every buyer i [n]: 1. For every items j, j Si, ˆpj = ˆpj and ˇpj = ˇpj . Let ˆp(i) and ˇp(i) denote these prices, respectively. 2. ˇp(i) mini [n] ˆp(i ). 3. ˇp(i) vi(|Si|). 4. ˆp(i) maxi =i n vi (|Si |) o . 5. All items are allocated. Then, (S, ˆp, ˇp) is a U-2PE for v. Notice that for the case of two buyers, condition (4) of Proposition 6.5 is identical to condition (3) of Proposition 6.4, and therefore the conditions specified in Proposition 6.5 are also necessary conditions. 7 Discrepancy in Markets with Identical Subadditive Buyer In this section we establish the existence of 2PEs with small discrepancy for markets with identical items and identical subadditive buyers. We first show that every market with identical items and 2 identical subadditive buyers admits a 2PE with discrepancy of at most 2. Theorem 7.1. Every market with 2 identical subadditive symmetric valuations admits a U-2PE (S, ˆp, 0) with discrepancy of at most 2. We next establish a lower bound on the discrepancy of a 2PE for 2 identical subadditive buyers. Theorem 7.2. There exists a market with identical items and 2 identical subadditive buyers that admits no 2PE with discrepancy smaller than 1.3895. We now extend the result of Theorem 7.1 to markets with an arbitrary number of identical subadditive buyers. Theorem 7.3. Every market with n > 2 identical subadditive symmetric valuations admits a U-2PE, (S, ˆp, ˇp), with discrepancy of at most max n 2, n+2 8 Discrepancy in Markets with Heterogeneous Subadditive Buyers In this section we show that for every market with identical items and any number of subadditive buyers, there exists a 2PE with discrepancy of at most 6. Theorem 8.1. Every market with subadditive symmetric valuations admits a U 2PE, (S, ˆp, 0), with discrepancy of at most 6. To prove Theorem 8.1, we present an algorithm that computes some allocation (k1, k2, . . . , kn), and show in Lemma 8.2 that the obtained allocation is supported in a 2PE with discrepancy of at most 6. Line 11 in the algorithm refers to a 3 good pair. For two buyers x, y [n] and integers kx, lx, ky, ly, r [m], we say that a pair (lx, ly) is 3 good w.r.t. r, kx and ky if (i) lx, ly 0: (ii) lx+ly = r, (iii) vx(kx+lx) 3 vx(kx), and (iiii) vy(ky + ly) 3 vy(ky). Algorithm 1: An algorithm for finding an allocation with discrepancy of at most 6 for heterogeneous buyers. Input: m, n, (v1, v2, . . . , vn) Output: (k1, k2, . . . , kn), s.t. P i [n] ki = m and ki 0 for every i [n] 1: Let ki = 0 for every i [n] 2: Let r = m 3: while r > 0 do 4: Let x = argmaxi [n] n vi(ki) o 5: Let t 1 be the number of items in x s current triangle. 6: if r t then 7: kx = kx + t 8: r = r t 9: else 10: Let y = argmaxi [n]\x n vi(ki) o 11: Find a 3 good pair, (lx, ly) w.r.t. r,kx,ky, s.t. lx r 2 12: kx = kx + lx 13: ky = ky + ly 14: r = 0 15: end if 16: end while 17: return (k1, k2, . . . , kn) Given the output (k1, k2, . . . , kn) of Algorithm 1, let S = (S1, S2, . . . , Sn) be an allocation satisfying |Si| = ki, and let ˆpj = maxi =i n vi (ki ) o for every j Si and ˇpj = 0 for every j [m]. It is easy to see that (S, ˆp, 0) satisfies all the conditions of Proposition 6.5, and hence it is a U 2PE. The following lemma shows that (S, ˆp, 0) has the desired discrepancy. Lemma 8.2. The discrepancy of (S, ˆp, 0) is at most 6. To conclude the proof of Theorem 8.1 it remains to establish the existence of a 3 good pair that satisfies the condition in line 11 of Algorithm 1. Lemma 8.3. For every two buyers x, y in line 11 of Algorithm 1, there exists a 3 good pair (lx, ly) with respect to r, kx, and ky such that lx r 9 WE in Markets with Identical Items In markets with identical items, one can restrict attention to WE in which all prices are equal. Indeed, if there are at least two allocated buyers, then it is clear. Otherwise, simply replace all prices by their average (see Lemma 6.3). A WE with a uniform price p and allocation S is denoted by (S, p). The following theorem establishes necessary and sufficient conditions for the existence of a WE in markets with identical items. Theorem 9.1. Let v = (v1, . . . , vn) be a symmetric valuation profile. Let vi be the SM-closure of vi for every i [n], and let v = ( v1, . . . , vn). (S, p) is a WE for valuation profile v if and only if (S, p) is a WE for valuation profile v and |Si| Ivi for every i [n]. Acknowledgments This research was supported by the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation program (grant agreement No. 866132), by the Israel Science Foundation (grant number 317/17), and by the NSF-BSF (grant number 2020788). Babaioff, M.; Dobzinski, S.; and Oren, S. 2018. Combinatorial auctions with endowment effect. In Proceedings of the 2018 ACM Conference on Economics and Computation, 73 90. Bhawalkar, K.; and Roughgarden, T. 2011. Welfare Guarantees for Combinatorial Auctions with Item Bidding. In Randall, D., ed., Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, 700 709. SIAM. Bikhchandani, S.; and Mamer, J. W. 1997. Competitive Equilibrium in an Exchange Economy with Indivisibilities. Journal of Economic Theory, 74(2): 385 413. Cai, Y.; and Papadimitriou, C. H. 2014. Simultaneous bayesian auctions and computational complexity. In Babaioff, M.; Conitzer, V.; and Easley, D. A., eds., ACM Conference on Economics and Computation, EC 14, Stanford , CA, USA, June 8-12, 2014, 895 910. ACM. Christodoulou, G.; Kov acs, A.; and Schapira, M. 2008. Bayesian Combinatorial Auctions. In Aceto, L.; Damg ard, I.; Goldberg, L. A.; Halld orsson, M. M.; Ing olfsd ottir, A.; and Walukiewicz, I., eds., Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, 820 832. Springer. Christodoulou, G.; Kov acs, A.; and Schapira, M. 2016. Bayesian Combinatorial Auctions. J. ACM, 63(2): 11:1 11:19. Christodoulou, G.; Kov acs, A.; Sgouritsa, A.; and Tang, B. 2016. Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions. ACM Trans. Economics and Comput., 4(2): 9:1 9:33. Ezra, T.; Feldman, M.; and Friedler, O. 2019. A General Framework for Endowment Effects in Combinatorial Markets. ar Xiv preprint ar Xiv:1903.11360. Ezra, T.; Feldman, M.; Roughgarden, T.; and Suksompong, W. 2020. Pricing multi-unit markets. ACM Transactions on Economics and Computation (TEAC), 7(4): 1 29. Feldman, M.; Fu, H.; Gravin, N.; and Lucier, B. 2013. Simultaneous auctions are (almost) efficient. In Boneh, D.; Roughgarden, T.; and Feigenbaum, J., eds., Symposium on Theory of Computing Conference, STOC 13, Palo Alto, CA, USA, June 1-4, 2013, 201 210. ACM. Feldman, M.; Gravin, N.; and Lucier, B. 2013. Combinatorial Walrasian Equilibrium. ar Xiv:1304.2244. Feldman, M.; and Shabtai, G. 2020. Simultaneous 2nd Price Item Auctions with No-Underbidding. ar Xiv preprint ar Xiv:2003.11857. Feldman, M.; Shabtai, G.; and Wolfenfeld, A. 2021. Two Price Equilibrium. ar Xiv:2112.08215. Fu, H.; Kleinberg, R.; and Lavi, R. 2012. Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding. In Faltings, B.; Leyton-Brown, K.; and Ipeirotis, P., eds., Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, 586. ACM. Gul, F.; and Stacchetti, E. 1999. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1): 95 124. Hartline, J. D.; and Roughgarden, T. 2009. Simple versus Optimal Mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC 09, 225 234. New York, NY, USA: Association for Computing Machinery. ISBN 9781605584584. Hassidim, A.; Kaplan, H.; Mansour, Y.; and Nisan, N. 2011. Non-price equilibria in markets of discrete goods. In Shoham, Y.; Chen, Y.; and Roughgarden, T., eds., Proceedings 12th ACM Conference on Electronic Commerce (EC2011), San Jose, CA, USA, June 5-9, 2011, 295 296. ACM. Kahneman, D.; Knetsch, J. L.; and Thaler, R. H. 1990. Experimental Tests of the Endowment Effect and the Coase Theorem. Journal of Political Economy, 98(6): 1325 1348. Kahneman, D.; Knetsch, J. L.; and Thaler, R. H. 1991. Anomalies: The Endowment Effect, Loss Aversion, and Status Quo Bias. Journal of Economic Perspectives, 5(1): 193 206. Kelso, A. S.; and Crawford, V. P. 1982. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, 1483 1504. Knetsch, J.; Tang, F.-F.; and Thaler, R. 2001. The Endowment Effect and Repeated Market Trials: Is the Vickrey Auction Demand Revealing? Experimental Economics, 4(3): 257 269. Lehmann, B.; Lehmann, D.; and Nisan, N. 2006. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2): 270 296. Lehmann, D. 2018. Local Equilibria. Co RR, abs/1807.00304. Walras, L. 1874. El ements d Economie Politique Pure. ed. Lausanne:[sn], 1877.