Расширения: экономическая интерпретация цен

В завершение нашего обсуждения идеального паросочетания минимальной стоимости мы немного разовьем экономическую интерпретацию цен. Рассмотрим следующий сценарий: допустим, X — множество из n людей, каждый из которых желает купить дом, а Y — множество из n домов.

А теперь зададимся следующим вопросом: можно ли убедить этих покупателей купить назначенный ему дом? Сам по себе каждый покупатель x хочет купить дом y, обладающий для него максимальным значением v(x, y).

Как убедить его вместо этого купить дом, выделенный нашим паросочетанием M? Мы будем использовать цены для стимуляции покупателей. Допустим, мы назначаем цену P(y) для каждого дома y — то есть человек, покупающий дом y, должен заплатить P(y).

С учетом этих цен покупатель будет заинтересован в покупке дома с максимальной чистой стоимостью — то есть дом y, максимизирующий v(x, y) − P(y).

Мы говорим, что идеальное паросочетание M и цены на дома P уравновешены, если для всех ребер (x, y) Ѯ M и всех других домов y’ выполняется v(x, y) − P(y) ≥ v(x, y’) − P(y’).

Но можно ли найти идеальное паросочетание и множество цен, достигающих такого состояния дел, при котором все покупатели остаются довольными? Оказывается, идеальное паросочетание с минимальной стоимостью и связанное с ним множество совместимых цен дает искомое.