Tysta dueller—Konstruera lösningen del 1 || Math ∩ Programmering

Tidigare inlägg i den här serien:

Tysta dueller och ett gammalt papper från Restrepo Tysta dueller – analysera konstruktionen

Förra gången vadade vi in ​​på Restrepos tysta duellpapper. Du kan se originalet och min omformaterade version på Github tillsammans med all kod i den här serien. Vi smälte avsnitt 2 och lite längre och ritade några förenklade exempel på den symmetriska versionen av spelet.

Jag erkänner att den här uppsatsen inte är lätt att läsa. Avsnitt 3-6 presenterar de centrala definitionerna, lemman och bevis. De är ett slag av tät notskrift utan vägledande intuition. Symbolerna får inte ens catchy namn eller “tänk på det här som” förklaringar! Jag tror att denna skillnad i kommunikation har något att göra med den period då uppsatsen skrevs, och något att göra med datorernas barndom vid den tiden. Tidningen publicerades 1957, vilket markerade året IBM bytte från vakuumrör till transistorer, långt innan Moores lag ens var en glimt i Gordon Moores ögon. Vi kan inte klandra Restrepo för att inte vädja till våra moderna känslor.

Jag tillbringade pinsamt mycket tid med att kämpa mig igenom avsnitt 3-6 när jag fortfarande inte riktigt förstod formen av den optimala strategin. Det är inte förrän i allra högsta grad avsluta av papperet (avsnitt 8, beviset för sats 1) att vi får en konstruktion. Se sista inlägget för en detaljerad beskrivning av den data som utgör den optimala strategin. I korthet är det en partition av $ (0,1)$ i delintervall $ (a_i, a_{i+1})$ med en sannolikhetsfördelning $ F_i$ på varje intervall, och tiden du tar din $ i$-th åtgärd väljs slumpmässigt enligt $ F_i$. Alternativt kan den sista fördelningen inkludera en poängmassa vid tiden $ t=1$, dvs “vänta till sista ögonblicket för en garanterad träff.”

Avsnitt 8 beskriver hur man väljer $ a_i$ och $ b_j$, med fördelningarna $ F_i$ och $ G_j$ byggda enligt formlerna som byggts upp i föregående avsnitt.

Eftersom vårt mål fortfarande är att förstå hur man konstruerar lösningen – även om varför det fungerar är fortfarande ett mysterium – vi kommer att skriva ett program som implementerar den här algoritmen i två inlägg. Först kommer vi att arbeta med ett förenklat symmetriskt spel, där svaret tillhandahålls för oss som ett testfall. I ett uppföljande inlägg kommer vi att omarbeta koden för att konstruera den generiska lösningen och välja nits om kodkvalitet, och de finare punkterna i algoritmen Restrepo utelämnar.

I slutändan, om det som programmet producerar stämmer överens med Restrepos exempel (i stället för att förstå tillräckligt mycket av tidningen för att konstruera vårt eget), kommer vi att utropa seger – vi har framgångsrikt förnuftskontrollerat Restrepos konstruktion. Sedan kan vi gå vidare till att studera varför den här lösningen fungerar och vilka förbehåll som döljer sig under matematiken.

Följ formlerna

Ingången till spelet är ett val av $ n$ åtgärder för spelare 1, $ m$ åtgärder för spelare 2, och sannolikhetsfördelningar $ P, Q$ för de två spelarnas framgångsannolikheter (respektive). Här är algoritmen som anges av Restrepo, med de refererade ekvationerna som följer. Om du följer med min “arbeta genom tidningen organiskt” shtick, rekommenderar jag att du försöker analysera texten nedan innan du läser vidare. Minns $ \alpha$ är sannolikheten “vänta tills slutet” för spelare 1:s sista åtgärd, och $ \beta$ är den analoga sannolikheten för spelare 2.

Låt oss reda ut den här röran.

Först den breda bilden. Hela konstruktionen beror på $ \alpha, \beta$, dessa poängmassor för spelarnas slutliga handlingar. Det finns dock detta villkor att $ \alpha \beta = 0$, dvs högst en kan vara lik noll. Detta ger en vagt intuitiv mening: en spelare med fler åtgärder kommer att ha extra “tillskott” och därför kan det vara vettigt för dem att vänta till slutet för att få en garanterad träff. Men bara en spelare kan ha en sådan fördel gentemot den andra, så bara en av de två parametrarna kan vara lik noll. Det är min informella motivering för $ \alpha \beta = 0$.

Om vi ​​inte vet $ \alpha, \beta$ i början, är Restrepos konstruktion (valet av $ a_i$s och $ b_j$s) en deterministisk funktion av $ \alpha, \beta$ och de andra fasta ingångarna.

$$\displaystyle (\alpha, \beta) \mapsto (a_1, \dots, a_n, b_1, \dots, b_m)$$

Konstruktionen hävdar att den optimala lösningen har $ a_1 = b_1$ och vi måste hitta en ingång $ (\alpha, \beta) \in (0,1) \times (0,1)$ så att $ \alpha \beta = 0$ och de producerar $ a_1 = b_1 = 1$ som utdata. Vi gör en sökning efter de “rätta” utdataparametrarna och använder kunskap om det kedjade sambandet mellan ekvationer för att titta på utdata, och använder det för att justera indata för att få utdata närmare det vi vill ha. Det är inte gradientnedstigning, men det skulle förmodligen kunna omformuleras på det sättet.

Tänk särskilt på fallet när vi får $ b_1 omvänd utdata, dvs kommer att göra $ a_1 mellanvärdessats från kalkyl, men till hitta det värdet det enklaste alternativet är binär sökning. Vi har de övre och nedre gränserna, $ \beta = 0$ och $ \beta = 1 – \varepsilon$, och vi vet när vi hittade vårt mål: när utgången har $ a_1 = b_1$.

Denna binära sökning kommer tillbaka i full gång i nästa inlägg, eftersom vi redan vet att den symmetriska tysta duellen börjar med $ a_1 = b_1$. Ingen sökning efter $ \alpha, \beta$ behövs, och vi kan fixa dem båda till noll för tillfället – eller snarare, anta att de rätta värdena är kända.

Det som återstår är att bestämma hur man beräknar $ a_i$ och $ b_j$ från en start $ \alpha, \beta$. Vi kommer att gå igenom algoritmen steg för steg med hjälp av det symmetriska spelet där $ P=Q$ (samma åtgärdsframgångsannolikhet) och $ n=m$ (samma åtgärdsantal) för att grunda vår studie. Ett uppföljningsinlägg kommer att se över dessa formler i full allmänhet.

Det symmetriska spelet

Grundidén med konstruktionen är att vi utgår från en beräkning av de sista handlingsparametrarna $ a_n, b_m$, och använder dem induktivt för att beräkna parametrarna för tidigare åtgärder via några integraler och substitutioner. Konstruktionen är med andra ord en rekursion, och intervallet i vilket spelarna gör sin sista åtgärd $ (a_n, 1), (b_m, 1)$ är basfallet. När jag började skriva programmen nedan, ville jag ge ett namn till dessa $ a_i, b_j$ värden. Restrepo verkar hänvisa till dem som “parametrar” i tidningen. Jag ringer dem övergångstidereftersom markera de ögonblick då en spelare “övergår” från ett åtgärdsintervall $ (a_2, a_3)$ till nästa $ (a_3, a_4)$.

För en enkel sannolikhetsfunktion $ P$ resulterar slutet av algoritmen i ekvationer som liknar: välj $ a_t$ så att $ P(a_{nt}) = 1/(2t + 3)$.

Kom ihåg att spelare 1 har en speciell funktion som används i varje steg för att konstruera sin optimala strategi, kallad $ f^*$ av Restrepo. Det definieras för icke-symmetriskt spel enligt följande, där återkallelse $ Q$ är motståndarens handlingssannolikhet:

$$\displaystyle f^*

def f_star(prob_fun, prob_fun_var, larger_transition_times):
”’Compute f* as in Restrepo ’57.

In this implementation, we’re working in the simplified example
where P = Q (both players probabilities of success are the same).
”’
x = prob_fun_var
P = prob_fun

product = 1
for a in larger_transition_times:
product *= (1 – P(a))

return product * diff(P(x), x) / P(x)**3

from sympy import Integral
from sympy import Symbol
from sympy.solvers import solve
from sympy.functions.elementary.miscellaneous import Max

def compute_a_n(prob_fun, alpha=0):
    P = prob_fun
    t = Symbol('t0', positive=True)
    a_n = Symbol('a_n', positive=True)

    a_n_integral = Integral(
        ((1 + alpha) - (1 - alpha) * P
    a_n_integrated = a_n_integral.doit()   # yes now "do it"
    P_a_n_solutions = solve(a_n_integrated - 2 * (1 - alpha), P(a_n))
    P_a_n = Max(*P_a_n_solutions)
    print("P(a_n) = %s" % P_a_n)

    a_n_solutions = solve(P(a_n) - P_a_n, a_n)
    a_n_solutions_in_range = (soln for soln in a_n_solutions if 0  soln  1)
    assert len(a_n_solutions_in_range) == 1
    a_n = a_n_solutions_in_range(0)
    print("a_n = %s" % a_n)

    h_n_integral = Integral(f_star(P, t, ()), (t, a_n, 1))
    h_n_integrated = h_n_integral.doit()
    h_n = (1 - alpha) / h_n_integrated
    print("h_n = %s" % h_n)

    return (a_n, h_n)