Games%with%bounded%ra4onality%agents%â% ... Evolu4onary%games%(couple%games%with% ... skype:%danielemiorandi% mob:%+39.335.78.96.385%.
Game%Theory%and%Programming% Social%Collec4ve%Intelligence% Daniele%Miorandi% CREATE=NET%&%U=Hopper% daniele.miorandi@{create=net.org,u= hopper.com}%
ACKs%and%Logos%
What%this%talk%is%about%% • Ideas% • On=going%research% • Assump4ons%and%hypotheses%yet%to%be% validated% • (Quite%some)%examples%of%real=world%systems%
What%this%talk%is%not%about%
• No%technical%stuff% • No%equa4ons/math% • No%graphs%with%results%
What%this%talks%aim%at%being%
• Inspiring%(op4mis4c)% • Not%(too)%boring%(pessimis4c)% %
Social%Collec4ve%Intelligence% “A#class#of#socio+technical#systems#able#to# leverage,#in#a#coordinated#way,#on#the# complementary#strengths#of#compu;ng# systems,#individuals#and#collec;ves”#
Why?% • Humans%beZer%than%machines%at%some%tasks% (e.g.,%understanding%images,%social%norms%etc.)% • And%vice%versa%(communica4on,%compu4ng,% storage)% • Can%we%‘compose’%them%to%tackle%effec4vely% complex%problems?%
New%vs.%not%new%
New%vs.%not%new%(cont’d)% • When%it%comes%to%computers,%think%of% – Social%networking%%pla]orms% – Crowdsourcing/crowdsensing% – Human%computa4on% – ....%
%BoZom%line% • This%is%not%science%fic4on% • This%is%not%blue%sky%research% • This%is%already%happening%
Example%#1%
Example%#2%
Example%#3%
Example%#3%
“ISN’T'CHESS'SOMETHING' MACHINES'ARE'BETTER'THAN' HUMANS'AT?”'
Example%#3%(cont’d)% • Efficiency,%not%just%performance% – G.%Kasparov:%~25W% – Deep%Blue:%no%data%available.%% • Data%for%Watson:%~200kW%
Example%#4%
Example%#4%(cont’d)%
Example%#5%(DARPA%Network% Challenge,%2009)%
Example%#6%(DARPA%Shredder% Challenge,%2011)%
Example%#7%(DARPA%Tag%Challenge,% 2012)% • 5%ci4es%(Washington%DC,% New%York,%London,% Stockholm,%Bra4slava)% • Suspect%face%+%t=shirt% with%event%logo% • 12hrs%4me% • 3%out%of%5%
Is%it%research?%
Limita4ons% • Current%systems%employing%humans%as% ‘computa4onal%units’%are%primi4ve% • 5%dimensions:%workflow,%social%dynamics,% composi4onality,%collec4veness,%generality%
Limita4on%#1:%Workflows% User% #1%
Mapper%(task% replica4on)%
User% #2%
User% #n%
Reducer% (majority%rule)%
Limita4on%#2:%Social%Dynamics% • Social%dynamics%as%a%powerful% computa4onal%tool% • The%most%basic%example:%peer%pressure%
Limita4on%#3:%Composi4onality% • Devised%upfront%what%is%done%by%humans% and%what%by%machines% • Can%we%build%a%system%able%to%seamlessly% compose%humans%and%machines%as% ‘computa4onal%units’?%
Limita4on%#4:%Collec4veness% • Fail%to%leverage%on%the%power%of%collec4ves% (‘teams’)% • Human%collec4ves%as%examples%of%systems% where%the%whole%(in%terms%of%ability%of%solving% tasks)%is%more%than%the%sum%of%its%parts% • How%to%dynamically%build%collec4ves%for% solving%a%given%task?%
Limita4on%#5:%Generality% • Lack%of%a%principled%approach%towards% how%to%design,%manage%and%control%SCI% systems% • In%par4cular%when%it%comes%to%incen4ves%
One%step%back% • Let’s%look%at%SCI%systems%from%a%computa4onal% perspec4ve% • Computers:%predictable%(modulo%unknown% dimensions%or%some%weird%programming% languages)% • Humans:%high%level%of%diversity,%very%sensi4ve% to%context,%expressing%a%mul4dimensional% value%systems%
So%how%to%‘program’%SCI?% • Move%from%‘programming’%to%‘incen4ves’% • From%algorithmic%behaviour%to%‘good%enough’% behaviour% • Take%advantage%of%performa4vity%
Incen4ves% • • • •
How%to%‘mo4vate’%people%to%do%something% Very%old%topic%in%social%sciences% Rela4vely%new%in%compu4ng% Monetary%vs.%non=monetary% – Non=monetary:%social%dynamics%(e.g.,%peer% pressure,%sense%of%belonging/community),% personal%beliefs%(ac4vism),%expected%return%(non= monetary,%shared%goods)%etc.%
Now%it’s%all%about%incen4ves% • Where%to%start%from?% • My%claim:%game%theory% • Why?%A%reasonable%framework%for%distributed% decision=making%by%autonomous%agents%
Game%Theory%Reloaded% • “GT%is%all%about%equilibria%and%ra4onal% strategic%games”% • In%reality,%there’s%much%more%than%this% • So%what%to%keep%and%what%to%leave%out?% %
The%behaviour% • Humans%are%not%always%ra4onal% – Games%with%bounded%ra4onality%agents%–% procedural%decision%making%
The%game% • In%many%cases%humans%do%not%have%full% informa4on% – Regret%minimiza4on%(modelling%choice%under% uncertainty)% – Par4al%informa4on%games% • Mul4=armed%bandit%games%
– Learning%in%games% • Heuris4c%(adap4ve)%learning% • Coordinated%Bayesian%(ra4onal)%learning%
The%system%dynamics %% • Forget%about%equilibria% • (PPAD=completeness%of%Nash% equilibria)% • Focus%on%dynamics%%
From%individuals%to%collec4ves% • Evolu4onary%games%(couple%games%with% replicator%dynamics)%for%modelling%how%a% given%choice/behaviour%propagates% (‘peer%pressure’)% • Games%on%graph,%to%model%explicitly% social%network%rela4onships%(of%course,% you%need%to%know%it!)%
From%model%to%control% • Algorithmic%mechanism%design% – A%mechanism%solves%a%given%problem%by% assuring%that%the%required%output%occurs,% when%agents%choose%their%strategy%as%to% maximise%their%own%selfish%u4li4es% – E.g.,%design%of%market%mechanisms,%design% of%onine%auc4on%systems%
Do%we%have%all%the%ingredients?% • No% • GT%provides%only%a%high=level%model%of%a% real%hybrid%system%(black%box%vs.%white% box),%we%need%to%put%in%place%adapta4on% mechanisms%for%monitoring%and%steering% in%vivo%
Does%it%sound%too%abstract?%
Maybe% %
So%what%shall%we%be%doing?%
How%to%run%experiments%with% individuals?%
How%to%understand%social%structures% and%dynamics% • Mine%online%social%media!% • Not%an%easy%task%(limited%APIs)% • Open%datasets%publicly%available% – Good%old%web%scraping%always%an%op4on,%in%case%
• Computa4onally%intensive% • No%representa4ve%sampling%
Take%home%messages% • A%highly%challenging%field% • Opportunity%to%mix%scien4fic%research%with% real=world%large=scale%applica4ons% • No%theory%without%experimenta4on%(and%vice% versa)% • Requires%mul4disciplinary%teams%
This%is%sketchy% % % Hopefully%in%the%next%years%it%will%become% clearer!%
Daniele'Miorandi' daniele.miorandi@create=net.org% daniele.miorandi@u=hopper.com% skype:%danielemiorandi% mob:%+39.335.78.96.385%
