Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCompetitive Equilibrium with Indivisible Goods and Generic Budgets
304
0
0.0
(
0
)
Added by
Inbal Talgam-Cohen
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [Foley67, Varian74]. Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible, even in the simple two-agent, single-item market. Yet, it is easy to see that once the two budgets are slightly perturbed (made generic), a competitive equilibrium does exist. In this paper we aim to extend this approach beyond the single-item case, and study the existence of equilibria in markets with two agents and additive preferences over multiple items. We show that for agents with equal budgets, making the budgets generic -- by adding vanishingly small random perturbations -- ensures the existence of an equilibrium. We further consider agents with arbitrary non-equal budgets, representing non-equal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among non-equal agents, and that it exists in cases of interest (like when the agents have identical preferences) if budgets are perturbed. Our results open opportunities for future research on generic equilibrium existence and fair treatment of non-equals.
rate research
Read More
We study competitive equilibrium in the canonical Fisher market model, but with indivisible goods. In this model, every agent has a budget of artificial currency with which to purchase bundles of goods. Equilibrium prices match between demand and supply---at such prices, all agents simultaneously get their favorite within-budget bundle, and the market clears. Unfortunately, a competitive equilibrium may not exist when the goods are indivisible, even in extremely simple markets such as two agents with exactly the same budget and a single item. Yet in this example, once the budgets are slightly perturbed---i.e., made generic---a competitive equilibrium is guaranteed to exist. In this paper we explore the extent to which generic budgets can guarantee equilibrium existence (and thus related fairness guarantees) in markets with multiple items. We complement our results in [Babaioff et al., 2019] for additive preferences by exploring the case of general monotone preferences, establishing positive results for small numbers of items and mapping the limits of our approach. We then consider cardinal preferences, define a hierarchy of such preference classes and establish relations among them, and for some classes prove equilibrium existence under generic budgets.
We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.
We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to select $k leq m$ goods in a fair and efficient manner. We first establish fundamental connections between the models of private goods, public goods, and public decision making by presenting polynomial-time reductions for the popular solution concepts of maximum Nash welfare (MNW) and leximin. These mechanisms are known to provide remarkable fairness and efficiency guarantees in private goods and public decision making settings. We show that they retain these desirable properties even in the public goods case. We prove that MNW allocations provide fairness guarantees of Proportionality up to one good (Prop1), $1/n$ approximation to Round Robin Share (RRS), and the efficiency guarantee of Pareto Optimality (PO). Further, we show that the problems of finding MNW or leximin-optimal allocations are NP-hard, even in the case of constantly many agents, or binary valuations. This is in sharp contrast to the private goods setting that admits polynomial-time algorithms under binary valuations. We also design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for the cases of (i) constantly many agents, and (ii) constantly many goods with additive valuations. We also present an O(n)-factor approximation algorithm for MNW which also satisfies RRS, Prop1, and 1/2-Prop.
We study the dynamic pricing problem faced by a monopolistic retailer who sells a storable product to forward-looking consumers. In this framework, the two major pricing policies (or mechanisms) studied in the literature are the preannounced (commitment) pricing policy and the contingent (threat or history dependent) pricing policy. We analyse and compare these pricing policies in the setting where the good can be purchased along a finite time horizon in indivisible atomic quantities. First, we show that, given linear storage costs, the retailer can compute an optimal preannounced pricing policy in polynomial time by solving a dynamic program. Moreover, under such a policy, we show that consumers do not need to store units in order to anticipate price rises. Second, under the contingent pricing policy rather than the preannounced pricing mechanism, (i) prices could be lower, (ii) retailer revenues could be higher, and (iii) consumer surplus could be higher. This result is surprising, in that these three facts are in complete contrast to the case of a retailer selling divisible storable goods Dudine et al. (2006). Third, we quantify exactly how much more profitable a contingent policy could be with respect to a preannounced policy. Specifically, for a market with $N$ consumers, a contingent policy can produce a multiplicative factor of $Omega(log N)$ more revenues than a preannounced policy, and this bound is tight.
We study equilibria of markets with $m$ heterogeneous indivisible goods and $n$ consumers with combinatorial preferences. It is well known that a competitive equilibrium is not guaranteed to exist when valuations are not gross substitutes. Given the widespread use of bundling in real-life markets, we study its role as a stabilizing and coordinating device by considering the notion of emph{competitive bundling equilibrium}: a competitive equilibrium over the market induced by partitioning the goods for sale into fixed bundles. Compared to other equilibrium concepts involving bundles, this notion has the advantage of simulatneous succinctness ($O(m)$ prices) and market clearance. Our first set of results concern welfare guarantees. We show that in markets where consumers care only about the number of goods they receive (known as multi-unit or homogeneous markets), even in the presence of complementarities, there always exists a competitive bundling equilibrium that guarantees a logarithmic fraction of the optimal welfare, and this guarantee is tight. We also establish non-trivial welfare guarantees for general markets, two-consumer markets, and markets where the consumer valuations are additive up to a fixed budget (budget-additive). Our second set of results concern revenue guarantees. Motivated by the fact that the revenue extracted in a standard competitive equilibrium may be zero (even with simple unit-demand consumers), we show that for natural subclasses of gross substitutes valuations, there always exists a competitive bundling equilibrium that extracts a logarithmic fraction of the optimal welfare, and this guarantee is tight. The notion of competitive bundling equilibrium can thus be useful even in markets which possess a standard competitive equilibrium.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
