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.

vodka køb ole

og resultatet, alle udgifter registreret. Forestil jer en uge i Tyskland til summer camp med mad, øl, og diverse andre udgifter! Pyha!

oversigt udgifter

og hvad så? Hvem skylder hvem og hvor meget? Tryk på knappen Result - og vupti! Alle udgifterne er delt og opsummeret.

oversigt over resultat

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.

Henrik Kramshøjs billede
Henrik Kramshøj er internet-samurai. Han elsker netværkspakker tcpdump, wireshark, BackTrack, Metasploit og andre hackerværktøjer og blogger om sikkerhed, netværk og unix.

Kommentarer (24)

Mikkel Mikjær

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

Bjarne Nielsen

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

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

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.

Thomas Dybdahl Ahle

> 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...
Og at bruge max flow: https://github.com/tykling/buddyledger/blob/master/src/buddyledger/views...

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

Thomas Dybdahl Ahle

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

Bjarne Nielsen

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.

Thomas Dybdahl Ahle

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

Thomas Dybdahl Ahle

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.

Bjarne Nielsen

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?

Morten Hansen

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.

Thomas Sejr Jensen

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.

Emil Stahl

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

Thomas Sejr Jensen

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.

Bjarne Nielsen

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.

Log ind eller opret en konto for at skrive kommentarer