Coin change problem with change – Dijkstra’s Algorithm

The coin change problem is a well studied problem in Computer Science, and is a popular example given for teaching students Dynamic Programming. The problem is simple – given an amount and a set of coins, what is the minimum number of coins that can be used to pay that amount?

So, for example, if we have coins for 1,2,5,10,20,50,100 (like we do now in India), the easiest way to pay Rs. 11 is by using two coins – 10 and 1. If you have to pay Rs. 16, you can break it up as 10+5+1 and pay it using three coins.

The problem with the traditional formulation of the coin change problem is that it doesn’t involve “change” – the payer is not allowed to take back coins from the payee. So, for example, if you’ve to pay Rs. 99, you need to use 6 coins (50+20+20+5+2+2). On the other hand, if change is allowed, Rs. 99 can be paid using just 2 coins – pay Rs. 100 and get back Re. 1.

So how do you determine the way to pay using fewest coins when change is allowed? In other words, what happens to the coin change problems when negative coins can be used? (Paying 100 and getting back 1 is the same as paying 100 and (-1) ) .

Unfortunately, dynamic programming doesn’t work in this case, since we cannot process in a linear order. For example, the optimal way to pay 9 rupees when negatives are allowed is to break it up as (+10,-1), and calculating from 0 onwards (as we do in the DP) is not efficient.

For this reason, I’ve used an implementation of Dijkstra’s algorithm to determine the minimum number of coins to be used to pay any amount when cash back is allowed. Each amount is a node in the graph, with an edge between two amounts if the difference in amounts can be paid using a single coin. So there is an edge between 1 and 11 because the difference (10) can be paid using a single coin. Since cash back is allowed, the graph need not be directed.

So all we need to do to determine the way to pay each amount most optimally is to run Dijkstra’s algorithm starting from 0. The breadth first search has complexity $latex O(M^2 n)$ where M is the maximum amount we want to pay, while n is the number of coins.

I’ve implemented this algorithm using R, and the code can be found here. I’ve also used the algorithm to compute the number of coins to be used to pay all numbers between 1 and 10000 under different scenarios, and the results of that can be found here.

You can feel free to use this algorithm or code or results in any of your work, but make sure you provide appropriate credit!

PS: I’ve used “coin” here in a generic sense, in that it can mean “note” as well.

Explaining UPI

I just paid my cook his salary for November. Given the cash crunch, I paid him through a bank transfer, using IMPS. Earlier today, my wife had asked him for his account details (last month I’d paid him on his wife’s account).

An hour back he sent me his account details (including account number and IFSC) via WhatsApp. I had to wait till I got home and got access to my laptop (Citibank app doesn’t let you add payees on mobile banking).

I get home, log in to Citibank Online. Add payee, which includes typing his bank account number twice. Get SMS asking me to confirm payee addition. I authorise payee. And after all this I am able to finally do the transfer – and I expect him to have got his money already.

For a long time I was wondering what the big deal with UPI was, given that IMPS is already fast enough. Having finally tried UPI earlier this week (it’s finally coming to iOS, but only available on ICICI now. And the implementation so far sucks, since you need to pull out your debit card for two factor authentication – defeating the point of UPI. I’m told it’s better on Android), I realise how much easier and safer the transaction would’ve been.

Firstly, the cook needn’t have sent me his account number. All I would need was his virtual payment address. I would then open my UPI app (in my case, iMobile) and click on “send money”. And then I’d add his virtual ID there, following which his name would appear. Two or three more clicks, and entering my PIN code, the transfer would be done.

No bank account number. Not even a mobile number or an email ID. Just a random string of characters would allow me to transfer money to him! And later I could give him my UPI ID, and next month onwards he could simply send me a request via UPI for his salary. And two clicks later it would be done!

Mint has reported that there are massive delays in merchants installing point of sale devices in response to the cash ban. Banks should instead seek to acquire merchants to accept money via UPI. It’s simple, it’s quick and it protects privacy.

In fact, if the bank sales staff now have bandwidth, it can be argued that all the planets have aligned for UPI to take off for merchant payments – people have less cash, point of sale devices are not available, and both merchants and shoppers have shown openness to cashless payments, and there is a push from the government.

If only the banks can bite…

Why PayTM is winning the payments “battle” in India

For the last one year or so, ever since I started using IMPS at scale, and read up the UPI protocol, I’ve been bullish about Indian banks winning the so-called “payments battle”. If and when the adoption of electronic payments in India takes off, I’ve been expecting banks to cash in ahead of the “prepaid payments instruments” operators.

The events of the last one week, however, have made me revise this prediction. While the disruption of the cash economy by withdrawal of 85% of all notes in circulation has no doubt given a major boost to the electronic payments industry, only some are in a position to do anything about this.

The major problem for banks in the last one week has been that they’ve been tasked with the unenviable task of exchanging the now invalid currency, taking deposits and issuing new currency. With stringent know-your-customer (KYC) norms, the process hasn’t been an easy one, and banks have been working overtime (along with customers working overtime standing in line) to make sure hard currency is in the market again.

While by all accounts banks have been undertaking this task rather well, the problem has been that they’ve had little bandwidth to do anything else. This was a wonderful opportunity for banks, for example, to acquire small merchants to accept payments using UPI. It was an opportune time to push the adoption of credit card payment terminals to merchants who so far didn’t possess them. Banks could’ve also used the opportunity to open savings accounts for the hitherto unbanked, so they had a place to park their cash.

As it stands, the demands of cash management have been so overwhelming that the above are literally last priorities for the bank. Leave alone expand their networks, banks are even unable to service the existing point of sale machines on their network, as one distraught shopkeeper mentioned to me on Saturday.

This is where the opportunity for the likes of PayTM lies. Freed of the responsibilities of branch banking and currency exchange, they’ve been far better placed to acquire customers and merchants and improve their volume of sales. Of course, their big problem is that they’re not interoperable – I can’t pay using Mobikwik wallet to a merchant who can accept using PayTM. Nevertheless, they’ve had the sales and operational bandwidth to press on with their network expansion, and by the time the banks can get back to focussing on this, it might be too late.

And among the Prepaid Payment Instrument (PPI) operators again, PayTM is better poised to exploit the opportunity than its peers, mainly thanks to recall. Thanks to the Uber deal, they have a foothold in the premium market unlike the likes of Freecharge which are only in the low-end mobile recharge market. And PayTM has also had cash to burn to create recall – with deals such as sponsorship of Indian cricket matches.

It’s no surprise that soon after the announcement of withdrawal of large currency was made, PayTM took out full page ads in all major newspapers. They correctly guessed that this was an opportunity they could not afford to miss.

PS: PayTM has a payments bank license, so once they start those operations, they’ll become interoperable with the banking system, with IMPS and UPI and all that.

Moving towards a cashless economy

In any transaction, the process of payment is a pain. It is a necessary step, of course, in that payment is what completes the transaction, but the process of payment is not something that adds any value to the transaction. If money could be magically be transferred from buyer to seller at the end of a transaction, both transacting parties would be happy.

In this context, any chosen method of payment, be it cash or credit card or cheque or bank transfer, involves some degree of pain for the transacting parties.

In case of cash, there’s the problem of counting out the money, cross checking it, finding exact change, being able to handle currency without the fear of being robbed, and making sure the currency is not counterfeit. Cheques have a credit risk, since they can bounce, not to speak of the time it takes to write one, and the time it takes for the money to get transferred.

Bank transfer requires parties to have bank accounts, and the ability of transacting parties to tell each other their account details. Credit cards have the most explicit pain of transaction – the transaction fees the merchants need to pay the acquiring bank – apart from the time and pain of swiping, entering the PIN, etc.

The reason India has so far been a primarily cash economy is that the pain of transacting through cash has been far lower than the pain through other means. Apart from the pains mentioned above, cash also has the advantage of anonymity, speed of transaction and ability to hide from the tax authorities.

So if we have to turn India closer to a cashless economy, as the current union government plans to do, we need to either increase the pain of transacting in cash, or reduce the pain of transacting through another means. The Unified Payments Interface (UPI), which was launched with much fanfare earlier this year but has spectacularly failed to take off, seeks to reduce pain of cashless transactions. The government’s efforts to get people open bank accounts through the Pradhan Mantri Jan Dhan Yojana (PMJDY) also seeks to reduce pain in non-cash transactions.

The government’s recent effort to withdraw legal tender of Rs. 500 and Rs. 1000 notes, on the other hand, seeks to increase the cost of transacting in cash – 85% of the current stock of cash in India needs to get banked in the next 50 days. This, however, is not a repeatable exercise – it can simply remove confidence in the rupee and drive people to alternate (formal or informal) currencies.

So what can be done to move India to a more cashless economy? The problem with small change has already played its part, with most auto rickshaw and taxi drivers in Mumbai supposedly willing to accept payment in digital wallets such as PayTM. If the stock for the new Rs. 2000 and Rs. 500 notes released is low, and most people have to transact using Rs. 100 notes, that will again increase the pain of transacting in cash, since the cost of handling cash might go up.

Perversely, if crime and robberies increase, that will again make people wary of handling cash. In fact, as this excellent piece in the New Yorker claims, the reason Sweden has moved largely cashless is that people got scared of handling cash after a series of cash robberies a few years ago. The cost of higher crime, however, means this is not a desirable way to go cashless.

It’s been barely three days since the new Rs. 500 and Rs. 2000 notes have been released, and there are already reports of counterfeiting in these notes. Given the framework I’ve proposed in this blogpost, it is not inconceivable that these rumours have been planted – when people become more wary of receiving large currency (thanks to the fear of counterfeiting), they want to reduce the use of such physical currency.

It’s perverse, I know, but nothing can be ruled out! As I’ve repeatedly pointed out, increased use of cash has a fiscal cost (in terms of printing and maintaining currency, apart from people not paying taxes), so the government has an incentive to stamp it out.

 

 

Dealing with loss of cash

Ever since Rs. 500 and Rs. 1000 notes ceased to be legal tender on Tuesday night, the internet has been full of “human stories” of people for whom tragedy has struck because they are not able to transact.

This is a valid concern – for there is a significant portion of the population without access to banking (numbers in a Mint piece I’ve sent but they’re yet to publish), and access to banking is necessary to do any transaction of reasonable size (there’s only so much you can pay with 100 buck notes).

One fallacy, though, is that people in rural areas, where access to banks and ATMs is lower compared to urban areas, are going to have it harder till the cash gets adequately replaced. While these places may be out of the way, what will help them tide it over is that everyone pretty much knows everyone else.

In Money: The Unauthorised Biography, Felix Martin argues that money is neither a store of value nor a medium of exchange. Instead, it is simply a method to keep track of debts, with the elegance being offered by the fact that money is “negotiable”. If I have a 100 rupee note, all it says is I’m owed 100 rupees. Who owes me those 100 rupees doesn’t matter. “I promise to pay the bearer the sum of one hundred rupees”, the front of the note declares. It just doesn’t matter who the “I” in question is.

In order to illustrate his theory of money, Martin gives the example of Ireland around 1970, when a six-month banking strike left the country’s financial system in tatters. Life didn’t come to a standstill, though, as people figured out ways of maintaining their credits and transferring them.

Initially, people wrote each other cheques. Despite the inherent credit risk, and the fact that they couldn’t be encashed in near future, people accepted them from people they knew. Then the cheques became negotiable, after “reputed community people” such as barmen started vouching for people’s creditworthiness. And so the economy moved along.

Debts were finally settled many months later when the banking system reopened, and people could cash in the cheques they held. A similar story played out in Argentina in the early 2000s when rampant inflation had rendered the currency useless – cities managed to invent their own currencies and life went on.

In a similar fashion, in small towns, and other communities where most people tend to know one another, people are unlikely to face that much trouble because of the cash crunch. Credit is already fairly common in such places, except that it will have to be extended for a longer period of time until the cash supply returns. It is similar in other remote unbanked areas, and perhaps even among tightly-knit communities of businessmen. Systems will spontaneously come up to extend and exchange credit, and life will go on.

The concern, however, is for the urban poor, since they tend to do a large number of transactions with people they don’t know well. In such situations, extension of credit is impossible, and people might find it hard.

Reasons for voting

A vote is fundamentally a blunt instrument. Each voter has exactly one vote, and this one vote needs to express the voter’s opinion on a large range of issues.

Since you are extremely unlikely to have a unique candidate for every combination of issues, a voter can’t have it all. He must be prepared to compromise on certain issues, in order to get his way on certain other issues.

This is where the voter’s preferences and objectives matter. In the longlist of issues, certain issues matter more to certain people than certain other issues. And voters usually put a “don’t care condition” on their less important issues, so that they can get their way on the more important ones.

So some voters might be okay voting in a racist if he promises to bring them jobs. Other voters might be okay to “sacrifice” cow protection because they believe the reduction in corruption is more important. Some others might be willing to throw minority citizens under the bus if that implies stronger labour protection. And so forth.

If a racist has won the election, it doesn’t mean that all those who voted for him are racist – there are surely racists among his supporter base, but many others voted for him simply because racism is not something they care that deeply about. Similarly, if a religious bigot has won, it doesn’t mean everyone who voted for him was a bigot – all it means is that bigotry was a less important issue for many of these voters.

The problem with a lot of the mainstream media and “commentariat” (in different countries) is that they somehow assume that all voters need to have the same set of preferences and priorities as them. And when that doesn’t happen, and results go against them, they start questioning the morals of their voters. An appreciation of diversity (that different people have different priorities) can help in this matter – assuming that everyone ought to have the same priorities is illiberal.

In this regard, an understanding of what voters’ priorities are is an important tool to frame campaign strategy, which can help politicians determine what areas of their manifestoes to lay more focus on. I had done this kind of an analysis prior to the Maharashtra elections two years ago, for example (based on a painstakingly elaborate survey by Daksh and the Association for Democratic Reforms).

I had taken pairs of communities, and compared them in terms of the order in which they ranked different key issues. The survey I based this on hadn’t asked for the respondents’ views on who they were voting for (that wasn’t the purpose of the survey), if we were to do this kind of preference ranking of voters of different parties, it will soon become evident why the election turned in a certain way.

Finally, the result of an election is usually a result of the issues that were on top of most voters’ priorities. The same parties with the same manifestoes across elections can lead to widely different results, only because the voters’ preferences have changed! It’s time for politicians and the media to chew on that.

Financial Inclusion

Matt Levine had a superb newsletter recently on whether asset managers and pension funds who push customers towards buying high-cost retirement savings plans are doing a good thing or a bad thing. As Levine expertly explained, it all depends upon the context.

 Is bad retirement advice worse than no retirement advice? Like here is a simple hierarchy of things you could do to save for retirement, from best to worst:

  1. Save for retirement in an efficient portfolio of index funds with very low fees.
  2. Save for retirement in a mediocre product with very high fees.
  3. Not save for retirement.

So if some slick-talking hustler shows up at your place of employment and talks you into option 2, has he done you a favor, or done you harm? The answer depends on what you would have done if he hadn’t shown up. If you were on your way to Vanguard to buy index funds when he waylaid you, he has moved you from option 1 to option 2, and made you poorer in retirement. If you were on your way to blow your paycheck on lattes at Starbucks, he has moved you from option 3 to option 2, and made you richer in retirement. The context is key.

Earlier today, I was at a post office, trying to cash a National Savings Certificate that my parents had somehow bullied me into investing in, and was reminded of how inefficient post offices are. For a long time, India Post has allowed people to maintain deposits, in so-called “savings accounts” (though India Post is itself not a bank).

And as I’ve experienced while trying to operate such accounts on behalf of sundry relatives, it’s incredibly inefficient. Lines are long. Post offices are understaffed, and staff mostly overworked. Computerisation is minimal – while finally they have a way to print out pass books, it still lags significantly behind even nationalised banks. Things we take for granted at most banks – such as ATM cards – are absent. You need to line up to take your cash out.

The reason I’m describing this is that the “Post Office Savings Bank” has recently received a license to formalise its banking, to become a so-called “payment bank“. The “bank” won’t be able to lend, but can facilitate payments and movement of money. The amount of money in the savings accounts is capped at Rs. 1 Lakh.

The intention behind the license is sound – India Post has a network that goes into all sorts of nooks and corners of the country, and now people in those nooks and corners can have a bank account, and send money to each other! Which is a wonderful thing.

But then, India Post is a really large and slow-moving operations, so it’s unlikely that they’ll adapt much towards modern ways of banking after they become a proper (small) bank. So the customers they’ve “financially included” will need to wait in line to put or get out money, perhaps fill forms in order to be able to transfer funds, and face other inconveniences to be able to “bank”. So is the financial inclusion worth it?

To paraphrase Levine, it all depends on the context. To continue paraphrasing Levine, if India Post Payments Bank (as it will be called) were to waylay a customer who was on his way to opening a PayTM account, it has done a disservice, by replacing an easy-to-use electronic account with one where he will have to face lines, which might dissuade him from banking altogether.

If on the other hand IPPB were to waylay a customer who was on his way to the post office (!) to send a money order to a relative, they are actually doing him a service, providing him a more efficient method for transferring funds.

It all depends upon the context.

When is a war a war?

War is an inherently political instrument used to achieve a political objective, so a credible political adversary is necessary for war to be war.

As the US Presidential election race hots up (or gets more one-sided, depending upon your interpretation), people continue to refer to former President George W Bush leading the US into two “wars” in Iraq and Afghanistan. Thinking about it, I’m not sure the two can actually be classified as wars.

To use a chess analogy, real wars seldom end in checkmate – they most often end in resignation, or an agreed draw. War is an instrument that is used to achieve a political objective, to get the other party to do what you want them to do.

And so war ends when one side has established such an utter dominance over the other that the counterparty decides that to resign, or “surrender” is superior to continuing fighting the war.

For this to happen, however, the counterparty needs to have a political leadership that is able and willing to take a decision, following which the war actually stops. In the absence of such a political leadership, the war will continue indefinitely until “checkmate”, and assuming that the losing side’s force “decays exponentially”, it can take a really long time for it to actually get over.

So based on this definition that war is a political instrument used to achieve a political objective, I’m not sure what happened in Iraq and Afghanistan can actually be classified as “war”.

The “government” of the day in Afghanistan (Taliban), for example, would have never come to the negotiating table with the US, so short of complete annihilation, there was no other “objective” that the US could achieve there.

Iraq, on the other hand, possessed credible political leadership (Saddam Hussein) when the US invaded, but by actually killing him, the US denied themselves the chance of a “real victory” in terms of a negotiated settlement. A game of chess might end when the king is mated (remember that the king never “dies”, only trapped), but in a situation such as Iraq, the battle will rage until each member of the opposing force is taken out.

And so fighting continues to this day, over a decade since it started, with no hope of it ending in the near future. Real wars never go on indefinitely.

The real benefit of direct benefit transfer

A week ago, I gave up. My LPG subsidy that is.

Having been out of the country for a few months, with our normal LPG usage being much lower than the average family’s, and having forgotten to book my spare cylinder, my LPG account had been “suspended”, for not booking a refill for over six months.

Back in the day when all domestic LPG connections were subsidised, you were required to book a cylinder every six months, else your account would get suspended. This was a measure to get rid of fake accounts and duplicate connections owned by a family (a family could have only one connection, legally).

So when I went to my dealer last week asking for my account to be unsuspended, I was told to submit my Aadhaar number to get it released. When I said I don’t have an Aadhaar number (I have one, but don’t want to use it unless mandatory), the clerk asked if I could give up my subsidy. With the LPG subsidy being a minuscule part of my overall annual expense, I quickly agreed, and after filling up a form and submitting a copy of my driving license, I had “given up”.

Later that day, my account was unsuspended, and I could presently book a refill, which arrived today. And having “given up”, there is no compulsion now to book a cylinder every six months!

The real benefit of the direct benefit transfer scheme adopted by the union government for LPG subsidy transfer is that it is now possible to have two classes of LPG connections, with several benefits.

Firstly, rules such as minimum and maximum frequency of booking don’t apply any more. Secondly, and more importantly, it is far easier nowadays to get an LPG connection – someone I know went to a nearby dealer to get a connection, and after submitting basic identification documents and paying a deposit, it took only a couple of days for the cylinders to arrive.

You might recall a campaign in the late 2000s by the then Karnataka Energy Minister Shobha Karandlaje to weed out duplicate LPG accounts in order to prevent wasteful subsidy. That brought in a regime of submitting a copy of an electricity bill to get LPG connections, in order to prevent one household from having more than one connection. Consequently, getting a new LPG connection became an absolute nightmare.

With the benefits now being targeted, and Aadhaar based, getting a new LPG connection is mostly straightforward, as long as you don’t claim a subsidy. And a lot of the times, the value of the subsidy is far lower than the additional cost of getting the cylinder itself!

In the earlier “indirect transfer regime”, this class of unsubsidided LPG connection did not exist (unless you went with one of the private sector players, most of whom have remained undependable), causing much harassment to consumers, and the need for various workarounds.

The direct benefit regime has thus not only saved the government the cost of wasteful subsidies, but also made life easier for consumers by making the market more rational!

Aswath Damodaran, Uber’s Valuation and Ratchets

The last time I’d written about Aswath Damodaran’s comments on Uber’s valuation, it was regarding his “fight” with Uber investor Bill Gurley, and whether his valuation was actually newsworthy.

Now, his latest valuation of Uber, which he concludes is worth about USD 28 Billion, has once again caught the attention of mainstream media, with Mint writing an editorial about it (Disclosure: I write regularly for Mint).

I continue to maintain that Damodaran’s latest valuation is also an academic exercise, and the first rule of valuation is that “valuation is always wrong”, and that we should ignore it.

However, in the context of my recent piece on investor protection clauses in venture investments (mainly ratchets), it is useful to look at Damodaran’s valuation of Uber, and how it compares to Uber’s valuation if we were to account for investor protection clauses.

“True value” of Indian unicorns after accounting for investor protection. Source: Mint

When Uber raised $3.5 Billion from Saudi Arabia’s Public Investment Fund earlier this year, the headline valuation number was $62.5 Billion. Given the late stage of investment, it is unlikely that the investor would have done so without sufficient downside protection – at the very least, they would want a “full ratchet” (if the next investment happens at a lower valuation, then they get additional shares to compensate for their loss). This is a conservative assumption since late stage (“pre-IPO”) investments usually have clauses more friendly to the investor, usually incorporating a minimum “guaranteed return”.

Plugging these numbers into the model I’ve built (pre-money valuation of $59 Billion and post-money valuation of $62.5 billion), the valuation of the put option written by existing investors in favour of Uber comes to around $1.28 Billion. Accounting for this option, the total value of the company comes out to $39.6 Billion.

Damodaran’s valuation, based on his views, principles and numbers, is $28 Billion. Assuming that investors and management of Uber are aware of the downside protection clauses and its impact on the company’s valuation, Damodaran’s valuation is not that much of a discount on Uber’s true valuation!