Cahier du Laboratoire d'Econometrie (Ecole Polytechnique)

Cahier du Laboratoire d'Econométrie

Cahier N° 2001-003

THE STABLE ALLOCATION (OR ORDINAL TRANSPORTATION) PROBLEM

Mourad Baïou

Michel Balinski

Abstract:

The stable allocation problem generalizes the 0,1 stable assignment problems (one-to-one, one-to-many and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of "stable allocations".

The set of stable allocations is shown to be a distributive lattice in general ; but in the "nondegenerate" case it is a complete linear order. Indeed, in the generic case, when a problem is "strongly nondegenerate," there exists a single stable allocation.

A simple algorithm finds "row optimal" and "column-optimal" stable allocations given any stable allocation. When a problem is nondegenerate if finds all stable schedules.

Résumé:

Le problème d'allocation stable généralise les problèmes d'affectations stables ("one-to-one," "one-to-many" ou "many-to-many") à l'attribution de quantités réelles ou d'heures. Un algorithme fortement polynomial établi l'existence d'allocations stables.

Il est montré que l'ensemble des allocations stables est un treillis distributif en général ; mais dans le cas "nondégénéré" il forme un ordre linéaire total. Dans le cas générique, quand un problème est "fortement nondégénéré", il existe une unique allocation stable.

Un algorithme simple donne l'allocation stable optimale par lignes et l'allocation stable optimale par colonnes. Quand un problème est nondégénéré l'algorithme produit toutes les allocations stables.

Keyword(s):
stable allocation, stable marriage, stable matching, ordinal transportation, university admissions, two-sided market, many-to-many matching.

Mots Clefs:
allocation stable, mariage stable, couplage stable, admission universitaire, "two-sided market"

JEL Classification: JEL : C78, C61, C62, C63
AMS : 90C27, 05C90, 90B80, 68W40

PDF Format

THE STABLE ALLOCATION (OR ORDINAL TRANSPORTATION) PROBLEM

Mourad Baïou Michel Balinski
Abstract:
The stable allocation problem generalizes the 0,1 stable assignment problems (one-to-one, one-to-many and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of "stable allocations". The set of stable allocations is shown to be a distributive lattice in general ; but in the "nondegenerate" case it is a complete linear order. Indeed, in the generic case, when a problem is "strongly nondegenerate," there exists a single stable allocation. A simple algorithm finds "row optimal" and "column-optimal" stable allocations given any stable allocation. When a problem is nondegenerate if finds all stable schedules.

Résumé:
Le problème d'allocation stable généralise les problèmes d'affectations stables ("one-to-one," "one-to-many" ou "many-to-many") à l'attribution de quantités réelles ou d'heures. Un algorithme fortement polynomial établi l'existence d'allocations stables. Il est montré que l'ensemble des allocations stables est un treillis distributif en général ; mais dans le cas "nondégénéré" il forme un ordre linéaire total. Dans le cas générique, quand un problème est "fortement nondégénéré", il existe une unique allocation stable. Un algorithme simple donne l'allocation stable optimale par lignes et l'allocation stable optimale par colonnes. Quand un problème est nondégénéré l'algorithme produit toutes les allocations stables.

Keyword(s):	stable allocation, stable marriage, stable matching, ordinal transportation, university admissions, two-sided market, many-to-many matching.
Mots Clefs:	allocation stable, mariage stable, couplage stable, admission universitaire, "two-sided market"
JEL Classification: JEL : C78, C61, C62, C63 AMS : 90C27, 05C90, 90B80, 68W40

PDF Format