<<
>>

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

В завершение нашего обсуждения идеального паросочетания минимальной сто- имости мы немного разовьем экономическую интерпретацию цен. Рассмотрим

следующий сценарий: допустим, X — множество из n людей, каждый из которых желает купить дом, а Y — множество из n домов.

Пусть v(x, у) обозначает ценность дома у для покупателя x. Так как каждый покупатель хочет купить один из домов, можно предположить, что лучшим вариантом будет идеальное паросочетание M,

максимизирующее гi ,f v(x, г). Такое идеальное паросочетание может быть най- дено применением алгоритма идеального паросочетания минимальной стоимости со стоимостями ce = -v(x, у), если e = (x, у).

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

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

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

(7.67) Пусть M — идеальное паросочетание минимальной стоимости, где ce = -v(x, у) для каждого ребра e = (x, у), а p — совместимое множество цен. Тогда паросочетаниеM и множество цен {P(у) = -p(у) : у ^ Y} уравновешены.

Доказательство. Рассмотрим ребро e = (x,у) M; пусть e' = (x,у'). Так какM

и p совместимы, имеем p(x) + ce = p(у) и p(x) + ce' > p(у'). Вычитая эти два нера- венства для исключения p(x) и подставляя значения p и с, мы получаем нужное неравенство в определении уравновешенности. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Приложение к § 23 О ценности имуществ. – Понятие о цене. – Мерило ценности. – Категория цен. – Способы оценки. – Таксы на разные предметы и таксы вознаграждения за труд. – Меры и весы.
  2. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  3. Расширение графического метода
  4. Самовоспитание как "расширение" сознания
  5. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  6. 3.12.2. Техника расширенного восприятия
  7. Расширение внутреннего кругозора
  8. 7.2.2. Расширение полноты ответа
  9. 7.2.2. Расширение полноты ответа
  10. Метод расширения сознания
  11. 2. Расширение круга наследников по закону в российском наследственном праве
  12. 2. Расширение сети вольной русской прессы в 1860-е годы
  13. Интерпретация.