september 04, 2004
Game Studies
Posted by hakank at 08:11 EM | Comments (0) | TrackBack
augusti 26, 2004
Röstningsmetoder
Google Answers-frågan Different ways of designing voting, depending on your goals? innehåller en mycket innehållsrik redogörelse för olika typer av system att rösta, inklusive fördelar och nackdelar.
Frågan börjar:
I'm asking for an easy-to-reference chart describing the strengths, weaknesses, "best use scenarios" and "worst use scenarios" of voting systems [...] I'd like it to be written at around an eighth-grade level.
Några länkar som nämns:
James Green-Armytage: A Survey of Basic Voting Methods
ElectionMethods.org
Center for Voting and Democracy.
Posted by hakank at 08:45 EM | Comments (1) | TrackBack
augusti 18, 2004
Om anseende (spelteori)
I blogganteckningen When Reputation Systems Are Worse Than Useless sammanfattar och diskuterar Paul Resnick ett spelteoretiskt paper skrivet av Jeffrey Ely, Drew Fudenberg och David K. Levine kring anseende. Se nedan för referens och abstract till papret.
Så här börjar blogganteckningen:
A paper by Ely, Fudenberg, Levine, titled When is Reputation is Bad?, analyzes mathematical models of situations where public reputations make it harder, not easier, to sustain good behavior. I'll start with their example of a car mechanic who prefers to be honest but will occasionally be tempted to take an unfriendly action in order not to be mistaken in the long run for a crooked mechanic. Then I try to summarize their findings about the class of situations that lead to this kind of problem.
Papret är Jeffrey Ely, Drew Fudenberg, David K. Levine:
When is Reputation Bad? (PDF).
Abstract:
In traditional reputation theory, reputation is good for the long-run player. In "Bad Reputation," Ely and Valimaki give an example in which reputation is unambiguously bad. This paper characterizes a more general class of games in which that insight holds, and presents some examples to illustrate when the bad reputation effect does and does not play a role. The key properties are that participation is optional for the short-run players, and that every action of the long-run player that makes the short-run players want to participate has a chance of being interpreted as a signal that the long-run player is "bad." We also broaden the set of commitment types, allowing many types, including the "Stackelberg type" used to prove positive results on reputation. Although reputation need not be bad if the probability of the Stackelberg type is too high, the relative probability of the Stackelberg type can be high when all commitment types are unlikely.
Posted by hakank at 08:10 EM | Comments (0) | TrackBack
juli 18, 2004
Recension: Thomas Schelling "The Strategy of Conflict"
Thomas Schelling har tidigare nämns här som författare till Micromotives and Macrobehavior (se t.ex. Matematiska och statistiska "självklarheter"), en tidigt och ofta refererad stöttepelare inom emergensteorin och agentbaserad modellering. Det är en (ganska) oteknisk bok som handlar om hur individers egna mål tillsammans skapar sociala fenomen.
Schellings Strategy of Conflict (från 1960) har samma kultstatus inom spelteorin, vilket har gjort honom till en dubbel husgud för mig.
Kort sammanfattning: Boken är lika underbar som "Micromotives and Macrobehavior" och av samma skäl: Schelling har förmågan att dels fråga intressanta frågor och dels förklara sina teorier på ett mycket förståeligt sätt.
Det finns vissa kapitel som är rätt tekniska (matematiska), men det går att snabbläsa dessa avsnitt eftersom poängerna de nästan alltid exemplifierar i pratversioner. Det är naturligtvis en fördel om man läst lite om spelteori tidigare. Min personliga erfarenhet inom området var de tre böcker som nämns i referenserna nedan. Schelling skriver om många andra saker inom spelteorin såsom minimaxprincipen, sekvensspel, Nash jämviktspunkt, men som jag inte tänker gå in på här.
Schelling kritiserar den då förhärskande spelteorin som varande (i princip) matematiska övningar för matematiker och som inte kunde användas i verkliga livet. Han försöker därför utvidga spelteorin så den även innefattar "strategic moves" såsom hot, löften, åtaganden (commitment) etc och även koppla det till 50-talets politiska arena. Och så är det naturligtvis det som fascinerade mig mest: "focal points", dvs att i förhandlingar eller koordinationsproblem finns det vissa punkter som är naturliga punkter att "stanna i". Dessa beskrivs mer nedan.
Förutom att beskriva sina teorier utifrån enkla vardagsexempel skrivs mycket om det kalla krigets politik, speciellt kärnvapenupprustningen och terrorbalansen, och detta görs förståeligt även om en oinvigd (även om vissa kriser kanske inte nämns numera). Han framför t.ex. teorin om att det är bra med med en terrorbalans, förutsatt att alla parter är medvetna om att de andra bygger upp en arsenal och att den är stabil. Appendix A ("Nuclear Weapons and Limited Wars") diskuterar om och hur kärnvapen skiljer sig från andra typer av vapen. Kontentan är att kärnvapen skiljer sig principiellt från andra vapen, inte så mycket av rent tekniska skäl som att det finns en tradition, kultur att dessa vapen skiljer sig från andra vapen.
Ett exempel på strategiska drag är att om man i förväg och offentligt binder sig till en viss strategi kan man begränsa motståndaren möjligheter; det fungerar dock endast om motståndaren tror att man verkligen har bundit sig och inte ändrar sig i sista sekunden. T.ex. i "Chicken" där två bilar kör emot varandra, och den förare förlorar som väjer först. Om förare A kastar ut ratten genom fönstret är det detta ett "åtagande" som B gör klokt i att lyssna på, och väja. (Vad händer om B samtidigt kastar ut ratten? Då flyttas spelet till en annan nivå: den som först kastar sig ut från sin bil förlorar.)
Ett annat exempel är automatiska vedergällningssystem: Om ett land A påvisar trovärdigt för ett annat land B att man har ett system som automatiskt bombar det anfallande landet, och att man inte kan avbryta detta vedergällningsanfall när den väl påbörjats, påverkar det sannolikt lusten för B att anfalla landet. I boken nämns naturligtvis länderna vid namn: USA och Sovjet. Problemet som Schelling också diskuterar är hur man trovärdigt visar att man har ett sådant system.
Detta visar också att det inte alltid är bäst att dölja all information man har, viss information vill man ska komma till motståndarens kännedom. (Och man ska veta att motståndaren vet att man vet att denne har fått informationen.)
Manipulerande av information: Om säljare S och köpare K försöker att komma till ett avslut i en affär där det finns en tidsgräns, kan endera S eller K kontakta den andra med ett bud (skambud) och därefter göra sig helt otillgänglig, t.ex. åka på semester utan mobiltelefon etc. Den andra har då som val endast att acceptera budet eller låta affären gå i stöpet.
Focal points, "brännpunkter"
Det som i mina ögon var det mest intressanta i boken är diskussionen om focal points (ung. brännpunkter, kallas numera "Schelling points") som diskuteras främst i kapitel 3 och kapitel 4, men återkommer även i senare kapitel.
Någon sida in i kapitel 3 finns ett exempel om två personer som hoppat ut från ett flygplan (med fallskärm) och som sedan vill mötas när de landat. De har inte bestämt någon mötesplats i förväg och har ingen kontakt med varandra. Däremot har de exakt samma karta. Var ska de träffas? (Kartan finns på sid 55, och utan den är det naturligtvis svårt att svara.) Det visar sig att det finns ett ställe på kartan där flera vägar går samman över en flod (den enda floden).
Denna punkt "står put" på ett unikt sätt på kartan och är alltså en naturlig träffpunkt (focal point). I andra miljöer/kartor kanske ett ensamt hus, eller ensamt träd vore en sådan punkt. Finns det ingen sådan punkt kan det vara mycket svårt att komma till en lösning.
Vad gäller begränsning om användadet av kärnvapen finns det ingen focal point som är naturlig och politisk rimlig, förutom 0: att inte tillåta någon användning alls. Alla andra nivåer t.ex. en bomb om året, eller 10 Megaton/månad eller endast för grannländer i den omedelbara närhetet, är "onaturliga".
Exempel
På sidan 56f finns flera exempel där man själv kan fundera hur man själv skulle välja. De är alla s.k. koordinationsspel där kommunikation inte är möjlig. Schelling kallar detta "tacit coordination", senare i boken diskuteras vad som händer om deltagarna får kommunicera med varandra.
Förutsättningen är att spelen spelas av flera personer som får samma instruktioner och där det gäller att på något sätt samordna sina lösningar utan att kommunicera med varandra (t.ex. att de sitter i olika rum eller få instruktionerna vid olika tidpunkter). Det är alltså frågan om att lista ut vad man tror att de andra tror att de andra tror (osv) att de ska svara.
Man kanske inte ens vet vilka de andra deltagarna är eller hur många de är. Notera att detta inte är nollsummespel (zero-sum) där en vinner det den andra förlorar utan där båda/alla deltagarna kan vinna eller förlora (non zero-sum). Dessa icke-nollsummespel är de mest intressanta och de som finns vanligast i "naturen".
Man bör också notera att det inte finns något "rätt" svar; de är inga trickgåtor. Som Schelling skriver: är det tillräckligt många som svarar samma sak så är det ett rätt svar. I en not skriver han resultaten på sina egna experiment, som finns senare i denna anteckning.
Pröva gärna själv innan du läser de "rätta" svaren.
1. Name 'heads' or 'tails'. If you and your partner name the same, you both win a prize.
2. Circle one of the numbers listed in the line below. You win if you all succeed in circling the same number.
7 100 13 261 99 555
3. Put a check mark in one of the sixteen squares. You win if you all succeed in checking the same square.
4. You are to meet somebody in New York City. You have not been instructed where to meet; you have no prior understanding with the person on where to meet; and you cannot communicate with each other. You are simply told you have to guess where to meet and that her is being told the same thing and that you will have to try to make your guesses coicide.
5. You where told the date but not the date of the meeting in No. 4; the two of you must guess the exact minute of the day for meeting. At what time will you appear at the meeting place that you elected in No 4?
6. Write some positive number. If you all write the same number, you win.
7. Name an amount of money. If you all name the same amount, you can have as much as you names.
8. You are to divide $100 into two piles, labeled A and B. Your partner is to divide another $100 into two piles labeled A and B. If you allot the same amounts to A and B respectively, that your partner does, each gets $100; if your amounts differs from his, neither of you gets anything.
9. On the first ballot, candidates polled as follows:
| Smith | 19 |
| Jones | 28 |
| Brown | 15 |
| Robinson | 29 |
| White | 9 |
The second ballot is about to be taken. You have no interest in the outcome, except that you will be awarded if someone gets a majority on the second ballot and you vote for the one who does. Similarly, all voters are interested only in voting with the majority, and everyone knows that this is everybody's interest. For whom do you vote on the second ballot?
These problems are artificial, but they illustrate the point. People can often consert their intentions or expectations with others if each knows that the other is trying to do the same. Most situations - perhaps every situation for people who are practiced at this kind of game - provide some clue for coordinating behaviour, some focal point for each person's expectation of what the other expects him to be expected to do
Några tankar kring detta
Detta innebär att vi faktiskt kan organisera oss utan kommunikation och utan att behöva ha speciellt mycket detaljkunskap om en situation. Det finns ledtrådar (tecken, vinkar, eng. cues) i problem som gör att vi ofta kan samordna oss kring problemet.
Unikhet en av de viktigaste ledtrådarna: Finns det någon punkt som "står ut" väljes troligen den, t.ex. störst, längst till vänster, högst. Vissa ledtrådar bygger på kulturell gemenskap, t.ex. att börja räkna från 1, läser texten från toppen nedåt och från vänster till höger.
Vet man inget om sina medspelare är man alltså tvungen att välja en strategi som är mer generell, t.ex. första talet i listan. Om man inte vet något om sina medspelare i fråga 4 väljer man säkert en "utstickande" byggnad som alla, inklusive de som inte känner till speciellt mycket om staden, troligen känner till.
Andra - mer "lokala" - sammanhang avgör också, t.ex. vem det är som spelar. Är det matematiker som löser problem 2 (och alla vet om att de andra deltagarna är matematiker) kan man anta att det är matematiska egenskaper som avgör vad som är focal point, t.ex. 7 som är det första primtalet i listan. Är det talmystiker (och alla vet om att det är talmystiker) kanske det magiska talet 13 väljs (eller 555 eftersom det liknar det magiska talet 666). Ett gift par kanske väljer ett tal med koppling till deras gemensamma bakgrund såsom datum för bröllopsdagen etc. Vissa "lösningar" ses då helt enkelt som självklara för deltagarna, och man antar att de andra antar att det är självklart. (Se mer om det självklara nedan.)
Det kan dock vara ett problem om man känner till bakgrund om sina spelare, eftersom det kan vara svårt att veta inom vilken domän man ska leta efter det gemensamma svaret. Om två personer som båda är matematiker och arkitekter ska svara på problem 4, var väljer de? Blir det en koppling till arkitekturen, matematiken eller något tredje ("common sense"-kunskap)?
I boken nämns också uttryckligen att "lösning" av focal points i ett spel är som att lösa gåtor eller rebusar: man får ledtrådar i problemformuleringen som man kan gå vidare på. Sådana Schellingska ledtrådar/vinkar var f.ö. de jag tänkte på i min kommentar i Erik Stattins anteckning Geekiga jobbannonser. Även om det kanske finns mängder av matematiskt likvärdiga lösningar är det för denna typ av gåtor ofta sammanhanget som avgör om det är en rätt lösning. T.ex. om Google gör en gåta, och man vet om att det är Google som gör den, och Google vet att man vet om detta, så kan man förvänta sig att den rätta lösningen ger någon ledtråd kring Google.
Nu fanns det dock två problem med denna förutsättning: 1. Från början var det okänt att det var Google som hade skapat problemet, det kom fram först senare via andra källor. Möjligen skulle man kunna tänka sig att google borde ana att det skulle komma fram och därmed lagt några ledtrådar i problemet. 2. En mer viktig sak var att man faktiskt kunde kontrollera svaret genom att gå till linux.org-sidan och testa sin lösning.
Emergens och självorganisation
Det finns en koppling men även skillnader mellan ovanstående typ av självorganisation och de självorganiserande principer som beskrivs i emergensteorin och agentbaserad modellering. Schelling skapade (några år senare) en modell för hur segregation i bostadsområde kan uppstå: även om varje hyresgäst kan acceptera att ha flera invandrare som grannar kan detta leda till en segregering i två olika områden. Detta diskusteras bl.a. i "Micromotives and Macrobehavior".
Skillnaden mellan de två typerna av självorganisation är att den som beskrivs i "Strategy of Conflict" är aktiv, medveten och bygger på att man man gör bedömningar av vad andra tror att de andra tror att de tror att .... I "Micromotives and Macrobehavior" är det däremot en fråga om att handlingar med preferenser på en lokal ("lägre") nivå leder till fenomen på en annan ("emergent") nivå som man inte är medveten om när man agerar, eller i alla fall normalt inte har med i sin planering. (För mer om detta, se t.ex. kategorierna komplexitet/emergens samt agentbaserad modellering.)
När jag läste "Strategy of Conflict" tänkte jag bl.a. på Peter Lindberg och hans undersökningar hur systemutvecklare kan (själv)organisera sig utifrån mer lokala principer än traditionell toppstyrning. Peter har skrivit en hel del om emergensprinciper som möjlig lösning, men kanske även ska fundera på om och hur man kan använda Schellings focal point principer för detta.
Focal points, självklarheter och affordances
Här måste också nämnas Simon Winters underbara essä Det självklara behöver inte sägas (1996) som också diskuterar Schellingpunkterna men utifrån ett lite annat angreppssätt: när och hur vet vi att vi har gemensam kunskap kring ett ämne. Simon drar även den intressanta parallellen till Donald Normans utmärkta bok The Design of Everyday Things om hur man bör designa saker för att de ska bli så enkla som möjligt att använda och förstå.
Normans motsvarighet till Schellingpunkterna är "affordances" där t.ex. formen hos ett ting avgör hur det ska användas. T.ex. en stol ska se ut att kunna sittas på, en ratt ska man kunna vrida på, en knapp trycker man på etc.
Ofta är det sedvänja och traditioner som avgör hur en sak används, men ibland måste man helt enkelt läsa instruktionerna för att förstå hur prylar ska fungera. Det gäller speciellt de mer tekniska såsom datorsystem. (Omvänt kan man säga att kan man inte sitta på en "stol" är det ingen stol, kan man inte vrida på "ratten" är det konstigt att kalla det för ratt etc. Både själva användandet av sakerna och dess begreppen hör ihop.)
Begreppet affordance myntades av James J. Gibson i The Ecological Approach to Visual Perception.
Referenser
Lite mer om focal points:
Schelling's Focal Point
More on schelling point
Understanding Riots.
Följande tre introduktionsböcker om spelteori lästes under hösten 2002 och kan rekommenderas.
Morton D. Davis: Game Theory: A Nontechnical Introduction
En trevlig låg-teknisk introduktion i spelteori med massor av roliga exempel. Det finns övningar som är utmanande att lösa på egen hand. Speciellt roligt var, för mig som gammal statsvetare, exemplen med val (elections) och vissa av dess paradoxer. Förklarar bland annat "Prisoner's Dilemma" på ett bra sätt.
William Poundstone: Prisoner's Dilemma/John Von Neumann, Game Theory and the Puzzle of the Bomb
Även detta är en mycket trevlig bok om spelteori, med tonvikt på vad von Neumann gjorde och tänkte inom området. Fascinerande person och bok. Speciellt den biografiska delen var bra och det var även intressant att läsa om hur alla "di där gubbarna" höll på före och efter Bomben. Den är betydligt mindre strukturerad än Davis bok, men försöker - och lyckas ofta - att förklara teori med exempel från verkliga livet.
Sylvia Nasar: A Beautiful Mind
Biografin över John Nash, matematikern som bland annat forskade kring spelteori (som han fick Nobelpriset för 1994). Boken skildrar på ett intressant sätt matematiken och till viss del spelteorin under kriget och efterkrigstiden, samt även rätt mycket om Nashs sjukdom (schizofreni).
Filmen med samma namn är inspirerad av boken, men frisserar sanningarna lite väl mycket för min smak. Filmen har dock sina egna kvaliteter.
Se även
gametheory.net som innehåller mycket mer information, t.ex. spelteori i filmer och skönlitteratur. Det finns även en Dictionary
An Introductory Sketch of Game Theory (bok)
De "rätta" "svaren" på problemen
Som ovan nämns är alla svar på problemen "rätt" om tillräckligt många svarar samma sak, men det finns troligen en gemensam kulturell eller psykologisk grund som gör att många svarar på samma sätt.
Här är de svar som gavs på Schellings undersökning (och skrivs i noten på sid 55). Inom [hakar] skrivs mina kommentarer om möjliga cues etc.
In the writer's sample, 36 persons conserted on "heads" in problem 1, and only 6 chose "tails".
[Möjlig cue: "heads" nämns före "tails" i problemet.]
In problem 2, the first three numbers were given 37 votes out of a total of 41; the number 7 led 100 by a slight margin, with 13 in third place.
[7 är det första talet i listan. 100 är väldigt jämnt och är en tiopotens. Se även andra funderingar kring detta ovan.]
The upper left corner in problem 3 recieved 24 votes out of a total of 41, and all but 3 of the remainder were distributed in the same diagonal line.
[Det övre vänstra är det första om man "läser" bilden som en text. Den längst ned till höger är den sista. Varför man skulle välja de två andra i diagonalen förstår jag inte riktigt. Skulle det vara en 3x3 matris skulle mittenrutan säkert få många röster eftersom den är unik att vara totalt omgiven av andra rutor.]
Problem 4, which may reflect the location of the sample in New Haven, Connecticut, showed an absolute majority managing to get together in at Grand Central Station (information boot), and virtually all of them succeeded in meeting at 12 noon.
[För svenska förhållanden: I Stockholm skulle det troligen bli "Träffpunkten" eller möjligen informationsdisken på Centralstationen, i alla fall om det är icke-stockholmare som ska mötas. Och i Paris är det med största sannolikhet Eifelltornet. 12.00 är den exakta mitten på dagen, både 0000 och 2400 är otydliga gränser till föregående respektive nästa dag.. Notera att man här helt bortser från praktiska saker som att man jobbar, har olika dygnsrytmer, tid för resan till Stockholm etc.]
Problem 6 showed a variety of answers, but twofifths of all persons succeeded in conserted on the number 1; and in problem 7, out of 41 people, 12 got together on $1,000,000, and only 3 entries consisted on numbers that were not a power of 10; of those 3, 2 were $64 and, in the more up-to-date version, $64,000.
[Problem 6: 1 är det första "naturliga" talet. I fråga 7 är 1 miljon en väldigt jämn och tillräckligt stor summa. Kanske skulle en samling matematiker säga gogolplex eller något annat stort tal.]
Problem 8 caused no difficulty to 36 out of 41, who split the total fifty-fifty.
[50-50 är den "naturliga" delningen av något mellan två personer. Några sidor senare finns det liknande exempel där det gäller ungefär samma problem men där det finns extra information såsom att A tjänar $100 per år och B tjänar $150 per år. Hur ska de dela på de $100? Påverkar denna extra information hur pengarna ska delas?]
Problem 9 secured a majority of 20 out of 22 for Robinson. An alternative formulation of it, in which Jones and Robinson were tied on the first ballot at 28 votes each, was intended by the author to demonstrate the difficulty of concerting in case of tie; but the respondents surmonted the difficulty and gave Jones 16 out of 18 votes (apparently on the bases if Jones's earlier position on the list, proving the main point but overwhelming the subsidiary point in the process.
[I den första versionen av problemet valdes Robinsom eftersom denne utmärktes av att ha flest röster och alltså sticker ut som det högsta talet. Man skulle tänka sig att välja på Smith eftersom denne finns först i listan, men i en kontext av röstningsförfararande väger denna ledtråd troligen mindre.]
Posted by hakank at 09:42 EM | Comments (3) | TrackBack