<p>Consider the following game. We are given two sets of sentences $S_1,S_2$ where $S_1$ is the set of "ambiguous sentences"
and $S_2$ is the set of "explicit sentences". Each ambiguous sentence $s \in S_1$ can be decoded to a set $\Delta(s) \subseteq S_2$. Suppose
furthermore that to each "explicit sentence" $s \in S_2$ is associated a cost $c(s)$, e.g. evaluating the cost of the action described by the sentence.</p>

<p>Now the game involves $n$ players $P_1,...,P_n$ that can communicate through a common network $N$. In each turn, a player $P_i$ can broadcast a sentence $s \in S_1$, and each other player $P_j$ can interpret it as some sentence $s_j \in \Delta(s)$. Suppose that the players are scored as follows: every time a player $P_i$ sends a sentence $s$ decoded into a set of sentences $s_j$, he is charged a score of $\sum_j c(s_j)$.</p>

<p>Suppose for simplicity that there are two types of players: the "honest players" that always choose a minimum-cost decoding, and the "devious players" that always choose a maximum-cost decoding. Is it possible to devise an approximate strategy for the honest players in order to minimize their total score?</p>

CC BY-SA 3.0
2014-03-18T16:14:05.747Z
We could also assume that there are different cost functions $c_1,\ldots,c_p$ corresponding to different criterions to optimize (deep, interesting, funny, etc...), and that each player is assigned a specific function $c_i$ corresponding to its mindset, and always tries to pick a decoding optimizing this cost. Consider an "affinity" function $A(P_i,P_j)$ that sums the scores awarded by player $P_j$ to the messages of $P_i$. For a given partition $K_1,...,K_q$ of the mindsets, is it possible to form a corresponding clustering in the affinity relation within a small number of steps?
NisaiVloot
CC BY-SA 3.0
2014-03-19T03:10:12.337Z
Here is another possible approach for decoding: when player $P_j$ receives a message $s$ from $P_i$, he picks a decoding $d \in \Delta_j(s)$ according to a probability distribution (i.e. with prob. $p_j(d) = c_j(d) / \sum_{d' \in \Delta_j(s)} c_j(d')$), and then awards to $P_i$ the score $p_j(d)$. With this approach it seems possible to confuse adversary players by sending them messages that have many possible decodings w.r.t. their cost function (thus incurring a small score increase from this player).
NisaiVloot
<gt.game-theory>
Message-based games with ambiguous communication
NisaiVloot
# Message-based games with ambiguous communication

(Asked by: username_0 on 2014-03-18)

Consider the following game. We are given two sets of sentences $S\_1,S\_2$ where $S\_1$ is the set of "ambiguous sentences"
and $S\_2$ is the set of "explicit sentences". Each ambiguous sentence $s \in S\_1$ can be decoded to a set $\Delta(s) \subseteq S\_2$. Suppose
furthermore that to each "explicit sentence" $s \in S\_2$ is associated a cost $c(s)$, e.g. evaluating the cost of the action described by the sentence.

Now the game involves $n$ players $P\_1,...,P\_n$ that can communicate through a common network $N$. In each turn, a player $P\_i$ can broadcast a sentence $s \in S\_1$, and each other player $P\_j$ can interpret it as some sentence $s\_j \in \Delta(s)$. Suppose that the players are scored as follows: every time a player $P\_i$ sends a sentence $s$ decoded into a set of sentences $s\_j$, he is charged a score of $\sum\_j c(s\_j)$.

Suppose for simplicity that there are two types of players: the "honest players" that always choose a minimum-cost decoding, and the "devious players" that always choose a maximum-cost decoding. Is it possible to devise an approximate strategy for the honest players in order to minimize their total score?

**Tags:** gt.game-theory

> **Comments:**
> **username_0**: We could also assume that there are different cost functions $c_1,\ldots,c_p$ corresponding to different criterions to optimize (deep, interesting, funny, etc...), and that each player is assigned a specific function $c_i$ corresponding to its mindset, and always tries to pick a decoding optimizing this cost. Consider an "affinity" function $A(P_i,P_j)$ that sums the scores awarded by player $P_j$ to the messages of $P_i$. For a given partition $K_1,...,K_q$ of the mindsets, is it possible to form a corresponding clustering in the affinity relation within a small number of steps?  
> **username_0**: Here is another possible approach for decoding: when player $P_j$ receives a message $s$ from $P_i$, he picks a decoding $d \in \Delta_j(s)$ according to a probability distribution (i.e. with prob. $p_j(d) = c_j(d) / \sum_{d' \in \Delta_j(s)} c_j(d')$), and then awards to $P_i$ the score $p_j(d)$. With this approach it seems possible to confuse adversary players by sending them messages that have many possible decodings w.r.t. their cost function (thus incurring a small score increase from this player).  

---

## 0 answers

