Crate vcg_auction

A Vickrey-Clarke-Groves auction library.

Given a set of items and bids, the highest value combination of bids is calculated, along with the payments each winner must make. Payments are the harm each winner causes to other bidders.

Compatible bid types implement the Bid trait.

The default feature rand can be disabled if only the non-tiebreaking implementation is desired.

Bid Combinations

Bids associate a bidder name, a bid value, and a collection of items and quantities being bid on. Bids are supplied as a collection of “bid sets”, where the bids inside a bid set are mutually-exclusive. Bids that are in separate bid sets are not mutually-exclusive.

[
    [
        (Alice, 5, [(chair, 1)]),
        (Alice, 7, [(chair, 2)])
    ],
    [
        (Bob, 4, [(chair, 1)])
    ]
]

Here Alice either wants one chair for 5, or two chairs for 7. Her bids are mutually-exclusive, and no outcome is considered where both bids win. Even if three chairs were available, Alice couldn’t win all three.

Bob’s bid is in another bid set, so any combination of Bob’s bid with one of Alice’s bids is valid.

Mutually-exclusive bids let bidders express their demand curves when their valuations are different for different combinations of items.

If bidders want to bid for multiple items with unrelated valuations, those bids can be placed in separate bid sets instead of enumerating all combinations.

[
    [
        (Alice, 5, [(chair, 1)])
    ],
    [
        (Alice, 10, [(table, 1)])
    ],
    [
        (Bob, 20, [(chair, 1), (table, 1)])
    ]
]

Here Alice wants a chair for 5, a table for 10, or a table and a chair for 15. Bob only wants the chair and table together for 20.

Similarly, if bidders are mutually-exclusive they can be put into the same bid set. If Bob and Carol wouldn’t want to win a chair if the other person was also going to win a chair, their bids could be expressed like this:

[
    [
        (Bob, 4, [(chair, 1)]),
        (Carol, 3, [(chair, 1)])
    ]
]

No outcome is considered where both win, even if two chairs are available. Since these bidders are different people, Bob’s payment for winning a chair accounts for Carol’s exclusion.

Example

use vcg_auction::{vcg_auction, types::SimpleBid};


// Two chairs up for auction.
let items = vec![("chair".to_string(), 2)];
let bids = [
    vec![
        SimpleBid::new("Alice", 5, [("chair", 1)]),
        SimpleBid::new("Alice", 7, [("chair", 2)]),
    ],
    vec![SimpleBid::new("Bob", 4, [("chair", 1)])],
];
let result = vcg_auction(&items, &bids)?;

// Alice and Bob each win a chair.
assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
// Bob's participation in the auction prevented Alice from getting a second
// chair for an additional value of 2, so Bob only pays 2. Alice pays
// nothing since her participation didn't prevent any other valuable
// outcomes.
assert_eq!(
    result.payments,
    [(&"Alice".to_string(), 0), (&"Bob".to_string(), 2)]
);

// Example from the VCG auction Wikipedia page.
let items = vec![("apple".to_string(), 2)];
let bids = vec![
    vec![SimpleBid::new("Alice", 5, [("apple", 1)])],
    vec![SimpleBid::new("Bob", 2, [("apple", 1)])],
    vec![SimpleBid::new("Carol", 6, [("apple", 2)])],
];
let result = vcg_auction(&items, &bids)?;

assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
assert_eq!(
    result.payments,
    [(&"Alice".to_string(), 4), (&"Bob".to_string(), 1)]
);

See the tests directory for examples using floating point numbers for bid values and item quantities, and the secrecy crate to help keep bid values confidential. For floating point bid values, which must implement Ord, you may want to use ordered-float or a similar crate.

Modules

types

Structs

AuctionResult

Result of a VCG auction. Contains the set of winning bids, and the payments to be made by each bidder.

Traits

AddSubSelf

Trait with methods that take two references of the same type and returns the result of addition or subtraction. Used as a trait bound for Bid associated types.

Bid

Trait for a bid that can be auctioned.

Functions

vcg_auctionrand

Calculate a Vickrey-Clarke-Groves auction. Takes a set of items with the quantities to be auctioned, and a collection of “bid sets”, each containing bids which are mutually-exclusive of one another. Bids are typically grouped by bidder in these mutually-exclusive bid sets, but bidders can also put bids in separate bid sets if they are independent of each other. If multiple outcomes are tied, one is selected at random using a uniform distribution.

vcg_auction_with_tiebreaker

Calculate a VCG auction with a tiebreaking scheme passed in as a closure. The tiebreaker takes a collection of bid sets that all scored the highest, and returns the index of the winning bid set. An invalid index will cause None to be returned.