24 Dec 2018
In this post we explore recent experiments simulated on ridesharing data that detail how efficient it is viz-a-viz a centralized cab assignment system.
The paper considers two kinds of vehicular matching problems:
- Decentralized Model: This model approximates a ride-hailing system. The system sends nearby rider requests to a driver and leaves it upto the driver to choose a rider
- Centralized Model: This model approximates a cab booking system. The centralized broker assigns matches to drivers.
Several simulations are run on both the models using both myopic (matches made immediately for centralized and driver taking closest request immediately for decentralized) as well as patient (matches being made after developing market thickness in centralized and driver waiting a stochastic amount of time before selecting in decentralized) heuristics. In the centralized system the patient version understandably improves both thickness and match rate of the market. In the decentralized system the patient version improves thicknes in the market but surprisingly leads to a lower number of matches. This is likely due to the forgone matches in the cases where a driver is in an underserved part of the city and forgoes a match for hope of a better one. The presence of a central broker enforcing matches ostensibly prevents this eventuality in a centralized market.
Finally it is shown that these conclusions are robust to a number of deviations in the model:
- An alternative strategy being used by drivers or brokers such as selecting the second best match
- An alternative strategy being used by drivers or brokers such as following a patient approach but turning greedy just before leaving the market unmatched
- Each driver having differing tolerances to the maximum viable match distance
This work largely looks at a simplified stylized version of a similar problem. The model considers a cirular road on which a fixed number ofdrivers keep moving at a constant pace. The drivers arrive uniformly along the circle with the arrival rates of passengers modelled by a poisson distribution and their trip durations being modelled by an exponential distribution. Two models of cab hailing are considered:
- Ride-Hailing: One can call a taxi from a certain position and the request is assigned to the closest driver.
- Streeet-Hailing: One can sit in a taxi only when it passes by him on the circle.
Additionally, both one-way (ride-hailing taxis move only clockwise) and two-way systems (ride-hailing taxis move clockwose and counter-clockwise) are considered. Street-hailing taxis always move clockwise and only pick passengers up when they drive past them. Simulations are run for varying levels of congestion (by varying the poisson distribution parameters) and a few important observations are made:
- In the street-hailing system average wait-time rises monotonocally with congestion levels. This system is best for reducing waiting time during sparse and medium supply of drivers.
- In the one-way ride hailing system wait-times initially increase with congestion, then decrease for medium congestion levels and then increase again. This is thought to be due to commited assigned drivers missing out on closer but later-arriving passengers. This system is best for reducing waiting time during driver oversupply.
- All of the aforementioned observations regarding waiting times hold true for two-way ride-hailing systems but are less prominent.
- Finally a ride-hailing system operating on a radius limit with which requests are accepted seems to perform best in all cases regarding waiting times. The authors also propose a heuristic based method for deriving a good radius figure that allows for a reasonable bound on waiting times.
23 Dec 2018
This post covers a few recent results in one-sided matching markets that reveal that low-latency solutions to matching problems may not always be the way to go. Making agents wait so as to increase their options can lead to inproved matches and increased social welfare in general.
This paper details the improvements observed in social welfare and reduction in number of agents leaving the market (perishing) by making agents wait for their matches rather than matching them immediately as they enter the market. Agents need to be matched urgently only when they become critical (in urgent need of leaving the market). These results are derived for varying levels of agent impatience (which is encoded as a utility discounted with time). The implicit assumption is that there exists a central broker with a certain time horizon who can detect critical agents and match them if possible. The paper contrasts two different models:
- Greedy: The algortihm maatches agents as soon as they enter the market
- Patient ($\alpha$): The algorithm matches agents only as they become critical. Optionally non-critical agents may be matched at a rate determined by a parameter ($\alpha$)
The work shows that under certain bounds on $\alpha$, the loss of the patient algortihm isn’t much worse than the best possible with an omneiscent broker. This allows an acceleration of the patient algorithm with only minimal degradation in performance. The comparative performance of the two methods are shown under differing rates of impatience. Under some low bounds of impatience, all parameterizations of the patient algorithm are always shown to outperform the greedy one. Additionally, under some medium bounds on impatience, some parameterization of the patient algorithm is shown to outperform the greedy variant.
Most interestingly, the advantage of the patient algorithm over the greedy one seems to stem entirely from the advantage in information. This is reinforced by the fact that divergence in the performance of the two methods seems to be largely governed by the time horizon that the central broker possesses. When the broker is unable to indentify critical agents, the advantage of the patient algorithm is negligible. On the other hand the difference in performance is maximum when the broker is omneiscent and has an infinite time horizon, allowing it to plan matches from the start.
This paper extends the aforementioned work by considering the scenario in which the two kinds of markets co-exist and compete against one another. Agents are split into three pools, with one participating exclusively in the greedy pool, one participating exclusively in the patient pool and the rest participating in both the markets.
The patient market is once again shown to be the single best solution. However, the presence of a competing greedy market that hurts the usage of the patient market (thickness) produces the worst possible result of all, with the resultant performance being inferior to that of even a purely greedy approach. This in turn enforces an incentive structure wherein in the presence of a competing greedy market, a patient market is forced to switch to a greedy mechanism of operation.
29 Nov 2018
In this review we start looking at papers that lay out the scenario of matching with location based rights and constraints and also what until recently, the current state of the field was.
This survey paper details the various kinds of ride-sharing scenarios such as single rider single driver, multiple rider single driver, etc as well as the various complications that arise in dynamic matching scenarios such as predicting future requests and handling detours for new closeby requests.
The work also points out that solutions that optimize system-wide objectives do not necessarily give the users the best experience. It thus mentions that a system planner must choose between one of several objectives such as minimizing system-wide travel time, minimizing average waiting time for users, etc.
The paper also mentions a few open challenges:
- Building critical market mass. This has been addressed in later papers on market thickness which will be discussed in a later post
- Allowing the user a choice between several matches rather than just assigning them a ride, which still seems to be an open problem.
This paper introduces a novel combination of ideas into a well known matching problem - the roommate problem. Agents are subject to location constraints brought about not by their preferences over locations but by the scarcity of viable matching locations. This is a direct result of the location ownership model that the paper considers wherein, once matched in a specific room, two roommates have effective collective ownership of that room and no other agent can get in that room without the explicit approval of at least one of the two agents.
The paper develops two stability concepts with respect to this new model:
- Direct Stability: Under this notion a coalition looking to deviate from a given match can only change the assignments of people in the locations wherein both the owners of a room belong in the coalition. In effect, this means that the match of a non-coalition member can only be changed by his partner (who is part of the coalition), moving to an emplty slot or one completely controlled by colition agents. If such a deviation is not possible, then no other matching directly dominates the given matching and the matching is directly stable.
- Exchange Stability: Under this notion a coalition looking to deviate from a given match can reassign the partners of non-menbers by exchanging amonst themselves and also relocate to spots completely owned by coalition members in addition to unopccupied slots. This in effect requires only the permission of one of the owners of a room to change its mapping. If such a deviation is not possible, then no other matching exchange dominates the given matching and the matching is exchange stable. Coalition Exchange stability is a refinement of Direct Stability such that if a matching is directy stable, it is also coalition exchange stable.
The work finally refers to another notion of dominance called indirect dominance in which a match indirectly dominates another match when it can be obtained from the other match by a series of successively directly dominant intermediate matches. The largest possible group of matches, such that no match in the group indirectly dominates another match in the group and no match outside the group indirectly dominates a match in the group, is called the Farsighted Stable Set. Similarly, the largest possible group of matches, such that no match in the group exchange dominates another match in the group and no match outside the group exchange dominates a match in the group, is called the Exchange Stable Set. The appendix of the paper goes into the relation between the two stable sets with further mathematical rigour.
This paper looks into the problem of maximal matchings over graphs whose edge weights are uncertain. Usually matching strategies seek to maximize expected utlity without regards to the variance in the outcome. This paper seeks to efficiently find the maximal utility matching that respects a certain variance bound which can be uselful in use cases where the user cares more about worst case rather than average case performance. The edge weights are are drawn from a probability distribution with a known mean and variance. Although not directly applied to matching with location considerations, this method would lend itself well to such a setting where the distributions of the various edges can be modelled using a preference order ot some distance based penalty.
Having sorted the edges by their ratio of reward to risk, their approach uses a binary search technique to greedily yield a risk bounded matching that is guaranteed to be at least a third as good as the offline optimal (where the distributions are collapsed and the actual rewards are known beforehand). The work is also extended to be compatible with hypergraphs with probabilistic hyperedges.
An online home for all things Paul