Конкурентный аукцион

Постановка задачи

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

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

Определение 1 (Оптимальный одноценовой аукцион [math]\displaystyle{ \mathcal{F} }[/math] с предварительным знанием заявок). Пусть дан вектор заявок [math]\displaystyle{ \mathbf{b} }[/math], отсортированный в порядке убывания, [math]\displaystyle{ \mathcal{F}(\mathbf{b}) = max_{1 \le i \le n} \; i \cdot b_i }[/math].

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

Очевидно, что [math]\displaystyle{ \mathcal{F} }[/math] максимизирует доход аукциониста, если допускается только единая цена.

Однако в этой задаче каждый участник аукциона [math]\displaystyle{ i }[/math] ассоциирован с частным значением [math]\displaystyle{ v_i }[/math], представляющим ценность экземпляра товара по его мнению. Таким образом, если участник [math]\displaystyle{ i }[/math] получает товар, его выигрыш должен быть равен [math]\displaystyle{ v_i - p_i }[/math]. В противном случае выигрыш равен 0. Таким образом, для любого участника торгов [math]\displaystyle{ i }[/math] его функция выигрыша может быть сформулирована как [math]\displaystyle{ (v_i - p_i)x_i }[/math]. Кроме того, в модели допускается свобода воли. Другими словами, каждый участник аукциона предлагает цену [math]\displaystyle{ b_i }[/math], отличную от его истинной ценности [math]\displaystyle{ v_i }[/math], чтобы максимизировать свой выигрыш.

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

Определение 2 (конкурентные аукционы).

Дано: вектор поданных заявок [math]\displaystyle{ \mathbf{b} }[/math].

Требуется: получить вектор распределения [math]\displaystyle{ \mathbf{x} }[/math] и вектор цен [math]\displaystyle{ \mathbf{p} }[/math].

Ограничения:

(а) Честность

(б) Доход аукциониста отличается от оптимальной единой цены для всех входных данных не более чем на константный коэффициент.

Основные результаты

Пусть [math]\displaystyle{ \mathbf{b}_{- i} = (b_1,..., b_{i-1}, b_{i+1}, ..., b_n) }[/math]. [math]\displaystyle{ f }[/math] - любая функция, связывающая [math]\displaystyle{ \mathbf{b}_{-i} }[/math] с ценой.

  1: for i = 1 to n do
  2:    if [math]\displaystyle{ f(\mathbf{b}_{- i}) \le b_i }[/math] then
  3:       [math]\displaystyle{ x_i = 1 }[/math] и [math]\displaystyle{ p_i = f(\mathbf{b}_i) }[/math]
  4:    else
  5:       [math]\displaystyle{ x_i = 0 }[/math]
  6:    end if
  7: end for

Конкурентный аукцион, алгоритм 1. Аукцион, не зависящий от заявок: [math]\displaystyle{ \mathcal{A}_f (b) }[/math]

Теорема 1 [6]. Аукцион является честным тогда и только тогда, когда он эквивалентен аукциону, не зависящему от заявок.

Определение 3. Честный аукцион [math]\displaystyle{ \mathcal{A} }[/math] является [math]\displaystyle{ \beta }[/math]-конкурентным по отношению к [math]\displaystyle{ \mathcal{F}^{(m)} }[/math], если для всех векторов заявок [math]\displaystyle{ \mathbf{b} }[/math] ожидаемая прибыль [math]\displaystyle{ \mathcal{A} }[/math] на [math]\displaystyle{ \mathbf{b} }[/math] удовлетворяет условию [math]\displaystyle{ E(\mathcal{A}(\mathbf{b})) \ge \frac{\mathcal{F}^{(m) (\mathbf{b})}}{\beta} }[/math].

Определение 4 (CostShare[math]\displaystyle{ _C }[/math]) [10]. При наличии вектора заявок [math]\displaystyle{ \mathbf{b} }[/math] этот механизм находит наибольшее число [math]\displaystyle{ k }[/math], такое, что заявки [math]\displaystyle{ k }[/math] участников аукциона, предложивших максимальные ставки, не меньше [math]\displaystyle{ C/k }[/math]. С каждого из таких [math]\displaystyle{ k }[/math] участников взимается [math]\displaystyle{ C/k }[/math].

  1: Равномерно случайным образом разбить вектор заявок [math]\displaystyle{ \mathbf{b} }[/math] на два набора [math]\displaystyle{ \mathbf{b}' }[/math] и [math]\displaystyle{ \mathbf{b}'' }[/math].
  2: Вычислить [math]\displaystyle{ \mathcal{F}' = \mathcal{F}(\mathbf{b}') }[/math] и [math]\displaystyle{ \mathcal{F}'' = \mathcal{F}(\mathbf{b}'') }[/math]. 
  3: Запустить CostShare[math]\displaystyle{ _{\mathcal{F}''} }[/math] на [math]\displaystyle{ \mathbf{b}' }[/math] и CostShare[math]\displaystyle{ _{\mathcal{F}'} }[/math] на [math]\displaystyle{ \mathbf{b}'' }[/math].

Конкурентный аукцион, алгоритм 2. Аукцион с получением образцов и распределением затрат (Sampling Cost Sharing Auction, SCS)

Теорема 2 [6]. SCS 4-конкурентен относительно [math]\displaystyle{ \mathcal{F}^{(2)} }[/math], граница является строгой.

Теорема 3 [9]. Пусть [math]\displaystyle{ \mathcal{A} }[/math] – любой честный рандомизированный аукцион. Существует входной вектор заявок [math]\displaystyle{ \mathbf{b} }[/math], на котором [math]\displaystyle{ E(\mathcal{A}(\mathbf{b})) \le \frac{\mathcal{F}^{(2)} (\mathbf{b})}{2,42} }[/math].

Применение

С ростом популярности Интернета появляется все больше аукционов, где продаются самые разные предметы – от антиквариата и картин до цифровых товаров, таких как mp3-файлы, лицензии и сетевые ресурсы. Честные аукционы могут снизить затраты участников на изучение стратегий конкурентов, поскольку поощряют участников заявлять свои истинные цены. С другой стороны, конкурентные аукционы также могут гарантировать прибыль аукционистов. Таким образом, данная задача является очень практичной и значимой. Разработка и анализ конкурентных аукционов в рамках различных моделей аукционов стали актуальной темой [1, 2, 3, 4, 5, 7, 8].

См. также

• Ценообразование процессорного времени
• Многотоварные аукционы с ограничением бюджета

Литература

1. Abrams, Z.: Revenue maximization when bidders have budgets. In: Proceedings of the seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-06), Miami, FL, 22-26 January 2006, pp. 1074-1082. ACM Press, New York (2006)

2. Bar-Yossef, Z., Hildrum, K., Wu, F.: Incentive-compatible online auctions for digital goods. In: Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02), New York, 6-8 January 2002, pp. 964-970. ACM Press, New York (2002)

3. Borgs, C., Chayes, J.T., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: ACM Conference on Electronic Commerce (EC-05), 2005, pp. 44-51

4. Bu, T.-M., Qi, Q., Sun, A.W.: Unconditional competitive auctions with copy and budget constraints. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) Internet and Network Economics, 2nd International Workshop, WINE 2006, Pa-tras, Greece, 15-17 Dec 2006. Lecture Notes in Computer Science, vol. 4286, pp. 16-26. Springer, Berlin (2006)

5. Deshmukh, K., Goldberg, A.V., Hartline, J.D., Karlin, A.R.: Truthful and competitive double auctions. In: Mohring, R.H., Raman, R. (eds.) Algorithms-ESA2002, 10th Annual European Symposium, Rome, Italy, 17-21 Sept 2002. Lecture Notes in Computer Science, vol. 2461, pp. 361-373. Springer, Berlin (2002)

6. Fiat, A., Goldberg, A.V., Hartline, J.D., Karlin, A.R.: Competitive generalized auctions. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC-02), New York, 19-21 May 2002, pp. 72-81. ACM Press, New York (2002)

7. Goldberg, A.V., Hartline, J.D.: Competitive auctions for multiple digital goods. In: auf der Heide, F.M. (ed.) Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, 28-31 Aug 2001. Lecture Notes in Computer Science, vol. 2161, pp. 416^27. Springer, Berlin (2001)

8. Goldberg, A.V. Hartline, J.D.: Envy-free auctions for digital goods. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC-03), New York, 9-12 June 2003, pp. 29-35. ACM Press, New York (2003)

9. Goldberg, A.V., Hartline, J.D., Wright, A.: Competitive auctions and digital goods. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01), New York, 7-9 January 2001, pp. 735-744. ACM Press, New York (2001)

10. Moulin, H.: Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice and Welfare, 16, 279-320(1999)

11. Nisan, N.and Ronen, A.: Algorithmic mechanism design. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC-99), New York, May 1999, pp. 129-140. Association for Computing Machinery, New York (1999)

12. Parkes, D.C.: Chapter 2: Iterative Combinatorial Auctions. Ph. D. thesis, University of Pennsylvania (2004)