Posts

  • The Blogging Gauntlet: May 10 - Splitwise is NP-Complete

    This is part of The Blogging Gauntlet of May 2016, where I try to write 500 words every day. See the May 1st post for full details.

    Say you go on a group trip. People foot the bill for different expenses, and need to get paid back later. Splitwise is a webapp that does all the bookkeeping for you.

    As an example, consider this case. Alice, Bob, Carol, and Dave went on a trip together. Alice spent $60 and needs to get paid back by Bob, Carol, and Dave. Carol spent $20 and needs to get paid back by Bob and Dave. Dave spent $30 and needs to get paid back by Alice and Bob, and Alice’s share should be twice as big as Bob’s.

    We can interpret these payments as a weighted directed graph, where people are vertices and edges are payments.

    First payment graph

    Alice needs $20 from everyone else, Carol needs $10 from Bob and Dave, and Dave needs $20 from Alice and $10 from Bob.

    There are some redundancies in the graph. For example, Alice and Dave each need to pay each other $20. Since the net money between them is $0, we should just remove those edges to avoid doing extra transactions.

    Second payment graph

    Splitwise does this for you. In fact, it goes one step further. Splitwise tries to minimize the total number of transactions in the graph.

    Let’s go back to the example above. Carol receives $20 in total from Bob and Dave, then pays $20 to Alice. Instead of routing their money through Carol to Alice, Bob and Dave could pay Alice directly. Carol is still net +$0 and Alice is still net +$20, but now Carol doesn’t have to pay anyone. That reduces the graph to this one.

    Third payment graph

    Bob is sending $10 to Dave, who is sending $10 to Alice. We can simplify this by having Bob send $10 to Alice straight.

    4th payment graph

    We’ve simplified the graph down to a single payment. Pretty neat, right? You can see how a tool that does this automatically could be useful.

    This raises an interesting question. How would you solve the Splitwise problem in general? We formalize the problem below.

    Let \(G = (V,E)\) be a weighted directed graph. Given \(G\), construct an equivalent graph \(G'\) such that every vertex \(v\) receives/gives the same amount of money it would in \(G\), and \(G'\) has as few edges as possible.

    Flow Representation

    My first intuition was that the Splitwise problem was very similar to a network flow problem. You want to shuffle money around a graph while minimizing costs.

    This motivated looking at the min-cost flow problem. In the min-cost flow problem, sending one unit of flow through an edge \((u,v)\) has some cost. We want to minimize cost while sending enough flow through the graph.

    5th payment graph

    The system on the left has \(20\) total flow, while the system on the right has \(10\) total flow. Assuming all edges have the same cost per unit flow, the latter graph is cheaper.

    Min-cost flow is solvable through linear programming, but it’s not obvious that minimizing the flow in the graph is the same as minimizing the number of edges needed. So, I started looking elsewhere.

    A Greedy Algorithm

    Note that in flow problems, we assume only edges \((u,v)\) in the graph can send things to each other. In the Splitwise problem, anyone can send money to anybody else.

    Instead of trying to reduce existing edges, let’s figure out how much everybody should pay, then add edges by ourselves. To minimize the number of edges, one natural idea is to send as much money as possible in every edge. This motivates the following algorithm.

    1. Read the input \((V, E)\) to compute the net balance for everyone.
    2. While someone owes money to somebody else:
    3.         Find the person \(v_{max}\) who owes the most money.
    4.         Find the person \(v_{min}\) who requests the most money.
    5.         Have \(v_{max}\) send as much money as possible to \(v_{min}\).
    6.         Update everyone’s net balance.

    Here’s an example run. \(v_1,v_2,v_3,v_4\) owe $1,$2,$3,$4 respectively, and \(v_5,v_6\) request $5 each. The outputted set of edges is

    • \(v_4\) sends $4 to \(v_5\)
    • \(v_3\) sends $3 to \(v_6\). (Before this step, \(v_5\) is owed $1 and \(v_6\) is owed $5.)
    • \(v_2\) sends $2 to \(v_6\). (Before this step, \(v_5\) is owed $1 and \(v_6\) is owed $2.)
    • \(v_1\) sends $1 to \(v_5\).

    Every party that owes money must send money at least once, which gives a lower bound of \(4\) transactions. This solution uses \(4\) transactions, so it’s optimal.

    On mentioning this problem to a friend, he pointed out the following example. Have \(v_1,v_2\) owe $3, and \(v_3\) owe $5. Then have \(v_4\) request $6 and \(v_5\) request $5. The output is

    • \(v_3\) sends $5 to \(v_4\)
    • \(v_2\) sends $3 to \(v_5\)
    • \(v_1\) sends $2 to \(v_5\)
    • \(v_1\) sends $1 to \(v_4\)

    However, we only need \(3\) transactions if \(v_3\) sends money to \(v_5\) in the first step.

    He then proved Splitwise is NP-Complete, by showing Partition reduces to Splitwise.

    NP-Completeness Proof

    First, reformulate Splitwise as a decision problem.

    Let \(G = (V,E)\) be a weighted directed graph. Given \(G\) and \(k\), return whether there exists an equivalent graph \(G'\) with at most \(k\) edges.

    Given a \(G'\), we can verify it’s valid and has at most \(k\) edges in polynomial time. So Splitwise is in NP.

    Next, construct a reduction from Partition to Splitwise. Given a list \(S\) of positive integers, we want to know if there is a partition \(S_1,S_2\) such that both sets have the same total sum.

    Given \(S = \{a_1,a_2, \ldots, a_n\}\), construct \(G\) with \(n+2\) vertices \(v_1,v_2,\ldots, v_{n+2}\). Add edges such that \(v_i\) owes \(a_i\), and \(v_{n+1}, v_{n+2}\) request \(\frac{1}{2}\sum_{i=1}^n a_i\) each.

    Any solution to this instance must have at least \(n\) transactions, because \(n\) people owe money. Furthermore, if the solution has exactly \(n\) transactions, \(v_i\) must send \(a_i\) for their transaction. The edges entering \(v_{n+1}\) and \(v_{n+2}\) correspond exactly to a partition of \(\{a_1,\ldots,a_n\}\) Thus, there is a solution with \(n\) transactions if and only if a partition exists. Since Partition is NP-Complete, it follows that Splitwise is NP-Complete. \(\blacksquare\)

    Splitwise in Practice

    It turns out the greedy algorithm gets pretty close to the optimal value in most cases. Based on a Quora post by a Splitwise founder, the site uses something similar.

    So, Splitwise isn’t finding optimal solutions on a regular basis. Oh well. I still think it’s neat that an NP-Complete problem fell out at all.

    Comments
  • The Blogging Gauntlet: May 9 - Reality is The Null Hypothesis

    This is part of The Blogging Gauntlet of May 2016, where I try to write 500 words every day. See the May 1st post for full details.

    Very minor spoilers for Ra, major spoilers for The Matrix. Avoid if you dislike metaphysics.

    Among the many excellent sequences of Ra, this is in my top 3. To set the stage: Laura and Natalie have just come back from a harrowing experience in the shared dreamscape called Tanako’s world. In that dreamscape, Laura killed someone. Natalie is not happy.

    (For brevity, I’ve cut out some of the middle paragraphs.)

    Natalie pulls Laura aside. “I need you to do something for me.”

    “Okay?”

    “I need you to stop killing people.”

    Laura chokes. “Ah, what?”

    “You killed that person,” Natalie says to Laura. “You could have vented the energy upwards, away from all of us. You vaporised him and you didn’t need to.”

    “He was threatening lives!”

    “You had neutralised that threat. That makes it murder.” Natalie’s tone of voice isn’t even accusatory. It’s completely flat.

    “I don’t understand what you’re saying. It was a dream.”

    So when did you wake up?

    Laura steps through her memories one at a time. She remembers walking home. She walked all the way back from her memory palace to Tanako’s world to the fissure to reality. It’s a continuous record. “…We’re awake right now, right?”

    “That’s the null hypothesis,” says Natalie. “Until you can prove otherwise, always assume you’re in reality. Now, repeat after me: ‘We don’t know what happened.’”

    ***

    About two years ago, I remember telling someone about the simulation hypothesis. The argument goes like this: suppose humanity could one day create high-fidelity simulations of the world. These simulations are so good that the simulated people have consciousness. Many people could run these simulations, or the simulated people could run their own high-fidelity simulations. There could be several layers of simulation or just one, but in either case the number of simulated people is much larger than the number of real people.

    Thus, one of the following must hold true.

    • Most civilizations cannot simulate self-aware beings.
    • Most civilizations can simulate self-aware beings, but choose not to.
    • Most civilizations can and do simulate self-aware beings.

    And if the last holds true, we are very likely living in a simulation.

    I accept this argument, with a small extension. It goes like this: we’re probably a simulation, but I don’t give a shit. Why should I? It’s real to me.

    In essence, I’m Cypher from The Matrix. Except, you know, with less murder, and less betrayal, and less facial hair.

    Cypher

    A guy who isn’t wrong. He’s just an asshole.

    ***

    The null hypothesis is that the world is real.

    What if I was given proof that the world was a simulation? Let’s handwave the details, and assume that this proof is incredibly convincing and almost impossible to fake.

    Well, it doesn’t change my position. Okay, now I know for sure the world isn’t real. It’s still real to me. Presumably I don’t get access to anything that lets me alter my simulated reality, so I have to keep going along anyways. I’m not bothered by knowing the world’s rules were constructed by some third party.

    A similar argument holds for perfect crimes. By definition, if people commit a perfect crime, there is no evidence of that crime. It is impossible for me to distinguish between a world with perfect crimes and one without perfect crimes, so I shouldn’t bother thinking about it.

    ***

    Okay. What about virtual reality?

    I got to try out a virtual reality headset last week, and it’s quite impressive. Right now, it’s still slightly off from reality, but there were moments where I genuinely forgot I was standing in a room.

    So, let’s up the ante. Suppose VR technology starts looking very similar to reality. You put on a VR headset, and jump into a constructed world. Are you ethically obligated to act as if the constructed world is reality, or are you free to act amorally?

    At this point, I’m actually not so sure. Here’s something I call the Reality Turing Test.

    You walk into a room with the lights out. You put on a VR headset. The proctor then either has the headset display the room around you and turns on the lights, or has the headset display VR. The headset passes the test if you can’t tell if you’re looking at VR or looking at reality.

    Right now, VR headsets don’t pass this test. The graphics aren’t perfect, and occasionally there’s a slight stutter. But in the future, VR headsets may pass the Reality Turing Test, and that’s where ethics gets complicated. When you put on a VR headset, you’re aware of the transition between reality and virtual reality. But, if you act amorally in virtual reality, and virtual reality is hard to distinguish from true reality, it’s a very small step to acting amorally in the real world.

    If you agree with my position, then at some point in the future video game designers are obligated to keep VR video games as unrealistic as possible, to maximize the gaps between VR and reality. A video game protagonist is a monster by reality’s standards, and acting like one in high-fidelity VR is too close to acting like one in reality for my tastes.

    Reality may be the null hypothesis, but in a future where we can approximate reality to high-fidelity, it may not be the only null hypothesis. That’s creepier than you might think.

    We’re not there yet. I’d say we’re not even close to there yet. But the ethics are interesting to think about, and we can’t punt them down the horizon forever.

    “You know, choosing not to choose isn’t really a decision.”

    (Twilight Sparkle, My Little Pony: Friendship is Magic)

    I’ve made my choice. Perhaps now, you’ve made yours. In either case: may your null hypothesis be rich and enlightening.

    ***

    If you like thinking about things like this, I recommended: I don’t know, Timmy, being God is a big responsibility, Inception, The Matrix (just the first one), and the TVTropes article on Lotus-Eater Machines. And of course, Ra, but that’s longer than the rest.)

    Comments
  • The Blogging Gauntlet: May 8 - Shut Up And Write

    This is part of The Blogging Gauntlet of May 2016, where I try to write 500 words every day. See the May 1st post for full details.

    When it’s 10:20 PM, I have to write a 500 word post, and I have no idea what’s I’m going to write about, you know I’m going to dredge the bottom of the self-reference barrel.

    So, I have 100 minutes to write a post. By itself, this wouldn’t be the trickiest task. Some of the posts on previous days were written in less time than that. However, on those days I knew I would be time-crunched, and deliberately thought about a topic I wanted to write about. That let me plan out an outline in advance. When you know what you want to say, it’s surprisingly easy to say it.

    Today, I didn’t think of a topic ahead of time, and here we are. Let’s see if my lightly edited stream of consciousness is remotely coherent.

    First off, I could always just give up. It’s $20 if I don’t write a post. Twenty dollars isn’t that much for me, which I’m sure says something about my socioeconomic status. But here I am, writing out words.

    So, let’s assume I’m acting rationally, or at least acting in a way that could be interpreted as the actions of a rational person. Then, we immediately prove some interesting things about myself. For instance, I value 100 minutes of my time at more than $20.

    That assumes I get nothing out of writing blog posts, or rising to meet one of my self-imposed challenges. I get a really big sense of accomplishment when I finish something, and that feeling is definitely worth more than $20 to me. In retrospect, the feeling of accomplishment is worth a LOT more than that - it might be my primary motivator. It was one of the biggest things that made deciding not to go to grad school so difficult. Should probably keep a closer eye on that part of myself.

    Now, on the other hand…I have a final tomorrow. I have not studied for this final as much as I should have. Evidently, I value writing blog posts and going on road trips to LA more than studying for finals. Which I guess makes sense. Writing tons of garbage and doing random things in LA is so much more interesting than reading my scribbled notes from weeks long past. I can justify not studying by saying “I’m a second semester senior”, “I’m taking this class pass-no pass”, and from your perspective you might be wondering why I feel guilty at all. But I do. It’s probably tied to that feeling of accomplishment. The feeling I get when I fail to do something simply because I didn’t put in enough time is terrible. For me, there isn’t some line in the sand marking things I want to do and things I should do but don’t want to. It’s one big gradient of priorities and procrastination. Envisioning achievement motivates working towards that achievement, even if the path required to get there isn’t worth it in the end.

    you’ll never give up, even if there’s, uh… absolutely NO benefit to persevering whatsoever. if i can make that clear. no matter what, you’ll just keep going. not out of any desire for good or evil… but just because you think you can. and because you “can”… … you “have to”

    (Naming the source would be a spoiler.)

    Hey, will you look at that. I hit 500 words! Cool. Nice. See you all next time.

    (Also, I think I’ll be fine for the final. If I’m not, well, life is one big tapestry. In any piece of work that big, it’s expected that patches of it will be baby barf green.)

    Comments