  In this paper, we address the existence and computation of competitive
equilibrium in the transportation market for autonomous carpooling first
proposed by [Ostrovsky and Schwarz, 2019]. At equilibrium, the market organizes
carpooled trips over a transportation network in a socially optimal manner and
sets the corresponding payments for individual riders and toll prices on edges.
The market outcome ensures individual rationality, stability of carpooled
trips, budget balance, and market clearing properties under heterogeneous rider
preferences. We show that the question of market's existence can be resolved by
proving the existence of an integer optimal solution of a linear programming
problem. We characterize conditions on the network topology and riders'
disutility for carpooling under which a market equilibrium can be computed in
polynomial time. This characterization relies on ideas from the theory of
combinatorial auctions and minimum cost network flow problem. Finally, we
characterize a market equilibrium that achieves strategyproofness and maximizes
welfare of individual riders.
