Алгоритмический дизайн механизмов: различия между версиями

Другое определение пытается передать первоначальные интуитивные соображения, используя классическое теоретико-игровое понятие недоминируемых стратегий:

'''Определение 4 [5]'''. Механизм M является «алгоритмической реализацией c-аппроксимации (в недоминируемых стратегиях)», если существует набор стратегий D, такой, что (1) M получает c-аппроксимацию для любой комбинации стратегий из D за полиномиальное время, и (2) для любой стратегии, не входящей в D, существует стратегия в D, которая слабо доминирует над ней, и этот переход вычислим за полиномиальное время.

Согласно второму условию, разумно предположить, что игрок действительно будет играть, следуя ''некоторой'' стратегии из D; а, согласно первому условию, не имеет значения, какой набор стратегий из D будет выбран на самом деле, поскольку любая из них обеспечит аппроксимацию. Это переносит часть бремени с теоретико-игрового проектирования на алгоритмический дизайн, поскольку теперь гарантия аппроксимации должна обеспечиваться для большего диапазона стратегий. [5] используют это понятие для разработки детерминированного комбинаторного аукциона для многомерных игроков, который достигает гарантии аппроксимации, близкой к оптимальной. Схожим по духу понятием, хотя и более слабым, является понятие «множества Нэша» [25].