Searching Market Equilibria under Uncertain Utilities