• Hi All

    Please note that at the Chandoo.org Forums there is Zero Tolerance to Spam

    Post Spam and you Will Be Deleted as a User

    Hui...

  • When starting a new post, to receive a quicker and more targeted answer, Please include a sample file in the initial post.

For me to understand how it works, I need excel

Hi ,

I find this switching somewhat confusing ! Sometimes we are discussing rent-sharing , and at other times it is cake cutting.

Even if we now continue discussing cake-cutting , if we are to simulate this in Excel , how would we go about it ?

In cake cutting , the difficulty is in visualization , since what I perceive as 50 % of the cake might appear to be 52 % to the other person.

In rent-sharing , the question is slightly different ; given a number of rooms 'x' , and a number of people 'y' , we are given the following :

1. The overall house rent for the 'x' number of rooms ; let us say this is R.

2. Obviously , just dividing R by y will not lead to everyone of the 'y' people being satisfied , otherwise we would not need any algorithm.

3. Thus , we need a system to specify :

a. The value of each room to each person ; this is what is being done in the online rent calculator , where each person is allowed to choose from the several rooms , based on their preference , which may mean that a person may not always choose to take the room with the lowest rent

b. The rent for each room ; do you have the algorithm for this ?

c. When the process of selection can be deemed to be completed ; do you have this criterion ?

Narayan
 
We are in search of the algorithm, this is our focus. Talking about different "Implementations" should not confuse us. The consensus from what I read the cake case has the lion share. BUT they all talk about ONE thing.
If you have a look at the document cake.pdf written by:

University of Utah School of Computing called Cake Cutting and recently written (June 213)

is the closest in talking "our" language, it even produced some pseudo code.

About the calculator, can you please specify which one you refer to, so I can use it to provide some results for your charting approach.

And we will use the Rent case study. No more cakes for you, only when you deliver!! Just kidding.
 
edit

What do you think ?
 
Hi ,

You need to start division , and then note down all the values which are presented in succession till the process ends !

Narayan
 
My strategy is not working, because each one is actually looking for a DIFFERENT room ( no disagreement )
I need to create a situation where they are competing for the best room at the best price.
So I will pick 3 rooms, 2 same size but front and back ( the front is the ace) and one smaller room, that no body wants UNLESS it is good price. My mind will not be able to function if more than 3
 
Hi Samir ,

My comments are the same as before :

1. How were these 3 values arrived at ? I assume you went through more than 1 step , where at each step , the values changed ; how did the values change i.e. what is the algorithm for selecting the values at each step ?

2. How did the calculator come to the conclusion that this was a fair division ? what are the criteria that were used to conclude the division ?

Narayan
 
@arishy

I agree with Narayan Sir's above comment, and still searching for the working algorithm.

I tried many times the calculator and sometimes went upto 30 choices offered. Sometime the result come to around $180 for a person and other person paying say $1000 and $1500. I can't say it's a fair division.

Regards,
 
Somendra Misra said:
Hi All,

Just go through this calculator, will give a brief idea about how may be the prices are arrived at.

https://www.splitwise.com/calculators/rent

Regards,
Click to expand...
Hi Misra ,

The calculator you have posted does not use the same algorithm , I think ; this is a practical calculator , which takes several factors into account in estimating the fair price for each share. It will not be correct to compare this to an algorithm which uses Sperner's lemma , whose basis is different ; in the latter , each person who wishes to take a portion is allowed to select the rent that they are willing to pay ; using a process of iteration , the rent progressively changes , sometimes going up and sometimes going down till when the process concludes , each person is satisfied that they got what they desired at the best possible price. The term 'envy-free' is used because if a person A has taken a room X at price Y , no other person wanted that same room at that price , which is why it is envy-free.

Secondly , suppose we decide that a sea-side room is worth paying 500 more ; if the price of 500 is known before-hand to all participants , then it is no longer an envy-free algorithm , since everyone can feel that they would have paid 500 more to get that room.

But suppose , the sea-side room is allotted a price based on an algorithm which progressively changes this amount , and eventually it is taken by A at a price which is 5000 more ; this means that no other person wanted the room at that price , and therefore A's possession of that room is not envied by others.

Thus , the changing of the prices , as well as the iterative and interactive process makes the algorithm complex ; if every feature of every room is allotted its price , and all the prices are known before-hand to all participants , then there is no complexity ; this is how every practical real-estate sale takes place.

Narayan
 
Narayan,

You are on the right track.......I will do more and try to answer your 2 questions.
Do you have specific format in mind to provide you with calculation details digitally ??
 
Hi ,

What ever you can unearth !

What we can work with is an algorithm , or pseudo-code or ...

Anything that helps us understand is welcome.

Narayan
 
Ref. to the calculator test runs observations:
1. If I use the SAME input say 3 and 3 for the same total.. Each time I use the calc,I get different results !!!!
2. The algorithm is relying on the fact that each selection is based on "invisible value system" by each player. Since I represent the 3 players, it is hard to play the role Ideally, the 3 players should actually use the model, not one represent the 3.

I still see the beauty of this approach, because it asks the minimum from the user:
No. pf player
No. of items
Total figure.
 
Dear All specially @arishy ,

Sorry for replying late, please see this graphical imitation of the problem:

@Debraj

Hi, :) :p

I think now we can focus on the algorithm as said Narayan.
 

Attachments

  • Triangular Plot.xlsx
    19 KB · Views: 7
Nice work Faseeh, You took the approach that NT article used to explain the mechanics AND produced a tool.
The challenge is now to coordinate with the rest of us to nail this algorithm down.
I will spend sometime understanding what you did,and of course I will have questions, but let me do my home work first.
 
You must log in or register to reply here.
Back
Top