In the research area of scheduling and optimization, auction-based algorithms like vickrey-auctions are often used. As I understand all these approaches, the goal is to assign a property to the highest bidder. In scheduling problems, a resource will be assigned to a job with the highest success. However, the results may not reflect the global best solution in a huge scheduling problem with many jobs and many resources.
For example: There are two jobs "a, b" and two resources "A, B". Job "a" will achieve 0 P (points) on "A "and 5 P on "B". Job "b" will achieve 7 P on "A" and 10 P on "B". During an auction, job "b" will bid on resource "B" and the global success will be 10 P. But if job "b" allocates resource "A" and job "a" allocates resource "B", the overall success will be 12 P.
Does anybody know for sure, if I am right with this assumption? Or in other words, does anybody know an auction-based algorithm that is capable to optimize to the global optimum?
Thanks in advance!
Auction-based algorithms will not, in general, give optimal solutions to scheduling and resource allocation problems. They are a heuristic rather than an exact solution.
That said, there is a large variety of auction-based algorirhms, and they differ in the quality of solutions they give for different problems.
Let's look at your particular problem using an auction based algorithm that is intended to maximize individual Return, i.e., profit.
Suppose we have multiple rounds of bidding and that in each round, a job will bid if both of the following statements are true: (1) the job is not the current high bidder for any resource, (2) there is a resource available whose value to the job is greater than the current high bid for that resource. In this case, a job, j, will make a bid for the resource X whose Return(j,X) = [Value(j,X) - (current bid(X) + minimal bid increment)] is greatest, provided of course that Return(j,X) is positive. The price of each resource is monotone rising throughout the auction.The auction ends when no job bids.
Then job a will bid only on resouce B. Job b will bid on whatever resource gets it the greater Return.
Both a and b will start out bidding on B. The price of B will rise. Job a will keep on bidding for B until the price reaches 5, if the price ever reaches that height. Job b will start out bidding on B until Return(b,B) is less than Return(b,A).
When the bidding for B reaches 3+(2*increment), it is now in job b's best interest to stop bidding for B and instead bid for A. Return(b,B) is now less than 7-(2*increment), but Return(a,B) will be 7-increment. Thus, in the next round b will make a minimal bid for A, and a will not bid.
After this bid, bidding stops because both jobs are current high bidders for a resource. Job a has resource B and job b has resource A. The total value obtained is 7+5=12, which is the maximum.
However, note that maximizing the value may not be the objective you want for this problem. Instead, you may want to maximize total Return. In fact, total Return in a world where resouces are limited and contentious is a more natural objective than total value regardless of price. Further, in an auction-based allocator, you want the prices and the values to have meaning. Else, there is nothing to motivate using an auction paradigm.
In the example auction, the outcome has total Return = [9-(3*increment)]. Return(a,B) = [5-(3+2*increment)] and Return(b,A) = [7-increment]. This total Return is also maximal in a contentious world. (By contentious, I mean that it is not the case that job a for some unstated altruistic reason chooses not to bid at all, leaving a total return of [10-increment] for job b.)
It is still possible to create problem examples where neither the total Value nor the total Return under contention is optimal. As I said auctions are a heuristic. But careful consideration of the format of the auction can deliver very high quality results.
Let me know in this question or by message at ResearchGate, you want to discuss this further. Best of luck to you.
Auction-based algorithms will not, in general, give optimal solutions to scheduling and resource allocation problems. They are a heuristic rather than an exact solution.
That said, there is a large variety of auction-based algorirhms, and they differ in the quality of solutions they give for different problems.
Let's look at your particular problem using an auction based algorithm that is intended to maximize individual Return, i.e., profit.
Suppose we have multiple rounds of bidding and that in each round, a job will bid if both of the following statements are true: (1) the job is not the current high bidder for any resource, (2) there is a resource available whose value to the job is greater than the current high bid for that resource. In this case, a job, j, will make a bid for the resource X whose Return(j,X) = [Value(j,X) - (current bid(X) + minimal bid increment)] is greatest, provided of course that Return(j,X) is positive. The price of each resource is monotone rising throughout the auction.The auction ends when no job bids.
Then job a will bid only on resouce B. Job b will bid on whatever resource gets it the greater Return.
Both a and b will start out bidding on B. The price of B will rise. Job a will keep on bidding for B until the price reaches 5, if the price ever reaches that height. Job b will start out bidding on B until Return(b,B) is less than Return(b,A).
When the bidding for B reaches 3+(2*increment), it is now in job b's best interest to stop bidding for B and instead bid for A. Return(b,B) is now less than 7-(2*increment), but Return(a,B) will be 7-increment. Thus, in the next round b will make a minimal bid for A, and a will not bid.
After this bid, bidding stops because both jobs are current high bidders for a resource. Job a has resource B and job b has resource A. The total value obtained is 7+5=12, which is the maximum.
However, note that maximizing the value may not be the objective you want for this problem. Instead, you may want to maximize total Return. In fact, total Return in a world where resouces are limited and contentious is a more natural objective than total value regardless of price. Further, in an auction-based allocator, you want the prices and the values to have meaning. Else, there is nothing to motivate using an auction paradigm.
In the example auction, the outcome has total Return = [9-(3*increment)]. Return(a,B) = [5-(3+2*increment)] and Return(b,A) = [7-increment]. This total Return is also maximal in a contentious world. (By contentious, I mean that it is not the case that job a for some unstated altruistic reason chooses not to bid at all, leaving a total return of [10-increment] for job b.)
It is still possible to create problem examples where neither the total Value nor the total Return under contention is optimal. As I said auctions are a heuristic. But careful consideration of the format of the auction can deliver very high quality results.
Let me know in this question or by message at ResearchGate, you want to discuss this further. Best of luck to you.
Thank you very much Mr. Courtney! That answer helped me a lot. Auction-based algorithms aren’t that bad as I expected. I forgot, that the bidder can change their target during the bidding process. The target switching and a well-chosen increment are the keys to reach a good solution or even the global optimum.
Thank you both! This thread captures concisely the recent interest in auction-based approaches to resource allocation. As Mr. Courtney observes, the methods are heuristic and admit a variety of objectives for which solutions can be decided by way of suitably designed auctions.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms