Matching Algorithms Paper Review I

Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation

This paper looks into the dynamic resource assignment problem wherein agents have varying arrival and departure times and have preference orders on a set of resources. The agent reporting it’s preference truthfully is not a given and four algorithms are evaluated to this end:

• Arrival Priority Serial Dictatorship (APSD): In this method each agent on arrival selects the resource for which he has the highest valuation and no payments are made to the platform. This method has been proven to be the only one in which a true value elicitation over resources is a dominant strategy given that payments are not allowed and that an agent does not misreport his arrival and departure times to be earlier than and later than actual respectively.
• Split Dynamic VCG (SDV): It finds an assignment that maximizes the sum of agents valuations for their alloted resources and their payments are determined by the extent to which they have affected other agents allotments. It was originally proposed under static settings but has been adapteed to dynamic settings by partitioning hte agents into groups that exist in the system simultanously. At each timestep the VCG auction is rerun with the remaining resources.
• E-Auction: This method uses the solution to the standard secretary problem adapted to the multiple resources setting. The platform waits for \(\frac{n}{e}\) fraction of the agents to arrive in the first phase and sets the reserve price as the highest valuation received for that resource in the first phase. The first agent to arrive in thesecond phase with a bid surpassing the reserve price is awarded the resource. This mechanism is aso truthful for settings in which agents do not misreport their arrival and departures to be later than and earlier than actual.
• Online Ranked Competition Auction (ORCA): The system extends on the earlier E-Auction by considering the possibility that some resources may be more coveted across the board by all agents and thus it makes sense to have differing thresholds in the multiple secretaries problem with less coveted resources having lower thresholds. These thresholds are solved using a dynamic programming approach resulting in the algorithm having similar truthfulness characteristics as the method above.

The above algorithms are compared to the offline optimal which is an omneiscent god-like algorithm which knows all the user valauations from the start, no matter when they enter the market. Once all valuations are known an optimization problem can be solved to get the best possible result. The ratio of the value extracted by the offline algorithm to that of any online algorithm is its competitive ratio. APSD and SDV have a competitive ratio in the order of number of agents, while E-Auction has a cometitive ratio of \(\mathrm{e}\) and ORCA has the best competitive ratio of less than \(\mathrm{e}\). The paper also compares the algorithms in differeing scenarios and finds that in scenarios with low competition SDV is the best performing method while in scenarios with high competition ORCA is the best performing method.

Assigning Tasks to Workers based on Historica Data: Online Task Assignment with Two-Sided Arrivals

This paper looks into the scenario where both sides of the market are dynamic rather than just one side. There are a couple of working assumptions:

• The arrival of workers and tasks can be inferred from past data into known independent distributions.
• The number of different distributions one side is far lesser than that on the other.

The paper contributes one adaptive and one non-adaptive approach. The adaptive approach changes its matching strategy depending on the type and the number of agents in the system ehile the non-adaptive matching strategy is decided before the start of the algorithm. The paper uses a stocastic tool called the Two-Stage Birth Death Process to draw parrallels with the problem and uses that to derive competitive ratios and hardness results such as theoretically maximum possible competitive ratio. The following are the pertinent observations:

• The non-adaptive greedy algorithm achieves a Competitve Ratio (CR) of 0.3 which is shown uing the stochastic process to be the maximum possible for a non-adaptive process. This beats a previous result of 0.25 which assumed random arrival order, thus demonstrating the value of using past data to infer arrival distributions.
• An adaptive greedy algorithm is shown to outperform the best non-adaptive algortihm using simulations and for a node-weighted relaxation of the problem (each agent has similar value over all resources) a linear program with tight constraints exploiting the same is used to achieve a CR of 0.34. Here again the stochastic tool is used to provide a theoretical bound of 0.58 indicating scope for improvement.

Matching with Externalities and Attitudes

This is a largely theoretical paper that looks into the repurcussions of a blocking coalition (A subset of users that can all improve their utlities by deviating from the specified matching) imposing their deviations on the rest of the system in the presence of their differing attitudes to the rest. An additive model of externalities are assumed wherein the utlity of an agent is the sum of values of the matches it is a part of and the externalities arising due to the matches of other agents. The assumprion of the externalities depends on the attitude of the agents in the blocking coalition:

• Neutral Attitude: Agents in the blocking coalition assume that the rest will not react to their deviation.
• Optimistic Attitude: Agents in the blocking coalition assume that the rest will act to their own best interest.
• pessimistic Attitude: Agents in the vlocking coalition assume that the rest will act to punish them for their deviations.

The work looks into the questions of membership and non-emptiness i.e whether a given matching is stable under the given attitude and whether a given problem with a given attitude even has a stable matchig, respectively. The paper contributes the result that under assumptions of additive externalities only Gale-Shapely style pairwise stability questions of non-emptiness and membership can be answered in polynomial time. Also questions of membership can always be answered in polynomial time for optimistic attitudes, whether the stability be pairwise or setwise. All other combinations of the pproblem are computationally intractable.