4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 15:11, 9 июля 2023
, 9 июля 2023→Предметная область 3: комбинаторные аукционы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 117: | Строка 117: | ||
Комбинаторным аукционом называется многотоварный аукцион, участники которого заинтересованы в приобретении пакетов | Комбинаторным аукционом называется многотоварный аукцион, участники которого заинтересованы в приобретении ''пакетов'' товаров. Такая структура оценки может представлять взаимозаменяемость товаров, взаимодополняемость товаров или комбинацию того и другого. Если говорить более формально, m товаров (<math>\Omega</math>) должны быть распределены между n игроками. Игроки оценивают подмножества товаров, а <math>v_i(S)</math> обозначает стоимость i-го пакета <math>S \subseteq \Omega</math>. Оценки дополнительно обладают следующими свойствами: (1) монотонности, то есть <math>v_i(S) \le v_i(T)</math> для <math>S \subseteq T</math>, и (2) нормализации, то есть <math>v_i (\empty) = 0</math>. В литературе в основном рассматривается цель максимизации общественного благосостояния: требуется найти распределение <math>(S_1, ..., S_n)</math>, для которого значение <math>\sum_i v_i (S_i)</math> максимально. | ||
