From 42a2e5df0fccf1baf2e55a40336953e8b22adb03 Mon Sep 17 00:00:00 2001
From: Christian Grothoff <christian@grothoff.org>
Date: Thu, 13 Sep 2018 17:41:23 +0200
Subject: add refresh cost to model

---
 coinselection/ilp.tex | 42 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 36 insertions(+), 6 deletions(-)

(limited to 'coinselection/ilp.tex')

diff --git a/coinselection/ilp.tex b/coinselection/ilp.tex
index ee74b60..b182000 100644
--- a/coinselection/ilp.tex
+++ b/coinselection/ilp.tex
@@ -19,6 +19,8 @@
       changes the denomination. So technically this formula depends on the exact coins
       we would obtain from a refresh. But in a first approximation, some bound like this
       should hold for sanity.}
+\item[$r_c$] Let $r_c \in \mathbb N_0$ represent the number of coins of type  $c \in {\cal C}$
+         that require a refresh after the operation because they were partially spent (deposit ILP only)
 \item[$p$] Let $p > 0$ be the amount to be paid in the spend/deposit operation (deposit ILP only)
 \item[$f$] Let $f \ge 0$ be the amount of fees the merchant would cover in the spend/deposit operation (deposit ILP only)
 \item[$w$] Let $w > 0$ be the amount to be withdrawn (withdraw ILP only)
@@ -43,7 +45,8 @@ We will use the big-M method to stress that customers paying any fees is bad.\fo
 we could use a smaller $M$ to trade-off paying fees for using coins close to expiration. So maybe
 $M$ should just be a constant to represent this trade-off instead of the traditional big-$M$.}
 Thus, let $M$ be a sufficiently ``big'' number.  We will use $\alpha$ as an
-additional cost factor to model the bandwidth and computational cost per coin.
+additional cost factor to model the bandwidth and computational cost per coin, and
+$\beta$ as an additional cost factor to represent the (approximate) cost of a refresh.
 
 
 \section{Withdraw ILP}
@@ -81,10 +84,36 @@ implications on privacy.
 
 \section{Deposit ILP}
 
+The following deposit constraint system makes simplfiying assumptions
+about the refresh by not fully considering the refresh costs.  Imagine
+a systen where we have a 1 EUR and a 10 EUR coin, and need to pay 6
+EUR.  The system offers 1, 5 and 10 EUR coins. All fees are zero.  In
+this case, paying with both the 1 EUR and 10 EUR coins might be nice,
+as we would get one 5 EUR coin as change.  The algorithm below would
+always choose paying with just the 10 EUR coin, getting four 1 EUR
+coins in change.  The simplification results from us not
+differenciating between different refresh operations -- we consider
+all of them as having roughly the same cost, thus the only objective
+is to avoid refreshs overall, but not to pick ``nice'' refreshs.
+
+This is probably OK for two reasons: (1) the example is a bit
+constructed, and is unlikely to appear this extreme with denominations
+following powers of two. (2) a more comprehensive algorithm for the
+example could still only consider the direct cost of the refresh
+operation.  However, it might be {\em nice} to have five 1 EUR coins
+as this would avoid refresh costs for future operations (more exact
+change!).  Or it might be terrible, as nobody should eventually pay
+with hundreds of 1 cent pieces!  However, whether the wallet's coins
+would devolve as a result is unclear. It seems likely that such change
+would quickly be spent in the next transactions.  Thus, analyzing this
+choice cannot be done by looking at an individual operation.  We might
+adjust the model in a future version to capture the alternative design
+and then study the affect on larger simulations of many transactions.
+
 \begin{align}
   \min &M \cdot \tau + \sum_{c \in {\cal C}} s_c 
                      + \sum_{c \in {\cal C}} n_c \cdot \alpha)
-                     + refresh-cost \\
+                     + \sum_{c \in {\cal C}} r_c \cdot \beta \\
   \texttt{such that} \quad
   \bigwedge_{c \in {\cal C}} n_c \cdot d_c &\ge s_c  \label{eq:coinnum} \\ 
   \bigwedge_{c \in {\cal C}} n_c &\le a_c \label{eq:exists} \\
@@ -93,7 +122,9 @@ implications on privacy.
        \sum_{c \in {\cal C}} s_c - \tau p &\le p \label{eq:tau} \\
        \tau &\in \{0,1\} \label{eq:bin} \\
        n_c &\in {\mathbb N_0} \label{eq:nc} \\
-       s_c &\in {\mathbb R^+_0} \label{eq:r}
+       s_c &\in {\mathbb R^+_0} \label{eq:r} \\
+       r_c \cdot d_c + sc_c \ge  n_c \cdot d_c \label{eq:refresh} \\
+       r_c &\in \{0,1\}_ \label{eq:rc}        
 \end{align}
 
 Explanations:
@@ -111,14 +142,13 @@ Explanations:
 \item[\eqref{eq:bin}] Force $\tau$ to be 0 or 1 as per our model.
 \item[\eqref{eq:nc}] Force selected coins to be a discrete number.
 \item[\eqref{eq:r}] Force coin contributions to be non-negative.
+\item[\eqref{eq:refresh}] If a coin was partially spent, force $r_c$ to be 1 instead of 0.
+\item[\eqref{eq:rc}] Force $r_c$ to be 0 or 1 as per our model.
 \end{description}
 
 Note that the refresh cost is missing, as for that we will need to introduce
 a dependency on a withdraw operation as well!
 
-TODO: introduce additional variable to model when coins need to be
-refreshed, and model the refresh cost itself!
-
 
 \section{Refresh ILP}
 
-- 
cgit v1.2.3

