Online Weighted Matching with Delays

Problem Statement

In this problem, we manage a 2 player game coordinator. Over time, a sequence of players (Players) arrive desiring to be matched against other players. Each player has a known function (matchPerception) that reports their dis-utility of playing a given other player. These dis-utilities need not be symmetric.

The mechanism's (MatchingAlgorithm's) role is to choose what matches to create and when; the mechanism is permitted to delay creation of matches between compatible players. In particular, a MatchingAlgorithm must specify what matches the mechanism would create of the players currently unmatched and when they would create them. The goal of the mechanism is to minimize the combined sum of

1. The waiting time of each player between their arrival into the system and the start time of the match they are put in
2. Each player's perceived dis-utility of the match they are put in

Files Included:

• Player.java: This (abstract) class is used for representing players in a given Instance. Every player must implement the matchPerception function, which outputs their dis-utility of playing against a given other player.
• Match.java: This class holds the necessary information of a given Match, including the Players involved and the match's starting time.
• Instance.java: This (abstract) class is used for creating instances of the problem. Any valid instance must define the getNextPlayer method, which returns the next Player to arrive in the coordinator.
• MatchingAlgorithm.java: This (abstract) class is used for denoting mechanisms for matching Players. Any valid mechanism must implement the matchesFromPool method, which returns a list of matches to create from the unmatched Players in the pool.
• jgrapht-core-1.5.2.jar: Theoretically contains code for computing max-weight-matching (see problems below).
• GreedyMatching.java: An example of a matching algorithm for this problem. It's not good; it just matches everyone in the pool that it can, disregarding the players' matchPerceptions.
• Algorithm1.java: An algorithm we developed in class. It seems to be a bit better than Greedy, but unclear exactly how much better.
• Driver.java: This class is the Driver for the game. It takes in two command line parameters.
• • The first parameter controls the number of requests to draw (by default, 6)
• • The second parameter controles whether debugging is printer (by default, true)
• • An example run would look like $ java Driver 100 false