a1: a2, a3, a5
a2: a1, a3, a4
a3: a1, a2. a5
a4: a2
a5: a1, a3
a6:

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}
pairs = {(k,v) for k in agents for v in agents[k]}

pairs = {(k,v) for k,vs in agents.iteritems() for v in vs}

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

interactions = []
for agent, connections in agents.iteritems():
    interactions.extend((agent, connection) for connection in connections if agent < connection)

print interactions
# [('a1', 'a2'), ('a1', 'a3'), ('a1', 'a5'), ('a3', 'a5'), ('a2', 'a3'), ('a2', 'a4')]

>>> from itertools import combinations
>>> agents=['a1','a2','a3','a4','a5']
>>> list(combinations(agents, 2))
[('a1', 'a2'), ('a1', 'a3'), ('a1', 'a4'), ('a1', 'a5'),
 ('a2', 'a3'), ('a2', 'a4'), ('a2', 'a5'),
 ('a3', 'a4'), ('a3', 'a5'),
 ('a4', 'a5')]
>>>

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

pairs = {tuple(sorted((k,v))) for k in agents for v in agents[k]}