In this paper we provide textual evidence on the sophistication of medieval deterrence strategies. Drawing on one of the great opera librettos based on medieval sources, Wagner's Tannhäuser, we shall illustrate the use of optimal randomization strategies that can be derived by applying notions of dominance or trembling-hand perfection. Particular attention is paid to the employed randomization device.