Differential Equations Challenge - How Much Can a Nation Save

Problem Statement

Prize Distribution

• 1st - $2000
• 2nd - $1250
• 3rd - $750
• 4th - $500
• 5th - $400
• 6th - $300
• 7th - $200
• 8th - $100
• Total - $5500

Additional Opportunity ($1200 + Co-Authoring)

Up to an additional (12) $100 awards will be awarded to the 12 best write-ups that competitors (winners and non-winners) submit to describe their approach used. These methods will be evaluated by a panel of experts from MIT and Crowd Innovation Laboratory at Harvard University. The main evaluation criteria are validity, flexibility, performance and originality. The competitors having developed the best approach, as judged by Harvard and MIT, will not only have a chance to win an extra $100 per person but may also be invited as co-authors to write a research paper featuring the results of the challenge. Note that winners are required to write a description of the approach used to be awarded any of the prizes (see the "Requirements To Win A Prize" section below).

Background

This challenge is the warm-up for what will be a larger match later in the year.

How much of its income should a nation save? To tackle this problem, economists traditionally use mathematical models focused on the decisions of a representative agent living for T periods. At each period, the agent chooses how much to consume and save while facing uncertainty about future income. The agent's overall well-being is measured by a utility function that is increasing in consumption and the utility of future consumption is discounted by a factor β < 1. The agent gets an income that can be either consumed or invested into capital K_t+1. The returns on this investment are uncertain and will generate the agent's income in the next period.

In this challenge, your task is to develop an algorithm that dictates how much the agent should consume and save at each period in order to maximize his or her expected well-being. This task can be thought of as if you were the main adviser of a policy maker that is deciding about the optimal level of investments of a country in order to maximize the national welfare.

Objective

You have to make a series of decisions about consumption C_t and invested capital K_t+1 to solve the following maximization problem.

The operator E_t is the expectation with respect to consumption at a given time t. Your preferences towards consumption in a given period are characterized by the following utility function.

You'd rather prefer to consume a given quantity today than tomorrow. That is, utility in future periods is discounted by a discounting factor 0 < β < 1. The sum of consumption and invested capital must be less than or equal to the wage W_t which is determined by:

where 0 ≤ δ < 1 is the depreciation rate of capital, 0 < α < 1 is the productivity of capital and Z_t is the realization of an exogenous random variable distributed as follows.

where 0 < ρ < 1 is the degree of correlation with past shocks and ε_t is a normal random variable with zero mean and standard deviation σ. Initial conditions K₀ > 0 and Z₀ > 0 are given.

To solve the problem, you have to develop a decision rule for consumption which delivers the optimal choice of consumption C_t as a function of the level of capital K_t, the realized shock Z_t, and the parameters of the economy that satisfies the following optimality conditions.

Analytical decision rules that satisfy these optimality conditions are not known. Researchers typically turn to numerical methods to find approximate solutions. For example, a standard procedure is based upon a Taylor's series expansion of the decision rule when shocks are deterministic. The effectiveness of many of these algorithms is discussed by Taylor and Uhlig (1990). You are encouraged to implement one of such methods or come up with a new one.

Functions

Your task is to develop two functions: SetEconomyParameters and ConsumptionDecisionRule. SetEconomyParameters will be called once at the beginning of each test case. ConsumptionDecisionRule will be called iteratively T times for each test case (for times t = 0 to t = T-1) with each call considering N concurrent simulations.

SetEconomyParameters recieves the following arguments:

• β (beta) - Future utility discount factor
• η (eta) - Consumption utility parameter
• α (alpha) - Productivity of capital
• δ (delta) - Depreciation rate of capital
• ρ (rho) - Degree of correlation with previous shocks
• σ (sigma) - Standard deviation of ε_t
• N - Number of concurrent simulations
• T - Total number of time periods

ConsumptionDecisionRule recieves the following arguments:

• K_t - Invested capital at current time for each of the N concurrent simulations
• Z_t - Shock at current time for each of the N concurrent simulations

ConsumptionDecisionRule must return the consumption for this time period for each of the N concurrent simulations. Consumption at each time period for each simulation must be real, non-negative, and not greater than the current wage.

Data Sets

Test cases are defined by a specific configuration of the economy's parameters, the time horizon T, and the number of simulations N. Test cases have been randomly split into three sets: example, provisional, and system. The example set contains 800 test cases can be downloaded here. The provisional set contains 400 test cases and is used for scoring during the contest. The system set contains 800 test cases and is used for final testing resulting in your final score and placement.

Scoring

For each test case, the method ConsumptionDecisionRule is called iteratively for each time t from t = 0 to t = T-1.

• Each test case has N simulations of the shocks and each simulation runs for T periods.
• In each iteration t < T of a simulation i, the evaluation program computes the wage W_t of the period, given the realized variable ε_t and the initial conditions Z_t-1 and K_t. Using your implemented decision rule, a consumption C_t is computed. This step also gives the capital in the next period K_t+1, given the budget constraint. All values are then saved and used as initial conditions for the next iteration.
• At the last iteration t = T of a simulation, we do not request a decision for the last period but make an arbitrary choice to consume the entire capital.

• At this point, it computes (the deterministic version of) the Euler conditions residuals in each period where i is the index of the current simulation:

  

  This value is then averaged as follows.

  

  Where

  

Your score for each test case is the averaged Euler conditions residuals over all N simulations multiplied by 1,000,000. Scores over each test case in a set of test cases (example, provisional, or system) are averaged to find your final score.

Tools

An offline tester is available. You can use it to test/debug your solution locally. This program requires as input a set of test cases like the example data provided here.

You are encouraged to check the source code for exact implementation of the simulation and score calculation. Feel free to use the simulator code in your solution.

Limits

• Each test case must complete within 120s
• The memory limit is 2048 megabytes.
• There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). The compilation time limit is 30 seconds.
• You will be allowed to make example submissions every 30 minutes and provisional submissions every 3 hours.

MATLAB Support!

Free MATLAB! Mathworks has very kindly agreed to support this challenge by granting access to MATLAB for competitors! Competitors can click here to request software from MATLAB. License periods are 30 days. Here is the link to the trial instructions.

IMPORTANT NOTE: MATLAB solutions cannot be submitted in the marathon platform but can be submitted in our simultaneously running "MATLAB only" contest here which will run in parallel alongside this marathon contest. The scores of the submissions to the "MATLAB only" contest will be manually inserted into the marathon leaderboard of this contest periodically. These MATLAB submissions will qualify for the prizes in this contest.

General Notes

• This match is not rated.
• The allowed programming languages are C++, Java, C#, Python, VB, and MATLAB!
• You can include open source code in your submission, provided it is free for you to use and would be for the client as well. Code from open source libraries under the Apache2, BSD or MIT licenses will be accepted. Other open source licenses may be accepted too, just be sure to ask us first.
• The test servers have only the default installs of all languages, so no additional libraries will be available.
• Use the match forum to ask general questions or report problems, but please do not post comments and questions that reveal information about the problem itself or possible solution techniques.

Requirements to Win a Prize

In order to receive a prize, you must do all the following:

1. Achieve a score in the top 8 according to system test results (see the Scoring section above).
2. Within 7 days from the announcement of the challenge winners, complete a full description of your approach through an online survey. Topcoder will send qualifying contestants a URL to the survey that should be completed.

Your report must be at least 2 pages long, contain at least the following sections, and use the section and bullet names below.

Your Information

This section must contain at least the following:

• First name
• Last name
• Topcoder handle
• Email address

Approach Used

Please describe your algorithm so that we know what you did even before seeing your code. Use line references to refer to specific portions of your code.

This section must contain at least the following:

• Approaches considered
• Approach ultimately chosen
• Steps to approach ultimately chosen, including references to specific lines of your code
• Open source resources and tools used, including URLs and references to specific lines of your code
• Advantages and disadvantages of the approach chosen
• Comments on libraries
• Comments on open source resources used
• Special guidance given to algorithm based on training
• Potential improvements to your algorithm

Definition

Examples