How to Recursively Formulate a Speed vs Quality Problem
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm studying the trade-off between speed and quality. We need to finish a fixed number of jobs, let's say $n$ jobs. We receive a reward for finishing a job and this reward is decreasing and convex in time. All jobs are the same and share the same reward function. At each job, we can work at a normal rate and get a normal reward; or we can work fast and get a discounted reward, but this allows us to get to the other jobs faster. Our objective is to maximize the total reward for all $n$ jobs. I formulated the problem as follows:
Let the reward function $f(x)$ be decreasing and convex in $x$, $0leq f(x)leq 1$ and $xgeq 0$. When you work normally, it takes you $μ$ units of time to finish a job. When you speed up, it takes you $μ'$ units of time to finish a job. $μ$ and $μ'$ are fixed. Let $g_i(x)$ be the maximum expected reward from job i to job n when you start job $i$ at time $x$, $i∈(1,2,...,n)$. Let the discount in reward when you speed up be $α$, $0<α<1$. For a fixed $alpha$, we can construct $g_i(x)$ recursively as:
beginequationg_i(x)=max (f(x)+g_i+1(x+mu), alpha f(x)+g_i+1(x+mu')) endequation
where $mu>mu'>0$ and $iin(1,2,...,n-1)$.
Whether we should speed up for a job depends on the comparison between the fixed $alpha$ and $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$. We speed up if $alpha$ is greater. I've been trying to understand how $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ changes with respect to $i$ and $x$ without giving $f(x)$ an explicit form. What are some sufficient conditions so that $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ is monotonically increasing or decreasing in $i$ or $x$?
With the current formulation, I find it very difficult to obtain any useful analytical results, is there a better way to formulate this problem?
analysis convex-analysis recursion
asked Aug 15 at 4:22
Eric M.
263
add a comment |Â
up vote
2
down vote
favorite
I'm studying the trade-off between speed and quality. We need to finish a fixed number of jobs, let's say $n$ jobs. We receive a reward for finishing a job and this reward is decreasing and convex in time. All jobs are the same and share the same reward function. At each job, we can work at a normal rate and get a normal reward; or we can work fast and get a discounted reward, but this allows us to get to the other jobs faster. Our objective is to maximize the total reward for all $n$ jobs. I formulated the problem as follows:
Let the reward function $f(x)$ be decreasing and convex in $x$, $0leq f(x)leq 1$ and $xgeq 0$. When you work normally, it takes you $μ$ units of time to finish a job. When you speed up, it takes you $μ'$ units of time to finish a job. $μ$ and $μ'$ are fixed. Let $g_i(x)$ be the maximum expected reward from job i to job n when you start job $i$ at time $x$, $i∈(1,2,...,n)$. Let the discount in reward when you speed up be $α$, $0<α<1$. For a fixed $alpha$, we can construct $g_i(x)$ recursively as:
beginequationg_i(x)=max (f(x)+g_i+1(x+mu), alpha f(x)+g_i+1(x+mu')) endequation
where $mu>mu'>0$ and $iin(1,2,...,n-1)$.
Whether we should speed up for a job depends on the comparison between the fixed $alpha$ and $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$. We speed up if $alpha$ is greater. I've been trying to understand how $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ changes with respect to $i$ and $x$ without giving $f(x)$ an explicit form. What are some sufficient conditions so that $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ is monotonically increasing or decreasing in $i$ or $x$?
With the current formulation, I find it very difficult to obtain any useful analytical results, is there a better way to formulate this problem?
analysis convex-analysis recursion
asked Aug 15 at 4:22
Eric M.
263
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm studying the trade-off between speed and quality. We need to finish a fixed number of jobs, let's say $n$ jobs. We receive a reward for finishing a job and this reward is decreasing and convex in time. All jobs are the same and share the same reward function. At each job, we can work at a normal rate and get a normal reward; or we can work fast and get a discounted reward, but this allows us to get to the other jobs faster. Our objective is to maximize the total reward for all $n$ jobs. I formulated the problem as follows:
Let the reward function $f(x)$ be decreasing and convex in $x$, $0leq f(x)leq 1$ and $xgeq 0$. When you work normally, it takes you $μ$ units of time to finish a job. When you speed up, it takes you $μ'$ units of time to finish a job. $μ$ and $μ'$ are fixed. Let $g_i(x)$ be the maximum expected reward from job i to job n when you start job $i$ at time $x$, $i∈(1,2,...,n)$. Let the discount in reward when you speed up be $α$, $0<α<1$. For a fixed $alpha$, we can construct $g_i(x)$ recursively as:
beginequationg_i(x)=max (f(x)+g_i+1(x+mu), alpha f(x)+g_i+1(x+mu')) endequation
where $mu>mu'>0$ and $iin(1,2,...,n-1)$.
Whether we should speed up for a job depends on the comparison between the fixed $alpha$ and $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$. We speed up if $alpha$ is greater. I've been trying to understand how $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ changes with respect to $i$ and $x$ without giving $f(x)$ an explicit form. What are some sufficient conditions so that $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ is monotonically increasing or decreasing in $i$ or $x$?
With the current formulation, I find it very difficult to obtain any useful analytical results, is there a better way to formulate this problem?
analysis convex-analysis recursion
asked Aug 15 at 4:22
Eric M.
263
I'm studying the trade-off between speed and quality. We need to finish a fixed number of jobs, let's say $n$ jobs. We receive a reward for finishing a job and this reward is decreasing and convex in time. All jobs are the same and share the same reward function. At each job, we can work at a normal rate and get a normal reward; or we can work fast and get a discounted reward, but this allows us to get to the other jobs faster. Our objective is to maximize the total reward for all $n$ jobs. I formulated the problem as follows:
Let the reward function $f(x)$ be decreasing and convex in $x$, $0leq f(x)leq 1$ and $xgeq 0$. When you work normally, it takes you $μ$ units of time to finish a job. When you speed up, it takes you $μ'$ units of time to finish a job. $μ$ and $μ'$ are fixed. Let $g_i(x)$ be the maximum expected reward from job i to job n when you start job $i$ at time $x$, $i∈(1,2,...,n)$. Let the discount in reward when you speed up be $α$, $0<α<1$. For a fixed $alpha$, we can construct $g_i(x)$ recursively as:
beginequationg_i(x)=max (f(x)+g_i+1(x+mu), alpha f(x)+g_i+1(x+mu')) endequation
where $mu>mu'>0$ and $iin(1,2,...,n-1)$.
Whether we should speed up for a job depends on the comparison between the fixed $alpha$ and $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$. We speed up if $alpha$ is greater. I've been trying to understand how $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ changes with respect to $i$ and $x$ without giving $f(x)$ an explicit form. What are some sufficient conditions so that $1-fracg_i+1(x+μ′)−g_i+1(x+μ)f(x)$ is monotonically increasing or decreasing in $i$ or $x$?
With the current formulation, I find it very difficult to obtain any useful analytical results, is there a better way to formulate this problem?
analysis convex-analysis recursion
asked Aug 15 at 4:22
Eric M.
263
edited Aug 15 at 13:46
asked Aug 15 at 4:22
Eric M.
263
asked Aug 15 at 4:22
Eric M.
263
asked Aug 15 at 4:22
Eric M.
263
263
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17
add a comment |Â
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2883185%2fhow-to-recursively-formulate-a-speed-vs-quality-problem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
As written now, there is no overall deadline. Hence, taking the slow route for all $n$ jobs will get you the maximal reward in the (possibly later) end
– Hagen von Eitzen
Aug 15 at 7:54
Would you elaborate a bit? I fail to see how taking the slow route for all jobs brings the maximal reward in the end. For example, when $n=2$, if $alphageq 1-fracf(mu')-f(mu)f(0)$, we are better off taking the quicker route for the first job.
– Eric M.
Aug 15 at 11:17