Найдена модель максимально выгодного аукциона

В 2007 г. Роджер Майерсон (Roger Myerson) из университета Чикаго получил Нобелевскую премию за исследования, опубликованные в 1981 г. Используя инструменты теории игр, он описал структуру аукциона с одним продавцом и несколькими покупателями, и показал, что если все покупатели реализуют стратегию получения максимальной выгоды, то и аукционист получает наибольшую прибыль. После публикации этой работы немедленно возникла другая задача: как оптимальным способом организовать аукцион, в котором участвуют несколько покупателей и несколько продавцов? Эта задача оставалась нерешенной на протяжении 30 лет, и только теперь группа ученых Массачусетского технологического института под руководством адъюнкт-профессора компьютерных наук Константиноса Даскалакиса (Constantinos Daskalakis) описала алгоритм поиска наилучшего приближения структуры оптимального аукциона. Результаты исследований были представлены на 44-м симпозиуме Theory of Computing и опубликованы онлайн.

По словам Константиноса Даскалакиса, оптимальный многопредметный аукцион нельзя описать в лаконичной форме. Чтобы максимизировать прибыль аукционист должен соглашаться продать лот по цене, представляющей собой некоторую долю от наибольшей цены предложения, и эта доля зависит от многих факторов: разницы между двумя наилучшими предложениями, конечной цены предыдущего лота, особенностей покупателей. И для каждого набора лотов можно составить собственный весьма длинный список правил, которым необходимо следовать для каждого возможного набора заявок.

Несмотря на это, даже самый сложный аукцион можно описать как вероятностную комбинацию простых. При этом использовался тот факт, что задачу можно свести к геометрической, а рассматриваемые аукционы лежат внутри сложной конструкции, вершинами которой являются так называемые аукционы Викри-Кларка-Грува (Vickrey-Clarke-Groves, VCG). На практике это означает, что аукционисту не нужно следовать сложному набору правил – достаточно собрать заявки, случайным образом выбрать один из VCG аукционов и по относительно простому алгоритму разместить лоты.

В используемой вариации VCG аукционов учитывалось поведение разных групп выступающих на торгах покупателей. Заявки самых богатых покупателей могли быть уменьшены вдвое, средних – увеличены до 20%. Предложенный алгоритм основан именно на этих, модифицированных заявках.

Стратегія охолодження ЦОД для епохи AI