Конкурентный аукцион
Постановка задачи
В данной задаче изучается модель аукциона в один тур с закрытыми заявками, на котором аукционист хочет продать специфический товар с неограниченным количеством копий [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)
