Showing posts with label Delay. Show all posts
Showing posts with label Delay. Show all posts

Saturday, August 30, 2014

The Best Decisions are Optimally Delayed

The lessons learned from the last few years of practice have convinced me that analytics and OR (OR = Operations Research), or at least MyOR is mainly about learning the art and science of engineering an optimally delayed response. Good analytics produces an optimally delayed response.

But why introduce a delay in the first place? Isn't faster always better? 'Science of better' does not always mean 'science of faster'. From age-old proverbs we find that in between 'haste makes waste or knee-jerk reaction' and being 'too clever by half' lies 'look before you leap'. If we view Einstein from an OR perspective: "Make things as simple as possible, but not simpler", the reason seems clearer. We must make situation-aware and contextually-optimal decisions as fast as possible, or as slow as necessary, but not faster, or slower, i.e., there exists a nonzero optimal delay for every response decision. A middle path in between a quick-and-shallow suboptimal answer, or a slow-and-unwieldy 'over-optimized' recipe. Of course, one must work hard during this delay to maximize the impact of the response, and put Parkinson's law to good use, as suggested below:
See this old post on 'optimally delaying an apology' to maximize benefit to the recipient, or recall the best players of every sport being able to delay their response by those few milliseconds to produce moments of magic, or Gen. Eisenhower delaying the call to launch D-Day. In the same way, a good OR/analytics practitioner will instinctively seek an optimal delay. For an example of this idea within an industrial setting, read this excellent article by IBM Distinguished Engineer J. F. Puget on taxicab dispatching that he shared in response to the above tweet. Implication: If your analytics system is responding faster than necessary, then slow it down a bit to identify smarter decision options. The 'slower' version of this statement is more obvious and is a widely used elevator pitch to sell high-performance analytics and optimization tools.

The history of the 'optimal delay' is many thousand years old, going back to the writing of the world's longest dharmic poem, the Mahabharata, which also includes within it, the Bhagavad Gita, one of the many sacred texts of Hinduism.

(pic link: http://www.indianetzone.com)

The story about how this epic came to be written is as follows:
Krishna Dvaipana (the Veda Vyasa) wanted a fast but error-free encoding of the epic that could be told and re-told to generations thereafter. The only feasible candidate for this task was the elephant-faced and much beloved Ganesha, the Indian god of wisdom and knowledge, and remover of obstacles. The clever Ganesha agreed to be the amanuensis for this massive project on the condition that he must never be delayed by the narrator, and must be able to complete the entire epic in ceaseless flow. Veda Vyasa accepted but had his own counter-condition: Ganesha should first grasp the meaning of what he was writing down. This resulted in a brilliant equilibrium.

Veda Vyasa composed the Mahabharata in beautiful, often dense verse that Ganesha had to decipher and comprehend even as he was writing it down without lifting the piece of his tusk that he had broken off to inscribe, from the palm leaves. If Ganesha was too slow, it would potentially give Vyasa the opportunity to increase the density and frequency of incoming verses that may overload even his divine cognitive rate. If he went too fast, he would risk violating Vyasa's constraint. Similarly, if Vyasa was too slow, he would violate Ganesha's constraint. If he went too fast, his verse would lose density and risk becoming error-prone, and of course, then Ganesha would not have to think much and perhaps write it down even faster. Imagine if you will, a Poisson arrival of verses from Vyasa divinely balanced by the exponentially distributed comprehension times of Ganesha. Writer and composer optimally delayed each other to produce the greatest integral epic filled with wisdom ever known; written ceaselessly in spell-binding Sanskrit verse, without error, and flowing ceaselessly to this day without pause.

I can think of no better way to celebrate Ganesha Chathurthi than to recall and apply this lesson in everyday life.

Friday, November 8, 2013

Optimizing Kindle Book Rentals

When to buy at Amazon
Amazon just raised their 'free shipping' threshold to 35$, a few weeks before the holiday shopping season. This simple 'entropic optimization' approach, which utilizes Amazon's wish list to time-prioritize purchases remains valid, but requires an increased level of procrastination. What also caught my attention is Amazon's Kindle rental models. Beyond the initial sunk costs, virtual products are high margin, with negligible holding cost, besides an infinite, instantaneously replenish-able inventory. They are also scratch/damage proof. The only long-term downside to providing a renting option appears to be faulty pricing. If we price too low, we may turn many potential buyers into renters, and a high price may discourage potential renters. Let's look at a couple of (real) Kindle rentals for which I laboriously pulled data while watching Sachin Tendulkar's 199th cricket test match.

Kindle Book 1 (Undergrad Math textbook)
The minimum rental period is 60 days (50$), and the maximum (apparently) is around 360 days (140$), with the marginal price held approximately constant. We pay 30 cents for every extra rental day beyond the minimum period.

Kindle Book 1: Price Versus Rental Days

The cost (snapshot at the point of observation) of purchasing a permanent copy was 200$. If we plot the percentage price discount versus the rental period expressed as percentage of a year, we can see that the discount varies between 25% and 70% of the full cost. Approximately linear model employed for this book. Here, we can rent the book for an entire year without paying the full price.

Price Discount Percentage versus Rental Percentage-of-Year


Kindle book 2 (Advanced forecast-modeling textbook)
The second example is a bit more interesting. The content is technically far more sophisticated compared to Book 1, but the target market is different, and the number of (paper) pages is far lower, and so is the price. In both instances, the cheapest rental can be purchased at less than half the full price. There are roughly three different marginal prices employed within a rental period that varies between a minimum of 30 days (~$15) and a maximum of 365 days (~$35, also the full Kindle price). The corresponding breakpoints occur (roughly) near the 90-day, and 180-day rentals, respectively. If we restrict our attention to this rental time period, the price is concave, with the marginal prices decreasing as the rental period increases. It is preferable to simply buy the book rather than rent it for close to a year.

Kindle Book 2: Piece-wise linear rental pricing
A percentage based plot is show below, along with an empirical power-law pricing model (using Open Office) that looks like a near-perfect fit for this particular book rental. A log(x) model also works well in this instance.



Optimization Models
Seller: How would optimization scientists go about determining these marginal rental prices? Suggestions welcome. Perhaps ideas from analytical rental models for other products (cars, houses, equipment ...) can be used as a starting point to figure out this "information rental" model. Perhaps the pricing model can be initialized using historical rental data gathered for similar books. This being an online retail sales model, we can dynamically and frequently update these models or their parameters to maximize performance metrics. 

Buyer: From a user-perspective, if we can assign a value for owning a permanent copy, and have an informal mental model of the temporal utility of a rental as T(x), then (for example), we could solve some variation of this single-decision problem in 'x':
Maximize Value V = T(x)/f(x) ( Maximize log T - log f, optionally)
 x  u
to determine an optimal 'rent versus buy versus walk-away' decision based on our willingness-to-pay. Assuming a 1:1 mapping between 'f' and 'x', so we could transform any price range limit into an equivalent (l, u) bound on 'x'.
A simple way to solve this problem is to enumerate the values of V for all rental days using a spreadsheet.

Renting digital textbooks over a semester
Like thousands of Indian immigrants in the U.S, I came on an assistantship, carrying a couple of hundred bucks in my pocket that represented a big chunk of my parent's savings. I actually felt rich when I discovered that the take-home monthly income from my research assistant-ship after tuition fees turned out to be more than what my engineer dad was earning after decades of dedicated service in Nehruvian India. Until I saw the prescribed textbook prices, that is. Buying overpriced books was simply out of the question when the few copies in the library were already taken. There was no Amazon then, and it would've been amazing to have a rental option like this, especially when continued funding is dependent on maintaining good grades.

For example, if we only cared about a textbook for portions of a semester (our total planning horizon), and our total price budget is 'pmax', then we can informally solve a multiple-period version of the above optimization model to come up with a best waiting strategy and rent for one or more time periods ("quiz time") which maximizes our total T(x) and also keeps us within our "knapsack" like price budget for the semester. This policy of "rent as needed" may work well with book rentals having a constant marginal price. On the other hand it may be worthwhile renting fewer times for an optimally longer duration if the price is concave in the length of the rental, as it is in our second instance. 

Monday, May 20, 2013

Solve TRP, Drive Tesla

So the awesome and hyped Tesla Model S is beating Mercedes, BMW, and Audi in sales despite the $70K price tag. One problem is the current lack of charging stations required to recharge over long trips. CNNMoney reports:
"CNNMoney took a Tesla Model S on a test drive from Washington D.C. to Boston. The all-electric car drove 450 miles with two stops to recharge at Tesla's Supercharger stations in Delaware and Connecticut"



A second problem is that unlike conventional gasoline cars that can be refueled very quickly, charging can take a relatively long time, and adds significantly to your total travel time. In the near future, as the number of Teslas increase, the number of charging stations is likely to go up too. However, it will remain a sparse resource for some time. A future Tesla trip from New York to California will require many recharging stops, reminiscent of the old stagecoach problem during the Gold Rush era, which is used to illustrate the principles of Dynamic Programming.

Update: May30, 2013
Popular Mechanics reports:
"...the California-based EV automaker plans to expand its fast-charging "supercharger" network across the continental U.S. During today's announcement, Musk said New York to Los Angeles trips would be viable as soon as this winter. 

"When you get in a car you have the ability to go almost anywhere," Musk said. "That's what the supercharger network will do." 

The rollout will begin as soon as this summer, with the number of stations tripling to 27 nationwide by the end of June. In addition to increasing supercharger density along the already-established California and Mid-Atlantic coasts, Tesla will debut chargers in a handful of new metropolitan areas within the next few weeks, including Austin/Houston, Portland/Seattle, Boulder/Denver, and Chicago/Milwaukee. By the end of the year, Musk expects to to have "a couple hundred" superchargers spread across the U.S. and southern Canada, with as little as 80 to 90 miles between stations along the Altantic and Pacific coasts..."

Tesla Routing Problem
Given a road network G having a limited number of charging stations located at specific nodes, the Tesla Routing Problem (TRP) will have to:
Find the shortest feasible time path from origin O to Destination D in network G.

Feasibility requires the car to visit enough charging stations in a timely manner. Optimality requires that the sequence of visits be carefully selected such that the total time spent is kept to a minimum.

Total travel time = driving time + recharge time

This involves two decisions:
D1. Which recharging stations to visit en-route?
D2. How long to recharge at every pit stop?

Assumptions:
A1. The longer you recharge, the longer your available range (to a limit).
A2. All recharging stations are similar, and infinite capacity (no queuing!)
A3. Range is deterministic

Update on A2: The Tesla can charge on any outlet, but the time to recharge can vary depending on the source.

Clearly, optimally solving TRP involves the finding a solution to a Traveling Salesman Problem even in the special case of instantaneous recharge (Y=0).

(Updated September 2013: As mentioned in the comments, the general case is not a TSP in the network of charging stations. Here, the assumption is that stations are sparsely located and we visit each one along the way. The title is changed to reflect this distinction).

This is no different from the (milder) challenge faced by conventional car drivers in unfamiliar areas where gas stations may be hard to come by (see this old post). Charge cannot be carried in Jerry-cans. The  shortage of charging stations does make every long Tesla trip a non-trivial problem to manage. Tesla owners have to deal with a NP-Hard Optimization Problem (Heh) on every such trip, but in practice, it should not be difficult to find good quality, feasible TRP solutions.

The recharge time makes the TRP a bit more interesting. If two stations are close to each other, we don't have to recharge fully, and just need the minimum to reach the next stop - or perhaps we recharge fully, which allows us to reach a station that is further away but turns out to be more time-effective, overall. Clearly, these two decisions appear to be interlinked and may need to be jointly optimized. D1 is a binary decision variable X(i) - we either visit or don't visit a station at node X(i), whereas D2 is a semi-continuous variable Y(i) conditional on D1:

Y(i)  U.X(i)
where U = maximum recharge time.

Another interesting and maybe even useful problem for Tesla-makers to solve is where to add new charging stations on the network G over time. What is the minimum number and location of stations required to guarantee feasible solutions to any TRP in the 48 states of continental US? How will stations deal with congestion in the future? and so on ...

I haven't driven a Tesla yet but I wouldn't mind relocating my office to inside one and telecommute.

Sunday, January 13, 2013

Being Optimally Sorry: When to Apologize?

A Delayed Apology
This post examines modeling ideas related to the timing of an apology in a two-person scenario that results in a maximally effective 'sorry'. We optimize timing here not to maximize own benefits (user optimal), but on the basis of mutual respect, to express regret and maximally repair the damage in a timely manner that most helps the subject (recipient optimal). We start with the findings in Frank Partnoy's book "Wait: the Art and Science of Delay". It's one of the many useful books in the last couple of years that analyze human decision making. We introduce a mental decision support model for a timely apology that is derived from decision analytical methods employed in an industrial setting.

Objectives and Constraints
Justice delayed may be justice denied, but an apology that is optimally delayed may not be such a bad thing. The 'Wait' book recognizes the existence of a suitable time to apologize, and notes that the fastest apology in not necessarily the most effective. Given that we may have to apologize more than once, in general we have to determine an optimal trajectory of timed apologies. Thus, our goals are to:
i)   apologize at least once,
ii)  in a timely manner, and
iii) within a finite time horizon, such that
iv) a measure of the recipient's benefits is maximized

'Wait' notes:
"... Saying you are sorry is always better than not apologizing at all. But as with the first study, the students felt better about a delayed apology: “Improvement in the late apology condition was significantly greater than improvement in the early apology condition.” In fact, a statistically significant improvement in the students’ reactions occurred only in the late apology condition, when there was a chance for them to discuss what had happened and why. Overall, these studies suggest that the relationship between apologies and timing follows a “bell curve” distribution: effectiveness is low at first, then rises, peaks, and ultimately declines."

(It seems that these ideas are related to the complementary 'problem' of delivering the most time-effective 'Thank You')


We can see that the timing-effectiveness curve described in the book extract above is related to the subject's level of distress/angst (which we represent as 'entropy') that follows a similar trajectory of rise, cruise, and a gradual demise. Depending on the person, the 'cruise' and 'demise' portions can last long and result in a very fat-tailed distribution. But before we get into 'when', a quick comment from the book on the what/why/how questions:
".... effective apologies typically contain four parts: 
1. Acknowledge that you did it. 
2. Explain what happened. 
3. Express remorse. 
4. Repair the damage, as much as you can."

Searching for the Optimal Timing
'Wait' notes:
"The art of the apology centers on the management of delay. For most of us, the lesson is that the next time we do something wrong to a close friend or family member, or say something at work we wish we could take back, we should try to imagine how the victim might react to an apology tomorrow instead of today, or in a few hours instead of right now. If delay will give a friend or relative or coworker a chance to react, to voice a response and prepare themselves to hear our regret, the apology will mean more later than right away."

In other words, the timing has to take into account where the subject is located in their entropic life cycle: is the person likely to be getting angrier by the hour now (positive entropic gradient), or has reached the peak and is calming down (negative entropic gradient). To formulate a model based on these observations, we borrow ideas from a classical inventory management problem analyzed in retail operations research: Markdown Optimization (MDO).

An Optimization Model
MDO is employed to manage an inventory of short-life cycle (SLC) products that are manufactured pre-season, with the (sunk) costs paid up-front. Thus MDO typically focuses on total revenue earned in-season. Analogously, we already messed up in the beginning incurring an irreversible cost, and thereafter it costs relatively little to issue a sincere apology.  Retailers employ a cadence of optimally delayed price cuts to smartly boost the end-of-season demand rate so as to maximize revenue over the remaining life of the product. Like MDO, we eventually have to solve an entropic inventory depletion problem: optimally alter the entropic gradient via one or more carefully timed apologies, which will (ideally) reduce the inventory level to zero within a finite time period.

Disclaimer: The postulated model is not assumed to be the most suitable or even a "correct" one for this problem, but merely a useful starting point. Some brief comments on the modeling elements, next.

a. Life-cycle of the entropy
SLC products (like designer fashion apparel) often have little to no historic data early in the season, and retailers may borrow results for a comparable historical "like-item" to produce an initial prediction and then continually update their sales projection based on in-season demand. Here, we play the role of a 'like-item' and place ourselves in the recipient's shoes to better appreciate the degree of distress caused and the impact it will have on the recipient over time. The entropy level is an uncertain quantity that must be learned, but its 'mean value' is assumed to representable using an approximately concave function like the one shown in the figure below. Note that unlike the MDO case where inventory is always non-increasing, entropic inventory initially increases before gradually decreasing.



b. Elasticity of the entropy with respect to an apology

Elasticity ~ % change in entropy / % change in regret and effort, as perceived by the subject
 
A simple model like the inverse square law that abounds in nature (elasticity = -2) may be a good starting point. Ill-timed and empty-sounding apologies may have zero elasticity and do little to reduce entropic inventory. A careless apology can result in an entropic spike ("adding insult to injury"). On the other hand, an apology that is 'deep and sincere' and well-timed can be expected to have a calming effect.

c. Timings
Optimally timing a single apology requires impeccable timing. On the other hand, randomly distributed, and incessant apologies may not be helpful either. A premature apology (e.g. around an increasing entropic gradient) that kicks the can down the road is a greedy approach that may be counter-productive. Thus, optimally timing multiple apologies can require a degree of coordination between decisions. Today's apologize-or-delay decision will impact the timings of future decisions, so we have to holistically manage the impact on the entropic life-cycle. 

Often, despite our best efforts, the damage can never be fully repaired. Note that our objective function was setup to be indifferent to personal benefits. To paraphrase a profound Indian saying: "You have the right to optimize, but not to the fruits of your actions". Regardless of the outcome, a sincere and optimally timed apology is good Karma.