Research Scientist Delves into Problem of Persuading Millions of People to Cooperate for a Secure Internet

Grad­u­ate Stu­dent Yamel Rodriguez and Pro­fes­sor Jared Saia

Any­one who owns a com­puter plays the “Virus Inoc­u­la­tion Game” every day whether they want to or not.  We each decide whether or not to spend money and time to pro­tect our com­puter against mali­cious soft­ware.  In a per­fect world, every­one would make this effort.  In the real world, many do not, hop­ing that the efforts of oth­ers will pro­tect them.

The “Virus Inoc­u­la­tion Game” is just one of many prob­lems in game the­ory that illus­trate what is known as the “tragedy of the com­mons” effect.  Specif­i­cally, self­ish actions of play­ers reduce the over­all social wel­fare. So how do you stack the deck to con­vince more peo­ple to buy the pro­tec­tion soft­ware even if it costs them money in the short term?

UNM Asso­ciate Pro­fes­sor of Com­puter Sci­ence, Jared Saia says one way is to inject an ele­ment of fear into the game to coun­ter­act the nat­ural self-interest of the play­ers.  His lat­est research, funded by the National Sci­ence Foun­da­tion, will test the idea of using a medi­a­tor to achieve this goal.

The job of the medi­a­tor is to per­suade peo­ple to act in a more col­lab­o­ra­tive way.  The medi­a­tor only has the power to offer advice to each player.  The play­ers main­tain their free will and may decide whether or not to fol­low that advice.  Sur­pris­ingly, in many cases, the advice alone can be enough to elim­i­nate the tragedy of the com­mons effect.

For exam­ple, the medi­a­tor might try to con­vince more peo­ple to buy soft­ware to pro­tect their com­put­ers against virus attacks.  Of course, if the medi­a­tor just advises every­body to buy soft­ware, few peo­ple will fol­low his advice.  Instead, the medi­a­tor can use a more per­sua­sive, “reac­tive” algo­rithm that will react to the actions of the play­ers.  In this sce­nario, the medi­a­tor tells a per­son, “Alice” to buy the soft­ware.  If Alice ignores the advice, then with some prob­a­bil­ity, the medi­a­tor later tells sev­eral peo­ple who nor­mally inter­act with Alice not to buy the soft­ware.  That greatly increases the chances of Alice’s com­puter becom­ing infected with a virus.  The medi­a­tor has now intro­duced the fear of infec­tion into the game.

Unfor­tu­nately, a reac­tive algo­rithm may not be prac­ti­cal in a game with mil­lions of anony­mous play­ers.  Thus, Saia has also stud­ied proac­tive algo­rithms.  In this sce­nario, fear of reprisal is “baked in” to the algo­rithm the medi­a­tor uses to advise the players.

Specif­i­cally, when Alice is advised to inoc­u­late, there is some small prob­a­bil­ity that, at the same time, her neigh­bors are all told not to inoc­u­late.  Thus, Alice has a stronger incen­tive to fol­low the mediator’s advice.  If this small prob­a­bil­ity is cho­sen care­fully for Alice, and for all other play­ers in the net­work, it is pos­si­ble to find the right bal­ance of fear and greed that will con­vince peo­ple to act in a way that con­tributes to the safety of everyone.

Saia and his research group will spend the next three years find­ing ways to design medi­a­tors to help ame­lio­rate the tragedy of the com­mons effect. He believes his approach will be use­ful for many types of games includ­ing find­ing ways to ensure shar­ing of resources in sys­tems like Bit­Tor­rent; allow­ing mul­ti­ple users of wire­less fre­quen­cies to share lim­ited band­width; and allow­ing peo­ple to coop­er­ate to counter denial of ser­vice attacks.

Saia is also inter­ested in the the­o­ret­i­cal lim­i­ta­tions of the medi­a­tor approach.  He has shown that there is a cer­tain class of games for which a medi­a­tor can­not reduce a tragedy of the com­mons effect, and is cur­rently study­ing what prop­er­ties of a game allow for effec­tive mediation.

Saia’s research builds on his pre­vi­ous work in which he sought to under­stand the strength of group col­lab­o­ra­tions.  He dis­cov­ered algo­rithms that would allow web-based projects, in which many peo­ple work together on the same prob­lem, to con­tinue to func­tion even if up to a third of the peo­ple work­ing on the project are try­ing actively to destroy it.  These same algo­rithms can now be used as the build­ing blocks for imple­ment­ing a medi­a­tor in a com­pletely dis­trib­uted fashion.

Saia works with col­lab­o­ra­tors around the world to build and test the math­e­mat­i­cal algo­rithms that can be trans­lated into use­ful ways to strengthen the inter­net and make it safer for everyone.

Media con­tact: Karen Went­worth (505) 277‑5627; e-mail: kwent2@unm.edu