BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/990
DTSTAMP:20230914T125946Z
SUMMARY:Computational Aspects of Equilibria in Discrete Preference Games
DESCRIPTION:Speaker: Phani Raj Lolakapuri\n\nAbstract: \nAbstract: We stud
 y the complexity of equilibrium computation in discrete preference games. 
 These games were introduced by Chierichetti\, Kleinberg\, and Oren (EC '13
 \, JCSS '18) to model decision-making by agents in a social network that c
 hoose a strategy from a finite\, discrete set\, balancing between their in
 trinsic preferences for the strategies and their desire to choose a strate
 gy that is `similar' to their neighbours. There are thus two components: a
  social network with the agents as vertices\, and a metric space of strate
 gies. These games are potential games\, and hence pure Nash equilibria exi
 st. Since their introduction\, a number of papers have studied various asp
 ects of this model\, including the social cost at equilibria\, and arrival
  at a consensus.\nWe show that in general\, equilibrium computation in dis
 crete preference games is PLS-complete\, even in the simple case where eac
 h agent has a constant number of neighbours. If the edges in the social ne
 twork are weighted\, then the problem is PLS-complete even if each agent h
 as 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 socia
 l network is directed\, modelling asymmetric influence\, an equilibrium ma
 y 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 equilibriu
 m can be computed in polynomial time.\n
URL:https://www.tcs.tifr.res.in/web/events/990
DTSTART;TZID=Asia/Kolkata:20190906T171500
DTEND;TZID=Asia/Kolkata:20190906T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR