Конкурентный аукцион
Постановка задачи
В данной задаче изучается модель аукциона с закрытыми заявками в один тур, на котором аукционист хочет продать спефицический товар с неограниченным количеством копий n участникам торгов, и каждый участник i 2 f1... ; ng получит не более одного экземпляра.
Сначала для любого i участник торгов i выставляет значение bi, представляющее цену, которую он готов заплатить за экземпляр. Заявки подаются одновременно. Получив вектор заявок b = (b 1... ; bn), аукционист вычисляет и выдает вектор распределения x = (x1... ; xn) 2 f0; 1gn и вектор цен p = (p1 ; : : : ; pn). Если для любого i, xi = 1, то участник i получает экземпляр и платит за него цену pi. В противном случае участник i проигрывает и ничего не платит. Доход аукциониста составляет ELxp1.
Определение 1 (Оптимальный одноценовой аукцион F с предварительным знанием заявок). Пусть дан вектор заявок b, отсортированный в порядке убывания,
Далее,
Очевидно, что F максимизирует доход аукциониста, если допускается только единая цена.
Однако в этой задаче каждый участник аукциона i связан с частным значением vi, представляющим ценность экземпляра товара по его мнению. Таким образом, если участник i получает товар, его выигрыш должен быть равен vi - pi. В противном случае выигрыш равен 0. Таким образом, для любого участника торгов i его функция выигрыша может быть сформулирована как (vi - pj)xj. Кроме того, в модели допускается свобода воли. Другими словами, каждый участник аукциона предлагает цену bi, отличную от его истинной ценности vi, чтобы максимизировать свой выигрыш.
Задача состоит в том, чтобы разработать честный аукцион, который мог бы максимизировать доход аукциониста. Аукцион является честным, если для каждого участника i предложение его истинной ценности максимизирует его выигрыш, независимо от заявок, поданных другими участниками [11, 12].
Определение 2 (конкурентные аукционы).
Дано: вектор поданных заявок b.
Требуется: получить вектор распределения x и вектор цен p.
Ограничения:
(а) Честность
(б) Доход аукциониста отличается от оптимальной единой цены для всех входных данных не более чем на константный коэффициент.
Основные результаты
Пусть b_, = (foi,... , bj-i, bj+i,... , bn). f - любая функция от b_, к цене.
Конкурентный аукцион, алгоритм 1. Аукцион, не зависящий от заявок: Af (b)
Теорема 1 [6]. Аукцион является честным тогда и только тогда, когда он эквивалентен аукциону, не зависящему от заявок.
Определение 3. Честный аукцион A является /3-конкурентным по отношению к F(m), если для всех векторов заявок b ожидаемая прибыль A на b удовлетворяет условию
Определение 4 (CostShareC) [ ]. Учитывая заявки b, этот механизм находит наибольшее число k, такое, что наибольшие заявки k участников аукциона не меньше C/k. Каждому из таких k участников начисляется C/k.
1: Равномерно случайным образом разбить вектор заявок b на два набора b0 и b00.
2: Вычислить f = F(b0) и F00 = F(b00).
3: Запустить CostShareF00 на b0 и CostShareF0 на b00.
Конкурентный аукцион, алгоритм 2. Аукцион с получением образцов и распределением затрат (Sampling Cost Sharing Auction, SCS)
Теорема 2 [6]. SCS 4-конкурентен относительно J:<-2\, граница является строгой.
Теорема 3 [9]. Пусть A – любой честный рандомизированный аукцион. Существует входной вектор заявок b, на котором ВДЬ)) < Л
Применение
С ростом популярности Интернета появляется все больше аукционов, где продаются самые разные предметы – от антиквариата и картин до цифровых товаров, таких как 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)