Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")
One approach is to view this as an instance of the assignment problem: you have a bipartite graph, with items on the left and positions on the right, and $f_i(p)$ tells you the value of matching item $i$ to position $p$, so draw an edge $i \to p$ with weight $f_i(p)$, and then find the maximum-weight bipartite matching.  This will give an optimal solution.  It also demonstrates that the problem can be solved in polynomial time, i.e., it is not NP-hard.  The running time will be $O(n^3)$, which might be reasonable if $n$ is not too large but might be too expensive if $n$ is very large.
It might be possible to find some other algorithm that is more efficient (i.e., has faster runtime), by taking advantage of the fact that each $f_i$ is monotonically decreasing.