4817
правок
Конкурентный аукцион: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
Определение 3. Честный аукцион A является / | '''Определение 3.''' Честный аукцион <math>\mathcal{A}</math> является '''<math>\beta</math>-конкурентным''' по отношению к <math>\mathcal{F}^{(m)}</math>, если для всех векторов заявок <math>\mathbf{b}</math> ожидаемая прибыль <math>\mathcal{A}</math> на <math>\mathbf{b}</math> удовлетворяет условию <math>E(\mathcal{A}(\mathbf{b})) \ge \frac{\mathcal{F}^{(m) (\mathbf{b})}}{\beta}</math>. | ||
Определение 4 ( | '''Определение 4 (CostShare<math>_C</math>)''' [10]. При наличии вектора заявок <math>\mathbf{b}</math> этот механизм находит наибольшее число <math>k</math>, такое, что наибольшие заявки <math>k</math> участников аукциона не меньше <math>C/k</math>. Каждому из таких <math>k</math> участников начисляется <math>C/k</math>. | ||
2: Вычислить | 1: Равномерно случайным образом разбить вектор заявок <math>\mathbf{b}</math> на два набора <math>\mathbf{b}'</math> и <math>\mathbf{b}''</math>. | ||
2: Вычислить <math>\mathcal{F}' = \mathcal{F}(\mathbf{b}')</math> и <math>\mathcal{F}'' = \mathcal{F}(\mathbf{b}'')</math>. | |||
3: Запустить | 3: Запустить CostShare<math>_{\mathcal{F}''}</math> на <math>\mathbf{b}'</math> и CostShare<math>_{\mathcal{F}'}</math> на <math>\mathbf{b}''</math>. | ||
Конкурентный аукцион, алгоритм 2. Аукцион с получением образцов и распределением затрат (Sampling Cost Sharing Auction, SCS) | Конкурентный аукцион, алгоритм 2. Аукцион с получением образцов и распределением затрат (Sampling Cost Sharing Auction, SCS) | ||
Теорема 2 [6]. SCS 4-конкурентен относительно | '''Теорема 2 [6]. SCS 4-конкурентен относительно <math>\mathcal{F}^{(2)}</math>, граница является строгой.''' | ||
Теорема 3 [9]. Пусть A – любой честный рандомизированный аукцион. Существует входной вектор заявок b, на котором | '''Теорема 3 [9]. Пусть <math>\mathcal{A}</math> – любой честный рандомизированный аукцион. Существует входной вектор заявок <math>\mathbf{b}</math>, на котором <math>E(\mathcal{A}(\mathbf{b})) \le \frac{\mathcal{F}^{(2)} (\mathbf{b})}{2,42}</math>.''' | ||
== Применение == | == Применение == | ||
