We consider a basic resource allocation game, where the players' strategy spaces are subsets of @math and cost utility functions are parameterized by some common vector @math and, otherwise, only depend on the own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. We assume that resources can be priced, that is, the game is augmented by a price vector @math and players have quasi-linear overall costs utilities meaning that in addition to the original costs utilities, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors @math can we find prices @math that induce an equilibrium realizing the targeted consumption profile? For answering this question, we develop a duality-based framework and derive a characterization of the existence of such @math and @math . We show that our characterization can help to unify parts of three largely independent streams in the literature -- tolls in transportation systems, Walrasian market equilibria and congestion control in communication networks. Besides reproving existing results we establish novel existence results by drawing connections to polyhedral combinatorics and discrete convexity.
For multi-unit items, several recent papers studied the existence of Walrasian equilibria. @cite_45 investigated the existence of Walrasian equilibria in multi-unit auctions and identified general conditions on the demand sets and valuations related to discrete convexity. The conditions of Milgrom and Struluvici @cite_4 and Ausubel @cite_76 appear as special cases of those in @cite_45 . Baldwin and Klemperer @cite_20 explored a connection with tropical geometry and gave necessary and sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result is also closely related to the work of Danilov, Koshevoy, and Murota @cite_45 , see also Sun and Yang @cite_71 . Tran and Yu @cite_57 gave a new proof of the sufficiency condition of @cite_20 using a unimodularity theorem in integer programming. For a comparison of the above works especially with respect to the role of discrete convexity, we refer to the excellent survey of Shioura and Tamura @cite_54 . @cite_74 @cite_64 showed that valuations classes (beyond GS valuations) based on graphical structures also imply the existence of Walrasian equilibria. Their proof uses integrality of optimal solutions of an associated linear min-cost flow formulation.
@cite_64 @cite_4 @cite_54 @cite_57 @cite_45 @cite_71 @cite_74 @cite_76 @cite_20
2788862187 1973520166 2099063943 2966800818 2008980884 2159078604 2304647284 2150880868 2127265337
We introduce feature valuations, a new class of valuations that compactly capture preferences of agents who value items based on the features they possess. Such preferences are relevant in many important practical settings, such as Internet advertising markets (where impressions have associated attributes), labor markets (where workers’ skills titles correspond to features), and long-term bond markets (where coupon payments can be associated with features). We focus on settings where features can be organized in a tree network, and features possessed by items are captured by paths on the tree. In such settings, under appropriate consistency conditions, we establish that Walrasian equilibria exist. In addition, we provide a computationally tractable price update algorithm that terminates with market-clearing prices that support an efficient outcome. The e-companion is available at https: doi.org 10.1287 mnsc.2017.2917. This paper was accepted by Yinyu Ye, optimization. This paper identifies two notions of substitutes for auction and equilibrium analysis. Weak substitutes, the usual price-theory notion, guarantees monotonicity of Tatonnement processes and convergence of clock auctions to a pseudo-equilibrium, but only strong substitutes, which treats each unit traded as a distinct good with its own price, guarantees that every pseudo-equilibrium is a Walrasian equilibrium, that the Vickrey outcome is in the core, and that the "law of aggregate demand" is satisfied. When goods are divisible, weak substitutes along with concavity guarantees all of the above properties, except for the law of aggregate demand. Efficient allocation of indivisible goods is an important problem in mathematical economics and operations research, where the concept of Walrasian equilibrium plays a fundamental role. As a sufficient condition for the existence of a Walrasian equilibrium, the concept of gross substitutes condition for valuation functions is introduced by Kelso and Crawford (1982). Since then, several variants of gross substitutes condition as well as a discrete concavity concept, called M ♮ -concavity, have been introduced to show the existence of an equilibrium in various models. In this paper, we survey the relationship among Kelso and Crawford's gross substitutes condition and its variants, and discuss the connection with M ♮ -concavity. We also review various characterizations and properties of these concepts. In a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota in discrete convex analysis. We give a new proof of the Unimodularity Theorem via the classical unimodularity theorem in integer programming. We give a unified treatment of these results via tropical geometry and formulate a new sufficient condition for competitive equilibrium when there are only two types of product. Generalizations of our theorem in higher dimensions are equivalent to various forms of the Oda conjecture in algebraic geometry. Abstract We consider a production economy with many indivisible goods and one perfectly divisible good. The aim of the paper is to provide some light on the reasons for which equilibrium exists for such an economy. It turns out, that a main reason for the existence is that supplies and demands of indivisible goods should be sets of a class of discrete convexity. The class of generalized polymatroids provides one of the most interesting classes of discrete convexity. We propose a new Walrasian tatonnement process called a double-track procedure for efficiently allocating multiple heterogeneous indivisible items in two distinct sets to many buyers who view items in the same set as substitutes but items across the two sets as complements. In each round of the process, a Walrasian auctioneer first announces the current prices for all items, buyers respond by reporting their demands at these prices, and then the auctioneer adjusts simultaneously the prices of items in one set upward but those of items in the other set downward. It is shown that this procedure converges globally to a Walrasian equilibrium in finitely many rounds. Copyright 2009 The Econometric Society. We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities substitutabilities between items. It is known that for graphical valuations a Walrasian equilibrium (a pricing equilibrium that relies on anonymous item prices) does not exist in general. On the other hand, a pricing equilibrium exists when the seller uses an agent-specific graphical pricing rule that involves prices for each item and markups discounts for pairs of items. We study the existence of pricing equilibria with simpler pricing rules which either (i) require anonymity (so that prices are identical for all agents) while allowing for pairwise markups discounts or (ii) involve offering prices only for items. We show that a pricing equilibrium with the latter pricing rule exists if and only if a Walrasian equilibrium exists, whereas the former pricing rule may guarantee the existence of a pricing equilibrium even for graphical valuations that do not admit a Walrasian equilibrium. Interestingly, by exploiting a novel connection between the existence of a pricing equilibrium and the partitioning polytope associated with the underlying graph, we also establish that for simple (series-parallel) value graphs, a pricing equilibrium with anonymous graphical pricing rule exists if and only if a Walrasian equilibrium exists. These equivalence results imply that simpler pricing rules (i) and (ii) do not guarantee the existence of a pricing equilibrium for all graphical valuations. This article proposes a new dynamic design for auctioning multiple heterogeneous commodities. An auctioneer wishes to allocate K types of commodities among n bidders. The auctioneer announces a vector of current prices, bidders report quantities demanded at these prices, and the auctioneer adjusts the prices. Units are credited to bidders at the current prices as their opponents' demands decline, and the process continues until every commodity market clears. Bidders, rather than being assumed to behave as price-takers, are permitted to strategically exercise their market power. Nevertheless, the proposed auction yields Walrasian equilibrium prices and, as from a Vickrey-Clarke-Groves mechanism, an efficient allocation. (JEL D44) We propose new techniques for understanding agents' valuations. Our classification into types", incorporates existing definitions (substitutes, complements, substitutes", etc.) and permits new ones. Our Unimodularity Theorem generalises previous results about when competitive equilibrium exists for any set of agents whose valuations are all of a type" for indivisible goods. Contrary to popular belief, equilibrium is guaranteed for more classes of purely-complements, than of purely-substitutes, preferences. Our Intersection Count Theorem checks equilibrium existence for combinations of agents with specific valuations by counting the intersection points of geometric objects. Applications include matching and coalition-formation; and the Product-Mix Auction, introduced by the Bank of England in response to the financial crisis.