Approximate Competitive Equilibrium from Equal Incomes

Last updated December 18, 2020

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.^[1]

Background

CEEI (Competitive Equilibrium from Equal Incomes) is a fundamental rule for fair division of divisible resources. It divides the resources according to the outcome of the following hypothetical process:

Each agent receives a single unit of fiat money. This is the Equal Incomes part of CEEI.
The agents trade freely until the market attains a Competitive Equilibrium. This is a price-vector and an allocation, such that (a) each allocated bundle is optimal to its agent given his/her income - the agent cannot purchase a better bundle with the same income, and (b) the market clears - the sum of all allocations exactly equals the initial endowment.

The equilibrium allocation is provably envy free and Pareto efficient. Moreover, when the agents have linear utility functions, the CEEI allocation can be computed efficiently.

Unfortunately, when there are indivisibilities, a CEEI does not always exist, so it cannot be used directly for fair item assignment. However, it can be approximated, and the approximation has good fairness, efficiency and strategic properties.

Assumptions

A-CEEI only assumes that the agents know how to rank bundles of items. The ranking need not be weakly additive nor even monotone.

Procedure

A-CEEI with parameters $\alpha ,\beta$ divides the resources according to the outcome of the following hypothetical process:

Approximate-EI: each agent receives an income between 1 and $1+\beta$ . The exact income of each agent can be determined randomly, or by seniority (seniors can get a slightly higher income).
Approximate-CE: a price-vector and an allocation are calculated, such that (a) each allocated bundle is optimal to its agent given its budget, and (b) the market "almost" clears: the Euclidean distance between the sum of all allocations and the initial endowment is at most $\alpha$ .

Budish proves that, for any $\beta >0$ , there exists $\alpha ,\beta$ -CEEI where $\alpha$ depends on the minimum between the number of different item-types and the number of different items that an agent may receive.

Guarantees

The allocation satisfies the following properties:

Envy-free-except-1-item (see envy-free item assignment).
$(n+1)$ -maximin-share-guarantee.
Pareto efficiency with respect to the allocated items. I.e, there is no Pareto-improving trade among the agents, but there may be Pareto-improving traders between an agent and the market-maker.

Moreover, the A-CEEI mechanism is strategyproof "in the large": when there are many agents, each agent has only a small influence on the price, so the agents act as price takers. Then, it is optimal for each agent to report his true valuations, since it allows the mechanism to give him an optimal bundle given the prices.

Computation

The A-CEEI allocation is hard to compute: it is PPAD complete.^[2]

However, in realistic-size problems, A-CEEI can be computed using a two-level search process:

Master level: the center uses tabu search to suggest prices;
Agent level: mixed integer programs are solved to find agent demands at the current prices.

The agent-level program can be done in parallel for all agents, so this method scales near-optimally in the number of processors.^[3]

The mechanism has been considered for the task of assigning students to courses at the Wharton School of the University of Pennsylvania. ^[4]

Comparison to maximum-Nash welfare

The Maximum-Nash-Welfare (MNW) algorithm finds an allocation that maximizes the product of the agents' utilities. It is similar to A-CEEI in several respects:^[5]

Both algorithms find an EF-except-1 allocation.
Both algorithms approximate the maximin-share-guarantee.

However, A-CEEI has several advantages:

It works with arbitrary utility functions - not only submodular ones. It does not even require monotonicity of preferences.
It works with ordinal input - the agents are only required to report their ranking over bundles - not their numeric valuation of items.
It is strategy proof "in the large".

On the flip side, A-CEEI has several disadvantages:

There is an approximation error in the items that are allocated - some items might be in excess demand or excess supply.^[6]
In particular, the returned allocation is not Pareto-efficient - some items remain unallocated (it is Pareto-efficient only with respect to the allocated items).

The approximation error of A-CEEI grows with the number of distinct items, but not with the number of players or the number of copies of each item. Therefore, A-CEEI is better when there are many agents and many copies of each item. A typical application is when the agents are students and the items are positions in courses.^[6]

In contrast, MNW is better when there are few agents and many distinct items, such as in inheritance division.

Comparison to competitive equilibrium

A-CEEI (and CEEI in general) is related, but not identical, to the concept of competitive equilibrium.

Competitive equilibrium (CE) is a descriptive concept: it describes the situation in free market when the price stabilizes and the demand equals the supply.
CEEI is a normative concept: it describes a rule for dividing commodities between people.

Related Research Articles

Pareto efficiency or Pareto optimality is a situation where no individual or preference criterion can be better off without making at least one individual or preference criterion worse off or without any loss thereof. The concept is named after Vilfredo Pareto (1848–1923), Italian engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related:

In economics, an Edgeworth box is a graphical representation of a market with just two commodities, X and Y, and two consumers. The dimensions of the box are the total quantities Ω_x and Ω_y of the two goods.

Welfare economics can be connected back to Adam Smith's The Wealth of Nations. It describes and quantifies the welfare of society and its purpose is to identify which policies lead to optimal outcomes or if multiple optima should be chosen. There are two fundamental theorems of welfare economics. The first states that in economic equilibrium, a set of complete markets, with complete information, and in perfect competition, will be Pareto optimal. The requirements for perfect competition are these:

There are no externalities and each actor has perfect information.
Firms and consumers take prices as given.

Competitive equilibrium is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

Group envy-freeness is a criterion for fair division. A group-envy-free division is a division of a resource among several partners such that every group of partners feel that their allocated share is at least as good as the share of any other group with the same size. The term is used particularly in problems such as fair resource allocation, fair cake-cutting and fair item allocation.

Fair item allocation is a kind of a fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

In economics and consumer theory, a linear utility function is a function of the form:

Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of m agent-names, where each name determines what agent is the next to pick an item.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Fair random assignment is a kind of a fair division problem.

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into n parts and taking the part with the minimum value.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately-fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students allowed to register to each course, in order to ensure that the teachers can give sufficient attention to each individual student. Since the demand for some courses is higher than the upper bound, a natural question is which students should be allowed to register to each course.

References

↑ Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613.
↑ Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (2016). "The Complexity of Fairness Through Equilibrium". ACM Transactions on Economics and Computation. 4 (4): 1. arXiv: 1312.6249 . doi:10.1145/2956583.
↑ Abraham Othman; Tuomas Sandholm & Eric Budish (2010). Finding approximate competitive equilibria: efficient and fair course allocation (PDF). AAMAS '10. acm.org
↑ Budish, Eric; Kessler, Judd B. (2016). "Bringing Real Market Participants' Real Preferences into the Lab: An Experiment that Changed the Course Allocation Mechanism at Wharton" (PDF). Archived from the original (PDF) on 2017-03-07. Retrieved 2017-03-06.
↑ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare (PDF). Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.
1 2 Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing (2018-02-01). "Fair Enough: Guaranteeing Approximate Maximin Shares". J. ACM. 65 (2): 8:1–8:27. doi:10.1145/3140756. ISSN 0004-5411.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[b11-1] Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613.

[2] Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (2016). "The Complexity of Fairness Through Equilibrium". ACM Transactions on Economics and Computation. 4 (4): 1. arXiv: 1312.6249 . doi:10.1145/2956583.

[osb10-3] Abraham Othman; Tuomas Sandholm & Eric Budish (2010). Finding approximate competitive equilibria: efficient and fair course allocation (PDF). AAMAS '10. acm.org

[bk16-4] Budish, Eric; Kessler, Judd B. (2016). "Bringing Real Market Participants' Real Preferences into the Lab: An Experiment that Changed the Course Allocation Mechanism at Wharton" (PDF). Archived from the original (PDF) on 2017-03-07. Retrieved 2017-03-06.

[ckmpsw16-5] Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare (PDF). Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.

[:0-6] 1 2 Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing (2018-02-01). "Fair Enough: Guaranteeing Approximate Maximin Shares". J. ACM. 65 (2): 8:1–8:27. doi:10.1145/3140756. ISSN 0004-5411.

[1]

[2]

[3]

[4]

[5]

[6]