Justin Toth (University of Waterloo): A General Framework For Computing the Nucleolus Via Dynamic Programming
Justin Toth (University of Waterloo) presents A General Framework For Computing the Nucleolus Via Dynamic Programming at the Corvinus Game Theory SeminarSzervezők elérhetősége
C épület, 708
In a cooperative game when the problem of computing the minimum excess
coalition for a given allocation can be formulated as a dynamic program
we show that the nucleolus can be computed in time polynomial in the
size of the dynamic program. This gives
a general technique for designing efficient algorithms for computing
the nucleolus of a cooperative game. This technique is inspired by a
recent result of Pashkovich on weighted voting games. However, our
technique significantly extends beyond the capabilities
of previous work. We demonstrate this by applying it to give an
algorithm for computing the nucleolus of b-matching games in polynomial
time on graphs of bounded treewidt
If you wish
to receive a link for the zoom meeting on the day of the event, please
send an email to Tamás Solymosi (tamas dot solymosi at uni dash corvinus
dot hu)