Is there any gain by adding correlated categorical variables (e.g.: city and neighborhood) in a model? It's a very straightforward question that I've never seen any discussion.
To keep it simple, let's say I have a Linear Regression and I want to predict housing prices. I have a dataset that contains both the city and the neighborhood of a city. Should I keep both? Does that matter? Another similar example could be: if I'm predicting the price of a car, and I have the car name and the brand.
Is my model getting any better when I add both features? Should I keep both? If not, how can I choose which feature should I keep?
 A: Its possible the model may get better, yes.
Cities and neighborhoods are a particularly good example.  The price of homes in Ontario varies quite drastically.  In Toronto, single family dwellings top out around a million dollars on average, where as in my home town they are just about half that.  But anyone who has searched for a home to buy knows that price varies within the city, not just between city and that variation can be used to obtain a more accurate estimate.
These sorts of approaches (neighborhoods within cities, models within brands) are often handled using a mixed effect model.   Let $y_{i, c, n}$ be the price of house $i$ which resides in city $c$ in neighbourhood $n$.  One possible model for the neighbourhood example might be as follows.
$$ \beta_{c} \sim \mathcal{N}(\beta_0, \sigma)$$
$$ \beta_{n} \sim \mathcal{N}(\beta_0 + \beta_c, \sigma_c)$$
$$ y_{i, c, b} \sim \mathcal{N}(\beta_0 + \beta_c + \beta_n, \sigma_n)$$
Here, there is some population level average housing price $\beta_0$.  The city level average housing price varies about $\beta_0$ (here, we idealize the variation between cities as coming from a normal distribution with some variance $\sigma^2_c$).  The neighbourhood level average housing price is again idealized as varying around the city level average housing price, and the individual homes around this mean.
In short, yes it can be useful to keep those variables.  They are correlated (only in so far as Shoreditch can not appear when London is not the city, for example), but they can be used to further explain variation within the larger class.
A: Presumably the neighbourhoods are unique to their city, so once you know the neighbourhood you know the city.  Assuming this is the case, adding both variables will lead to an over-parameterised model; you should use the neighbourhood variable but not the city variable.  The problem is not merely that neighbourhood and city are correlated, but that the latter is a deterministic function of the former.
