×

Quality of local equilibria in discrete exchange economies. (English) Zbl 1434.91042

Summary: This paper defines the notion of a local equilibrium of quality \(( r,s)\), \(0\leq r\), \(s\), in a discrete exchange economy: a partial allocation and item prices that guarantee certain stability properties parametrized by the numbers \(r\) and \(s\). The quality \((r,s)\) measures the fit between the allocation and the prices: the larger \(r\) and \(s\) the closer the fit. For \(r\), \(s \leq 1\) this notion provides a graceful degradation for the conditional equilibria of H. Fu et al. [“Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding”, in: Proceedings of the 13th ACM conference on electronic commerce, EC’12. New York, NY: Association for Computing Machinery (ACM). 586 (2012; doi:10.1145/2229012.2229055)] which are exactly the local equilibria of quality \((1,1)\). For \(1<r\), \(s\) the local equilibria of quality \((r,s)\) are more stable than conditional equilibria. Any local equilibrium of quality \((r,s)\) provides, without any assumption on the type of the agents’ valuations, an allocation whose value is at least \(\frac{rs}{1+rs}\) the optimal fractional allocation. In any economy in which all agents’ valuations are \(a\)-submodular, i.e., exhibit complementarity bounded by \(a \geq 1\), there is a local equilibrium of quality \((\frac{1}{a},\frac{1}{a})\). In such an economy any greedy allocation provides a local equilibrium of quality \((1,\frac{1}{a})\). Walrasian equilibria are not amenable to such graceful degradation.

MSC:

91B52 Special types of economic equilibria
91B24 Microeconomic theory (price theory and economic markets)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arrow, Kenneth J.; Debreu, Gérard, Existence of an equilibrium for a competitive economy, Econometrica, 22, 265-290 (1954) · Zbl 0055.38007
[2] Aumann, Robert J., Existence of competitive equilibria in markets with a continuum of traders, Econometrica, 34, 1, 1-17 (1966) · Zbl 0142.17201
[3] Babaioff, Moshe; Dobzinski, Shahar; Oren, Sigal, Combinatorial auctions with endowment effect, (Proceedings of EC’18 (2018), ACM) · Zbl 1505.91178
[4] Babichenko, Yakov; Dobzinski, Shahar; Nisan, Noam, The communication complexity of local search (2018), Available as arXiv:1804.02676 [cs.GT] · Zbl 1433.68143
[5] Bikhchandani, Sushil; Mamer, John W., Competitive equilibrium with indivisibilities, J. Econom. Theory, 74, 385-413 (1997) · Zbl 0887.90051
[6] Christodoulou, George; Kovács, Annamária; Schapira, Michael, Bayesian combinatorial auctions, J. ACM, 63(2), 11, 1-19 (2016) · Zbl 1427.91137
[7] Conforti, Michele; Cornuéjols, Gérard, Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math., 7, 251-274 (1984) · Zbl 0533.90062
[8] Dobzinski, Shahar; Nisan, Noam; Schapira, Michael, Approximation algorithms for combinatorial auctions with complement-free bidders, (Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC (2005), ACM), 610-618 · Zbl 1192.68890
[9] Feige, Uriel., Uriel feige on maximizing welfare when utility functions are subadditive, SIAM J. Comput., 39, 1, 122-142 (2009) · Zbl 1185.68855
[10] Feldman, Michal; Gravin, Nick; Lucier, Brendan, Combinatorial auctions via posted prices (2014), arXiv:1411.4916 [cs.GT] · Zbl 1372.91049
[11] Fisher, M. L.; Nemhauser, G. L.; Wolsey, L. A., An analysis of approximations for maximizing submodular set functions-ii, (Polyhedral Combinatorics. Polyhedral Combinatorics, Mathematical Programming Studies, vol. 8 (1978), North-Holland: North-Holland Amsterdam), 73-87 · Zbl 0408.90085
[12] Fu, Hu; Kleinberg, Robert; Lavi, Ron, Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding, (EC12 (2012), Citeseer), 586
[13] Gul, Faruk; Stacchetti, Ennio, Walrasian equilibrium with gross substitutes, J. Econom. Theory, 87, 95-124 (1999) · Zbl 0998.91010
[14] Hatfield, J.; Kominers, S.; Nichifor, A.; Ostrovsky, M.; Westkamp, A., Stability and competitive equilibrium in trading networks, J. Political Economy, 121, 5, 966-1005 (2013)
[15] Hatfield, John William; Milgrom, Paul R., Matching with contracts, Amer. Econ. Rev., 95, 4, 913-935 (2005)
[16] Kelso Jr., Alexander S.; Crawford, Vincent P., Job matching, coalition formation and gross substitutes, Econometrica, 50, 1483-1504 (1982) · Zbl 0503.90019
[17] Lehmann, Daniel, What is there when there is no walrasian equilibrium? Presented at Dagstuhl workshop on Electronic Market Design, 2002.
[18] Lehmann, Benny; Lehmann, Daniel; Nisan, Noam, Combinatorial auctions with decreasing marginal utilities, Games Econom. Behav., 55, 2, 270-296 (2006), A preliminary version appeared in ACM EC’01, Tampa, Oct. 2001 · Zbl 1125.91043
[19] Lehmann, Daniel; O’Callaghan, Liadan Ita; Shoham, Yoav, Truth revelation in approximately efficient combinatorial auctions, J. ACM, 49, 5, 577-602 (2002), CoRR: cs.GT/020217 · Zbl 1326.91011
[20] Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing submodular set functions-i, Math. Program., 14, 265-294 (1978) · Zbl 0374.90045
[21] Qu, Guannan; Brown, Dave; Li, Na, Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions, Automatica, 105, 206-215 (2019) · Zbl 1429.93028
[22] Smith, Adam, An Inquiry Into the Wealth of Nations (1776), W. Strahan and T. Cadell: W. Strahan and T. Cadell London
[23] Sun, Ning; Yang, Zaifu, Equilibria and indivisibilities: Gross substitutes and complements, Econometrica, 74, 5, 1385-1402 (2006) · Zbl 1138.91535
[24] Wald, Abraham, Ueber einige gleichungssysteme der matematischen Ökonomie, Z. Nationalökonomie, 7, 637-670 (1936), Translated as On some systems of equations of mathematical economics, Econometrica 19 (1951) 368-403 · JFM 62.1368.05
[25] Walras, Léon, Eléments d’économie politique pure (1874), Lausanne: Lausanne Rouge · JFM 21.0229.03
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.