# Online bipartite matching problem for task assignment

I have $$n$$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current month.

And I have an estimated number $$m$$ tasks (rides) per month, each task has a cost (wage) and a type (long ride, short ...). The tasks come one at a time (online).

When a task comes, I have to match it in time to one of the available drivers, according to the following criteria:

• the matching algorithm has to be fair. i.e in the end of the month the balances of the drivers has to be close to each other.
• If the algorithm has to choose between 2 drivers with equal balances it has to be the one with the least number of rides in the current month.
• Tasks are assigned to available drivers only.

In the beginning I thought of a greedy solution which assigns the task to the driver with the least balance. But I realised that it does not work in case the cost of the task is not significant and won't add much to the least driver.

E.g : let's say we have 2 available drivers A(100usd) and B(700usd), and then a 50usd task T1 came, then a 500Usd task one t2.the gready algorithm will assign T1 to A make him busy for quite some time and then the T2 will be assigned to B. Having this the balance gap will be greater.

Can this problem be modeled by a bipartite online matching problem. What is the best solution in this case?