BEGIN:VCALENDAR VERSION:2.0 PRODID:ILLC Website X-WR-TIMEZONE:Europe/Amsterdam BEGIN:VTIMEZONE TZID:Europe/Amsterdam X-LIC-LOCATION:Europe/Amsterdam BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:19700329T020000 RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:19701025T030000 RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:/NewsandEvents/Archives/2018/newsitem/9890/23- April-2018-ILLC-Seminar-Anja-Rey DTSTAMP:20190307T164604 SUMMARY:ILLC Seminar, Anja Rey ATTENDEE;ROLE=Speaker:Anja Rey DTSTART;TZID=Europe/Amsterdam:20180423T140000 DTEND;TZID=Europe/Amsterdam:20180423T145000 LOCATION:ILLC Seminar Room F1.15, Science Park 107 , Amsterdam 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/Archives/2018/newsitem/9890/23- April-2018-ILLC-Seminar-Anja-Rey CONTACT:Yde Venema at Y.Venema at uva.nl END:VEVENT END:VCALENDAR