[Taler] optimal coin spending

[Jeff Burdges]

Just to answer Marcello's question from this evening about optimal coin
spending.  -Jeff



We have:
  a set D of denominations,
  a value function v : D -> R,
  a deposit fee function f : D -> R,
  a maximum deposit fee m>=0,
  a refresh/melt fee function r : D -> R,
  a wallet function w : D -> Z,
  an unknown constant c>0 but very small,
  and a price>0
where f, r, and w are non-negative.  And R and Z denote the reals and
integers, respectively.

We want to select two functions
  spend total t : D -> Z, 
  spend partial p : D -> Z, and
  partial value v' : D -> R
so as to minimize the function :
  max(0, -m + sum_x f[x]*d[x])
  + sum_x r[x]*p[x]
  + c * sum_x (d+p)[x]
subject to the constraints
  t[x] >= 0
  p[x] >= 0
  (t+p)[x] <= w[x]
  sum_x v[x]*d[x] >= price
  sum_x (v[x]*t[x] + v'[x]) <= price
  v'[x] <= v[x]
  p[x] <= 1
where d = t+p is a convenient notation.

We assume these last two because if p[x] > 1 then you could refresh one
less coin.  In fact, you should never refresh more than one coin, so
that's sum_x p[x] <= 1, but not sure we need that much.


1.  Dynamic Programming

There is a solution using dynamic programming because the problem has
the optimal substructure property : 

If the above parameters have an optimal assignment, then replacing 
  price := price - v[x]*t[x] - v'[x],  
  t[x] := 0,  
  p[x] := 0,  and  
  v'[x] := 0
gives another optimal solution, as otherwise we'd get a better one for
the first situation.  

There is however no assurence that t[x] = price mod v[x] for some x in
D, so nievely such solutions give you running times like O(price *
|D|), which kinda sucks actually.  Just one simplified example :
 http://www.codeproject.com/Articles/31002/Coin-Change-Problem-Using-Dy
namic-Programming


2.  Greedy Algorithm

There is a greedy algorithm that runs linear time for the usual change
problem, but it assumes a sane coin systems.  I have not read the
reference 
 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5254395
but presumably it assumes v[x] divides v[y] whenever v[y]>v[x] or
something similar.

There are crazy coin systems that violate this assumption, which
impacts Taler in two ways :

First, an obnoxious mint could make insane denominations that forced
customers and merchants to spend slightly more, while nominally
claiming fees competitive with other mints.  We can ignore this as it's
rather obvious manipulation and an obnoxious mint cannot charge much
more.  I think an approximation result says the mint cannot even double
the fees.  

Second, there could be two mints whose denominations together formed an
insane set that caused bad coin usage.  Again the results should not be
too bad, but one could combat this by processing mints individually
before considering them together.  

Now there are some additional complexities related to giving change and
not knowing how to order the denominations, so maybe worth a bit more
formalism first.


3.  Integer linear programming
(It helps with understanding the greedy algorithm too)

We almost have an integer linear program because all these functions
parameterized by D are simply vectors.  We just need to eliminate that
annoying max(0, ), which we do by introducing a variable z.  I'm going
to switch from t[x] to d[x] = t[x] + p[x] and surpress the indexes [x]
here since only m, c, and z lack indexes.

Select d : D -> Z and p : D -> Z so as to minimize the function 
  z + sum_x ( r*p + c*(d+p) )
subject to the constraints
  d <= w  for all x
  sum_x v*(d-p) <= price
  sum_x v*d >= price
  z >= - m + sum_x f*(t+p)
and
  z >= 0
  d >= 0  for all x
  p >= 0  for all x

We should introduce slack variables so that row operations cannot lose
information:

Select d and p so as to minimize the function 
  z + sum_x ( r*p + c*(d+p) )
subject to the constraints
  d(x) = w - w'  for all x
  sum_x v*(d-p) = price - price1
  sum_x v*d = price + price2
  z - sum_x f*d = -m + m'
and
  w' >= 0  for all x
  m' >= 0
  price1 >= 0
  price2 >= 0
  z >= 0
  d >= 0  for all x
  p >= 0  for all x

We can eliminate z with a row operation and then drop -m + m' from the
objective, so that price is the only constraint set by the merchant. 

Select d and p so as to minimize the function 
  sum_x ( r*p + c*(d+p) + f*d ) = sum_x ( (r+c)*p + (f+c)*d )
subject to the constraints
  d = w-w'  for all x
  sum_x v*(d-p) = price - price1
  sum_x v*d = price + price2
and  ...

And those constraints could again be written as
  d <= w
  sum_x v*(d-p) <= price
  sum_x v*d >= price

It's maybe now easier to visualize the greedy algorithm working when
you think about that sum_x v*d together with this simple objective
function.  As a bonus, we observe that c got folded into r and f, which
simplifies implementing stuff. 


4.  Smarter Greed

If we're only allowed to spend one denomination at some price, then we
shown the minium is achieved when that denomination x in D is chosen to
minimize 
        (f[x]+c)/v[x] + (r[x]+c)/(v[x]*d[x])*p[x]
where p[x] = max(1,price mod v[x]).  We could approximate this by
(f[x]+c)/v[x] under several reasonable hypotheses, not unfortunately r
>> f, but price >> v[x] still helps.  In any case, there are many
situations where minimizing (f[x]+c)/v[x] handles this single
denomination spend.

We know from our optimal substructure property that, for an optimal
allocation, there is a denomination x such that zeroing out t[y], p[y],
and v'[y] for y not x, and adjusting the price acordingly, gives an
optimal allocation.  It follows that a greedy algorithm that uses D
sorted by increasing (f[x]+c)/v[x] frequently works, although not when
mints charge too much for refreshes

Roughly this algorithm looks like: 

FindCoinsGreedily(price,D,v,f,m,r,w,c) 
  set cost = 0
      t = empty_array
      done_cost = infinite
      done_denom = null
      done_t = empty_array
  sort D by increasing (f[x]+c)/v[x]
  for x in D do
    let t[x] = price mod v[x]
    set price = price - v[x]*t[x]
    set cost = cost + (f[x]+c)*v[x]*t[x]
    if cost + r[z]+c < done_cost then
      set done_cost = cost + r[z]+c
      set done_denom = x
      set done_t to be a copy of t
  return (done_t,done_denom)


4.  Linear programming

In the linear programming case, we know any acceptable solution must
occur along the "value plane" face given by
  sum_x v*(d-p) = price - price1
with 
  p = 0 or 1  for all x
  sum_x p = 0 or 1

Almost all the other constraints have the form d[x] <= w[x], the form
d[x] >= 0, the form price1 >=0, or are one of the p constraints. 

As all the d[x] variables appear in the value plane, we know these d
constraints meet the value plane in lines, and similarly the price1 and
p constraints. 

As any two non-parallel lines in a plane meet in a point, the minimum
must lie at the intersection of two of these lines in the value plane
given by other constraints. 

We can simply try all pairs in time O(|D|^2), which we consider to be
constant time. It therefore beats the naive dynamic programming
solutions linked above, although perhaps it could be written dynamic
programming somehow.  It deals with all cases too, unlike the greedy
algorithm.

signature.asc
Description: This is a digitally signed message part