Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception

다음은 논문 "비대칭 정보 자원 할당 게임: 의도적 기만을 위한 선형 계획법 접근법"에 대한 상세한 기술적 요약입니다.

1. 문제 정의: 기만적 자원 할당 게임 (DRAG)

이 논문은 Defender(정보를 가진 에이전트)와 Attacker(정보를 갖지 않은 에이전트) 간에 그래프 $G=(S, E)$ 위에서 수행되는 이산 시간 동적 게임인 DRAG를 소개합니다.

• 설정: 자연 (Nature) 은 사전 확률 분포 $b_0$에 따라 후보 자산 집합 $\Theta$에서 "진짜 자산" $\theta_{true}$를 선택합니다. 이 정보는 Defender 에게만 비밀로 유지됩니다.
• 동역학:
  • Attacker는 그래프 위를 이동하여 진짜 자산에 도달하려 시도하며, 그곳에 축적된 자원을 최소화하려 합니다.
  • Defender는 각 시간 단계마다 제한된 방어 자원을 하나의 후보 자산에 할당합니다.
  • Attacker 는 Defender 의 할당 이력을 관찰하지만, 진짜 자산이 무엇인지는 알지 못합니다.
• 목표:
  • Defender: 진짜 자산에 축적된 총 자원을 최대화합니다. 이를 위해 Defender 는 진짜 자산을 보호하는 것과 동시에, Attacker 의 신념을 조작하기 위해 미끼 자산에 자원을 할당하여 Attacker 를 기만하는 것 사이에서 균형을 맞춰야 합니다.
  • Attacker: 관찰된 할당 이력으로부터 $\theta_{true}$를 추론하고 그곳으로 이동하여 진짜 자산의 자원을 최소화합니다.
• 주요 차이점: 이전의 "기만적 경로 계획 (Deceptive Path Planning, DPP)" 연구들에서는 정보를 가진 에이전트가 관찰 가능한 신호 (궤적) 를 통제했으나, DRAG 에서는 신호 (할당 이력) 가 두 에이전트의 상호작용에서 발생합니다. Defender 는 할당을 통해 신념에 영향을 미치지만, Attacker 가 상태 진화를 통제하므로 신념과 정책 간의 결합적 상호의존성이 발생합니다.

2. 방법론: PBNE 를 위한 선형 계획법

핵심적인 과제는 에이전트들이 베이즈 규칙을 통해 신념을 업데이트하면서 전략을 최적화하는 **완전 베이지안 내쉬 균형 (Perfect Bayesian Nash Equilibrium, PBNE)**을 계산하는 것입니다. Defender 의 정책과 Attacker 의 신념 업데이트 사이의 결합은 일반적으로 이를 비볼록하게 만들고 해결을 어렵게 만듭니다.

저자들은 PBNE 를 해결하기 위한 효율적이고 비반복적인 선형 계획법 (LP) 공식을 제안합니다.

A. 동적 계획법 (DP) 공식화

저자들은 먼저 게임 가치에 대한 DP 표현을 수립합니다. 그들은 사전 가치 (ex-ante value) 가 신념 $b_t$에 대해 선형이라는 점을 활용합니다.

• 그들은 Attacker 의 전략 $\sigma$와 Defender 의 전략 $\tau$에 대한 min-max 문제로 균형 가치 $V^*(h_t, b_t)$를 정의합니다.
• 결정적으로, 그들은 미래 가치가 Defender 의 현재 정책에 의존하는 확대된 신념 (scaled belief) $\alpha b_{t+1}$에 의존함을 보여줍니다.

B. 선형 계획법 변환

신념과 정책 간의 비선형 결합을 제거하기 위해, 저자들은 유형과 이력의 결합 분포를 인코딩하는 보조 변수를 도입합니다.

• Defender 의 LP: 그들은 Defender 가 유형 $\theta$일 확률과 이력 $h_t$가 실현될 확률, 그리고 취해진 행동을 결합한 $z^\theta_{h_t}$라는 변수를 정의합니다.
  • 이 변환은 신념과 정책의 곱을 포함하는 이차 (bilinear) 제약 조건을 선형 제약 조건으로 변환합니다.
  • 결과적으로 도출된 LP(식 18) 는 다음을 보장하는 제약 조건 하에서 Defender 의 기대 보상을 최대화합니다:
    1. 최적성: 모든 Attacker 행동에 대한 최선의 대응이 되는 전략입니다.
    2. 일관성: 결합 확률들은 게임 동역학과 베이즈 업데이트에 따라 올바르게 전파됩니다.
• Attacker 의 LP: Attacker 의 균형 전략은 Defender 의 LP 의 **쌍대 (dual)**에서 유도됩니다. Attacker 는 궤적을 따라 행동 확률을 인코딩하는 변수 $\eta$를 사용하여 기대 보상을 최소화합니다.

C. 정책 재구성

LP 가 풀리면 균형 전략은 정규화를 통해 재구성됩니다:

• Defender 정책: $\tau^\theta_{ht} = z^\theta_{ht} / \sum z^\theta_{ht}$.
• Attacker 정책: $\sigma_{ht} = \eta_{ht} / \sum \eta_{ht}$.

3. 주요 기여

1. 새로운 게임 공식화 (DRAG): 정보를 가진 에이전트 (Defender) 가 신호 (할당) 를 조작하지만 게임 상태 진화를 완전히 통제하지는 않는, 기만적 경로 계획의 이중 문제를 도입합니다.
2. 구조적 통찰: 정보를 가진 플레이어가 상태에 대한 완전한 통제 없이도 관찰 가능한 할당 이력의 분포를 형성함으로써 정보를 갖지 않은 플레이어의 신념 업데이트에 영향을 줄 수 있음을 입증합니다.
3. 효율적인 계산: 복잡한 신념 - 정책 결합에도 불구하고 PBNE 가 단일, 비반복적 선형 계획법을 통해 계산될 수 있음을 증명합니다. 이는 이전 연구 (2 개의 목표와 완전한 신호 통제에 국한됨) 를 여러 개의 후보 목표를 가진 임의의 그래프로 확장합니다.
4. 의도적 기만: 기만이 모호함을 위한 것이 아니라 Defender 의 성과를 향상시킬 때만 사용된다는 "의도적 기만"을 정의하고 특징화합니다.

4. 수치적 결과

저자들은 두 개의 후보 자산과 사전 확률 $b_0 = [0.2, 0.8]$을 가진 $4 \times 4$ 그리드 게임에서 이 접근법을 검증했습니다.

• 창발적 기만 행동:
  • LP 해는 Defender 가 Attacker 에게 특정 "모호한" 신념 ($b_1 \approx [0.53, 0.47]$) 을 생성하기 위해 초기에 할당을 무작위화함을 보여주었습니다.
  • 이 신념은 Attacker 가 중요한 결정 지점에서 자산 0 또는 자산 1 로 이동하는 것 사이에서 **무관심 (indifferent)**하게 만듭니다.
  • Attacker 가 무관심해지면 Defender 는 기만을 중단하고 진짜 자산에 자원을 집중합니다. 이는 기만의 "의도적" 성격을 확인시켜 줍니다. 즉, 기만은 Attacker 의 결정을 무력화시키는 상태에 도달하기 위해만 사용됩니다.
• 기만의 가치 (VoD):
  • 완전 정보 기준: 진짜 자산이 알려져 있었다면 Defender 의 기대 보상은 $-20.6$이었을 것입니다.
  • DRAG 균형: 기만을 통해 Defender 는 $-16.68$의 기대 보상을 달성합니다.
  • 결과: 이는 성능이 19% 개선된 것으로, Defender 의 정보 우위와 전략적 기만의 가치를 정량화합니다.
• 균형 검증:
  • 저자들은 어느 한 플레이어도 일방적인 편차 (deviation) 로부터 이익을 얻지 못함을 검증했습니다.
  • 기만을 무시하는 전략 (예: 항상 진짜 자산에 할당하는 것) 은 Attacker 에 의해 착취될 수 있으며, Defender 에게 더 나쁜 결과를 초래함이 입증되었습니다.

5. 의의

이 연구는 이론적 게임 이론과 적대적 환경에서의 실용적 자원 할당 사이의 간극을 메웁니다.

• 이론적: 결합된 신념 - 정책 동역학을 가진 게임에서 PBNE 를 해결하는 계산적 어려움을 해결하여 확장 가능한 LP 접근법을 제공합니다.
• 실용적: 자원이 제한되어 있고 보호뿐만 아니라 적을 능동적으로 오도하기 위해 할당되어야 하는 방어 시스템 (예: 사이버 보안, 군사 물류) 을 설계하기 위한 프레임워크를 제공합니다.
• 개념적: "모호함을 위한 기만"에서 "의도적 기만"으로의 패러다임 전환을 이룹니다. 여기서 목표는 Defender 의 효용을 극대화하는 특정 상태로 상대방의 신념을 유도하는 것입니다.

향후 연구로는 양측 정보 비대칭으로의 프레임워크 확장 및 대규모 환경에 대한 학습 기반 접근법의 적용이 제안되었습니다.