I was recently called the devil [read: open-minded] for considering the merits of lust. I was called naïve [read: disciplined] for believing I should invest now for a promise tomorrow. So, let's examine the merits of lust and naïvety.
What do I do now?One way to decide on an action is to ask whether you in the future will approve or even applaud the decision.
Objective Function: Max E [x] ; Evaluation: Your future self
Some decisions can really change the way your future self thinks. For example, a drug will change the way you perceive drugs. Becoming religious might change the way you see religion. So barring those
reflexive decisions, the future-self-metric yields some consistently desirable results. After all, you are always looking back to decide if you acted correctly. So, yay! right? Well, not exactly. You can't always analyze if you are trying to act and there may be some good opportunities in the 'heat of the moment.'
LustOne way is to think only in the present. Why? You could choose not to trust tomorrow because the future is uncertain, because analyzing takes too much time, or because ‘that cheesecake looks sooo good.’ This blog post is devoted to the greedy algorithm, hungry people, and in general to the beautiful irresponsibility of brain myopia.
Greedy Algorithm – (minus) Algorithm ≠ GreedGreedy algorithm is an algorithm that isn't really greedy. An algorithm is a step-by-step process to find a solution. Greed, in the popular lexicon, is the excessive self-interest that tramples other people’s needs. A greedy algorithm, however, is one that ‘gobbles up its favorites first.’ Another way to say the same thing would be, a greedy algorithm is a step by step process that looks at only the payoff from the next step. After all, there might not be a better way to get up the stairs than one at a time. Greedy algorithms seek to maximize instantaneous momentum rather than consider the position it is in once that step is taken. Think about it: position depends on the choices at the next step and those choices depend on the position thereafter, and so on. Greed is a lot less complicated. Greedy algorithms don’t go to college; they don't invest. But don’t feel bad learning all the good things about greedy algorithms. After all, the greedy algorithm is just myopically self-interested, not greedy. This is similar to elitism in that elitism seeks out those who are likely to know (considered experts). Elitism may not reach all the right people, but it might yield a relatively good conversation quickly. That might even be why you subscribe to this blog. : ) <- a lusty smile
Speed[Get to the trading already!] Most trading opportunities happen fast and last a short time. In finance, we are taught that it is the present value of all cash flows out to time t-approaches-infinity that should determine which step has the highest value. Two questions arise from this approach:
1)
How can you be sure that your opportunity will last until tomorrow? Though tomorrow, not today, may be when you have determined this next step is optimally taken, you may not be able to count on tomorrow. In finance and in competition, often you have to be faster than tomorrow. Greedy algorithms may not have gone to college, but they know that you better get yours while the getting is good. That is, short-sightedly, they don’t consider that Lehman Brothers has been around 158 years.
2)
How can you be sure that spending time making decisions is going to be worth effort? Though a better solution may exist, it may be too costly to find that solution. Said again, the cost of analysis may be higher than the marginal return on the choice between methods.
Getting to the good stuff, what are greedy algorithms good at?1) Speed sensitive problems like
competitive markets
2) Promoting natural talent. Rather than cultivate a new skill, you could just focus on what you do well.
3) Acting predictably – coming up with solutions easily verified
4) Not assuming anything about position [tomorrow’s opportunities]
Here are some examples of problems to which greedy algorithms may yield the best solution:
1. ‘
Egyptian Fractions’
Each fraction can be expressed as a sum of different fractions with unit numerators. Fibonacci proved that this greedy algorithm is guaranteed to halt.
2. ‘Voting Districts’
Given an integer number N, and a map in which each region is assigned an integer number (= population size), the problem asks to create N district with minimal deviation of population. The regions in each district must be connected.
A greedy algorithm can start by choosing the N biggest regions as cores of the different districts. Then, in each iteration, the largest unassigned region, among those that are adjacent to assigned regions, is assigned to the district with the smallest population.
3. ‘
0/1 Knapsack’
Some good news about Optiver RecruitingLast week, I was at the recruiting booth at MIT. One question that came up was how many people we are willing to take to trade. In a no bullshit sense, we have no cap. Taking on every opportunity with a positive
NPV maximizes firm value. You can apply at
optiverBlog PostingHow can I share with you if you do not share with me? You can request blog topics (and even recruitment advice) at igor (dot) schmertzler@gmail.com