Protip: Buddyledger deling af udgifter mellem venner

Sehttp://c2.com/doc/expense/

Ward Cunningham, som er en af opfinderne bag wiki skrev ovenstående program i 1981.

Et elegant script på få linjer :-)

Det er rigtigt. Så minimering af \sum_{i, j \in P} My_{ij} + x_{ij} at foretrække.

Hvis en person betaler mere end nødvendigt, skal det tilbageføres til den pågældende person.

Ja, men det er heller ikke det, som jeg vil undgå.

Eksempel: A og B skylder hver 1, og C har 2 tilgode. Det kan løses med to betalinger på flg. måder: A betaler 1 til B, som betaler 2 til C hhv. A betaler 1 til C og B betaler 1 til C.

Samme antal betalinger, men alligevel er den anden løsning at foretrække.

Jo, x variablerne er unbounded.

Du har ret i at man bør også bør minimere afregningsbeløbet, hvilket din objektfunktion gør.

Jeg kan ikke gennemskue om minimering af \sum_{i, j \in P} y_{ij} implicit vil minimere afregningsbeløbet. Hvis en person betaler mere end nødvendigt, skal det tilbageføres til den pågældende person. Spørgsmålet er om dette altid vil gøre at en ekstra x variabel stiger fra nul til en positiv værdi og dermed tvinger en ekstra y variabel til at være 1.

Objektfunktion:
Minimér \sum_{i, j \in P} y_{ij}

Hmm. Er betalingerne (x) ikke unbounded (<M)? Vi foretrækker vel den løsning af de mulige løsninger, som har det mindste afregningsbeløb.

Vil det kunne løses med flg. mål i stedet?

Minimér \sum_{i, j \in P} My_{ij} + x_{ij}

Eller overser jeg noget?

Hvorfor bruge et self signed cert når Let’s Encrypt findes…

Attackers might be trying to steal your information from buddyledger.baconsvin.org (for example, passwords, messages, or credit cards). NET::ERR_CERT_AUTHORITY_INVALID

Nedenstående - utestede - heltalsprogram (i Latex-syntaks) burde minimere antallet af betalinger mellem personer.

Mængder:

• P er mængden af alle personer, indekseret med indeks i
• R_i er mængden af delregnskaber for person i, indekseret med indeks r
• P_r \subseteq P er mængden af personer som er med i delregnskab r

Parameter:

• u_{ir} >= 0 er udlæg fra person i til delregnskab r

Beslutningsvariable:

• reel x_{ij} >= 0 er betaling fra person i til person j
• binær y_{ij} er lig 1 hvis og kun hvis x_{ij} > 0

Objektfunktion: Minimér \sum_{i, j \in P} y_{ij}

Begrænsninger:

• for alle i,j \in P: y_{ij} >= x_{ij} / M
• for alle i \in P: \sum_{r \in R_i} \sum_{j \in P_r} u_{jr} / |P_r| = \sum_{r \in R_i} u_{ir} + \sum_{j \in P} x_ij - \sum_{j \in P} x_{ji}

Selvom heltalsprogrammering (generelt) er NP-hårdt og store M begrænsninger ikke ligefrem gør tingene nemmere, så vil jeg gætte på at realistiske instanser kan løses på få sekunder af en god MIP solver.

Vil lige henlede til et alternativ i samme retning, dog beregnet til forhold over længere tid. I dette system er der ligeledes mulighed for en ujævn fordeling af betaling, såsom eksemplet i bloggen.

https://secure.splitwise.com/

Online demoen skal man lige være opmærksom på ikke egner sig til egentlig brug da de forskellige ledgers får et unikt ID (fortløbende fra 1 og frem) - man kan altså tilgå andres ledgers blot ved at ændre i URLen. Det er fint som et demo system, men man bør ikke bruge det til noget med rigtig data.

Jeg frygter derfor at maxflow kan komme op med unødigt kompliceret løsninger.
Måske ville en fornuftig heuristik være at foretrække?

Men som sagt kan man løse det eksakt med dynamisk programmering, så længe at der ikke er mere end 20-30 betalere involveret. Mon ikke det er 90% af tilfældene?

Så vidt jeg kan se i koden, sættes costen altid til 1 ...

Jeg kan heller ikke se, hvordan cost kan være andet end konstant. Der er ikke forskel på en betaling (af en given størrelse) uanset hvor den går fra eller til.

Men det betyder også, at algoritmen synes at flere del-betalinger "koster" det samme som en fuld betaling, og derfor har den ingen interesse i at minimere antallet af del-betalinger.

Maxflow sikrer mao. kun at alle betaler hvad de skal uden at nogen får for meget, men kan ikke kende forskel på en løsning, hvor alle debitorer betaler noget til alle kreditorer og en løsning med få betalingsstrømme, bare summerne stemmer - det samlede flow er det samme i de to, og ingen begrænsninger er overskredet.

Eksempel: A og B skal have 9 hver, og C, D og E skal betale 6 hver. En løsning vil være, at C betaler A og B 3 hver og D og E betaler 6 til hhv. A og B. Samlet flow er 18.

Men en løsning, hvor C, D og E alle betaler 3 til både A og B har også et samlet flow på 18. For maxflow vil de to løsninger være lige gode. Den ene med 4 betalinger og den anden med 6 (for fem aktører). Min anden løsning vil næppe blive førstevalg i praksis, men mon ikke der kan konstrueres tilpas snedige eksempler til at lokke almindelige implementationer af algoritmen i uføre?

Jeg frygter derfor at maxflow kan komme op med unødigt kompliceret løsninger. Måske ville en fornuftig heuristik være at foretrække?

Vil max flow finde det minimale sæt af betalinger? Der er vel ingen cost forbundet med at opsplitte betalingen i flere flows?

Så vidt jeg kan se i koden, sættes costen altid til 1, men det er muligt jeg tager fejl. Jeg ved ikke om der er nogen grund til at antage, at maxflow ofte giver en bedre løsning end bare at lave en lang kæde, som du siger.

Ja, hvis du kan finde passende subset. Viser det andet end, at med tilstrækkelig mange subsets, så vil problemet have en løsning? Men det løser vel ikke udfordringen med at finde det minimale sæt af betalinger?

Reduktionen går omvendt: Hvis vi kan finde det minimale antal betalinger, så kan vi løse subset sum. Ergo er det np-hårdt at finde det minimale antal betalinger.

Mere præcist vil vores subset-sum-algoritme svare "ja" netop når den antagede betalings-algoritme svarer n-2. (Og som du selv siger, hvis betalings-algoritmen er korrekt, vil den altid som minimum finde en n-1 betaling.)

Det er klart at vi kan opnå n-2 når svaret er ja: Det givne subset betaler til kreditor 1, de resterende betaler til kreditor 2. Hvis svaret er nej, må svaret stadig være mindst n-2, da der er n-2 debitorer. Hvis vi antager at det faktisk er n-2 (for at få en modsætning), må betalingerne udgøre to træer, med rod i de to kreditorer. Men så er der ingen mulighed for at en debitor kunne betale til mere en én kreditor, og så må debitorerne i første kreditors træ udgøre en undermængde med den søgte sum x.

Så ja, hvis man har n-1 betalinger, kan man altid kæde alting sammen, men hvis man vil bruge færre end det, kræver det at man opdeler i undermængder, der ikke kommunikerer/betaler med hinanden.

Jeg håber, at det giver mening :-)

I øvrigt kan problemet med at aftegne imellem n deltagere altid løses med n-1 betalinger:

Del deltagerne op i netto-debitorer og netto-kreditorer i vilkårlig orden. Hver debitorer betaler næste debitor, hvad han har modtaget fra foregående debitor plus hvad han selv skylder. Sidste debitor i rækken betaler første kreditor. Hver kreditor tager, hvad han har tilgode og betaler resten videre til næste kreditor. Når sidste kreditor modtager betaling er alt fuldt afregnet.

Det vil give stort cash-flow omkring det punkt, hvor man skifter fra debitorer til kreditorer, og det ignorerer at der kunne være subset, som internt ville kunne aftegne fuldt ud (og dermed reducere det samlede antal betalinger), så det kan egentlig kun bruges til at sætte et minimums niveau for heuristikker.

Og at bruge max flow:

Vil max flow finde det minimale sæt af betalinger? Der er vel ingen cost forbundet med at opsplitte betalingen i flere flows?

Du kan reducere til subset-sum.

Ja, hvis du kan finde passende subset. Viser det andet end, at med tilstrækkelig mange subsets, så vil problemet have en løsning? Men det løser vel ikke udfordringen med at finde det minimale sæt af betalinger?

Det lugter af at være en variant af et rygsæksproblem, men jeg kan ikke lige genkende det.

Du kan reducere til subset-sum.

Hvis du har en mængde S af positive tal, og vil teste om den har et subset med sum x, så kan du lave |S| personer med negativ "netto betaling", og to personer med positiv "netto". Personerne med positiv netto, som altså skal have penge af de andre, har henholdsvis betalt x og sum(S)-x for meget.

Hvis betalingerne kan klares med kun |S| overførsler, ved vi at alle kun har betalt til én person, og derfor var der et subset med summen x.

Er det ikke bare gaussisk eliminering?

Du kan finde en korrekt mængde af overførsler sådan. Det der gør problemet svært er, at vi er interesseret i den mindste sådan mængde - eller den hvor flest overførsler er 0.

For n personer kan man kan løse det i 3^n med dynamisk programmering over undermængder: http://www.spoj.com/problems/TRANSFER/Eller vel med interger linær programmering.

Buddy ledger lader til at give valget mellem en 'basic' udregning, som vist mere eller mindre bare starter fra en ende af: https://github.com/tykling/buddyledger/blob/master/src/buddyledger/views/basiccalc.pyOg at bruge max flow: https://github.com/tykling/buddyledger/blob/master/src/buddyledger/views/graphbuilder.py

I de fleste tilfælde virker det nok også lige så godt, men måske kunne det være sjovt at tilføje en eksakt, dynamisk-programmeringsversion også.

Er det ikke bare gaussisk eliminering?

Det lugter af at være en variant af et rygsæksproblem, men jeg kan ikke lige genkende det.

Er det ikke bare gaussisk eliminering?

... men kan vi ikke reducere resultattrinnet yderligere?

Nemt. Men ikke meget. Hvis vi lige kigger på nettotallene:

Derfor er flg. betalingsplan også en løsning:

Det lugter af at være en variant af et rygsæksproblem, men jeg kan ikke lige genkende det.

Det må være til at finde fornuftige heuristikker, idet løsningen ikke behøver være optimal, bare effektiv.

Det er snedigt, men kan vi ikke reducere resultattrinnet yderligere? Jeg hæfter mig eksempelvis ved at Bent skal betale til Ole, som skal betale videre til Du og HLK. Personer som Bent betaler til i forvejen..

Hvis Thomas læser med her, vil du så ikke forklare hvilke to algoritmer du bruger til udligning?

Men jeg må nu indrømme at jeg ikke bryder mig om den slags milimeter regnskab mellem venner ... der vil jeg hellere bare være den der giver, og så satse på at de andre også giver efter evne ... og hvis ikke lige det går op på den her fest / tur ... så gør det næste gang :-)