Welchen Optimierungsalgorithmus brauch ich

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

[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