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

1. Probleemdefinitie: Het Deceptieve Resource Allocation Game (DRAG)

Het artikel introduceert DRAG, een discrete-tijd dynamisch spel dat wordt gespeeld op een graaf $G=(S, E)$ tussen een Verdediger (informatiegedragen agent) en een Aanvaller (oninformatiegedragen agent).

• Opzet: De natuur selecteert een "echt bezit" $\theta_{true}$ uit een set van kandidaat-besit $\Theta$ volgens een a priori verdeling $b_0$. Deze informatie is privé voor de Verdediger.
• Dynamiek:
  • De Aanvaller beweegt over de graaf en probeert het echte bezit te bereiken om de daar geaccumuleerde middelen te minimaliseren.
  • De Verdediger wijst op elk tijdstip beperkte defensieve middelen toe aan één kandidaat-besit.
  • De Aanvaller observeert de toewijzingsgeschiedenis van de Verdediger, maar kent het echte bezit niet.
• Doelstelling:
  • Verdediger: Maximaliseer de totale middelen die op het echte bezit worden geaccumuleerd. Om dit te doen, moet de Verdediger een balans vinden tussen het beschermen van het echte bezit en het bedriegen van de Aanvaller door middelen toe te wijzen aan decoys om de overtuiging van de Aanvaller te manipuleren.
  • Aanvaller: Minimaliseer de middelen op het echte bezit door $\theta_{true}$ af te leiden uit de waargenomen toewijzingsgeschiedenis en er naartoe te navigeren.
• Belangrijk onderscheid: In tegenstelling tot eerdere werken over "Deceptive Path Planning" (DPP), waarbij de geïnformeerde agent het waarneembare signaal (traject) controleert, ontstaat het signaal (toewijzingsgeschiedenis) in DRAG uit de interactie van beide agenten. De Verdediger beïnvloedt overtuigingen via toewijzingen, maar de Aanvaller controleert de evolutie van de staat, wat een gekoppelde onderlinge afhankelijkheid van overtuiging en beleid creëert.

2. Methodologie: Lineaire Programmering voor PBNE

De kernuitdaging is het berekenen van het Perfect Bayesian Nash Equilibrium (PBNE), waarbij agenten strategieën optimaliseren terwijl ze overtuigingen bijwerken via de regel van Bayes. De koppeling tussen het beleid van de Verdediger en de bijwerkingen van de overtuigingen van de Aanvaller maakt dit doorgaans niet-convex en moeilijk op te lossen.

De auteurs stellen een efficiënte, niet-iteratieve Lineaire Programmering (LP)-formulering voor om het PBNE op te lossen.

A. Dynamische Programmering (DP) Formulering

De auteurs stellen eerst een DP-representatie voor de spelwaarde vast. Zij benutten de lineariteit van de ex-ante waarde met betrekking tot de overtuiging $b_t$.

• Zij definiëren de evenwichtswaarde $V^*(h_t, b_t)$ als een min-max-probleem over de strategie $\sigma$ van de Aanvaller en de strategie $\tau$ van de Verdediger.
• Cruciaal tonen zij aan dat de toekomstige waarde afhangt van de geschaalde overtuiging $\alpha b_{t+1}$, waarbij de schalingsfactor $\alpha$ afhangt van het huidige beleid van de Verdediger.

B. De Lineaire Programmering Transformatie

Om de niet-lineaire koppeling tussen overtuigingen en beleidslijnen te elimineren, introduceren de auteurs hulpvariabelen die de gezamenlijke verdeling van types en geschiedenissen coderen:

• LP van de Verdediger: Zij definiëren variabelen $z^\theta_{h_t}$ die de gezamenlijke waarschijnlijkheid vertegenwoordigen dat de Verdediger van type $\theta$ is en dat de geschiedenis $h_t$ realiseert, gecombineerd met de ondernomen actie.
  • Deze transformatie zet de bilineaire constraints (die producten van overtuigingen en beleidslijnen bevatten) om in lineaire constraints.
  • De resulterende LP (Vergelijking 18) maximaliseert de verwachte uitbetaling van de Verdediger, onderworpen aan constraints die ervoor zorgen dat:
    1. Optimaliteit: De strategie een beste reactie is tegen alle acties van de Aanvaller.
    2. Consistentie: De gezamenlijke kansen correct voortvloeien volgens de spel-dynamiek en Bayesiaanse updates.
• LP van de Aanvaller: De evenwichtsstrategie van de Aanvaller wordt afgeleid uit het dual van de LP van de Verdediger. De Aanvaller minimaliseert de verwachte uitbetaling, met behulp van variabelen $\eta$ om actiewaarschijnlijkheden langs trajecten te coderen.

C. Beleidsreconstructie

Zodra de LP is opgelost, worden de evenwichtsstrategieën gereconstrueerd via normalisatie:

• Beleid Verdediger: $\tau^\theta_{ht} = z^\theta_{ht} / \sum z^\theta_{ht}$.
• Beleid Aanvaller: $\sigma_{ht} = \eta_{ht} / \sum \eta_{ht}$.

3. Belangrijkste Bijdragen

1. Nieuwe Spelformulering (DRAG): Introduceert een dual probleem voor Deceptive Path Planning waarbij de geïnformeerde agent (Verdediger) signalen (toewijzingen) manipuleert, maar de evolutie van de spelstaat niet volledig controleert.
2. Structureel Inzicht: Demonstreert dat de geïnformeerde speler de bijwerkingen van overtuigingen van de oninformatiegedragen speler kan beïnvloeden door de verdeling van waarneembare toewijzingsgeschiedenissen te vormen, zelfs zonder volledige controle over de staat.
3. Efficiënte Berekening: Bewijst dat ondanks de complexe koppeling tussen overtuiging en beleid, het PBNE kan worden berekend via een enkele, niet-iteratieve Lineaire Program. Dit breidt eerdere werken (beperkt tot 2 doelen en volledige signaalcontrole) uit tot willekeurige grafen met meerdere kandidaat-doelen.
4. Doelbewuste Bedrog: Definieert en karakteriseert "doelbewuste bedrog", waarbij bedrog uitsluitend wordt ingezet wanneer het de prestaties van de Verdediger verbetert, en niet omwille van ambiguïteit.

4. Numerieke Resultaten

De auteurs hebben de aanpak gevalideerd op een $4 \times 4$ raster-spel met twee kandidaat-besit en een a priori $b_0 = [0.2, 0.8]$.

• Ontstaande Deceptief Gedrag:
  • De LP-oplossing onthulde dat de Verdediger aanvankelijk toewijzingen randomiseert om een specifieke "ambigu" overtuiging ($b_1 \approx [0.53, 0.47]$) bij de Aanvaller te creëren.
  • Deze overtuiging maakt de Aanvaller onverschillig tussen het bewegen naar Bezit 0 of Bezit 1 op een kritisch beslispunt.
  • Zodra de Aanvaller onverschillig is, stopt de Verdediger met bedriegen en concentreert de middelen op het echte bezit. Dit bevestigt het "doelbewuste" karakter van de bedrog: het wordt uitsluitend gebruikt om een staat te bereiken waarin de beslissing van de Aanvaller wordt geneutraliseerd.
• Waarde van Bedrog (VoD):
  • Full Information Baseline: Als het echte bezit bekend was, zou de verwachte uitbetaling van de Verdediger $-20.6$ zijn.
  • DRAG Evenwicht: Met bedrog bereikt de Verdediger een verwachte uitbetaling van $-16.68$.
  • Resultaat: Dit vertegenwoordigt een 19% verbetering in prestaties, wat de waarde van het informatievoordeel en de strategische bedrog van de Verdediger kwantificeert.
• Evenwichtsvalidatie:
  • De auteurs verifieerden dat geen enkele speler baat heeft bij een eenzijdige afwijking.
  • Strategieën die bedrog negeren (bijvoorbeeld altijd toewijzen aan het echte bezit) bleken uitbuitbaar door de Aanvaller, wat leidde tot slechtere resultaten voor de Verdediger.

5. Betekenis

Dit werk overbrugt de kloof tussen theoretische speltheorie en praktische resource-allocation in vijandige omgevingen.

• Theoretisch: Het lost de computationele moeilijkheid op van het oplossen van PBNE in spellen met gekoppelde overtuigings-beleid dynamiek, en biedt een schaalbare LP-aanpak.
• Praktisch: Het biedt een raamwerk voor het ontwerpen van verdedigingssystemen (bijvoorbeeld cyberveiligheid, militaire logistiek) waarbij middelen beperkt zijn en niet alleen voor bescherming moeten worden toegewezen, maar ook om tegenstanders actief te misleiden.
• Conceptueel: Het verschuift het paradigma van "bedrog voor ambiguïteit" naar "doelbewuste bedrog", waarbij het doel is om de overtuigingen van de tegenstander te sturen naar een specifieke staat die de nuttigheid van de verdediger maximaliseert.

Toekomstig werk dat wordt voorgesteld, omvat het uitbreiden van het raamwerk naar tweezijdige informatieasymmetrie en het toepassen van leer-gebaseerde benaderingen op grootschalige omgevingen.