2
$\begingroup$

Background

I have a setup where I need to make an API call to a partner to initiate a financial transaction. I have multiple partners, and I need to choose which one to use each time a transaction needs to happen. The characteristics differentiating two partners are:

  • if the transaction is accepted or not (acceptance)
  • the cost of the transaction (fee charged by the partner, assumed to be constant over time)
  • the speed of the transaction (assumed to be constant over timefor each partner)

The characteristics of a transaction are especially:

  • amount
  • currency
  • (several other factors such as the user's country, the payment method he chose, etc)

Additional info: the acceptance rate of a partner is subject to change arbitrarily over time.

.

Algorithm

As you probably guessed, I am currently thinking about solutions and algorithms that could be used to solve the following problem.

Inputs:

  • a transaction (with all its characteristics)
  • the database of all transactions having ever happened, containing for each transaction
    • the partner used
    • the fee charged
    • if the transaction was accepted or not

Output: the best partner to use to execute the transaction.

Obviously, the first step is to define best. Do we value speed more than cost? Do we value the expected acceptance rate more than both the cost and speed? etc.

Another important aspect I mentioned earlier is that the acceptance of the same transaction by the same partner might change over time. This means that the algorithm should sometimes try a partner that is believed not to be currently the best just to be able to, for instance, check if a partner's acceptance rate has improved over time.

My question

I'm obviously not asking someone to write a magic algorithm solving that. I have a background of CS, but I am unsure about what algorithms and types of algorithms are usually used to solve this kind of problem. I would be grateful to be given some extra terminology (e.g. if this is a typical problem with a particular name in the domain) and resources to be able to dig into the problem.

Please don't hesitate to ask if something is unclear.

Thank you!

[Edit] After searching a bit more on the web, it seems that this problem has a lot in common with the multi-armed bandit problem. However I believe that the algorithms presented to solve this problem (e.g. UCB1) could be suboptimal in this context, because they wouldn't take into account the characteristics of a transaction and act as if the partner didn't take them into account.

$\endgroup$

1 Answer 1

2
$\begingroup$

Techniques developed for the multi-armed bandit problem might be useful for discovering the partner with the best acceptance rate and dealing with the changing acceptance rate over time. Those techniques balance "exploration" (sending transactions to a partner as a way to learn more information about their acceptance rate) vs "exploitation (sending transactions to the partner with the highest acceptance rate, to make use of the information gained previously). You'll probably be especially interested in the non-stationary bandit problem.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. How would you deal with the fact that the transactions have attributes that are important? For instance, intuitively the amount is important: transactions of 2 euros are less likely to be refused. So if the algorithm doesn't consider the features of the transactions, it seens to me like a waste. $\endgroup$ Dec 12, 2016 at 16:45
  • $\begingroup$ @christophetd, I don't know, but it sounds like you're one step closer to being able to ask a new, more specific question -- i.e., a multi-armed bandit where the odds of payout depend both on what arm you choose and on some visible attribute you can't choose but can observe. It might be useful to spend a little time thinking about how the acceptance-probability might depend on the amount (what do you think the shape of that curve might look like?) and see if you can think of any way to generalize multi-armed bandit algorithms to this setting. $\endgroup$
    – D.W.
    Dec 12, 2016 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.