summaryrefslogtreecommitdiff log msg author committer range
path: root/coinselection/ilp.tex
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
Diffstat (limited to 'coinselection/ilp.tex')
-rw-r--r--coinselection/ilp.tex42
1 files changed, 36 insertions, 6 deletions
 diff --git a/coinselection/ilp.tex b/coinselection/ilp.texindex 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}