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