Algorithm for closest available resource
I would call this problem as closest matching between two equal sets with priority.

Here is an $O(n\log n)$ algorithm, assuming the distance is the 2-dimensional Euclidean distance. It might work with the Manhattan distance as well; however, I have not double checked that.

Build a balanced 2-d tree for all taxis in $O(n\log n)$ time. Attach to each node an inventory number, the number of all points in the rectangle or half plane represented by that node, which can be done in an $O(n)$-time tree traversal.

Now iterate over $P_1, P_2, \cdots, P_n$ in that order. For each person $P$, do the following.


  Find all nearest taxis of $P$, using the inventory number and ignore the unavailable taxis, which takes (amortized) $O(\log n)$ time. Assign the taxi with the lowest index among them to $P$. Mark that taxi as unavailable. Subtract one from the inventory number attached to each node that contain $P$, which takes $O(\log n)$ time.