Protip: Buddyledger deling af udgifter mellem venner
Kender I det at man skal holde nytårsfest eller andre ting, hvor flere skal dele udgifterne?
Så er det på tide at du lærer den lille applikation Buddyledger at kende. Den er lavet af Thomas Rasmussen, i daglig tale tykling. Han har lavet den som open source på https://github.com/tykling/buddyledger/blob/master/README.md men den findes online på https://buddyledger.baconsvin.org/
Problemet er:
- Jeg køber kød 249kr
- Du køber tilbehør 123kr
- Alex køber sodavand 456kr
- osv.
- Bent, Ole og Georg skal dele en flaske vodka som Ole har købt, men de andre skal ikke betale denne udgift
- Alle skal dele maden
Pyha, men her kommer Buddyledger flyvende ind og håndterer det hele! DET HELE!
Lad os springe ud i det, jeg har her oprettet en ny ledger, indtastet personnavne og smider en udgift ind.
Denne udgift er betalt af HLK - 249kr og da den skal deles mellem alle er alle personer tilføjet - så alle skal have andel i denne udgift.
Lad os så antage jeg har tastet resten ind, og kommer til vodkaen som skal deles mellem tre.
og resultatet, alle udgifter registreret. Forestil jer en uge i Tyskland til summer camp med mad, øl, og diverse andre udgifter! Pyha!
og hvad så? Hvem skylder hvem og hvor meget? Tryk på knappen Result - og vupti! Alle udgifterne er delt og opsummeret.
Det er fandme smart! Så med Swipp og mobilepay er der hurtigt afregnet og alle kan være glade og fulde.
Godt nytår til alle og tak for opmuntring, diskussioner og snak i året 2015.
- emailE-mail
- linkKopier link

...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.
Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.
Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.
Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.
- Sortér efter chevron_right
- Trådet debat
Ward Cunningham, som er en af opfinderne bag wiki skrev ovenstående program i 1981.
Et elegant script på få linjer :-)
- more_vert
- insert_linkKopier link
Det er rigtigt. Så minimering af \sum_{i, j \in P} My_{ij} + x_{ij} at foretrække.
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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?
- more_vert
- insert_linkKopier link
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
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
Ja, sådan virker det også til mig.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?
- more_vert
- insert_linkKopier link
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?
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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 :-)
- more_vert
- insert_linkKopier link
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.
- more_vert
- insert_linkKopier link
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?
- more_vert
- insert_linkKopier link
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?
- more_vert
- insert_linkKopier link
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
.
- more_vert
- insert_linkKopier link
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å.
- more_vert
- insert_linkKopier link
Jeg havde selv en tanke om at det nok reducerede til et eller andet grafproblem, måske polynomielt måske ikke. Men Gauss-elimination er jo også lidt hen af det...Er det ikke bare gaussisk eliminering?
- more_vert
- insert_linkKopier link
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?
- more_vert
- insert_linkKopier link
... men kan vi ikke reducere resultattrinnet yderligere?
Nemt. Men ikke meget. Hvis vi lige kigger på nettotallene:
Person Netto A 318 B -248 D -15 G -248 H 111 O 82Derfor er flg. betalingsplan også en løsning:
Fra Til Beløb B A 248 D A 15 G A 55 G H 111 G O 82Det 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.
- more_vert
- insert_linkKopier link
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..
- more_vert
- insert_linkKopier link
Hvis Thomas læser med her, vil du så ikke forklare hvilke to algoritmer du bruger til udligning?
- more_vert
- insert_linkKopier link
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 :-)
- more_vert
- insert_linkKopier link