Using KPs for Ongoing Resource Negotiation

Introduction

This is a demonstration of an auction for a contended resource, conducted by and among KPs. It suggests a mechanism for conducting ongoing resource renegotiation using KP technology. The current implementation is very basic, providing the mechanisms for conducting a single, randomized round-robin auction.

The Scenario

The premise of the demo is an auction of network bandwidth, with bandwidth parcels each constituted by a number of bandwidth "chunks" of some size. Some bidding customers are seeking fewer, more massive chunks, while some customers are seeking more numerous, smaller ones.

In the demo a KP acts as the auctioneer. It is equipped with a small set of parcels representing a range of characteristics. Bidder KPs arrive at the station, register themselves with the auctioneer, and when all have arrived the auctioneer starts the auction.

The bidders use a shared bidding strategy, parameterized to reflect individual bidder's situation:

available funds
total bandwidth being sought
chunk size preference
list of bidders to be particularly treated as opponents

The different parcels are expressed as variously sized bundles of one of the following three chunk sizes:

T1: unit 1 scale (in fact, 1.54 MB/second)
T3: unit 30 scale (in fact, 45 MB/second)
ISDN: unit .01 scale - (in fact, around 1.5 KB/second for a B pair)

The aggregate bandwidth of the parcels vary, from 400 total units down to 150 units.

Here are the players - the bidders in the auction:


                   Total      Chunk
          Funds  Bandwidth  Preference  Opposes   Description
          -----  ---------  ----------  -------   -----------
MidBell    500      800         1       BigCable  Seeking mid-range chunks
BigCable   500      800        30       MidBell   Seeking big chunks
MidFed     250      500         1       -         More modest MidBell
TinyNet    500      500         0.01    -         Seeking many small chunks;
                                                       modest bandwidth goal

The bidding strategies used by the auction participants rates the bid prospect according to:

The degree to which the parcel satisfies bandwidth and chunk criteria,
The ratio of the bandwidth versus the asking price ("bang-for- the-buck"),
The degree to which their bandwidth goal has been satisfied,
Their urgency over satisfying that goal versus the remaining number of parcels, and
Whether or not the prior bid is by a bidder they oppose.

For more information on the default bidding strategy, see the code which implements it, in the Bidder.SolicitBid() method in demos/market/Bidder.py.

Here are the parcels:


                              Total   Chunk Type  Number   Opening  Price
Description                 Bandwidth  (Units)   of Chunks  Price   Floor
-----------                 ---------  -------   ---------  -----   -----
Medium size                    200      T1 (1)        200    120     100
Big chunks, lowish total       150      T3 (30)         5    100      80
Small chunks, medium total     200    ISDN (.01)    20000     80      50
Medium chunks, double total    400      T1 (1)        400    320     300

In addition to the variety of bidder parameters and parcel characteristics, the auctioneer randomizes the order of the parcels and the order by which bids are solicited from bidders. This enables a diversity of bidding situations in each auction run.

Running the Demo

Once you have a KSS running on your system (see the quick start guide), use the launch-auction script in the market demo directory to start the demo:

$ $KOSROOT/demos/market/launch-auction

When the auctioneer arrives at the station it establishes a service by which the bidders register themselves. The bidders arrive and look for that interface, and once they find it they register their bidding interface, by which the auctioneer solicits bids and settles accounts. Once all the bidders are registered the auctioneer takes over and the auction begins.

The auctioneer prompts the user for confirmation before proceeding at various points during the auction. The frequency of those pauses is controllable by the user, by entering a '+' for more pausing, or a '-' for less, at any of the prompts. By default, the auctioneer pauses between parcels, but not between individual bids on a parcel.

Auctioning a Parcel

For each parcel, the auctioneer first announces the label and crucial stats of the parcel (see the parcels chart), and then proceeds (after prompting) to offer the opening bid for it. The actual bidding is conducted by querying the bidders, via their bidding interface, in random order, changing the order from round to round. The first bidder who accepts the current bid gets it, and the bidding proceeds to the next round.

During bidding, the auctioneer indicates who accepted the bid with a '->' symbol, followed by the name of the bidder (see the bidders chart) who took it, or it indicates that there were no takers on the current bid.

If there is a bid in the current round, the bid level is increased by a fixed factor (five credits), and the new bid is offered up.
If there is no new bid:
- If there has been a bid accepted for the current parcel, then the auctioneer awards the sale and announces the fact, and bidding proceeds to the next parcel.
- If, however, there were no already accepted bids, then the asking bid is lowered by five credits.
  - If the new price is at or above the minimum acceptable price for the item (see the parcels chart) then the bidding proceeds from that new price.
  - If the bid does not meet the minimum acceptable price then the auctioneer announces that the item is tabled with no sale, and the auction proceeds to the next parcel.

Whether a parcel is sold or tabled, the auctioneer announces the fact both to the user and to each of the bidders. This way the bidders could factor who got what in their strategies for bidding on subsequent items.

After all four parcels are auctioned the auctioneer announces a summary of the results, stating the number that were sold and the number that were tabled and then displaying a small table indicating who paid what price for which parcel, substituting an asterisk ("*") in the "who" and "price" column for those items that were tabled instead of sold. Then the auctioneer prompts the user for confirmation to wrap up the auction, and upon receiving it notifies the bidders of the conclusion, whereupon they and the auctioneer all exit.

Files

All files reside in demos/market except koe/interfaces/MarketAPI.isl.

launch-auction: Auction demo start script.
MarketAPI.isl: Market demo interfaces, in $KOSROOT/interfaces.
auctiontools.py: Essential auction demo facilities.
Auctioneer.py: Abstract definition of the auctioneer.
auctioneer.py: Auctioneer implementation, including parcels, expected bidders, etc.
Bidder.py: Abstract definition of a bidder.
bigbidder.py, fedbidder.py, midbidder.py, tinybidder.py: Bidder implementations.