Что такое VCG auction (Vickrey-Clarke-Groves) и как он обеспечивает truthfulness?

Краткий тезис

VCG auction (аукцион Викри-Кларка-Гровса) — это механизм распределения ресурсов среди нескольких агентов, который стимулирует каждого участника называть свою истинную ценность ресурса (truthfulness). Он гарантирует allocative efficiency (максимизацию суммарной ценности) и individual rationality (никто не платит больше своей оценки). В контексте RAG|Agentic RAG VCG применяется для распределения дефицитных вычислительных ресурсов (например, GPU) между LLM-агентами, чтобы система работала оптимально и честно.

1. Определение VCG аукциона

VCG auction (Vickrey-Clarke-Groves) — это семейство аукционных механизмов, в которых:

• Allocation rule (правило распределения): ресурс достаётся тому агенту (или комбинации агентов), который максимизирует суммарную заявленную ценность (social welfare).
• Payment rule (правило платежа): каждый выигравший агент платит не свою заявку, а «внешний эффект» своего участия — разницу между оптимальной суммарной ценностью без него и суммарной ценностью остальных агентов при его участии.

Термин truthfulness (правдивость, или incentive compatibility) означает, что для каждого агента strategy|доминантная стратегия — сообщать свою истинную частную ценность ресурса, независимо от действий других.

2. История и контекст

Механизм назван в честь трёх экономистов:

• William Vickrey (1961) — предложил аукцион второй цены (auction|Vickrey auction) для одного товара.
• Edward H. Clarke (1971) — обобщил на случай нескольких товаров и ввёл правило платежа, основанное на «ущербе».
• Theodore Groves (1973) — дал общую теоретическую основу для механизмов с правдивостью.

VCG — это частный случай mechanism design (теории механизмов), где цель — создать правила игры, при которых рациональные агенты добровольно раскрывают свои истинные предпочтения.

3. Формальное описание VCG

Пусть есть множество агентов ( N = {1, \dots, n} ) и набор возможных распределений ресурса ( X ). Каждый агент ( i ) имеет частную ценность ( v_i(x) ) для каждого исхода ( x \in X ). Агенты сообщают заявки ( b_i(x) ) (возможно, не равные истинным ценностям).

Allocation rule: [ x^* = \arg\max_{x \in X} \sum_{i \in N} b_i(x) ]

Payment rule для агента ( i ): [ p_i = \max_{x \in X} \sum_{j \neq i} b_j(x) ;-; \sum_{j \neq i} b_j(x^*) ]

То есть агент ( i ) платит разницу между максимальной суммарной ценностью всех остальных агентов в мире без него и их суммарной ценностью при выбранном распределении ( x^* ).

Если агент не выигрывает (его вклад в social welfare нулевой), платёж равен 0.

4. Как VCG обеспечивает truthfulness (доказательство)

Ключевая идея: платёж агента не зависит от его собственной заявки напрямую, а только от того, как его заявка влияет на распределение. Агент может повлиять на исход только если его заявка изменит ( x^* ). Но если он завысит ценность, то может выиграть, но заплатит больше, чем его истинная ценность (риск переплаты). Если занизит — может проиграть, упустив выгоду. Оптимально — назвать истинную ценность.

Формально: полезность агента ( u_i = v_i(x^) - p_i ). Подставляя ( p_i ), получаем: [ u_i = v_i(x^) + \sum_{j \neq i} b_j(x^*) - \max_{x} \sum_{j \neq i} b_j(x) ]

Первые два слагаемых — это суммарная ценность всех агентов при исходе ( x^* ) (с учётом истинной ценности ( i )). Третье слагаемое — константа, не зависящая от заявки ( i ). Значит, агент максимизирует свою полезность, когда его заявка приводит к выбору ( x^* ), максимизирующему истинную суммарную ценность. А это достигается только при ( b_i = v_i ).

Таким образом, truthfulness — доминантная стратегия.

5. Allocative efficiency (эффективность распределения)

VCG гарантирует, что ресурс достанется тому, кто ценит его выше всего (в случае одного неделимого товара) или комбинации агентов с максимальной суммарной ценностью (в случае делимых ресурсов или нескольких товаров). Это свойство называется allocative efficiency (или Pareto efficiency в контексте распределения).

6. Individual rationality (индивидуальная рациональность)

Каждый агент участвует добровольно, если его полезность от участия неотрицательна. В VCG: [ u_i = v_i(x^) - p_i \ge 0 ] Это выполняется, потому что платёж ( p_i ) не превышает истинной ценности агента (доказательство: ( p_i \le \max_{x} \sum_{j \neq i} b_j(x) - \sum_{j \neq i} b_j(x^) \le v_i(x^*) ) при правдивых заявках). Никто не платит больше своей оценки.

7. Пример: распределение GPU между LLM-агентами

Представим систему Agentic RAG, где три LLM-агента (A, B, C) конкурируют за один GPU-ускоритель на один временной слот. Каждый агент имеет задачу, которую может выполнить только с GPU, и оценивает её ценность в условных единицах:

• Агент A: ценность = 100
• Агент B: ценность = 80
• Агент C: ценность = 120

Шаг 1: Allocation. VCG выбирает агента с максимальной заявкой (если все правдивы) — C (120). GPU достаётся C.

Шаг 2: Payment. Считаем, какова была бы максимальная суммарная ценность без C: max(A,B) = 100 (агент A). Суммарная ценность остальных (A и B) при участии C: они не получают GPU, их ценность 0. Платёж C = 100 - 0 = 100. Агент C платит 100, его чистая полезность = 120 - 100 = 20.

Если бы C завысил заявку до 150, платёж всё равно 100 (не зависит от его заявки), полезность остаётся 20. Если бы занизил до 90, он бы проиграл A (100 > 90) и получил 0 полезности. Значит, правдивая заявка — оптимальна.

8. Ограничения и недостатки VCG

9. Сравнение VCG с другими аукционами

10. Применение VCG в Agentic RAG и multi-agent systems

В архитектурах Agentic RAG несколько LLM-агентов могут конкурировать за:

• GPU-время для инференса
• Доступ к векторной базе данных (лимит запросов)
• Право на вызов внешнего инструмента (API с квотой)
• Память контекста (ограниченное окно)

VCG позволяет распределять эти ресурсы оптимально, стимулируя агентов сообщать истинную «срочность» или «ценность» своей задачи. Например, агент, обрабатывающий критический запрос пользователя, может указать высокую ценность, а фоновый агент — низкую. Система автоматически отдаст ресурс наиболее важному.

11. Пет-проект для закрепления

Задача: Реализовать симулятор VCG-аукциона для распределения одного GPU между тремя LLM-агентами.

Инструменты: Python (без внешних библиотек), можно использовать numpy для случайных значений.

Шаги:

1. Создать класс Agent с полями id, true_value, bid.
2. Реализовать функцию vcg_allocation(agents), которая:
   • Находит агента с максимальной заявкой (allocation).
   • Для каждого агента вычисляет платёж по формуле VCG.
   • Возвращает словарь {agent_id: (wins, payment)}.
3. Провести эксперимент: для каждого агента сгенерировать случайную истинную ценность (например, от 1 до 100). Затем для каждого агента перебрать возможные заявки (от 0 до 150) и вычислить его полезность при фиксированных заявках остальных (правдивых). Построить график зависимости полезности от заявки.
4. Убедиться, что максимум полезности достигается при заявке, равной истинной ценности.

Ожидаемый результат: График, подтверждающий truthfulness — пик полезности при bid = true_value.

Пример кода (фрагмент):

import random
import matplotlib.pyplot as plt

class Agent:
    def __init__(self, id, true_value):
        self.id = id
        self.true_value = true_value
        self.bid = true_value  # по умолчанию правдиво

def vcg(agents):
    # allocation: максимизируем сумму заявок (один ресурс)
    best_agent = max(agents, key=lambda a: a.bid)
    # payment for best_agent
    # сумма заявок остальных без best_agent
    others = [a for a in agents if a != best_agent]
    max_without = max(a.bid for a in others) if others else 0
    payment = max_without - 0  # остальные без ресурса дают 0
    return best_agent, payment

# симуляция
agents = [Agent(0, 100), Agent(1, 80), Agent(2, 120)]
winner, payment = vcg(agents)
print(f"Winner: Agent {winner.id}, payment {payment}")

12. Связь с другими вопросами

13. Навигация

• Предыдущий: 721
• Следующий: 723
• Индекс: 00. Индекс разборов

Навигация

• Предыдущий: 721
• Следующий: 723
• Индекс: 00. Индекс разборов