Speaker: |
Phani Raj Lolakapuri |

Organiser: |
Anamay Tengse |

Date: |
Friday, 6 Sep 2019, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We show that in general, equilibrium computation in discrete preference games is PLS-complete, even in the simple case where each agent has a constant number of neighbours. If the edges in the social network are weighted, then the problem is PLS-complete even if each agent has a constant number of neighbours, the metric space has constant size, and every pair of strategies is at distance 1 or 2. Further, if the social network is directed, modelling asymmetric influence, an equilibrium may not even exist. On the positive side, we show that if the metric space is a tree metric, or is the product of path metrics, then the equilibrium can be computed in polynomial time.