Welchen Optimierungsalgorithmus brauch ich

[Gutelo]

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

[Uwe Raabe]

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.

[Medium]

"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.)

[Gutelo]

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.

[jobo]

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)?

[Gutelo]

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.

[jobo]

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.

[Zoot]

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.

[Gutelo]

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

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

[BUG]

Zitat:

Zitat von jobo (Beitrag 1247833)

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 :stupid:


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 :wink:). 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.

[Blup]

Zitat:

Zitat von Gutelo (Beitrag 1247813)

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

Alles entscheidend ist, was versteht man unter gerecht geteilt?
Normalerweise teilt man die Gesamteinnahme.

EP1 = EG * (AP1 / AG)
EP2 = EG * (AP2 / AG)
EP3 = EG * (AP3 / AG)

Diese Formel lässt sich in beiden Situationen anwenden.
Im Gewinnfall ist EP1 > AP1, im Verlustfall EP1 < AP1

[Gutelo]

Zitat:

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

Falsche Denkweise. Die Gemeinschaft kauft 500 Lose. 4 Legen das Geld fuer 4 Lose aus, einer fuer 496 Lose. Ich verstehe das Problem nicht.

[Zoot]

Zitat:

Zitat von Gutelo (Beitrag 1247843)

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

Dass die Rechnung ganz einfach ist?
Jeder zahlt Ausgaben/3 ein und erhält Einnahmen/3 zurück.
Wenn der Saldo negativ ist, weil z.B. Einnahmen=0, muss er nachzahlen, sonst erhält er Geld.

Also
1: EG/3 - AG/3 + AG1
2: EG/3 - AG/3 + AG2
3: EG/3 - AG/3 + AG3

Sollte immer stimmen und ist ganz einfach.

[Gutelo]

Zoot: und wie genau laeuft das Zahlen und Erhalten ab? Es geht darum genau diese Transaktionen moeglichst optimiert zu bestimmen. Was jeder am Ende haben muss ist wie vorher gesagt trivial zu bestimmen.


Es soll nicht so laufen, dass alle Schuldner das Geld in einen Pott werfen und anschliessed Glaeubiger aus dem Topf bezahlt werden. Ich moechte eine optimnierte Liste, wer an wen direkt was bezahlen muss.

[Zoot]

Beispiel:

1 kauft 10 Lose, 2 kauft 50 Lose, 3 kauf kein Los.
Lose kosten 1 Euro, Gewinn beträgt 120 Euro.

1. 40 + 10 - 20 = 30
2. 40 + 50 - 20 = 70
3. 40 + 0 - 20 = 20

Alles paletti!

Beispiel2:

1 kauft 10 Lose, 2 kauft 50 Lose, 3 kauf kein Los.
Lose kosten 1 Euro, Gewinn gibts nicht.

1. 0 + 10 - 20 = -10
2. 0 + 50 - 20 = 30
3. 0 + 0 - 20 = -20

auch alles paletti!

[Zoot]

Zitat:

Zitat von Gutelo (Beitrag 1247853)

Zoot: und wie genau laeuft das Zahlen und Erhalten ab? Es geht darum genau diese Transaktionen moeglichst optimiert zu bestimmen. Was jeder am Ende haben muss ist wie vorher gesagt trivial zu bestimmen.

Ich weiß jetzt nicht, was es bei der kurzen Formel noch zu optimieren geben soll. Alle Einnahmen teilen, alle Ausgaben teilen, getätigte Ausgaben rückerstatten - fertig.

[Gutelo]

Ich rede von Transaktionen, dynamische Prozesse, basierend auf den Zahlen die du alles paletti berechnet hast.

In deinem Zweiten Beispiel waeren das:

Transaktion 1: Spieler 1 gibt Spieler 2 den Betrag von 10 Euro
Transaktion 2: Spieler 3 gibt Spieler 2 den Betrag von 20 Euro

Nun nimm 10 Spieler und weniger Schoene Betraege, dann gibt es zig Moeglichkeiten die Transfers zu machen, und einige Spieler muessen dann auch Betraege an 2 oder sogar mehr Spieler transferieren...

[Zoot]

Zitat:

Zitat von Gutelo (Beitrag 1247863)

Ich rede von Transaktionen, dynamische Prozesse, basierend auf den Zahlen die du alles paletti berechnet hast.

Welche Transaktionen, welche dynamischen Prozesse?

Die Verteilung der Kosten/Gewinne beruht auf einer einfachen Formel, wie wenige Variablen und wenige Rechenoperationen umfasst. Das ändert sich doch nicht in einem anderen Umfeld.
Mir ist völlig schleierhaft, auf was du hinauswillst, würde es aber gerne verstehen.

Das monetäre Ergebnis eines Teilnehmers n (von N Teilnehmern) ist EG/N - AG/N + agn
Was dasselbe ist wie (EG-AG)/N - agn

(EG-AG)/N wird ein einziges Mal berechnet, agn ist als Größe bekannt.
Wo sind hier Transaktionen und dynamische Prozesse?

[Zoot]

Zitat:

Zitat von Gutelo (Beitrag 1247863)

Ich rede von Transaktionen, dynamische Prozesse, basierend auf den Zahlen die du alles paletti berechnet hast.

In deinem Zweiten Beispiel waeren das:

Transaktion 1: Spieler 1 gibt Spieler 2 den Betrag von 10 Euro
Transaktion 2: Spieler 3 gibt Spieler 2 den Betrag von 20 Euro

Nun nimm 10 Spieler und weniger Schoene Betraege, dann gibt es zig Moeglichkeiten die Transfers zu machen, und einige Spieler muessen dann auch Betraege an 2 oder sogar mehr Spieler transferieren...

Ok, jetzt kapier ich was du meinst.
Da würde sich aber doch eine gemeinsame Kasse anbieten, aus der jeder erhält, bzw. in die jeder einzahlt, oder?

[Jumpy]

Sortiere die Spieler von Gewinn nach Verlust.
Ziehe die raus, wo Gewinn auf gleichen Verlust trifft, diese können sich mit einer Transaktion ausgleichen.
Der Rest gibt von oben nach unten jeweils seinen Überschuss weiter.

So muss jeder maximal eine Transaktion machen. Das ist natürlich nicht optimal, aber dafür fair. Ein anderer Algo würde vllt. die Zahl der Transaktonen insgesamt verringern, dafür müssten aber u.U. einzelne Leute mehrere Transaktionen durchführen.

[Gutelo]

Ja, gemeinsame Kasse waere das Beste.

Nur dann muesste man regelmaessig zusehen, dass jeder den gleichen Betrag einzahlt. Der aktuelle Kaeufer eines Tickets muss an die gemeinsame Kasse rankommen. Letzteres ist z.B. schwer wenn nicht alle in der selben Stadt wohnen. ...

Ich finde es besser wenn man im chat einfach abstimmt wer ein Ticket kauft, und nach 3,6, oder 12 Monaten macht man mal eine Abrechnung. Dann kriegt jeder ne mail wer and wen was ueberweisen soll.

Das ist alles in allem weit weniger Stress als eine gemeinsame Kasse zu unterhalten.

[BUG]

Zitat:

Zitat von Gutelo (Beitrag 1247853)

Es soll nicht so laufen, dass alle Schuldner das Geld in einen Pott werfen und anschliessed Glaeubiger aus dem Topf bezahlt werden. Ich moechte eine optimnierte Liste, wer an wen direkt was bezahlen muss.

Aber diese Methode gibt schon ein relativ gutes Ergebnis, von dem aus man lokal optimieren könnte.

OBdA gibt es niemanden mit t_i = 0, ansonsten lässt sich auch eine Lösung finden, in der diese Person keine Zahlungen empfängt oder sendet. Damit gibt auch eine untere Schranke für die Anzahl der Transaktionen: n/2. Entweder gibt es mehr Gewinner (t_i > 0) oder Verlierer (t_i < 0); diese Gruppe ist macht dann mindestens die Hälfte der Gesamtgruppe aus und jedes Mitglied muss mindesten eine Zahlung tätigen bzw. empfangen.

Damit hat man mit der Pott-Methode in jedem Fall weniger als doppelt so viele Überweisungen als das Optimum. Schonmal nicht schlecht.

Eine ähnliche Approximationsgüte erreichst du, indem du jedem Gewinner eine Kette von Verlierern anhängst, die denn Restbetrag jeweils an den nächsten Überweisen, bis es für keinen weiteren mehr reicht. Diese Ketten hängst du dann aneinander, bis die Reste wieder für einen Verlierer reichen. Alternativ könntest du jeden Gewinner an mehrere Verlierer überweisen lassen, wobei nur einer den Restbetrag zusätzlich erhält, den er dann an den nächten Gewinner überweist.

Insgesamt glaube ich nicht, dass dieses Problem im Allgemeinen besonders einfach zu lösen ist und in den real auftretenden Fällen beim Lotto das Optimum sehr stark von n-1 abweicht; eine Approximation wäre also nicht schlecht.

Zitat:

Zitat von Gutelo

Falsche Denkweise. Die Gemeinschaft kauft 500 Lose. 4 Legen das Geld fuer 4 Lose aus, einer fuer 496 Lose. Ich verstehe das Problem nicht.

Ah, die Gruppe einigt sich vorher auf die Anzahl der Lose. Das hättest du auch vorher sagen können :tongue:

[jensw_2000]

Bleiben wir mal bei dem Beispiel "Die Gemeinschaft kauft 500 Lose. 4 Legen das Geld fuer 4 Lose aus, einer fuer 496 Lose." Dann ist es doch immer noch einfach.

Keine Ahnung was ein Los kostet. Machen wir es mal der Einfachheit halber 1 EUR teuer.

- Gruppe kauft 500 Lose für 500 EUR
- im "Pott" liegen nun 500 Lose und Gesamtschulden von 500 EUR
- Spieler 1 kauft 496 der 500 Lose, hat also schon nur noch "Pottschulden" in Höhe von (Gesamtschulden-Eigeneinsatz) / (Anzahl Spieler-1)
- Spieler 2...5 kaufen jeweils 1 Los´. Da greift die gleiche Formel. Logisch.

Sobald ein Los gewinnt, wird die Gesamtschuld um die Einnahme verringert.

Am Ende, wenn ihr irgendwann abrechnet ist die Formel noch immer gleich, nur die Gesamtschulden sind geringer oder sogar negativ (im Gewinnfall).
Der Zahlungsausgleich zwischen den Spielern kann dann einfach ermittelt werden, in dem man die Pottschuldendifferenz zwischen den einzelnen Spielern ermittelt. Also "meine Schulden" - "seine Schulden". Ist das positiv muss ich ihm was zahlen, sonst zahlt er mir etwas.
Genau das gleiche Prinzip greift natürlich auch auf der Gewinnseite.

[Medium]

Was ich nach wie vor nicht kapiere ist, warum es keinen "Pott" gibt, und die Transaktionen unter den Teilnehmern passieren müssen. Wenn gemeinsam Tickets gekauft werden, tritt man doch faktisch als eine Person gegenüber dem Wettsteller auf. Dieser Zahlt nachher auch an diese eine virtuelle Person aus. Das ist doch der Pott dann, und auf irgend einem Konto muss die Knete ja nachher landen. Einem.
Im Gewinnfall rechnet man dann einfach jedem zunächst seinen Einsatz zu, und verteilt den Rest prozentual zum Einsatz auf die Teilnehmer. (Das dürfte sogar einer komplett prozentualen Verteilung entsprechen, aber der Wein verhindert gerade die Lust daran das nachzuprüfen.) Und dann wird einfach aus dem Pott pro Teilnehmer genau eine Überweisung daraus. Im Verlustfall würde ich genau so verfahren, nur dass keiner seinen Einsatz zurück erhält, sondern nur der Verlust auf alle entsprechend ihres Einsatzes verteilt ist. (Was auch wieder eine simple faire anteilige Verteilung ist.)

Das ganze macht praktisch gesehen ohne ein "Pott-Konto" irgendwie keinen wirklichen Sinn, da man sonst ja nicht wirklich als Gemeinschaft auftreten kann. Warum müssen die Teilnehmer untereinander agieren? Vielleicht wäre es an der Zeit mit den Metaphern aufzuhören, und ein konkretes Beispiel anzuführen. Mit Ausgangssituation, Spielverlauf, und gewünschtem Ergebnis. (Sowohl für Gewinn- als auch Verlustsituation je mindestens eines.) Und der vorhandenen realen Infrastruktur!

Wenn ich hier komplett falsch liege, und am Ende wirklich ein Ausgleich unterhalb der Teilnehmer stattfinden soll, so klingt mir das zunächst ein wenig nach einem Minimierungsproblem, dass man über einen Graphen lösen können müsste. Aber auch hier hindert mich die Getränkesituation an konkreteren Aussagen ;) (Zumal ich nach wie vor kaum glauben kann, dass die Einzahlungen bzw. Gewinne nicht doch an irgend einer Stelle am Stück auflaufen.)

[Sir Rufo]

Also nehmen wir mal den folgenden Fall an:

Person A hat 10€ ausgelegt und Person B 20€. Der Gewinn liegt bei 100€.
Dadurch ist der Reingewinn also 70€ und davon gehören je 35€ A und B.
In die Hand gedrückt bekommt A allerdings 10€+35€ = 45€ und B 20€+35€ = 55€

Jetzt spielen wir die gleiche Situation mit einem Gewinn von 20€ durch.

Der Reingewinn ist jetzt -10€ (also ein Verlust) und davon gehören je -5€ A und B.
In die Hand gedrückt bekommt A allerdings 10€-5€=5€ und B 20€-5€=15€

Und jetzt, wenn die gar nicht gewinnen:

Code:

Gesamteinsatz 10+20=30
Gewinn 0
Reingewinn 0-30=-30
Gewinnanteil pro Spieler -30/2=-15
A 10-15=-5
B 20-15=5