vcg_auction/
vcg.rs

1//! Main VCG auction implementation.
2
3use std::cmp::Ordering;
4
5use num_traits::Zero;
6#[cfg(feature = "rand")]
7use rand::{thread_rng, Rng};
8
9use crate::{AddSubSelf, Bid};
10
11/// Result of a VCG auction. Contains the set of winning bids, and the payments
12/// to be made by each bidder.
13#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
14pub struct AuctionResult<'a, B: Bid> {
15    pub winning_bids: Vec<&'a B>,
16    pub payments: Vec<(&'a B::Name, B::Value)>,
17}
18
19/// Calculate a Vickrey-Clarke-Groves auction. Takes a set of items with the
20/// quantities to be auctioned, and a collection of "bid sets", each containing
21/// bids which are mutually-exclusive of one another. Bids are typically grouped
22/// by bidder in these mutually-exclusive bid sets, but bidders can also put
23/// bids in separate bid sets if they are independent of each other. If multiple
24/// outcomes are tied, one is selected at random using a uniform distribution.
25#[cfg(feature = "rand")]
26#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
27pub fn vcg_auction<'a, B: Bid>(
28    items: &[(B::Item, B::Quantity)],
29    exclusive_bid_sets: &'a [Vec<B>],
30) -> Option<AuctionResult<'a, B>> {
31    let tiebreaker = |options: &[Vec<&B>]| {
32        if !options.is_empty() {
33            thread_rng().gen_range::<usize, _>(0..options.len())
34        } else {
35            0
36        }
37    };
38    vcg_auction_with_tiebreaker(items, exclusive_bid_sets, tiebreaker)
39}
40
41/// Calculate a VCG auction with a tiebreaking scheme passed in as a closure.
42/// The tiebreaker takes a collection of bid sets that all scored the highest,
43/// and returns the index of the winning bid set. An invalid index will cause
44/// `None` to be returned.
45///
46/// Here's a simple tiebreaker that always returns the first index of zero.
47/// ```
48/// # type Bid = usize; // just to get this to compile
49/// let tiebreak = |_: &[Vec<&Bid>]| 0;
50/// ```
51///
52/// [`vcg_auction`] uses a random uniform tiebreaker.
53pub fn vcg_auction_with_tiebreaker<'a, B: Bid>(
54    items: &[(B::Item, B::Quantity)],
55    exclusive_bid_sets: &'a [Vec<B>],
56    tiebreaker: impl FnOnce(&[Vec<&B>]) -> usize,
57) -> Option<AuctionResult<'a, B>> {
58    let exclusive_bid_sets = exclusive_bid_sets
59        .iter()
60        .map(|bs| bs.iter().collect::<Vec<_>>())
61        .collect::<Vec<_>>();
62    // multiple sets of bids could be tied for the highest value
63    let (highest_bid_sets, _highest_value) =
64        find_highest_value_bid_sets(items, &exclusive_bid_sets);
65    let winning_bid_set = if highest_bid_sets.len() <= 1 {
66        highest_bid_sets.get(0)?
67    } else {
68        highest_bid_sets.get(tiebreaker(&highest_bid_sets))?
69    };
70    let payments =
71        calculate_payments(winning_bid_set, items, &exclusive_bid_sets);
72    Some(AuctionResult {
73        winning_bids: winning_bid_set.to_vec(),
74        payments,
75    })
76}
77
78fn find_highest_value_bid_sets<'a, B: Bid>(
79    items: &[(B::Item, B::Quantity)],
80    exclusive_bid_sets: &[Vec<&'a B>], // sets of mutually-exclusive bids
81) -> (Vec<Vec<&'a B>>, B::Value) {
82    let mut highest_value_bid_sets: Vec<Vec<&'a B>> = vec![]; // empty
83    let mut highest_value = B::Value::zero();
84    // the items selected so far
85    let items_selected = items
86        .iter()
87        .map(|(item, _)| (item, B::Quantity::zero()))
88        .collect::<Vec<_>>();
89    // annotate the max possible value of each bid set, used to quickly prune
90    // the solution space
91    let bid_sets_remaining = exclusive_bid_sets
92        .iter()
93        .filter_map(|bs| {
94            bs.iter().map(|b| b.bid_value()).max().map(|max| (bs, max))
95        })
96        .collect::<Vec<_>>();
97    find_highest_value_helper(
98        items,
99        &items_selected,
100        &bid_sets_remaining,
101        &[],
102        B::Value::zero(),
103        &mut highest_value_bid_sets,
104        &mut highest_value,
105    );
106    (highest_value_bid_sets, highest_value)
107}
108
109/// Finds valid combinations of bids using recursive backtracking to limit the
110/// exploration space where bid combinations are invalid.
111fn find_highest_value_helper<'a, B: Bid>(
112    item_stock: &[(B::Item, B::Quantity)], // max number of items available
113    items_selected: &[(&B::Item, B::Quantity)], // items in selected bids
114    bid_sets_remaining: &[(&Vec<&'a B>, &B::Value)], // bid sets to consider
115    bids_selected: &[&'a B],               // selected bids
116    selected_value: B::Value,
117    highest_value_bid_sets: &mut Vec<Vec<&'a B>>, // highest-scoring bid sets
118    highest_value: &mut B::Value,                 // highest value found
119) {
120    // check that the allocated items is not greater than the stock
121    for i in 0..items_selected.len() {
122        if items_selected[i].1 > item_stock[i].1 {
123            // selected bids not valid -> return without further exploring
124            return;
125        }
126    }
127
128    // search reached full depth, check if selected bids are more valuable
129    if bid_sets_remaining.is_empty() {
130        match selected_value.cmp(highest_value) {
131            Ordering::Greater => {
132                *highest_value_bid_sets = vec![bids_selected.to_vec()];
133                *highest_value = selected_value;
134            }
135            Ordering::Equal => {
136                highest_value_bid_sets.push(bids_selected.to_vec());
137            }
138            Ordering::Less => (),
139        }
140        return;
141    }
142
143    // check the possible value achievable with remaining bids
144    let max_remaining_value = bid_sets_remaining
145        .iter()
146        .fold(B::Value::zero(), |sum, (_bs, max_bid_value)| {
147            sum.add(max_bid_value)
148        });
149    let possible_value = selected_value.add(&max_remaining_value);
150    if possible_value < *highest_value {
151        // can't achieve a result with a higher value than we've already
152        // found -> return
153        return;
154    }
155
156    // recurse with next element
157    let (next_bid_set, _max_bid_value) = bid_sets_remaining[0];
158    for bid in next_bid_set {
159        let mut bids_selected_with_new_bid = bids_selected.to_vec();
160        bids_selected_with_new_bid.push(bid);
161        let mut items_selected_with_new_bid = items_selected
162            .iter()
163            .map(|(id, qty)| (*id, qty.clone()))
164            .collect::<Vec<_>>();
165        for (item, qty) in items_selected_with_new_bid.iter_mut() {
166            if let Some((_, bid_qty)) =
167                bid.bid_items().iter().find(|(id, _)| *id == **item)
168            {
169                *qty = qty.add(bid_qty)
170            }
171        }
172        find_highest_value_helper(
173            item_stock,
174            &items_selected_with_new_bid,
175            &bid_sets_remaining[1..],
176            &bids_selected_with_new_bid,
177            selected_value.add(bid.bid_value()),
178            highest_value_bid_sets,
179            highest_value,
180        );
181    }
182    // also recurse without using any bids from this bid set
183    find_highest_value_helper(
184        item_stock,
185        items_selected,
186        &bid_sets_remaining[1..],
187        bids_selected,
188        selected_value,
189        highest_value_bid_sets,
190        highest_value,
191    );
192}
193
194/// Calculate the payments each winning bidder makes given the winning bid set.
195fn calculate_payments<'a, B: Bid>(
196    winning_bid_set: &[&'a B],
197    items: &[(B::Item, B::Quantity)],
198    exclusive_bid_sets: &[Vec<&'a B>], // sets of mutually-exclusive bids
199) -> Vec<(&'a B::Name, B::Value)> {
200    let mut payments = vec![];
201    for winning_bid in winning_bid_set {
202        let bidder_name = winning_bid.bidder_name();
203        if payments.iter().any(|(name, _)| *name == bidder_name) {
204            // already calculated this bidder's payment
205            continue;
206        }
207        // find the auction value without this bidder
208        let bid_sets_without_bidder = exclusive_bid_sets
209            .iter()
210            .map(|bs| {
211                bs.iter()
212                    .filter(|b| *b.bidder_name() != *bidder_name)
213                    .copied()
214                    .collect::<Vec<_>>()
215            })
216            .collect::<Vec<_>>();
217        let auction_value_without_bidder =
218            find_highest_value_bid_sets(items, &bid_sets_without_bidder).1;
219        // find the value of the bids placed by other bidders
220        let value_of_other_bids = winning_bid_set
221            .iter()
222            .filter(|b| *b.bidder_name() != *bidder_name)
223            .fold(B::Value::zero(), |acc, b| acc.add(b.bid_value()));
224        // invariant: this subtraction never underflows on unsigned types
225        let payment = auction_value_without_bidder.sub(&value_of_other_bids);
226        payments.push((winning_bid.bidder_name(), payment));
227    }
228    payments
229}
vcg_auction/vcg.rs

vcg_auction/
vcg.rs
