טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentRozenfeld Olga
SubjectMediators and Recommenders
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

This work deals with the effects of mediators and recommenders in multi-agent environments. A mediator is an interested external party that wishes to influence a game in order to achieve a desirable outcome. Specifically, we concentrate on solution concepts for games which provide immunity against joint deviations by coalitions of agents. We introduce two new solution concepts for complete information games. The first, which we call equilibrium in group dominant strategies, is the strongest of all known solution concepts so far, encompassing both the ideas behind dominant strategies and strong equilibrium. Because of its strength, GDS does not exist in any interesting game; however, as we show, such solutions can be achieved in various rich settings with the use of mediators.


The second concept, which we call near-strong equilibrium, considers stability against particular unilateral deviations from a deviation. Since near-strong equilibrium is weaker than strong equilibrium, we can consider weaker mediators in order to implement such solutions (e.g. mediators whose only power is to serve as a correlating device). We analyze the existence of near-strong equilibrium compared with strong equilibrium in a well studied setting of network creation.


The second half of this work deals with recommenders in social choice settings. Recommenders, unlike mediators, are not modeled explicitly as an entity within the system; rather, we explore various recommendation systems and their properties (systems which aggregate the ratings of the agents in order to present a set of predicted ratings to a given agent). We differentiate between trust-based and similarity-based recommendation systems.


The goal of a trust-based recommendation system is to generate personalized recommendations from known opinions and

trust relationships. We use the axiomatic approach: formulate desirable properties, and try to characterize aggregation rules that satisfy these properties. We introduce the model, discuss some axioms, and provide a characterization of a class of systems satisfying a set of basic axioms. A particular property we concentrate upon is consistency: the system should not change its predictions when it turns out that its previous predictions were correct.


Next, we do an experimental study of consistency in similarity-based recommendation systems. A basic idea of turning an inconsistent system into a (more) consistent one is adding some of the predictions with higher confidence to the input. We present a systematic study on the performance of such procedures. Our results indicate that the above transformation is helpful when small amount of data is originally available.