Hallo,

ich suche nach einem Algorithmus fuer ein Optimierungsproblem. Ich habe eine Gruppe von Personen, die alle unterschiedliche Ausgaben taetigen. Ferner hat die Gruppe gemeinsame Einnahmen. Also

Ausgaben Person 1: AP1 := a1 + a2 + a3 + ...
Ausgaben Person 2: AP2 := b1 + b2 + b3 + ...
Ausgaben Person 3: AP3 := c1 + c2 + c3 + ...

Einnahmen Gruppe: EG := z1 + z2 + z3 + ...

Zu einem bestimmten Zeitpunkt soll die Abrechnung gemacht werden.

1) Einfacher Fall: EG > AP1+AP2+AP3 (Gewinn), dann bekommt jeder seine Ausgaben zurueck und der Rest wird gerecht geteilt.

2) Komplizierter Fall: EG < AP1+AP2+AP3 (Verlust). In diesem Fall sollen Betraege zwischen den Personen (incl. Gewinn) so fliessen, so dass am Ende jede Person den gleichen Verlust hat.

Fuer den komplizierteren 2. Fall suche ich einen Algorithmus, der mir eine Liste mit den noetigen Geldtransaktionen zwischen den Personen liefert. Die Anzahl Transaktionen sollte natuerlich moeglichst gering sein.

Da das ein Standardproblem ist gibt es ziemlich sicher einen fertigen Algorithmus. Wonach muss ich googlen?

Danke, Gutelo

Vorausgesetzt ich verstehe das richtig, dann wird doch der Gesamtverlust auch einfach durch drei geteilt. Also fließt gar kein Geld zwischen den einzelnen Personen, sondern jeder bekommt aus dem EG exakt seine Ausgaben zurück minus seinen Anteil (1/3) am Verlust.

"Den gleichen Verlust" ist etwas vage. Sollen alle Personen absolut gleich viel Verlust tragen (Uwes Beispiel), oder prozentual den Anteil an ihrer eigenen Einlage? Bei ersterem ist das Problem, dass ein Kleinstanleger u.U. noch zusätzlich drauf zahlen müsste weil er ins Negative gerät. Prozentual ist es doch trivial: Anteil Verlust:Gewinn gesamt ermitteln, und diesen Faktor auf jede Einlage anwanden. (Die Beträge dann evtl. nochmals summieren und so zurecht runden, dass nachher centgenau der Gesamtverlust aufgefangen wird, und alle nur centgenau zahlen müssen. Das wäre aber erstmal ein nachgelagertes Problem.)

Hallo Uwe,

Ziel ist es, dass im Verlustfall die Personen gleich belastet werden. Es soll also gleichzeitig ein Ausgleich der einzelnen Ausgaben stattfinden.

Es geht um Spielgemeinschaften (z.B. Lotto)

Die Spieler kaufen ueber einen gewissen Zeitraum die Tickets. Dabei ist es erstmal irrelevant wer wann und wieviele Tickets kauft. Wenn ein Gewinn erwirtschaftet wird, dann wird der Einsatz zurueckgezahlt und der Rest des Gewinns geteilt. Wenn ein Verlust eingefahren wird, dann sollen am Ende alle gleichviel fuer die Tickets bezahlt haben.

Ein Spieler A kauft über einen Zeitraum x 50 Tickets(=Scheine=Tipps?), ein anderer B über den gleichen Zeitraum x nur 5 Tickets (Einheiten)
Dann bekommt A 50 Gewinnanteile, B bekommt 5.
Rückzahlung des Einsatz finde ich seltsam.
Gewinn = Glücksspielgewinn minus Einsatz (Ticketkosten)?

Wieso seltsam?

Es kommt ganz drauf an wie man sich einigt. Wenn man sich einigt alles zu teilen, dann macht es schon Sinn. Es hat nunmal nicht jeder gleich viel Zeit Tickets zu kaufen, oder einer wohnt direkt neben der Annahmestelle.

"Rueckzahlung" insofern, dass der Gewinn auch zum Ausgleich des Einsatzes verwendet wird.

Ich formuliere es einfacher:

N Spieler haben jeweils x_n Punkte, durch Gebe/Nehme Operationen zwischen den Spielern sollen die Punkte aller N Spieler ausgeglichen werden. Die Anzahl der Operationen ist zu minimieren.

Ansatz
Punkte Mittelwert bestimmen
Spieler über Mittelwert geben ab
Spieler unter Mittelwert erhalten

Für alle Spieler zum Startzeitpunkt über Mittelwert:
jeweils Höchster Punktstand gibt so lange an niedrigster Punktstand ab, bis fremder oder eigener Punktestand auf Mittelwert ist.

Warum trennst du nicht Einzahlung von Auszahlung?
Jeder wird mit (AP1+AP2+AP3)/3 belastet, und jeder wird mit EG/3 "entlohnt".
Dabei spielt keine Rolle, ob Gewinn oder Verlust erzielt wurde.

@Jobo: das ist trivial, aber alles andere als optimiert. Ich werde bestimmt nicht Tage-lang da sitzen bis unsere Geldtauscherei endlich terminiert

@Zoot: wie hilft einem das Trennen bei der Abrechnung? Es muss immer Geld zwischen den einzelnen Spielern fliessen...

Zitat von jobo:

Rückzahlung des Einsatz finde ich seltsam.

Deutlich wird das vor allem im Extremfall: 4 kaufen 1 Los, ein weiterer kauft 496. Wenn niemand was gewinnt, müssen alle 100 Lose bezahlen. Klingt nicht wirklich fair


Ansonsten würde ich dass Problem erstmal so formalisieren:
Sei n die Anzahl der Personen und p_1, ..., p_n der persönliche Gewinn (meist negativ ). Sei weiterhin b = (p_1 + ... + p_n) / n der ausgeglichene Gewinn. Nun ist das Ziel, eine minimale Anzahl an Überweisungen zu finden, so dass bei jeder Person der ausgeglichene Gewinn erreicht wird.

Klar ist, das man höchstens n-1 Transaktionen braucht. Die kann man so erreichen: Jeder Spieler i berechnet einen Transaktionsbetrag t_i = (p_i - b). Ist t_i > 0, sendet Spieler i den Betrag t_i an Spieler 1 (oBdA). Spieler 1 muss das natürlich nicht tun. Nun sendet Spieler 1 den Betrag |t_i| an alle Spieler i mit t_1 < 0. An sich selbst braucht er dabei nichts überweisen.