Change optimization
by Tom Temple
23 June 2005
I try to optimize my change. Carrying around nickles sucks. But since I have to use laundry machines, I like to get quarters. Since I like to get food from the vending maching that only takes ones I like them too.
Let’s say I have this vector of weights, W, that tells me how much each is worth to me (in the non-monetary sense). What strategy do I use to maximize W’M where M is the amount of money that I have in my pocket? What is the steady-state rate of coin collection?
Assume 1) transactions are uniform over [0… 5$] mod 5$ You can widen that if you want to include weights for larger bills. For instance hundreds scare me so I like to break them..
2) people always give me minimum change in number of coins, except,
3) people will not convert currency. For instance if I buy something at the dollar store and pay 1.25 using [1 0 2 1 0]’ I will not get a quarter back.
1)What if I start the week with only 20s (or hundreds if you are using more weights). During the week I make N transactions. At the end of the week, I take all of my money to the bank and get 20s again. At what rate is the bank acruing each denomination?
2) I have this friend with a different weight vector, W_f. At the end of the week we get together and trade money. Since I know W_f, do I change my change strategy? What is our combined rate of coin capture? How much do we profit by trading?
