Fractional hedonic games (FHGs) are an appealing class of hedonic coalition formation games, in which the utility of an agent equals the average utility she ascribes to the members of her coalition. We study the problem of maximizing the social welfare in FHGs both in the offline and online setting. For the offline setting, where the problem is known to be NP-hard, we show that no FPTAS exists. For the adversarial arrival online model, with unrestricted utilities, it is known that no constant competitive ratio is achievable with a deterministic algorithm. Therefore, we investigate two other interesting models of online FHGs. In the first one, the agents arrive in a uniformly random order. For this setting, we provide an asymptotically 1/6-competitive algorithm and prove an upper bound of 1/3 on the possible asymptotic competitive ratio. In the second model, an algorithm may dissolve (at no cost) an existing coalition before assigning an arriving agent to a coalition. Here, we show a 1/(6+4√2)-competitive algorithm and prove an upper bound of 1/(3+2√2) on the possible competitive ratio. For the adversarial arrival model, we show that a randomized algorithm achieves a better competitive ratio for symmetric simple FHGs than any deterministic algorithm. We also provide new results on online matching with random vertex arrival on general graphs, with an asymptotically 1/3-competitive algorithm and an upper bound of 1/3 on the possible asymptotic competitive ratio.     «

Fractional hedonic games (FHGs) are an appealing class of hedonic coalition formation games, in which the utility of an agent equals the average utility she ascribes to the members of her coalition. We study the problem of maximizing the social welfare in FHGs both in the offline and online setting. For the offline setting, where the problem is known to be NP-hard, we show that no FPTAS exists. For the adversarial arrival online model, with unrestricted utilities, it is known that no constant co...     »

Fraktionale Hedonische Spiele (FHGs) sind eine ansprechende Klasse von Hedonischen Koalitionsbildungsspielen, bei welchen die Auszahlung an einen Agenten dem durchschnittlichen Nutzen, den der Agent den anderen Mitgliedern seiner Koalition zuschreibt, entspricht. Wir untersuchen das Problem der Maximierung der Sozialen Wohlfahrt in FHGs im Online- und Offline-Szenario. Für das Offline-Szenario, wo das Problem bekanntermaßen NP-schwer ist, zeigen wir, dass kein FPTAS existiert. Für das Online-Modell mit gegnerischer Ankunft ist bekannt, dass, mit unbeschränkten Nutzen, mit einem deterministischen Algorithmus keine konstante Kompetitivität erreicht werden kann. Aus diesem Anlass untersuchen wir zwei andere interessante Modelle für Online-FHGs. Im ersten kommen die Agenten in gleichverteilt zufälliger Reihenfolge an. Für dieses Szenario stellen wir einen asymptotisch 1/6-kompetitiven Algorithmus bereit und beweisen eine obere Schranke von 1/3 für die mögliche asymptotische Kompetitivität. Im zweiten Modell darf ein Algorithmus eine existierende Koalition (kostenlos) auflösen bevor er einen ankommenden Agenten einer Koalition zuweist. Hier zeigen wir einen 1/(6+4√2)-kompetitiven Algorithmus und beweisen eine obere Schranke von 1/(3+2√2) für die mögliche Kompetitivität. Für das Modell mit gegnerischer Ankunft zeigen wir, dass für symmetrische einfache FHGs ein randomisierter Algorithmus eine bessere Kompetitivität als jeder deterministische Algorithmus erreicht. Wir liefern ebenfalls neue Resultate für Online-Paarung mit zufälliger Knoten-Ankunft auf allgemeinen Graphen, mit einem asymptotisch 1/3-kompetitiven Algorithmus und einer oberen Schranke von 1/3 für die mögliche asymptotische Kompetitivität.     «

Fraktionale Hedonische Spiele (FHGs) sind eine ansprechende Klasse von Hedonischen Koalitionsbildungsspielen, bei welchen die Auszahlung an einen Agenten dem durchschnittlichen Nutzen, den der Agent den anderen Mitgliedern seiner Koalition zuschreibt, entspricht. Wir untersuchen das Problem der Maximierung der Sozialen Wohlfahrt in FHGs im Online- und Offline-Szenario. Für das Offline-Szenario, wo das Problem bekanntermaßen NP-schwer ist, zeigen wir, dass kein FPTAS existiert. Für das Online-Mod...     »