An Incentive-Compatible Distributed Recommendation Model

by
José M. Vidal [1]

Computer Science and Engineering
University of South Carolina
Columbia, SC, USA.
http://jmvidal.cse.sc.edu [2]

1 Recommender Systems

All participants submit their preferences to a central server.
Server provides recommendations.

Problems:

Server becomes a central point of failure and attack target.
Assumes users are willing to provide information to server.

1.1 Paying for Recommendations

A common idea is to have agents pay to read other's recommendations. But this has some problems.

Processing payments adds overhead and third party.
Users don't generally trust agents with their money.

Idea: Trade recommendations.

2 The Model

$D$	set of documents, $d \in D$
$A$	set of agents, $i \in A$
$L_i(d)$	a proposition that is true if $i$ likes $d$
$R_i(d)$	a proposition that is true if $i$ has read $d$
$P_r$	the payoff for reading a liked document.
$C_r$	the cost of reading a document.
$C_m$	the cost of sending a message.

2.1 Utilities

Each agent gets a utility $U_i(d) = P_r - C_r$ when consuming a document it likes, otherwise its $-C_r$.
When two agents meet each must decide whether to tell the other about a document it likes:

Nothing Send

Nothing 0,0 $x_i(j), -C_m$

Send $-C_m, x_j(i)$ $x_i(j)-C_m, x_j(i)-C_m$

where \[ x_i(j) = r_i(j) (Pr[L_i(d)\,|\,L_j(d)] \cdot(P_r - C_r) + (1 - Pr[L_i(d)\,|\,L_j(d)])\cdot(-C_r)) \]
If we assume that $i$ knows which documents $j$ has read then we can approximate it using observations: \[ x_i(j) \approx \frac{|L_i^i \cap L_i^j|}{|L_i^j|}\cdot(P_r - C_r) + \left(1 - \frac{|L_i^i \cap L_i^j|}{|L_i^j|}\right)\cdot(- C_r). \]

2.2 Model Analysis

The payoff matrix is often a Prisoner's Dilemma, so we expect Tit-for-Tat to be the evolutionary stable strategy (so, they will Send).
The actual values of $x_i$ can be approximated with observations.
If two agents have completely uncorrelated preferences then they will rather choose documents randomly.

3 An Agent's Choice

An agent must also decide wether to ask an agent for a recommendation or pick a document at random.
We can calculate the expected utility to be gained from a recommendation: $x_i(j)$, a classic explore vs. exploit problem.
So, we use probabilities.
Also, when the agent receives a request it only replies if it expects more utility from the recommendation ($x_i(j)$) than it costs to send the message ($C_m$).

4 Experimental Model

We represent each document with an n-dimensional binary vector $d$.
An agent's preference is is also an n-dimensional vector $p_i$.
We say that $L_i(d)$ is true if and only if \[ \frac{d \cdot p_i}{n} \leq r \] for some constant $r$.

5 Implementation

http://jmvidal.cse.sc.edu/netlogomas/distributedrec.html [3]

6 Test Results

The total utility as a function of the clustering probability.

6.1 Test Results 2

The total utility when new documents continue to appear.

6.2 Test Results 3

Total utility gain for every agent when c=1 and new documents continue to appear.

6.3 Test Results 4

Total utility gain for every agent when c=.9.

6.4 Test Results 5

Total utility over time with agent-explore set to .05

6.5 Test Results 6

Gain of each agent for $c=1$ with agent-explore set to .05

6.6 Test Results 7

Gain of each agent for $c=.9$ with agent-explore set to .05

7 Conclusions and Future Work

Using information as currency is a viable approach but several obstacles need to be overcome.
Agents that have most common interests perform better. Need better ways to support unique agents (by finding friends quickly?)
The value of a new recommendation evaporates very quickly (unlike money). Need to re-think sharing strategy: share immediately?
Need to consider hostile agents.

	Nothing	Send
Nothing	0,0	$x_i(j), -C_m$
Send	$-C_m, x_j(i)$	$x_i(j)-C_m, x_j(i)-C_m$