BEGIN:VCALENDAR
CALSCALE:GREGORIAN
METHOD:PUBLISH
PRODID:-//github.com/rianjs/ical.net//NONSGML ical.net 4.0//EN
VERSION:2.0
X-FROM-URL:https://eom.sdu.dk/events/ical/cb462340-4cb2-4827-ac2d-7002e316
 0744
X-WR-CALNAME:Kollokvium: Computing better approximate pure Nash equilibria
  in cut games via semidefinite programming
BEGIN:VTIMEZONE
TZID:Europe/Copenhagen
X-LIC-LOCATION:Europe/Copenhagen
BEGIN:DAYLIGHT
DTSTAMP:20260405T222629Z
DTSTART:20261028T030000
SEQUENCE:0
TZNAME:CEST
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
UID:9d106667-8def-4137-b8bc-6454051df375
END:DAYLIGHT
BEGIN:STANDARD
DTSTAMP:20260405T222629Z
DTSTART:20260325T020000
SEQUENCE:0
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
UID:714da029-44a8-44d0-81b2-1c48593ac08c
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DESCRIPTION:[b]Speaker:[/b][nl]\n[url=https://cs.au.dk/~iannis/]Ioannis Ca
 ragiannis\, Department of Computer Science\, Aarhus University[/url][nl][
 nl]\n\n[b]Abstract:[/b][nl]\nCut games are among the most fundamental str
 ategic games in algorithmic game theory. It is well-known that computing 
 an exact pure Nash equilibrium in these games is PLS-hard\, so research h
 as focused on computing approximate equilibria. We present a polynomial-t
 ime algorithm that computes 2.7371-approximate pure Nash equilibria in cu
 t games. This is the first improvement to the previously best-known bound
  of 3\, due to the work of Bhalgat\, Chakraborty\, and Khanna from EC 201
 0. Our algorithm is based on a general recipe proposed by Caragiannis\, F
 anelli\, Gravin\, and Skopalik from FOCS 2011 and applied on several pote
 ntial games since then. The first novelty of our work is the introduction
  of a phase that can identify subsets of players who can simultaneously i
 mprove their utilities considerably. This is done via semidefinite progra
 mming and randomized rounding. In particular\, a negative objective value
  to the semidefinite program guarantees that no such considerable improve
 ment is possible for a given set of players. Otherwise\, randomized round
 ing of the SDP solution is used to identify a set of players who can simu
 ltaneously improve their strategies considerably and allows the algorithm
  to make progress. The way rounding is performed is another important nov
 elty of our work. Here\, we exploit an idea that dates back to a paper by
  Feige and Goemans from 1995\, but we take it to an extreme that has not 
 been analyzed before. [nl][nl]Joint work with Zhile Jiang (to appear in S
 TOC 2023)\n[nl][nl]
DTEND:20230629T140000Z
DTSTAMP:20260405T222629Z
DTSTART:20230629T121500Z
LOCATION:Syddansk Universitet\, Campusvej 55\, 5230\, Odense M
SEQUENCE:0
SUMMARY:Kollokvium: Computing better approximate pure Nash equilibria in c
 ut games via semidefinite programming
UID:2dd7aacf-32d6-4100-beb4-90bbb1e84411
END:VEVENT
END:VCALENDAR