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

Чем вызван переход от «в основном возможного» к «в основном невозможному»? Связанные автоматы – это одномерная область (игроки владеют только одним секретным числом), для которой правдивость характеризуется простым условием монотонности, что позволяет использовать достаточно гибкие подходы алгоритмического дизайна. С другой стороны, несвязанные автоматы представляют собой многомерную область, и в алгоритмических условиях, подразумеваемых правдивостью в этом случае, работать сложнее. До сих пор неясно, подразумевают ли эти условия реальные математические невозможности или просто представляют собой более сложные препятствия, которые в принципе могут быть решены. Одной из многомерных областей планирования, возможности для которой известны, является случай <math>p_{ij} \in \{ L_j, H_j \}</math>, где «низкие» и «высокие» значения фиксированы и известны. Этот случай обобщает классическую многомерную модель ограниченных машин <math>(p_{ij} \in \{ p_j, \infty \} )</math> и допускает правдивую 3-аппроксимацию [27].

В эпоху электронной коммерции появился новый вид «цифровых товаров»: товары без предельных издержек производства – иначе говоря, товары с неограниченным объемом предложения. Одним из примеров являются песни, продаваемые через Интернет. Производство песни требует затрат, но после этого создание дополнительных электронных копий не влечет за собой никаких дополнительных расходов. Как следует продавать такие товары? Одним из вариантов может быть проведение ''аукциона'''. Аукцион представляет собой односторонний рынок, где монополист (аукционист) желает продать один или несколько товаров ряду покупателей.