Welchen Optimierungsalgorithmus brauch ich

[Gutelo]

@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...

[Zoot]

Zitat von Gutelo:

@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]

Zitat von 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.

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 von Gutelo:

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 von 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...

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?

[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.

[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.

[BUG]

Zitat von Gutelo:

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