A-CEEI mechanism

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

Background

CEEI (Competitive Equilibrium from Equal Incomes) is a fundamental mechanism for fair division of divisible resources. It works in two steps:

• EI: Each agent receives an equal "income" - 1 unit of fiat money.
• CE: The agents trade freely until a competitive equilibrium is attained (a price-vector and an allocation).

The equilibrium allocation is provably envy free and Pareto efficient.

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 does not have to be weakly additive. It does not even have to be monotone.

Procedure

• Approximate-EI: each agent receives an income between 1 and ${\displaystyle 1+\beta }$, for some constant $\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 - up to a small constant that 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.

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:^[2]

• 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, the disadvantage of A-CEEI is that the returned allocation is not Pareto-efficient, since some items remain unallocated (it is Pareto-efficient only with respect to the allocated items).

In practice, A-CEEI is better when there are many agents, each of whom may get only a small number of items. A typical application is when the agents are students and the items are positions in courses. MNW is better when there are few agents and many items, such as in inheritance division.

References

1. Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061. doi:10.1086/664613.
2. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare. Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.