Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
×
Math The Almighty Buck

New Website Offers Provably Fair Solutions To Everyday Problems 167

An anonymous reader writes Carnegie Mellon researchers have just launched Spliddit, a website that offers methods for helping people split rent, divide goods, and share credit. The novelty is that these methods are all "provably fair": there are mathematical proofs showing that each algorithm on the site provides rigorous fairness guarantees. For example, the method for splitting rent is guaranteed to be envy free: the assignment of rooms and division of rent is such that a housemate would never want to swap places with another housemate. All it takes is a pair of siblings to prove that there's no such thing as "provably fair," non-mathematically.
This discussion has been archived. No new comments can be posted.

New Website Offers Provably Fair Solutions To Everyday Problems

Comments Filter:
  • by wcrowe ( 94389 ) on Thursday November 06, 2014 @04:51PM (#48328749)

    I keep telling my dogs that the way that Spliddit divvies up the expenses is PROVABLY FAIR, but all they do is look at me blankly, cocking their heads to one side. Damn dogs. I never see a dime out of either of them.

    • In addition to dogs children won't get it. If you give two children 4 crayons each, who has more? The answer is always the other does.

      • by Quirkz ( 1206400 ) <ross @ q u irkz.com> on Thursday November 06, 2014 @06:18PM (#48329823) Homepage

        Hell, if you give two children identical copies of the same color crayon, one will still want what the other has.

      • In addition to dogs children won't get it. If you give two children 4 crayons each, who has more? The answer is always the other does.

        As usual, the bible has the answer.

        First, "divide the living child in two" (1 Kings 3:25). This will give you four half-children, each with two crayons, and a blissfully quiet household.

      • Isn't there an implication that the algorithm is provably fair to a rational being. The last time I interacted with them, human children did not appear (mostly) to be rational beings.
    • http://www.spliddit.org/apps/g... [spliddit.org]

      I only got half of a cat!

    • It in fact doesn't work:

      This property is guaranteed, assuming that each housemate wishes to maximize the difference between what she thinks her room is worth and how much rent she has to pay.

      That's not the objective of most people -- they will value rooms differently depending on which other rooms they own.

      And I suspect someone could gain an advantage by dishonestly reporting how much they value each room. Specifically, if you express a value for the rooms as almost the same as your roommate, but slightly lower for the rooms he wants the most and slightly higher for the rooms he likes the least, I suspect their mechanism for overdemanded and underdemanded rooms will give

      • -> Specifically, if you express a value for the rooms as almost the same as your roommate, but slightly lower for the rooms he wants the most and slightly higher for the rooms he likes the least, I suspect their mechanism for overdemanded and underdemanded rooms will give you the slightly inferior rooms at a greatly reduced price

        You'll only screw yourself that way. Suppose he values the first bedroom at $600 and the second at $500, because the first bedroom is better in some way.

        You suggest going lowe

  • sibling fairness (Score:5, Interesting)

    by orgelspieler ( 865795 ) <w0lfieNO@SPAMmac.com> on Thursday November 06, 2014 @04:54PM (#48328777) Journal
    The best example of a fairness algorithm is an old one used with siblings. Tell one kid to divvy up the candy/cake/toys whatever, and let the other kid choose which half they want.

    Greece used something similar when trying to get people to honestly report the value of their antiquities. If they listed it for a price the government thought was too low, the agency could buy it for that price. I wish local governments would do something like that with home values. If they want to tax me for a house worth more than what I can get for it on the open market, then I should have the right to sell it to them at that price.

    • by Ichijo ( 607641 )

      If they want to tax me for a house worth more than what I can get for it on the open market, then I should have the right to sell it to them at that price.

      Better yet, make property taxes reflect the property's burden on the government. What we have now is an unscrupulous diner's dilemma [wikipedia.org] situation where people who maximize their street frontage in order to give themselves more places to park pay only a tiny fraction of the incremental cost (land, maintenance, lighting, emergency response, etc.), and everyon

      • What we have now is an unscrupulous diner's dilemma situation where people who maximize their street frontage in order to give themselves more places to park

        It doesn't matter how much frontage you have, the street is still the same length and there are still the same number of parking spaces. In fact, the fewer the driveways, the MORE spaces to park there are. How much space you have to park depends on the area of your property, not the frontage. A dual driveway and a two car garage gives four spaces no matter how much frontage that property has.

        You're confusing "public on-street parking" with "private parking". Those spaces on the street are intended for tr

    • The best example of a fairness algorithm is an old one used with siblings. Tell one kid to divvy up the candy/cake/toys whatever, and let the other kid choose which half they want.

      That's essentially how their web site works, except they're asking every roommate to divide up and assign a value to each space, before asking them which space they might prefer. In a way, I like their site better, because it seems to work more like a blind auction. By keeping the bids of other roommates initially secret, then they're essentially preventing them from changing their mind halfway before the process is finished. It makes the process much cleaner that way and much more haggle-free.

      • I'm putting a high value on the bathroom and the foyer. when I get those two rooms, I put a coin-op pay slot on the bathroom ... and sleep in the foyer.

      • by Kjella ( 173770 )

        Except you assume that all the players are actually honest about every option and valuation and not just playing the algorithm. Imagine a well off and not so well off student decide to share an apartment which consists of two rooms, one small and one big and a common area. They can't agree how much the extra space is worth, now the poor student he doesn't want the big room. He just wants the other guy to pay this "fair" share extra so he can pay as little as possible. Now the rich student he knows the poor

    • Hmm.... Maybe they should do this with intellectual property.

      The owner of intellectual property would be taxed based on a value the owner specifies annually. The government would have the option to purchase it for that amount, perhaps with an added premium. If the property is sold, the purchaser is taxed initially based on what they paid. Licences & royalties would be limited based on the taxed value.

      I was about to say maybe this would be too complicated to get right... then I remembered our tax co
      • I was about to say maybe this would be too complicated to get right... then I remembered our tax code.

        Are you, in any way, implying that the government got the tax code right?

        • Oops, I guess I did imply that. I just meant that their are good reasons why the tax code is complicated, and that shouldn't prevent the taxation of intellectual property. The whole system needs massive reform anyway; companies that own a lot of IP already put them in holding companies and then licence them back to themselves.
    • The best example of a fairness algorithm is an old one used with siblings. Tell one kid to divvy up the candy/cake/toys whatever, and let the other kid choose which half they want.

      Greece used something similar when trying to get people to honestly report the value of their antiquities. If they listed it for a price the government thought was too low, the agency could buy it for that price. I wish local governments would do something like that with home values. If they want to tax me for a house worth more than what I can get for it on the open market, then I should have the right to sell it to them at that price.

      Have you been reading old Heinlein novels? That's where I first encountered both of those concepts. Number of the Beast, right?

      As for letting one sibling divvy stuff up and letting the other sibling pick, that's why democracy doesn't work in practice. Because however many people are involved, you need to account for each individually, so it gets out of hand after only a few people are added to the society.

    • I had heard this too, in a Probate Case. It really works well when you have things of asymmetrical value. Dividing money is easy. Figuring out the relative worth of baseball cards to a rug wasn't so much in the Probate case.

    • Something like that was done for real estate assessment in fiction (some Robert Heinlein novel) and also (I think) in reality (Singapore, perhaps). As I recall, in the fictional instance, there was another wrinkle: anyone could buy it for your assessment of its value (and had to pay the difference of the taxes for the previous 3 years, to boot). The purchase price you pay to the owner; the increment on the tax you paid to the government.
  • Commercialism. (Score:2, Insightful)

    by ledow ( 319597 )

    I think the requirement to have all your roommate's email addresses is the actual point of the website.

    People can work out fair regimes. They can't spam their roommates easily enough, apparently.

    • They ask for all the emails, but only require one person to actually give the email.

      That is probably where they make their money.

      But the divorce settlement technique is actually pretty useful. Amazing how often people are just total SOB's and DOB's over silly things.

      The real problem there, however, is the desire to screw over, get revenge/compensation for other issues.

    • by Kvasio ( 127200 )

      what's the problem here? Just use disposable email addresses. Eg a browser plugin, Donottrackme.

  • by Anonymous Coward

    with 2 roomates I've done things this way: have one person set the prices of each room and the other person can then pick which room they want. this has worked well. the main practical complication I've had in real life is when one person makes much more money than the other person. the well off person would likely be willing to spend far more than the "fair" price in this situation for the better room. I don't think there's any clear cut solution that works in every case.

    • by guruevi ( 827432 )

      The market tells you what is fair and what is not.

      Let's say:
      If I have 1 really large attic-room and 2 small bedrooms for rent, I could (locally) ask probably $350-450 per small room including utilities. For the large room even though it's 500sqft vs 150 sqft for the small bedroom, I can't ask >$600, because once you get closer to 800-1000, they may as well rent an entire house and sublet the bedrooms (although they would have to pay utilities).

      The poorer person may want the bigger room because they also

      • by Lehk228 ( 705449 )
        there is nothing objectively unfair for you, the owner, to make a profit on renting out a space. if it was wrong to do so how would landlords exist at all?
    • the main practical complication I've had in real life is when one person makes much more money than the other person. the well off person would likely be willing to spend far more than the "fair" price in this situation for the better room. I don't think there's any clear cut solution that works in every case.

      Suppose the rent on the two bedroom place is $1,000. The "rich" roommate over bids as you suggest and says he'll pay $800 for the room on the left. Fine, that leaves the other roommate to cover only $200 for the other room. One can hardly complain about getting half of a $1,000 apartment for $200.

    • by devman ( 1163205 )
      If the well off person values the better room at more than "fair" price (fair being defined here as what the other roommate valued it at) that means the other roommate gets the other room cheaper than he would have valued it. That's win-win is it not?
  • by drooling-dog ( 189103 ) on Thursday November 06, 2014 @05:03PM (#48328885)

    To divide ice cream equally between two kids, have one dish it out and the other choose. My parents did this with my brother and me, and there was never anything to fight about afterwards. You'll never see more precise measurement in your life, though.

    • by Anonymous Coward

      I tried this once. One kid divided it up unfairly and stuck his finger in the bigger portion. The other kid would rather have the smaller portion than the tainted one.

      The second kid didn't get as much as was fair, but the trash can got the first kid's share...

    • What if you want to share it between three kids?
    • by Anonymous Coward

      I did this with my little brother, and he always answered that he wanted the bigger one. I had to explain every time that he had to choose one of the bowls. Then, when he was older, he realized he could just spit on both...

  • by agm ( 467017 ) on Thursday November 06, 2014 @05:07PM (#48328931)

    Can we finally solve the age old question as to whether the seat should be left up or down? This is a function based on how many males vs females there are, and how often a male needs to, er, sit.

    • Re: (Score:3, Insightful)

      by Anonymous Coward

      Always down -- including the lid.

    • by Some_Llama ( 763766 ) on Thursday November 06, 2014 @05:17PM (#48329063) Homepage Journal

      it should ALWAYS be that the person sitting is in charge of making sure it is down.

      Men sit down to poop, i don't hear them ever argue about who left the seat up, they just check before sitting.

      common sense?

      • You would be surprised at how popular a topic this is amongst economists [google.com]
        • by Anonymous Coward

          Both the seat and the lid get closed after use every time because the cats will otherwise play or fall into the toilet. That is all.

      • Would she rather he lift the seat and leave it up or pee on it when it is left down? They both need to reach a compromise--one can't unilaterally impose a toilet seat rule.

        • Tell that to me (ex) wife. I never believed that a couple could have such a petty argument (we're all rational adults right). Boy was I wrong.
      • Re: (Score:2, Insightful)

        by Anonymous Coward

        your argument doesn't work even though it is logical

        most men are rational about everything except relationships

        most women are the opposite

        It is impossible to discuss anything rationally with a woman because she believes that her "feelings" have a value, and that value is infinite. Therefore the only thing of importance is that she gets the result that makes her "feel" good (usually involving the man making a lot of extra effort/resource expenditure)

        It doesn't "feel" good for her to have to make the effort t

      • Yeah - how come nobody ever asks "Why can't women put the damned seat up after them? They are so inconsiderate."

        Maybe someone could hack one of those dopey toilet seat closers?

        • We had cats and kids at one point. Letting cats (or any other dependent) drink water from a toilet is an act of stupidity. Eventually, they're going to catch something, and it may be very nasty -- even nasty enough that you might get it.

          So... I set an alarm up that would go off in the kid's bathroom (they weren't allowed in ours) if the seat was up and the bathroom door was open.

          The rules were: (1) if the alarm went off, they lost 10% of their allowance. (2) If the alarm was found to be disabled in any way,

          • by Anonymous Coward

            Cool system, but...

            Cat's are a million times tougher than you think.

            Dogs are even more so. I've seen watched many dogs lap up shit (from a wide range of animals, carnivores and omnivores) and guzzle it down, doing so all their lives, and still remained perfectly healthy.

            • by fyngyrz ( 762201 )

              That's all fine... until something gets them. Better not to count on tough immune systems and provide a clean environment instead.

              I don't even let them drink out of a bowl. I use an IR sensor to drive a 12v valve, which runs a stream of water they lap out of the air from our RO system. My cats have consistently been living past 20 years. Pretty happy with that.

      • Men sit down to poop, i don't hear them ever argue about who left the seat up, they just check before sitting.

        Of course you don't "hear them ever argue". Who do you suppose the man might argue with, given that he would be the one who left the seat up?

        • by Anonymous Coward

          Let me spell it out for you since you can see past a fucking pebble. Men don't get bitchy when women leave the seat down.

      • Re:Toilet etiquette (Score:5, Interesting)

        by Solandri ( 704621 ) on Thursday November 06, 2014 @07:13PM (#48330329)
        Least-effort solution (minimum number of seat position changes) is for the person who uses the toilet to move it into the configuration they need it in, then leave it.

        Least-agony solution (minimum number of gross incidents) is to always lower the seat after use. However, the fact that "men won't follow" this solution is merely coincidence - this solution happens to coincide with the configuration women always use so they can never be guilty of transgressing it. When I was living alone I had a dog who liked to drink out of the toilet. Consequently, I always told guests to lower the lid of the toilet after using it. My female guests always left the lid up. About half the men would lower it (probably due to being scolded about it by women all too often).
      • My 90lb first wife was raised in a mostly female household. We had only been married a few days when from the bathroom I hear, "eek, splash".
      • it should ALWAYS be that the person sitting is in charge of making sure it is down.

        Men sit down to poop, i don't hear them ever argue about who left the seat up, they just check before sitting.

        common sense?

        Hmmm. I get pissed at girlfriends when they come over and leave the seat down but the lid up. I hate staring into the gaping maw of the toilet bowl every time I need to walk into the bathroom. Furthermore, at a previous home, someone put a cabinet above the toilet. Can't tell you how many times I accidentally dropped something into the bowl from the cabinet shelf. Now the seat and the lid are second nature to me.

    • by raymorris ( 2726007 ) on Thursday November 06, 2014 @05:29PM (#48329213) Journal

      The male wants to avoid unnecessary raising and lowering - conservation of energy.
      The female wants TWO things - she wants the seat lifted before the gentleman urinates, AND she wants it lowered before she does.

      If the gentleman leaves the seat up, the female (provably) got the first thing she wants - the seat was raised before he urinated. Each party ends up doing the same amount of effort - they either raise or lower the seat before using it. That's fair.

      The other option, that the seat is left down, means that a) the man is expected to do 100% of the work, both raising and lowering, while the female does none. More importantly from her point of view, if the seat is down, she doesn't know whether or not it was down when he peed. She might be sitting on pee spots.

      Fairness, and her own piece of mind, therefore dictate that he leave the seat up.

      However, if she's clever, she can't gently force the seat to be lowered afterwards by placing a tray of soaps, potpourri, etc. on top of the toilet. The tray will prevent the seat from being raised all way to vertical and gravity will ensure it ends up down. The clever gentleman can respond to this forcing function by pointing out that it prevents her from knowing whether male guests ever raised the seat at all.

      • by bn557 ( 183935 )

        This is why I always pee in the shower. Problem solved!

      • by mjwx ( 966435 )
        It sounds like you're applying a rational process to women... Stop it.
      • The other option, that the seat is left down, means that a) the man is expected to do 100% of the work, both raising and lowering, while the female does none.

        You're probably not serious, but just in case ...

        1. Women can be hard to please
        2. This is an easy way to please them

        Just sharing what little wisdom I've picked up over the years ..

        • I wasn't serious. My actual strategy is to leave drips all over whichever restroom does not contain her makeup. She'll quickly stop using that restroom and only use "her" bathroom, the one with her makeup in it. Bonus points if her bathroom is also the guest bathroom.

          Totally kidding- I want my woman to be happy when she has her pants down.

    • Given one man, one woman, one toilet. Women put the seat up when they're done, men put (or leave) the seat down when they're done.

      The next user will likely be the opposite person, and they will have the seat set for them unless:

      1 - They are a man who needs to take a shit after a woman last used the toilet. He has to put the seat down before shitting, but he then does not have to take an additional action afterward. No effort wasted here.

      2 - They were the one who used it last. They have to undo and repea

    • Re:Toilet etiquette (Score:5, Interesting)

      by tlhIngan ( 30335 ) <slashdot@worf.ERDOSnet minus math_god> on Thursday November 06, 2014 @06:44PM (#48330079)

      Can we finally solve the age old question as to whether the seat should be left up or down? This is a function based on how many males vs females there are, and how often a male needs to, er, sit.

      In a domestic (i.e., household) setting, the simple compromise is toilet LID down. This way EVERYONE has to lift something to do something. If you're a lady, you lift the lid and the seat is down. If you're man doing #1, then you lift the lid and seat together. for #2, you lift just the lid.

      Then when you're done, you put the lid back down. If also keeps the bathroom more hygienic as the act of flushing creates a plume of toilet water. Keeping the lid closed keeps that plume within the toilet and not the entire bathroom.

      It has the advantage that stuff doesn't accidentally fall into the toilet too.

      • by kooky45 ( 785515 )
        This is what I do at work, but it's because too many colleagues are either too lazy or too scared to touch the seat and they so wee all over it. With the lid down they either have to touch it and learn that a messy seat is a hazard, or choose another toilet.
      • by u38cg ( 607297 )
        Actually, closing the lid traps an aerosol of toilet water which blows up in the face of the next user. It persists a surprisingly long time. Citation: some Reader's Digest magazine I read in a dentist's waiting room twenty years ago.
      • It has the advantage that the cat doesn't fall into the toilet, too.
        FTFY
        --
        "Gravity just affects how distances are measured." Tell that to a skydiver's next of kin.

    • >> This is a function based on how many males vs females there are, and how often a male needs to, er, sit.

      No it isn't.
      The logical thing to do is the minimum possible - ie leave the seat where it is when the operation is complete. When the next user comes along they may - or may not - have to adjust it.

      Or are you suggesting that women reverse blindly into a bathroom and sit down?

    • by Lehk228 ( 705449 )
      always close the damned lid, to not do so is degenerate
    • Can we finally solve the age old question as to whether the seat should be left up or down? This is a function based on how many males vs females there are, and how often a male needs to, er, sit.

      Pee on the seat twice, then she'll start begging you to leave it up!

  • Sounds a lot like BillPin [billpin.com].

  • The best fairness concept i have ever seen involves two people trying to split one thing evenly, the way it works is one person does the splitting and the other gets to make the first choice of which half they want. this article reminds me of this concept.

    • and in rush to post my brilliant info i faled to notice the 50 other people who know this already.. yay!

  • Once you have an algorithm that is provably fair, all you need to do is prove that the algorithm itself was chosen in a provably fair manner.

    By another algorithm which is provably fair. With values which were chosen in a provably fair way. And so on. And so on.

    As long as that chain of logic doesn't end with "BECAUSE I SAID SO NOW SHUT UP AND PAY YOUR SHARE!" then everybody should be satisfied by how fair everything is.

  • by gurps_npc ( 621217 ) on Thursday November 06, 2014 @05:33PM (#48329287) Homepage
    People would never have a problem with dividing things if they didn't get all emotional about it.

    Divorce is the prime example - it's rarely about the 2nd home, the dog, the china, etc.

    It's about the cheating, the 'stealing the best years of my life', the drug addiction, etc.

    Nine times out of ten, people are not really looking for 'fair', they want 'JUSTICE' (in quotes).

    A pity, because in reality, 'JUSTICE" is another word for spending all your time and money on lawyers to punish someone else.

    If their algorithms won't let you spend all your time and money on punishing your opponent, it won't actually solve all the problems of sub-dividing property.

    • In my divorce, I decided I wasn't going to put up a fuss about owning things. I could replace them, and I wanted a divorce with as little fuss as possible.

      It may have helped that, when my soon-to-be-ex-wife got the papers, she seemed to think I needed her to sign them, so she didn't file an objection to what I thought reasonably fair. (The lack of kids and real estate also helped a lot.)

  • Cake-cutting algorithms, I love them. I've read parts of the book by Robertson and Webb and always wonder about unusual and new applications for them.

  • by PapayaSF ( 721268 ) on Thursday November 06, 2014 @06:39PM (#48330031) Journal

    We did this back in college, and it worked great.

    1. – Make a list of all chores that need to be done every week.
    2. – Agree on a point value for each one, with more points for longer or less pleasant chores.
    3. – Divide the total points by the number of roommates, so everyone has X points to do per week.

    The real genius of the system then comes in: whoever does their chores first gets to pick which ones to do, and whoever puts it off until the end has to do whatever's left. So there's a built-in incentive to do chores early, and no squabbling, because everyone agreed to the point rankings ahead of time.

    • Another neat thing about this: when somebody picks which chores to do, he or she picks the least onerous chores for the point value. That takes advantage of any differences in how unpleasant people think chores are. I'd likely wash all the dishes, for example, since I don't mind it as much as some people do. (Also, many people don't wash up to my standards, so there's another incentive that is not accounted for.)

  • "All it takes is a pair of siblings to prove that there's no such thing as "provably fair," non-mathematically."

    Obviously you did it wrong, you raised your kids wrong. They should be cooperating because they are fundamentally pack, team members and because they are mathematicians. You are illogical.

  • Congratulations to the researchers. They just re-invented PageRank.
  • If enough people start using tools like this and trusting game theorists, perhaps we will ultimately be able to get non-academics on board to fix our broken voting system. The American voting system was designed by people who thought slavery was fair, and was ultimately a compromise between people who thought land ownership should grant rights, and people who thought every white male should have equal rights.
  • "The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate, without further ado, to see who is right."

Dennis Ritchie is twice as bright as Steve Jobs, and only half wrong. -- Jim Gettys

Working...