Join table on some conditions
You don't need to include the table activities in the query at all. Only messages:
SELECT DISTINCT activity_id
FROM   messages m
WHERE  sender_id &lt;= receiver_id   -- reduce rows
AND    EXISTS (
    SELECT 1
    FROM   messages
    WHERE  activity_id = m.activity_id
    AND    sender_id   = m.receiver_id
    AND    receiver_id = m.sender_id
    );

That's much like @dezso's query, just on the right table and with an additional feature.
The condition sender_id &lt;= receiver_idis not strictly needed, but excludes half of the rows right away, increasing performance.
Index
The perfect index for the case should be a multicolumn index on all three columns in the WHERE condition of the EXISTS semi-join:
CREATE INDEX foo_idx ON messages (activity_id, sender_id, receiver_id);

Two squeeze out the last drop of read performance, you could make that a highly specialized partial index:
CREATE INDEX foo_idx ON messages (activity_id, sender_id, receiver_id)
WHERE receiver_id &lt;= sender_id;

And adapt the query accordingly:
...
WHERE  EXISTS (
    SELECT 1
    FROM   messages
    WHERE  activity_id = m.activity_id
    AND    sender_id   = m.receiver_id
    AND    receiver_id = m.sender_id
    AND   receiver_id &lt;= sender_id  -- redundant, just for partial index
    );
The added condition lets Postgres know, it can use the partial index.
This will only be moderately faster than the plain solution on top. Only worth the hassle if you need to optimize performance.
Alternatives
If there are many messages per activity, in particular also multiple message exchanges between different pairs, then this query will be faster:
SELECT activity_id
FROM   activities a
WHERE  EXISTS (
   SELECT 1
   FROM   messages m
   WHERE  m.activity_id = a.activity_id
   AND    sender_id &lt;= receiver_id
   AND    EXISTS (
      SELECT 1
      FROM   messages
      WHERE  activity_id = m.activity_id
      AND    sender_id   = m.receiver_id
      AND    receiver_id = m.sender_id
      AND    receiver_id &lt;= sender_id -- ?
      )
   );

Similar optimization possible as above. But you'd need another index:
CREATE INDEX foo2_idx ON messages (activity_id, sender_id, receiver_id)
WHERE  sender_id &lt;= receiver_id;

In this case the simple index might prevail (instead of reading from two smaller indexes). Again, test.
And while you are retrieving the whole table I would also compare performance with INTERSECT:
SELECT DISTINCT activity_id
FROM (
   SELECT DISTINCT activity_id, sender_id, receiver_id
   FROM   messages m
   WHERE  sender_id &lt;= receiver_id
   INTERSECT 
   SELECT DISTINCT activity_id, receiver_id, sender_id
   FROM   messages m
   WHERE  receiver_id &lt;= sender_id
   ) sub;

Might perform well, even without index. I would experiment with indexes and possibly GROUP BY instead of DISTINCT, or drop the DISTINCT in the subquery (depending on data distribution) to find the fastest variant.
All of these queries count a message to self as &quot;exchange&quot;, since those qualify for both directions. If there are no messages with sender_id = receiver_id, replace all the &lt;= with &lt; ...