MichaelR: "Präferenzsysteme"...

Hallo,

für ein Projekt suche ich Infos zu folgendem:

Als Beispiel nehmen wir mal drei Veranstaltungen, zu denen sich Kunden anmelden können. Dabei geben sie für jede eine Präferenz ab, also für die, die sie am liebsten besuchen würden, die 1, für zweitliebste die 2 und für die letzte Veranstlatung eine 3. Haben sie an einer Veranstaltung gar kein Interesse so können sie "X" angeben. Als Kundenmenge nehmen wir mal 100 Leute.

Die Verteilung der begrenzten Plätze auf diesen Veranstaltungen erfolgt jetzt nach den abgegebenen Präferenzen.
Soweit die Anzahl der Interessenten kleiner als die jeweilige Platzanzahl ist, ist es ja kein Problem, denn dann bekommt jeder, der eine 1 eingetragen hat, den gewünschten Platz. Problematischer wird es aber, wenn die Plätze nicht ausreichen ...

Ich hab schon eine gewisse Vorstellung wie ich (für dieses Beispiel bzw. für mein richtiges Projekt) die Anzahl der Plätze so verteilen kann, dass ich die höchste Zuteilungsquote habe (d. h. 100% = jeder bekommt, das was er will, z. B. 30% ein Großteil der Interessenten bekommen einen schlechten oder gar keinen Platz......)

Was mich jetzt interessieren würde, vielleicht kennt jemand ein paar Infoseiten, die sich mit Algorithmen zum Thema "Platzvergabe mit einem Präferenzsystem" beschäftigen?
Ich hoffe mein kurzes Beispiel hat einigermaßen klar gemacht worauf ich hinaus will?!

Danke+Grüße,
Michael

PS: Google hat nicht wirklich brauchbare Seiten zu Tage gefördert....

  1. Als Beispiel nehmen wir mal drei Veranstaltungen, zu denen sich Kunden anmelden können. Dabei geben sie für jede eine Präferenz ab, also für die, die sie am liebsten besuchen würden, die 1, für zweitliebste die 2 und für die letzte Veranstlatung eine 3. Haben sie an einer Veranstaltung gar kein Interesse so können sie "X" angeben. Als Kundenmenge nehmen wir mal 100 Leute.

    Problematischer wird es aber, wenn die Plätze nicht ausreichen ...

    Was mich jetzt interessieren würde, vielleicht kennt jemand ein paar Infoseiten, die sich mit Algorithmen zum Thema "Platzvergabe mit einem Präferenzsystem" beschäftigen?

    Weil die Anforderungslage trivial ist.

    Wie würdest Du denn die Sache "zu Fuss" umsetzen? Vielleicht durch Auslosen? Würden die Kunden vielleicht auch vorab benachrichtigt werden?

    Übrigens ist die gesamte Logik des Vorhabens zumindest zweifelhaft, wer meldet sich schon gerne auf "gut Glück" an? Kunden jedenfalls eher nicht, es müssten schon Zwangsteilnehmer sein.

    1. Wie würdest Du denn die Sache "zu Fuss" umsetzen? Vielleicht durch Auslosen? Würden die Kunden vielleicht auch vorab benachrichtigt werden?

      Wie geschrieben hab ich ja eine gewisse Vorgehensweise, ich wollte nur wissen ob es Alternativen gibt, die vielleicht an der einen oder anderen Stelle besser sind!

      Übrigens ist die gesamte Logik des Vorhabens zumindest zweifelhaft, wer meldet sich schon gerne auf "gut Glück" an? Kunden jedenfalls eher nicht, es müssten schon Zwangsteilnehmer sein.

      Auch wenn der Begriff "Kunden" hier vielleicht missverständlich ist, es gibt zahlreiche Anwendungsmöglichkeiten, z. B. im Hochschulbereich.

      1. Wie würdest Du denn die Sache "zu Fuss" umsetzen? Vielleicht durch Auslosen? Würden die Kunden vielleicht auch vorab benachrichtigt werden?

        Wie geschrieben hab ich ja eine gewisse Vorgehensweise, ich wollte nur wissen ob es Alternativen gibt, die vielleicht an der einen oder anderen Stelle besser sind!

        Wie sieht der Algorithmus denn genau aus?

        Vielleicht so:
        1.) Du füllst die Veranstaltungen, für die es nicht zu viele Anwärter gibt auf
        2.) Du füllst die Veranstaltungen, für die es zu viele Anwärter gibt durch Auslosen auf (erst die mit "Präferenz=2", dann die mit "Präferenz=3" etc.
        3.) Du presst den Rest mit Hilfe einer kleinen Regelmenge, die Du gerne beschreiben darfst, und durch Auslosung in andere verfügbare Veranstaltung, wiederum unter Berücksichtigung der Präferenz

        Mir scheint es so, dass ein einfaches Vorgehen das optimale Vorgehen darstellt. Gibt es da Gegenüberlegungen?

        1. OK, die Sache ist etwas komplexer.   ;)

          Du müsstest zuerst ein Zufriedenheitsmodell erarbeiten, dass die Kursteilnehmerzufriedenheit wiederspiegelt. Dazu kannst Du willkürlich ein System entwickeln (bspw. 100 Punkte für jeden Teilnehmer, der sein Wunschseminar bekommt, 50 Punkte für denjenigen, der Plan B erhält, 40 Punkte für denjenigen, der Plan C frisst, etc.) oder Du nimmst Zufriedenheitsmessungen vor. Letztere werden in der Praxis in der Tat über sog. Feedback-Bögen vorgenommen. Allerdings muss man die Teilnehmer per Bepreisung in aller Regel dazu drängen, zudem sind die Daten oft falsch.   :)

          Liegt ein Zufriedenheitsmnodell vor, kannst Du einen Mathematiker darauf loslassen. Das von mir weiter oben skizzierte Modell dürfte suboptimal sein, an hohen Ansprüchen gemessen.

          Ob Du dazu im Web was findest? Hmm, eine Diplomarbeit vielleicht?   ;)

          1. Moin!

            Du müsstest zuerst ein Zufriedenheitsmodell erarbeiten, dass die Kursteilnehmerzufriedenheit wiederspiegelt. Dazu kannst Du willkürlich ein System entwickeln (bspw. 100 Punkte für jeden Teilnehmer, der sein Wunschseminar bekommt, 50 Punkte für denjenigen, der Plan B erhält, 40 Punkte für denjenigen, der Plan C frisst, etc.)

            Die Punteverteilung ist gar nicht so doof. Denn für jeden Teilnehmer bedeutet es etwas anderes, nur seine zweite Wahl zu erhalten.

            Wenn man beispielsweise dem Teilnehmer eine Summe von 100 Punkten zur Verteilung zur Verfügung stellt, die er als Präferenz auf seine Wahl verteilen kann, dann kann man "relativ einfach" ermitteln, welche der vielen möglichen Mischungen das Teilnehmerinteresse am besten erfüllt - nämlich die Version, deren Summe der erfolgreichen Zuweisungen am größten ist.

            Das klappt natürlich auch dann noch, wenn man nur fixe, anonyme Auswahlmöglichkeiten wie "1,2,3" hat, würde dort aber identische Werte für alle Teilnehmer bedeuten. Abgesehen davon erforderte es vorweggenommenes Feintuning, die Abstufung der vorgegebenen Punkte passend zu ermitteln - und das dürfte nahezu unmöglich sein, um damit alle Wünsche optimal zu ermitteln.

            Um "Sichere Wahl" zu verhindern, kann man als zusätzliche EInschränkung der Punkteverteilung ja außerdem definieren, dass kein einzelner Punkt mehr als 50% der Gesamtpunkte erhalten darf, so dass der Teilnehmer gezwungen ist, sich noch Gedanken über eine für ihn möglichst attraktive Zweitwahl (die er dann mit 49% oder 50% bewerten würde - und die damit effektiv genausogut wie seine Erstwahl wäre) zu machen, und ebenso eine Drittwahl zu treffen.

            - Sven Rautenberg

            --
            "Love your nation - respect the others."
            1. Die Punteverteilung ist gar nicht so doof.

              Das Problem ist ja, wenn man die Problemstellung einem Mathematiker vorwirft, dass der fragen wird in welche Richtung er die Sache rechnen soll. Dazu benötigt er ein Modell gegen das er seine Algorithmen messen kann, dieses muss aus der Realität, also aus dem Lager des Anfordernden kommen.

              Das o.g. Zufriedenheitssystem kann auf unterschiedliche Art und Weise entwickelt werden, bei besonders heterogenen Veranstaltungsgruppen (1.Veranstaltung: moderner Anti-Semitismus, 2.Versanstaltung: die moderne NPD, 3.Veranstaltung: Gartenpflege) entsteht Zufriedenheit wohl ganz primär, wenn exakt die gewünschte Veranstaltung besucht werden kann, bei besonders heterogenen Veranstaltungsgruppen (1.)MS ist Scheisse, 2.)Open Source ist gut 3.)Google-Krake ist auch Scheisse) will der Teilnehmer möglicherweise einfach dabei gewesen sein.

              Steht das Zufriedenheitsmodell, dann liegt ein komplexer Verteilungsvorgang an, dessen Ausgang nun aber gemessen werden kann.
              Der in einem Beitrag weiter oben vorgeschlagene Algorithmus kann sicherlich optimiert werden, vermutlich dürfte die Gesamtkomplexität der problemstellung recht hoch sein, man fühlt sich an das Ampelproblem erinnert, bei dem sehr schnell nicht zu bewältigende Komplexität entsteht.