Blotto- spil (Colonel Blotto-spil) er en klasse af to-personers nulsumsspil, hvor spillernes opgave er at fordele begrænsede ressourcer over flere objekter (slagmarker). I den klassiske version af spillet vinder den spiller, der placerede flere ressourcer på banen, kampen på dette felt, og den samlede gevinst (spillets pris) er lig med summen af de vundne kampe.
Selvom oberst Blottos spil først blev udgivet af Borel [1] i 1921, blev de fleste af variationerne på det klassiske spil først løst i '91. I 2006 beskrev Roberson ligevægtsprisen for et klassisk spil for et vilkårligt antal felter og ethvert niveau af ressourcer, samt karakteristiske ligevægtssæt for de fleste variationer af det klassiske spil. [2]
Spillet er opkaldt efter den mytiske oberst Botto fra Gross og Wagners værk fra 1950 [3] . Obersten måtte finde den optimale fordeling af sine soldater på tværs af N slagmarker, vel vidende at:
Forestil dig som eksempel et spil, hvor to spillere skriver tre positive heltal ned i ikke-faldende rækkefølge, hvis sum er forudbestemt (=S). Derefter sammenligner begge spillere tallene (i rækkefølge). Den spiller, der har flere tal i to positioner, vinder.
For S = 6 er der kun tre muligheder: (2, 2, 2), (1, 2, 3) og (1, 1, 4). Det er let at se, at:
Enhver triple mod samme uafgjort; (1, 1, 4) vs. (1, 2, 3) remis; (1, 2, 3) vs. (2, 2, 2) uafgjort; (2, 2, 2) slag (1, 1, 4).Derfor er (2, 2, 2) den optimale strategi, da den vinder i ét tilfælde og ikke taber i alle andre. Men hvis begge spillere vælger strategien (2, 2, 2) eller (1, 2, 3), så kan ingen af spillerne slå den anden ved at ændre strategien, så hvert sådant par er en Nash Equilibrium .
Efterhånden som tallet S stiger, bliver analysen mere og mere vanskelig. For S = 12 kan det vises, at (2, 4, 6) er den optimale strategi, men for S > 12 er deterministiske strategier ikke optimale. For S = 13, viser det sig at være en optimal blandet strategi at vælge (3, 5, 5), (3, 3, 7) og (1, 5, 7) med sandsynlighed 1/3 for hver.
For at finde blandede løsninger af spillet kan man bruge variabel basismetoden , hvor et matrixspil reduceres til et lineært programmeringsproblem . Den resulterende matrix vil have et stort antal rækker og kolonner (svarende til antallet af strategier), men det behøver ikke at blive gemt - matrixelementerne kan hentes programmatisk på det rigtige tidspunkt. I dette tilfælde vil størrelsen af basismatrixen være lille.
Det amerikanske præsidentvalg i 2000 , en af de nærmeste kandidater på ranglisten, blev modelleret som Blotto's Game. [4] Avisen hævder, at Horus havde en strategi, der ville føre ham til at vinde, men han fandt den ikke.