Technische Samenvatting: Optimale Beleidsleer onder Budget- en Dekkingsbeperkingen

1. Probleemstelling

Het artikel behandelt het probleem van optimale beleidsleer in situaties waarin een beleidsmaker een beperkt hulpbron (behandeling) moet toewijzen aan een populatie van $N$ eenheden om de totale welvaart (verwachte winst) te maximaliseren. De toewijzing is onderworpen aan twee gelijktijdige beperkingen:

1. Budgetbeperking: De totale kosten van de behandeling mogen een vast budget $B$ (of een budget per hoofd $C$) niet overschrijden.
2. Minimale dekkingsbeperking: Een minimaal fractie $\rho$ van de populatie moet worden behandeld.

Dit probleem doet zich voor in contexten zoals openbare werkgelegenheidstrainingen, medische interventies of sociale uitkeringen, waar efficiëntie (het maximaliseren van winst) in evenwicht moet worden gebracht met rechtvaardigheid of politieke vereisten (het waarborgen van brede dekking). De kernuitdaging is dat de optimale oplossing het selecteren van een subset van eenheden uit een exponentieel grote verzameling alternatieven ($2^N$) vereist, wat een combinatorisch optimalisatieprobleem vormt dat NP-moeilijk is.

2. Methodologie en Theoretisch Kader

2.1 Primaal-Duale Karakterisering

De auteur formuleert het probleem binnen een kader van potentiële uitkomsten. Laat $\tau(x)$ het conditioneel gemiddelde behandelingseffect (CATE) zijn en $c(x)$ de kosten van het behandelen van een individu met covariaten $x$. Het doel is het maximaliseren van $E[\pi(X)\tau(X)]$ onderworpen aan $E[\pi(X)c(X)] \leq C$ en $E[\pi(X)] \geq \rho$.

Met behulp van Lagrange-dualiteit stelt het artikel vast dat het optimale beleid $\pi^*$ de vorm aanneemt van een affiene drempelregel:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
waarbij:

• $\lambda^*$ de schaduwprijs is van de budgetbeperking.
• $\nu^*$ de schaduwprijs is van de dekkingsbeperking.
• De regel een individu behandelt als hun voordeel, gecorrigeerd voor de schaduwprijs van de dekking, de kosten overschrijdt die zijn geschaald met de schaduwprijs van het budget.

Deze structuur verschilt van standaard budgetbeperkte problemen (die een eenvoudige ratio-regel opleveren: $\tau(x)/c(x) \geq \lambda^*$), omdat de dekkingsbeperking een additieve verschuiving ($\nu^*$) introduceert, wat een heterogene beslissingsgrens creëert.

2.2 Knapsack-equivalentie en LP-relaxatie

Het empirische tegenhanger van het probleem blijkt equivalent te zijn aan een 0-1 knapsack-probleem met een extra kardinaliteitsbeperking.

• Combinatorische vorm: Selecteer een binaire vector $d \in \{0,1\}^n$ om $\sum \hat{\tau}_i d_i$ te maximaliseren onderworpen aan $\sum c_i d_i \leq nC$ en $\sum d_i \geq n\rho$.
• Lineaire programmering (LP) relaxatie: De binaire beperking wordt losgelaten tot $z_i \in [0,1]$.

Een cruciaal theoretisch resultaat is de analyse van de integraliteitskloof (het verschil tussen de optimale LP-waarde en de optimale 0-1-waarde). Het artikel bewijst dat:

1. Elk extreem punt van de LP-relaxatie hooguit twee fractionele componenten heeft.
2. Bijgevolg is de absolute integraliteitskloof begrensd door een constante $O(1)$ (specifiek $2V_{max}$).
3. In termen per hoofd verdwijnt de kloof asymptotisch als $O(1/n)$. Dit impliceert dat de LP-relaxatie asymptotisch equivalent is aan de discrete optimale oplossing.

2.3 Implementeerbare Algoritmen

Gebaseerd op de LP-relaxatie en de affiene drempelstructuur worden twee algoritmen voorgesteld:

1. Gierig-Lagrangiaans met Dekking (GLC):

   • Mechanisme: Een primaal-duale zoektocht naar de budget-schaduwprijs $\lambda$. Voor een vaste $\lambda$ worden eenheden gescoord op basis van $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procedure: Het algoritme handhaaft de dekkingsbeperking door de top $K_n$ (minimaal vereiste) eenheden op basis van score naar de behandelset te forceren, en voegt vervolgens gretig resterende eenheden met positieve scores toe totdat het budget is uitgeput. De multiplier $\lambda$ wordt via bisection afgestemd om aan de budgetbeperking te voldoen.
   • Complexiteit: $O(n \log n \cdot \log(1/\varepsilon))$.

2. Rank-and-Cut (RC):

   • Mechanisme: Een niet-iteratieve, heuristische regel die eenheden uitsluitend rangschikt op basis van de kosten-effectiviteitsratio $s_i = \hat{\tau}_i / c_i$.
   • Procedure: Eenheden worden gesorteerd op $s_i$ in aflopende volgorde. Het algoritme selecteert het grootste haalbare prefix dat voldoet aan zowel de budget- als de dekkingsbeperking.
   • Complexiteit: $O(n \log n)$.

3. Belangrijkste Resultaten

3.1 Asymptotische Optimaliteit

Het artikel stelt vast dat het GLC-algoritme asymptotisch optimaal is. Omdat de LP-relaxatie een verdwijnende integraliteitskloof per hoofd heeft, is elke haalbare gierige regel die de LP-optimum benadert (wat GLC doet), ook asymptotisch optimaal voor het oorspronkelijke combinatorische probleem.

3.2 Prestaties van Rank-and-Cut (RC)

Het artikel biedt een precieze karakterisering van wanneer de eenvoudigere RC-regel bij benadering optimaal is. Het welvaartverlies van RC ten opzichte van het optimale beleid wordt gedreven door het verschil tussen de constante drempel die door RC wordt gebruikt en de heterogene affiene drempel van het optimale beleid.

• Voorwaarde voor equivalentie: RC is bij benadering optimaal als:
  1. Kosten homogeen zijn ($c(x) \approx c_0$), OF
  2. De dekkingsbeperking niet bindend is ($\nu^* \approx 0$).
• Voorwaarde voor verkeerde toewijzing: Significante verkeerde toewijzing treedt alleen op wanneer kostenheterogeniteit substantieel is EN de dekkingsbeperking bindend is ($\nu^* > 0$). In dit specifieke regime kan de affiene grens van het optimale beleid niet worden gerepliceerd door een eenvoudige op ratio gebaseerde rangschikking, wat leidt tot de behandeling van eenheden met een lage ratio (om aan de dekking te voldoen) en de uitsluiting van eenheden met een hoge ratio (vanwege het budget).

3.3 Monte Carlo-bewijs

Twee simulatiestudies ondersteunen de theoretische bevindingen:

1. GLC versus LP: Naarmate de steekproefgrootte $n$ toeneemt, neemt het regret per hoofd van GLC ten opzichte van de exacte optimale oplossing (MILP) snel af en stabiliseert op lage niveaus. De LP-integraliteitskloof verdwijnt ook snel, wat de convergentie van $O(1/n)$ bevestigt.
2. RC versus LP: Simulaties over vier regimes (variërende kostenheterogeniteit en dekkingsstrakheid) bevestigen dat verkeerde toewijzing tussen RC en het optimale beleid verwaarloosbaar is in alle gevallen, behalve wanneer kosten heterogeen zijn en de dekking bindend is. In dat specifieke "worst-case" scenario is het gebied van verkeerde toewijzing significant (~15%), wat het theoretische interactie-effect valideert.

4. Bijdragen en Betekenis

Het artikel levert drie primaire bijdragen:

1. Structurele Representatie: Het biedt een structurele karakterisering van beperkte beleidsleer als een knapsack-achtig probleem met een affiene drempelregel die twee schaduwprijzen omvat, waarbij expliciet de interactie tussen budget- en dekkingsbeperkingen wordt gemodelleerd.
2. Asymptotische Strakheid: Het stelt vast dat de LP-relaxatie van dit combinatorische probleem een integraliteitskloof van $O(1)$ heeft, wat asymptotische equivalentie tussen de relaxeerde en discrete oplossingen in termen per hoofd bewijst. Dit rechtvaardigt het gebruik van eenvoudigere, schaalbare regels in grootschalige toepassingen.
3. Implementatie en Grenzen: Het stelt twee schaalbare algoritmen voor en analyseert deze (GLC en RC). Cruciaal identificeert het de precieze structurele voorwaarden waaronder de eenvoudige, niet-iteratieve RC-regel faalt. Het artikel overbrugt de kloof tussen statistische beleidsleer en combinatorische optimalisatie, en biedt een kader dat zowel theoretisch onderbouwd als computationeel schaalbaar is.

De betekenis van het werk ligt in het vermogen om verder te gaan dan de theoretische karakterisering van optimale beleidslijnen om implementeerbare, schaalbare oplossingen te bieden met prestatiegaranties. Het verduidelijkt dat hoewel eenvoudige rangschikking op kosten-effectiviteit vaak voldoende is, beleidsmakers zich bewust moeten zijn van de specifieke structurele voorwaarden (heterogene kosten + bindende dekking) waarbij dergelijke heuristieken kunnen leiden tot significante welvaartverliezen.