Конкурентный аукцион: различия между версиями

В данной задаче изучается модель аукциона ''в один тур с закрытыми заявками'', на котором аукционист хочет продать специфический товар с неограниченным количеством копий <math>n</math> участникам торгов, и каждый участник <math>i \in \{ 1, ..., n \}</math> получит не более одного экземпляра.

Сначала для любого <math>i</math> участник торгов под номером <math>i</math> выставляет значение <math>b_i</math>, представляющее цену, которую он готов заплатить за экземпляр. Заявки подаются одновременно. Получив вектор заявок <math>\mathbf{b} = (b_1, ..., b_n)</math>, аукционист вычисляет и выдает вектор распределения <math>x = (x_1, ..., x_n) \in \{ 0, 1 \}^n</math> и вектор цен <math>\mathbf{p} = (p_1, ..., p_n)</math>. Если для некоторого <math>i</math> имеет место <math>x_i = 1</math>, то участник <math>i</math> получает экземпляр и платит за него цену <math>з_i</math>. В противном случае участник <math>i</math> проигрывает и ничего не платит. Доход аукциониста составляет <math>\sum_{i = 1}^n \mathbf{x} \mathbf{p}^T</math>.

'''Определение 1 (Оптимальный одноценовой аукцион F с предварительным знанием заявок)'''. Пусть дан вектор заявок <math>\mathbf{b}</math>, отсортированный в порядке убывания,

Далее, <math>\mathcal{F}^{(m)}(\mathbf{b}) = max_{m \le i \le n} \; i \cdot b_i</math>

Задача состоит в том, чтобы разработать ''честный'' аукцион, который мог бы максимизировать доход аукциониста. Аукцион является ''честным'', если для каждого участника <math>i</math> предложение его истинной ценности максимизирует его выигрыш, независимо от заявок, поданных другими участниками [11, 12].