Open Source and the Prisoner’s Dilemma

Some time ago, on one of the forums I got into discussion about merits and motivations of releasing projects and code as open source. Turns out that many people cannot exactly wrap their heads around the concept of giving away your code for free. Even leaving the exact meaning of ‘free’ aside (it applies to both of them), I believe we can observe a kind of cultural gap here. Strangely enough, it’s not even the case of Nerds vs. Rest of the World: the geek community is in itself somewhat divided with respect to this issue.

And that’s OK, in a way. I know it may not be obvious how value can be preserved if we just volunteer our time and skills for open source projects and don’t receive any direct compensation in return. Honestly, I’m still kinda amazed how it all works out, but I have my small theory. It’s somewhat tangential to the typical gift culture explanation, but could also shed some light on companies’ motivations for contributing to OSS.

Long story short, I think the relation dynamics between open source contributors and beneficents can be described in term of the prisoner’s dilemma: a rather classic example from the game theory. Before pursuing the analogy further, let’s have a brief look at this curious puzzle.

Of prisoners and stealing

Like the name suggests, the prisoner’s dilemma can be formulated in terms of jail, prisoners, cooperation and defection. I prefer an alternate setting, though, as it seems to better illustrate the concept and may be easier to understand. You can check the original formulation in Wikipedia, among other sources.

There is small game-theoretical difference between those two scenarios, but it’s largely irrelevant to our discussion.

Consider a two-player game with a potential reward of $100. The money can be taken by one of the players or split evenly among them. There is also a possibility of both players getting nothing. It all depends on how the players themselves decide what to do with the money.

They make independent decisions by choosing one of two options. They can decide to either split the money evenly between both of them, or steal (figuratively) the whole sum for themselves.
What happens next is the result of both decisions, revealed and applied at once:

• If both players choose to split, the reward is indeed split evenly. Each player walks away with $50.
• If both players choose to steal, they walk away with nothing.
• If one players choses to steal while the other decides to split, stealer gets the whole $100. The other player walks away with nothing.

Sounds contrived?… It’s been actually tested in real life (as much as television can be called that), sometimes with dramatic results.

If you’re splitting and you know it…

What is the optimal strategy in a setting like this? If both opponents are known to be rational agents, they should arrive at the same conclusions. Because they cannot know each other’s thoughts, they both may only speculate what – probability that opponent steals – may be.

We know their decisions are independent, though, so shall remain the same regardless of what the player chooses in the end. Hence the expected values of both decisions seem to clearly indicate which one is better:

Looks like we should simply steal and be done with it.

But wait! Since both players are rational agents, they will both arrive at the same conclusion. Moreover, each will know the other thought the same. So they both know that is actually 1. Unfortunately, in this case

and they will both get nothing if they follow this logic.

Pity. Or maybe it’s better to split, then? If they both do just that, each will at least get $50 instead of nothing… Yes, this looks like a much better alternative, especially that we can count on both players to apply this reasoning; they are rational agents, after all. So by this logic, they will both split and everyone will get something in the end…

Well, except that now is 0, so it’s actually better to steal instead. Oh, and both players know that, obviously, and are not happy about it… again. Hence they will rather split, which makes stealing more attractive option, which in turns compels splitting – and so on.

Complexity for the rescue

This example of circular meta-reasoning is unresolvable in two-player case, because a single choice will make or break the system. Fortunately, reality is much more complex, with multiple agents making countless decisions all the time.

Decisions such as, for example, whether to open source this new project, or maybe contribute to some existing one.

Just like with the situation described above, looks like the optimal choice is to “steal”: to draw liberally from the vast expanse of existing open source software while contributing nothing in return. No single such behavior would cause the whole ecosystem to crumble, so the incentive for exploitation is very tangible. Heck, it’s not even obvious what’s the steal here, because what value loss is incurred by “splitters” is not easily recognizable.

Yet it’s obvious why every party cannot apply this strategy, lest the result will be very suboptimal for everyone. Somewhere between those two extremes (everyone “splits” vs everyone “steals”) there might be the point of equilibrium: where stealers can derive maximum utility without irrevocably harming the game’s dynamics. We don’t really know where that point lies, though, so we just choose to play along and split.

Dwa paradoksy prawdopodobieństwa

Na dzisiaj przewidziałem ciekawostki z nieco innej niż zwykle beczki :) Chciałem mianowicie pokazać dwa przykłady na to, jak intuicyjnie całkiem proste pojęcie matematyczne w rzeczywistości jest bardzo podatne na niewłaściwe zrozumienie. Chodzi tutaj o zwykłe prawdopodobieństwo – czyli szansę na zajście jakiegoś zdarzenia.

Pierwszy przykład jest z gatunku rozrywkowo-medialnych i związany jest z pewnym teleturniejem, który zresztą był kiedyś emitowany także w Polsce. Oto w pewnym jego etapie uczestnik jest konfrontowany z trzema zasłoniętymi bramkami, z których jedna zawiera nagrodę, a dwie pozostałe są puste. Spośród tej trójki gracz wybiera jedną bramkę, by stać się właścicielem jej ewentualnej zawartości. Trik polega na tym, że gospodarz programu – już po wyborze gracza – odsłania jedną z pozostałych bramek, która okazuje się być pusta. Zgodnie z regułami teleturnieju gracz może w tym momencie zmienić swój wybór i wskazać trzecią bramkę zamiast tej wybranej pierwotnie. Pytanie brzmi: czy taka zamiana mu się opłaca?
Część ludzi stwierdziłaby zapewne, że nie ma to znaczenia, bo szansa wygranej przecież i tak wynosi 1 do 3, bo tylko za jedną bramką jest nagroda. Inni mogliby uznać, że po odsłonięciu jednej bramki wybieramy już spośród dwóch, więc nasze szansę rosną do 50% – też niezależnie od tego, czy zmienimy swój pierwotny wybór czy nie… A jak jest naprawdę?
Może się to wydawać niedorzeczne, jednak będąc na miejscu gracza, powinniśmy zawsze zmienić swój wybór. Mało tego, w ten sposób nasze szanse na wygraną rosną dokładnie dwukrotnie! Jak to możliwe?… Otóż kluczowe w wyjaśnieniu tego zjawiska jest zauważenie, że gospodarz programu zawsze odsłoni bramkę pustą i niewybraną przez gracza (w innym przypadku gra skończyłaby się od razu i w ogóle nie byłoby możliwości zmiany). Dlatego też opłaca się dokonać zmiany, bo w ten sposób w istocie odwracamy prawdopodobieństwo wygranej i przegranej. Możliwe są bowiem dwie sytuacje:

• gracz początkowo wybiera bramkę z nagrodą – po zmianie kończy więc z bramką pustą
• gracz najpierw wskazuje bramkę pustą; wówczas gospodarz odsłoni drugą pustą bramkę, więc zmiana skończy się wyborem bramki z nagrodą

Jak wiadomo prawdopodobieństwo dobrego wyboru spośród trzech bramek wynosi 1/3, a złego – 2/3. Takie są też odpowiednie prawdopodobieństwa dwóch powyższych scenariuszy; innymi słowy, zmiana bramki powoduje, że prawdopodobieństwo wygranej rośnie z początkowego 1/3 do 2/3.
Jeśli ktoś ma nadal wątpliwości, to nie ma czym się martwić – podobno wielu matematyków też ma kłopoty z ogarnięciem tego paradoksu :) Wydaje mi się, że rzecz w tkwi w błędnym określeniu, co tak naprawdę jest tutaj zdarzeniem losowym. Jeśli za takie będziemy uważali zarówno początkowy wybór, jak i zmianę, to rzeczywiście mogą być kłopoty z dojściem do poprawnych wniosków. Zamiast tego całą grę powinno się traktować jako jedno doświadczenie losowe, ze z góry ustalonym scenariuszem.

A co z drugim przykładem? Jest na szczęście nieco prostszy i dotyczy koncepcji zdarzeń (nie)zależnych. Oto kilka pytań dotykających tej kwestii, dla których odpowiedzi “intuicyjne” są zwykle błędne:

• Jeśli zakręcimy kołem ruletki 57 razy i za każdym razem kulka wpadnie w czarne pole, to jaka jest szansa na to, że będzie tak również przy następnym obrocie?
• Jeśli liczba 42 ostatni raz wystąpiła w Dużym Lotku pół roku temu, to jaka jest szansa, iż wypadnie w dzisiejszym losowaniu?
• Jeśli w grze X potwór Y wyrzuca przedmiot Z z prawdopodobieństwem 1/n, to jak dużo potworów Y powinienem zabić, aby być prawie pewien, że wypadnie mi z nich przedmiot Z?

Nie, prawdopodobieństwo wpadnięcia kulki w czarne pole to cały czas 1/2. Nie, liczba 42 może wypaść z takim samym prawdopodobieństwem dzisiaj, jak i w każdym innym losowaniu. Nie, zabicie n potworów Y wcale nie da nam prawie-pewności dostania Z – o ile mówimy o zwyczajowym użyciu słowa ‘prawie’ ;)
Wszędzie tutaj mamy bowiem do czynienia z sekwencją zdarzeń całkowicie niezależnych, których wyniki nie wpływają na siebie. Zatem nie ma znaczenia to, ile razy wcześniej kręciliśmy ruletką, ile wysłaliśmy już w życiu kuponów Lotto i ile wrażych monstrów zdołaliśmy zaszlachtować – prawdopodobieństwo zajścia interesującego nas zdarzenia w kolejnej próbie jest zawsze identyczne. Możemy aczkolwiek spróbować policzyć, na ile jest to prawdopodobne dla ciągu k kolejnych prób. Otóż ze schematu Bernoulliego wynika, że szansa na sukces wynosi wtedy

1 – (1 – p)^k

jeśli dla pojedynczej próby prawdopodobieństwo wynosi p. Stąd dla p = 1/n i k = n otrzymujemy (po kilku, jak to by powiedzieli matematycy, “trywialnych przekształceniach ;D) wynik: (e – 1)/e; nieco ponad 63%. To trochę mało jak na prawie-pewność, czyż nie? ;]

Jak więc widać na przykładach, szansa na to, że opacznie zrozumiemy sytuację, w której zastosowania mają pojęcia ‘szansy’ czy ‘prawdopodobieństwa’ (używane tutaj jako synonimy) jest – nomen omen dosyć duża. Może dlatego w szkole niespecjalnie przepadałem za tym działem matematyki :)

Losowanie tabelkowe

W niemal każdym programie chociaż raz zdarza się potrzeba, by “rzucić kośćmi” i pozwolić, by wydarzyło się coś losowego. Oznacza to skorzystanie z generatora liczb pseudolosowych, aby uzyskać ‘przypadkową’ wartość. Nie będzie ona faktycznie losowa, lecz dzięki zastosowaniu matematycznych formuł o dużej nieregularności rezultat może być bardzo zbliżony do ideału. Istnieje oczywiście wiele algorytmów wyznaczania liczb pseudolosowych, różniących się faktyczną przypadkowością uzyskiwanego wyniku.
W różnych językach programowania mamy natomiast odmienne sposoby na uzyskanie liczby ‘losowej’. Zwykle najwygodniejszym jest wartość z zakresu [0..1], bo odpowiada to matematycznemu pojęciu prawdopodobieństwa. Aby w C++ uzyskać taki rezultat, wystarczy napisać proste opakowanie na biblioteczną funkcję rand:

Mając taki generator, możemy już łatwo sprawdzić, czy “zdarzyło się” coś, czego prawdopodobieństwo znamy:
// doświadczenie losowe z określonym prawdopodobieństwem
bool RandomOccured(float fProbability) { return Random() <= fProbability; }[/cpp] W ten sposób możemy na przykład rzucać wirtualną monetą. Sprawa się jednak komplikuje, jeżeli możliwych wyników doświadczenia jest więcej, a przy okazji mają one różne prawdopodobieństwa zajścia. Tak się dzieje na przykład w grach RPG, w których konieczne jest obliczanie rezultatów zadanych ciosów (trafienie, pudło, unik, blok, itp.). Skuteczność postaci w walce zależy zwykle od jej statystyk, więc szanse poszczególnych wyników nie są stałe i zmieniają się w trakcie gry.
Dobre generatory liczb pseudolosowych są zaś nierzadko względnie kosztowne obliczeniowo. Dlatego zamiast wykonywać po jednym losowaniu dla każdego możliwego rezultatu (zaszedł – nie zaszedł), znacznie lepiej jest załatwić wszystko jednym losowaniem. Nie jest to trudne:
// doświadczenie losowe z prawdopodobieństwem określonym tabelką
int RandomResult(const float* aProbs, int n)
{
float fRand = Random();

float fAccum = 0.0f;
for (int = 0; i < n; ++i) { // sprawdzamy, czy wylosowana liczba mieści się w zakresie p-stwa if (fAccum <= fRand && fRand < fAccum + aProbs[i]) return i; fAccum += aProbs[i]; } // błąd return -1; }[/cpp] Tak naprawdę liczymy tutaj dla każdego możliwego rezultatu wartość tzw. dystrybuanty. Ale chyba nie warto wnikać w takie teoretyczne szczegóły – grunt, że powyższa metoda działa w praktyce :) Trzeba tutaj jednak pamiętać, aby prawdopodobieństwa sumowały się do 1. Jeśli tak nie jest, można przeskalować wylosowaną liczbę.