Receiver-Oriented Cheap Talk Design

Our work on the setting with transparent motives is closely related to that of Lipnowski and Ravid [17], who studied a cheap talk model where the sender has transparent motives and showed that the best sender equilibrium is the quasi-concave envelope of the sender’s utility function. Our result is complementary since we give the geometric characterization of the best equilibrium for the receiver. In fact, we show that the best equilibrium for the receiver can be computed as the maximum of at most $k^{2}$ affine functions, where $k$ is the number of states in the game.

Restricting the information available to the sender has been increasingly gaining traction in the community. Most notably, Bergemann, Brooks and Morris [6] considered a buyer-seller setting and studied possible ways to limit the seller’s information. In their work, they characterized the set of all pairs of possible utilities achievable in equilibrium. In particular, they provide an algorithm that achieves the optimal way to limit the seller’s information to maximize the expected buyers’ utility. Ichihashi [14] considered a Bayesian persuasion setting and studied how the outcome of the interaction is affected when the sender’s information is restricted. One of their results is that, if the receiver restricts sender information in a pre-play stage, the best utility that the receiver can get in this setting coincides with the one that the receiver would get in the “flipped game”, where the receiver persuades the sender. Other papers have studied similar questions in the context of common-interest coordination games [9, 11] and cheap talk games [15, 13]. The main differences with our work are the fact that (a) we have no restrictions on the utility of the sender or that of the receiver, and (b) we focus on the best equilibrium for the receiver.

The rest of the paper is organized as follows. In Section 2 we introduce the cheap talk setting where the sender has transparent motives. We also provide a geometric characterization of the best equilibrium for the receiver. In Section 3 we introduce filtered information aggregation games, where the receiver can limit the information of the senders. In Section 4 we state our main results regarding the characterization of the best sequential equilibrium for the receiver in filtered information aggregation games, and these are proved in Sections 5, 6 and 7, where we also show how to extend the results of Section 2 to sequential equilibria. We end with a conclusion in Section 8.

An information transmission game involves a sender $s$ and a receiver $r$, and is defined by a tuple $\Gamma=(A,\Omega,p,M,u)$, where $A=\{a_{1},\ldots,a_{\ell}\}$ is the set of actions, $\Omega=\{\omega_{1},\ldots,\omega_{n}\}$ is the set of possible states, $p$ is a commonly known prior distribution over $\Omega$ that assigns a strictly positive probability to each possible state, $M$ is a finite set that contains the messages that the sender can send to the receiver ($M$ is usually assumed to be the set of binary strings of length at most $N$, for some positive integer $N$), and $u:\{s,r\}\times\Omega\times A\longrightarrow\mathbb{R}$ is a utility function such that $u(i,\omega,a)$ gives the utility of player $i$ (where $i$ is either the sender or the receiver) when action $a$ is played at state $\omega$. Each information transmission game instance is divided into three phases. In the first phases, a state $\omega$ is sampled from $\Omega$ following the prior distribution $p$, and this state is disclosed to the sender $s$. During the second phase, the sender sends a message $m\in M$ to the receiver, and in the third phase the receiver plays an action $a\in A$ and each player $i\in\{s,r\}$ receives $u(i,\omega,a)$ utility.

Given an information transmission game $\Gamma=(A,\Omega,p,M,u)$, a strategy profile $\vec{\sigma}$ for $\Gamma$ consists of a pair of strategies $(\sigma_{s},\sigma_{r})$ for the sender and the receiver, where $\sigma_{s}$ is a map from $\Omega$ to distributions over $M$ (which is denoted by $\Delta(M)$), and $\sigma_{r}$ is a map from $M$ to $\Delta(A)$. We say that $\vec{\sigma}$ is a Nash equilibrium if no player can increase its utility by defecting from $\vec{\sigma}$. More precisely, denote by $u_{i}(\vec{\sigma})$ the expected utility that $i$ gets when players play $\vec{\sigma}$, then $\vec{\sigma}$ is a Nash equilibrium if

for all players $i\in\{s,r\}$ and all strategies $\tau_{i}$ for $i$.

For future reference, some of the results in this paper require a stronger notion of equilibrium known as sequential equilibrium. A sequential equilibrium consists of a strategy profile $\vec{\sigma}$ and a belief system $\beta$ that (in this case) assigns a posterior distribution over $\Omega$ to each possible message in $M$. Intuitively, $\beta$ represents the receiver’s beliefs about the posterior distribution over $\Omega$ given the message that it receives from the sender. The pair $(\vec{\sigma},\beta)$ form a sequential equilibrium if

• •

  $\beta$ is consistent with $\vec{\sigma}$, which means that there exists a sequence of completely mixed strategies $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ that converge to $\vec{\sigma}$ such that the sequence of maps from messages to posterior distributions over $\Omega$ obtained by applying Bayes’ rule assuming that the sender plays $\sigma_{s}^{1},\sigma_{s}^{2},\ldots$ converges to $\beta$.

• •

  $\sigma_{r}$ is, according to $\beta$, a best-response for the sender for all messages $m\in M$.

In this section, we are interested in information transmission games in which the sender has transparent motives. This means that the sender’s utility $u(s,\omega,a)$ only depends only on the action $a$ played by the receiver, and not on the state $\omega$. Thus, for simplicity, we will define functions $u_{s}:A\to\mathbb{R}$ and $u_{r}:\Omega\times A\to\mathbb{R}$ that denote the utilities of the sender and the receiver respectively. More precisely, $u_{s}(a):=u(s,\omega,a)$ and $u_{r}(\omega,a):=u(r,\omega,a)$ for all $\omega\in\Omega$ and $a\in A$.

In this section, we are interested in finding the best Nash equilibrium for the receiver given an information transmission game with transparent motives. We show later how to extend this equilibrium to a sequential equilibrium in Section 7.

We start by considering the case where the state space $\Omega$ is binary (i.e., $\Omega=\{\omega_{0},\omega_{1}$). We can assume without loss of generality that there exist $\ell+1$ real numbers $0=b_{1}<b_{2}<\ldots<b_{\ell+1}=1$ such that action $a_{i}$ is optimal for the receiver if and only if the posterior probability $q$ of state $\omega_{1}$ after her interaction with the sender is in the interval $[b_{i},b_{i+1}]$. To see this, note that the expected utility of the receiver given some action $a$ is a linear function over $q$ that goes from $(0,u_{r}(\omega_{0},a))$ to $(1,u_{r}(\omega_{1},a))$. Therefore, the set of points in which an action $a$ gives the maximal utility over all other actions is an interval in $[0,1]$. If this interval is empty for some action $a$, it means that $a$ will never be played under any circumstances since there will always be better options for the receiver. This implies that, without loss of generality, we can simply remove $a$ from $A$ and keep only those actions that are maximal at some point.

Using a slight abuse of notation, let $u_{r}(a,q)$ denote the expected utility of the receiver given action $a$ and the posterior probability $q$ of $\omega_{1}$. Note that $u_{r}(a,q)$ can be computed by the following expression:

For each $j\in\{1,2,\ldots,\ell+1\}$, let $I(j):=[u_{s}(a_{j-1}),u_{s}(a_{j})]$ (using the convention that $a_{-1}:=a_{0}$ and $a_{\ell+1}:=a_{\ell}$), and let $C$ be the subset of pairs $(j,k)\in[l+1]^{2}$ such that $I(j)\cap I(k)\not=\emptyset$. At a high level, $(j,k)\in C$ if the optimal actions with prior $b_{i}$ and the optimal actions with prior $b_{j}$ can be combined in such a way that the utility of the sender is equal in both combinations.

Let

Before proving Theorem 1, we illustrate its use via the following simple example. Consider an information transmission game $\Gamma=(A,\Omega,p,M,u)$ with transparent motives such that $|\Omega|=2$ and $A=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}$, in which the utilities are defined as follows:

If we plot the utility of the receiver in a bubbling equilibrium in which no information is revealed we get the following figure, where the dotted line represents the utility of the receiver as a function of the prior probability that the realized state is $\omega_{1}$.

If we follow the construction of Theorem 1, we have that $b_{1}=0$ $b_{2}=\frac{1}{6}$, $b_{3}=\frac{1}{3}$, $b_{4}=\frac{2}{3}$, $b_{5}=\frac{5}{6}$ and $b_{6}=1$, and the set $C$ consists of all pairs of the form $(j,j+1)$ in addition to $(1,3)$, $(2,5)$, $(3,5)$ and $(4,6)$. Thus, it follows from Theorem 1 that the function $\tilde{u}_{r}$ that represents the receiver’s utility in a Nash equilibrium is obtained by taking the maximum of the bubbling equilibrium and the following four segments: the segment $s_{1}$ that connects $(b_{1},\frac{1}{2})$ to $(b_{3},0)$, the segment $s_{2}$ that connects $(b_{2},\frac{1}{6})$ to $(b_{5},\frac{1}{6})$, the segment $s_{3}$ that connects $(b_{3},0)$ to $(b_{5},\frac{1}{6})$, and the segment $s_{4}$ that connects $(b_{4},0)$ to $(b_{6},\frac{1}{2})$, which are represented in the figure below with a solid green line:

Thus, the maximum utility that the receiver can get in a Nash equilibrium of $\Gamma$ is represented by the solid black line in the figure below:

Next, we proceed with the proof of Theorem 1.

In this section we generalize the proof of Theorem 1 to arbitrary information transmission games with transparent motives. At a high level, both the statement and the proof are quite similar to the case with binary states, although they require additional notation.

Let $\Gamma=(A,\Omega,p,M,u)$ be an information transmission game with transparent motives where $\Omega=\{\omega_{1},\ldots,\omega_{n}\}$ and $A=\{a_{1},\ldots,a_{\ell}\}$. As in the proof of Theorem 1, we identify $\Delta(\Omega)$ with $\Delta^{n-1}$ (the $n-1$-dimensional simplex) and assume without loss of generality that there exists no strictly dominated action. More generally, we assume without loss of generality that all actions are optimal in some posterior distribution, which is that, for all actions $a\in A$, the set

is non-empty.

Let $D_{1},D_{2},\ldots,D_{\ell}$ be the polytopes contained in $\Delta^{n-1}$ such that $D_{j}$ contains the set of points $q\in\Delta^{n-1}$ for which action $a_{j}$ is a best response given that the posterior distribution is $q$. Given a point $q\in\Delta^{n-1}$, let $A(q)$ be the set of indices $j\in[\ell]$ such that $v\in D_{j}$ and let $I(q):=[\min_{j\in A(v)}u_{s}(a),\max_{j\in A(v)}u_{s}(a)]$. Intuitively, $I(q)$ is the interval ranging from the minimum to the maximum utility that the sender can get with a receiver’s best-response for $q$. Let $V$ be the union of the set of vertices of $D_{1},D_{2},\ldots,D_{\ell}$ (i.e., $V$ is the set of points that are vertices of at least one of the polytopes), and let $C$ be the set of tuples of points $v_{1},\ldots,v_{k}$ of $V$ such that $k\leq n$ and the intersection of all of the intervals $I(v_{i})$ is non-empty. More precisely,

Moreover, given any vertex $\vec{v}=(v_{1},\ldots,v_{k})\in C$, let $H(\vec{v})\subseteq\Delta^{n-1}$ be the convex hull of $\{v_{1},\ldots,v_{k}\}$ (i.e., the set of all the affine combinations of points in $\vec{v}$). Let

where $a(v)$ is the action in $A(v)$ that has the lowest index and $(\alpha_{i})_{i=1}^{k}\in\Delta^{k-1}$ are some affine parameters such that $\sum_{i=1}^{k}\alpha_{i}v_{i}=p$. The generalization of Theorem 1 is as follows.

In this section we provide an algorithm that, given an information transmission game $\Gamma=(A,\Omega,p,M,u)$ with $|A|=n$, computes the best utility of the receiver in a Nash equilibrium and runs in $O(n\log n)$ time. By Theorem 1, we know that the best utility of the receiver in a Nash equilibrium of $\Gamma$ is a piece-wise linear function. More precisely, there exists a positive integer $k\leq n$, a sequence of $k+1$ real numbers $0=x_{1}<x_{2}<\ldots<x_{k+1}=1$, and $k$ linear functions $f_{1},\ldots,f_{k}$ such that, if $q$ is the prior probability that the realized state is $\omega_{1}$, then

Before describing the algorithm, we need the following additional notation. Given two pairs of indices $(i,j)\in C$ and $(i^{\prime},j^{\prime})\in C$, we say that $(i,j)$ is dominated by $(i^{\prime},j^{\prime})$ if $i\geq i^{\prime}$ and $j\leq j^{\prime}$. Intuitively, $(i,j)$ is dominated by $(i^{\prime},j^{\prime})$ if they both belong to $C$ and the interval $[i^{\prime},j^{\prime}]$ contains the interval $[i,j]$. It is easy to check that, if $(i^{\prime},j^{\prime})$ dominates $(i,j)$, then, for each point $(x,y)$ in the segment $s_{i,j}$ that goes from $(b_{i},u_{r}(a_{i}))$ to $(b_{j},u_{r}(a_{j}))$, there exists a point $(x,y^{\prime})\in s_{i^{\prime},j^{\prime}}$ with $y^{\prime}\geq y$ (this follows directly from the fact that the utility of the receiver is a convex function over the prior). This means that, in order to find the maximum of all the segments $s_{i,j}$ with $(i,j)\in C$, we can restrict the search to segments that are not dominated by other segments. In particular, if we denote by $C_{\max}(i)$ the maximum index $j$ such that $(i,j)\in C$, we can restrict our search to all segments of the form $s_{i,C_{\max}(i)}$.

Suppose that we have an oracle that gives $C_{\max}(i)$ for each $i$ in constant time. We show next how to construct an $O(n\log n)$ algorithm $\pi^{C_{\max}}$ that outputs $k$ and the sequences $x_{1},\ldots,x_{k+1}$ and $f_{1},\ldots,f_{k}$ using $C_{\max}$ as a black box. At a high level, the algorithm computes all the segments of the form $s_{i,C_{\max}(i)}$ and runs a variant of the Bentley-Ottmann algorithm in which, (a) we only output the segment intersections that involve the segment with the highest $y$-coordinate, and (b) whenever two segments $s$ and $s^{\prime}$ intersect, it eliminates the segment with the lowest slope. This guarantees that the number of segment intersections processed by the algorithm is at most $n$, and therefore that the total complexity of the algorithm is $O(n\log n)$. More precisely, $\pi^{C_{\max}}$ consists of running a vertical sweep-line $L$ that moves across the $x$-axis from left to right while keeping a list of all the segments that $L$ intersects, sorted by the $y$-coordinate of their intersection with $L$. In order to do so, we need two data structures: a binary search tree $T$ whose purpose is to keep track of all the segments that $L$ intersects, sorted by $y$-coordinate, and a priority queue $Q$ whose purpose is to keep a list of all the events that occur as $L$ moves from left to right, sorted by $x$-coordinate. There are three types of events:

• •

  A segment $s$ begins. In this case, we insert $s$ in $T$ and query from $T$ the segments $s^{\prime}$ and $s^{\prime\prime}$ that are immediately above and below $s$, respectively. If $s$ intersects $s^{\prime}$ or $s$ intersects $s^{\prime\prime}$, we add these intersections to the event queue.

• •

  A segment $s$ ends. If $s$ is still in $T$, we remove $s$ from $T$. Let $s^{\prime}$ and $s^{\prime\prime}$ be the segments in $T$ that are immediately above and below $s$. If $s^{\prime}$ and $s^{\prime\prime}$ intersect, we add the intersection to the event queue.

• •

  There is an intersection $P$ between two segments $s$ and $s^{\prime}$. If either $s$ or $s^{\prime}$ has been previously deleted from $T$, this event is ignored. Otherwise, we erase from $T$ the topmost segment between $s$ and $s^{\prime}$ and proceed as if the erased segment ended (i.e., we check the segments that are immediately above and below of the erased segment and, if they intersect, we add the intersection). If the segment removed was also the topmost segment of all $T$, we append $P$ to the output.

The full algorithm is as follows. We initialize an empty binary search tree $T$ and an empty priority queue $Q$ and push $2n$ events to $Q$ indicating the beginning and end of segments $s_{1,C_{\max}(1)},s_{2,C_{\max}(2)},\allowbreak\ldots,s_{n,C_{\max}(n)}$. We then process the events in $Q$ as described above until $Q$ becomes empty and output the sequence of points obtained this way, in addition to $(0,u_{r}(a_{1}))$ and $(1,u_{r}(a_{n}))$. The values $x_{i}$ correspond to the $x$-coordinates of the points in the output, and the linear functions $f_{i}$ are the ones that interpolate each pair of consecutive points.

The proof of correctness is equivalent to that of the Bentley-Ottmann algorithm. Note that the only difference between the algorithms is the way that we process the intersection events in $\pi^{C_{\max}}$. The Bentley-Ottmann algorithm outputs all segment intersections and, to do so, it swaps $s$ and $s^{\prime}$ inside $T$ whenever $s$ and $s^{\prime}$ intersect (instead of processing them the way that we do). However, since a segment that is surpassed in $y$-coordinate by another segment can never be maximal again, we can optimize the algorithm by removing it right after processing its intersection. Since each intersection event erases one of the segments involved, we process at most $n$ intersection events, which means that we process in total $3n$ events ($n$ starting points, $n$ endpoints, and $n$ intersections). Since each event is processed in $O(\log n)$ time, the total time complexity is $O(n\log n)$. To see that the output of $\pi^{C_{\max}}$ is correct, note that the vertices that define the piece-wise linear function $\tilde{u}_{r}$ are either (a) intersections of different segments $s_{i,j}$ or (b) points in which a segment $s_{i,j}$ ends and another segment $s_{i^{\prime},j^{\prime}}$ begins. If we use an implementation trick where we always process starting point events before endpoint events, the points defined in (b) would also be considered as intersections. This means that, using this implementation trick, the desired set of vertices is the subset of all segment intersections that occur at the top layer of the segments, which is precisely what $\pi^{C_{\max}}$ outputs.

As a final note regarding this part of the algorithm, note that, as in Theorem 1, we are assuming that $\Gamma$ is given in a form such that there exist $n+1$ real numbers $0=b_{1}<b_{2}<\ldots<b_{n+1}=1$ such that action $a_{i}$ is the receiver’s optimal action in the interval $[b_{i},b_{i+1}]$. However, even if we can assume that $\Gamma$ has this form without loss of generality, the input of the algorithm may not be reduced to this form yet. However, we can perform the same variant of the Bentley-Ottmann algorithm in order to reduce $\Gamma$ to such a form, and to compute $b_{1},b_{2},\ldots,b_{n+1}$. To see this, note that the linear function that outputs the utility that the receiver gets by playing $a_{i}\in A$ as a function of the prior is a segment going from $(0,u_{r}(0,a_{i}))$ to $(1,u_{r}(1,a_{i}))$. Reducing $\Gamma$ to the desired form means precisely to compute the upper envelope of this set of segments.

Now, we have an $O(n\log n)$ algorithm $\pi^{C_{\max}}$ that, given $C_{\max}$ as a black box, computes the best utility for the receiver. It remains to show how to compute $\{C_{\max}(1),\ldots,C_{\max}(n)\}$ in $O(n\log n)$ time as well.

Efficient Computation of $C_{\max}$

By definition, $(j,k)\in C$ if $I(j)\cap I(k)\not=\emptyset$, where $I(j)=[u_{s}(a_{j-1}),u_{s}(a_{j})]$. For simplicity, denote by $s_{j}$ and $e_{j}$ the minimum and maximum of $I(j)$, respectively. Consider the following algorithm $\rho$:

1. 1.

   Step 1: Initialize an array $C$ of $n$ elements in which $C[i]=i$ for all $i\in n$.

2. 2.

   Step 2: Initialize an empty array $A$. For each $j\in[n]$, append $(s_{j},0,j)$ and $(e_{j},1,j)$ to $A$.

3. 3.

   Step 3: Sort $A$ in lexicographical order (i.e., sort by the first coordinate, break ties with the second coordinate and then with the third one).

4. 4.

   Step 4: Initialize an empty binary search tree $T$ and two empty arrays $Pos_{1},Pos_{2}$ of $n$ elements each. Iterate through the elements $A[i]:=(a,b,j)$ of $A$ and do the following. If $b=0$, set $Pos_{1}[j]=i$, insert $j$ in $T$, and set $C[a]=T_{\max}$, where $T_{\max}$ is the maximal element of $T$. Otherwise, set $Pos_{2}[j]=i$, and remove $j$ from $T$.

5. 5.

   Step 5: For each $i\in[n]$, set $C[i]$ to the maximum between $C[i]$ and the highest third coordinate between all the elements of $A$ in the interval $[Pos_{1}[i],Pos_{2}[i]]$.

We claim that $\rho$ outputs $C_{\max}$ and can be implemented in $O(n\log n)$ time. To see that it gives the correct output, note that, given $k\in[n]$, the highest $j$ such that $I(k)\cap I(j)\not=\emptyset$ is either (i) the highest $j$ such that $s_{j}$ or $e_{j}$ appear between $s_{i}$ and and $e_{i}$ (after sorting all the starting points and endpoints of each interval as in Step 3), or (ii) the highest $j$ such that $s_{j}$ appears before $s_{i}$ and $e_{j}$ does not appear before $s_{i}$. The values described in (i) and (ii) are calculated in step 4 and step 5, respectively. To see that $\rho$ can be implemented in $O(n\log n)$ time, note that steps 1,2,3 and 4 can be implemented in $O(n\log n)$ time. A naive implementation of step 5 would be quadratic in $n$, but it can be performed in $O(n\log n)$ using a Segment Tree data structure.

In this section we analyze the effects of filtering on information aggregation games. At a high level, information aggregation games are information transmission games with multiple senders. For a rigorous definition, an information aggregation game consists of a receiver $r$, and a tuple $\Gamma=(S,A,\Omega,p,M,u)$ $S=\{1,2,\ldots,k\}$ is the set of senders and $A=\{a_{1},\ldots,a_{\ell}\}$, $\Omega=\{\omega_{1},\ldots,\omega_{k}\}$, $p\in\Delta(\Omega)$, $M$ and $u$ are defined as in Information Transmission games (see Section 2.1), with the only exception that $u$ is a function from $S\cup\{r\}\times\Omega\times A$ to $\mathbb{R}$ instead of a function from $\{s,r\}\times\Omega\times A$ to $\mathbb{R}$.

We are interested in a setting where the receiver can filter potential information from the senders. We model this as follows: at the beginning of the game, there is an additional phase (phase 0) where the receiver publicly chooses a function $X:\Omega\to\Delta(\{0,1\}^{*})$ that maps each state $\omega$ to a distribution over possible signals (we assume that signals are binary strings of arbitrary length). We call this function filter. The rest of the game follows exactly in the same way as in a (standard) information aggregation game, except that, if the realized state is $\omega$, the senders receive a signal $x$ sampled from $X(\omega)$ instead of $\omega$ itself. We call this a filtered information aggregation game (FIAG). More formally, a FIAG $\Gamma^{F}=(S,A,\Omega,p,M,u)$ runs as follows:

• •

  Phase 0: The receiver chooses a filter $X:\Omega\to\Delta(\{0,1\}^{*})$. The filter is disclosed to the senders.

• •

  Phase 1: A state $\omega\in\Omega$ is sampled according to the distribution $p$ and is disclosed to the senders.

• •

  Phase 2: Each sender $i\in S$ sends a message $m_{i}\in M$ to the receiver $r$.

• •

  Phase 3: The receiver plays an action $a\in A$.

• •

  Phase 4: Each player $i\in S\cup\{r\}$ receives $u(i,\omega,a)$ utility.

For an illustration of how the receiver may benefit from filtering, consider the following example.

We show next that, in Example 1, the receiver can double her maximal utility by filtering the sender’s information.