Работает ли алгоритм VCG для какой-либо функции оценки пакета?

3

Предположим, у нас на аукционе $ n $ покупателей $ | M | = m $ предметов. Итак, как мы знаем, мы можем использовать алгоритм Vickrey-Clarke-Groves (VCG), чтобы распределять комплекты предметов покупателям как можно лучше. Однако каждый игрок $ i $ имеет значение $ v_ {ij} $ для каждого отдельного элемента $ j $ и значение $ v_i (S) $ для каждого набора предметов $ S \ subset M $.

Мой вопрос заключается в следующем: можем ли мы всегда использовать алгоритм VCG, чтобы найти лучшее решение этой проблемы, даже если функция $ v_i (S) $ неаддитивна, например, если $ v_i (S) = \ max \ limit_ {k \ in S} v_ {ik} $? (Таким образом, в этом случае игрок $ i $ оценивает комплект предметов столько же, сколько его наиболее ценный предмет, независимо от того, сколько предметов в комплекте)

RBS
источник

Ответы:

1

В теории ответ - да. На практике ответ - нет, потому что это трудно поддается вычислению. Мой вывод из разговоров с учеными-компьютерщиками заключался в том, что определение победителя и вычисление переводов - трудная задача для NP. Смотрите, например, это рецензия Кирка Пруха.

Bayesian
источник