BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/9890/23-April-2018-ILLC-Seminar-Anja-Rey
DTSTAMP:20180422T193244
SUMMARY:ILLC Seminar, Anja Rey
ATTENDEE;ROLE=Speaker:Anja Rey
DTSTART:20180423T140000
DTEND:20180423T145000
LOCATION:ILLC Seminar Room F1.15, Science Park 107
, The Netherlands
DESCRIPTION:Coalition formation games model situat
ions in which agents cooperate in teams, such as s
table-roommate problems and project allocation pro
blems, based on individual preferences of the agen
ts. Questions of interests are related to stable a
nd fair outcomes as well as representations of the
se games. In this talk, firstly, an overview of
hedonic games is given. These can model agents' p
references over coalitions (i.e. sets of agents),
where the happiness of agents with a coalition st
ructure only depends on their own coalition. Withi
n the recent twenty years, various representations
and stability notions, such as Nash stability, ha
vebeen studied. Trade-offs exist between compact e
ncodings and expressivity as well as the computati
onal complexity of stability problems. Secondly,
a model of hedonic games with ordinal preferences
and thresholds is presented. Here, it is assumed
that agents only know a subset of their co-agent
s whom they partition into the sets of friends an
d enemies. The remaining agents are considered as
neutral. At the same time they specify a weak ord
er over the former two sets. This relation is ext
ended to a set of possible preferences over coali
tions such that it is reasonable to define the no
tions of possible and necessary stability. While t
his model can express preferences more generally
than related models, the complexity of various st
ability problems does not increase. Nevertheless m
any of these problems remain NP-hard or even hard
for the second level of the polynomial hierarchy.
In the literature natural restrictions are know
n that allow a decision of some stability problem
s. Nevertheless, in order to evaluate the stabili
ty of, e.g., a distribution into working groups, t
he whole game has to be taken into consideration.
In particular, in large institutions or social n
etworks, it would be desirable to deduce global i
nformation from local samples. Finally, in this
talk an initial result to tackle this problem with
property testing in the context of hedonic games
is introduced.
X-ALT-DESC;FMTTYPE=text/html:\n Coalition form
ation games model situations in which agents coope
rate in teams, such as stable-roommate problems an
d project allocation problems, based on individual
preferences of the agents. Questions of interests
are related to stable and fair outcomes as well a
s representations of these games.

\n

\n I
n this talk, firstly, an overview of hedonic games
is given. These

\n can model agents' preferen
ces over coalitions (i.e. sets of agents),

\n
where the happiness of agents with a coalition str
ucture only depends on their own coalition. Within
the recent twenty years, various representations
and stability notions, such as Nash stability, hav
ebeen studied. Trade-offs exist between compact en
codings and expressivity as well as the computatio
nal complexity of stability problems.

\n

\
n Secondly, a model of hedonic games with ordinal
preferences and

\n thresholds is presented. H
ere, it is assumed that agents only know

\n a
subset of their co-agents whom they partition into
the sets of

\n friends and enemies. The remai
ning agents are considered as

\n neutral. At t
he same time they specify a weak order over the fo
rmer

\n two sets. This relation is extended to
a set of possible

\n preferences over coaliti
ons such that it is reasonable to define

\n th
e notions of possible and necessary stability. Whi
le this model

\n can express preferences more
generally than related models, the

\n complexi
ty of various stability problems does not increase
. Nevertheless many of these problems remain NP-ha
rd or

\n even hard for the second level of the
polynomial hierarchy.

\n

\n In the liter
ature natural restrictions are known that allow a
decision

\n of some stability problems. Nevert
heless, in order to evaluate

\n the stability
of, e.g., a distribution into working groups, the<
br>\n whole game has to be taken into considerati
on. In particular, in

\n large institutions or
social networks, it would be desirable to

\n
deduce global information from local samples.
; Finally, in this

\n talk an initial result t
o tackle this problem with property

\n testing
in the context of hedonic games is introduced.

\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/9890/23-April-2018-ILLC-Seminar-Anja-Rey
CONTACT:Yde Venema at Y.Venema at uva.nl
END:VEVENT
END:VCALENDAR