path: root/coinselection/ilp.tex
diff options
Diffstat (limited to 'coinselection/ilp.tex')
1 files changed, 36 insertions, 6 deletions
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.
\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}
@@ -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.
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}