vcg-auction 0.2.0

A Vickrey-Clarke-Groves auction library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use pretty_assertions::assert_eq;

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

#[test]
fn vickrey_case() {
    let items = vec![("chair".into(), 1)];
    let bids = [
        vec![SimpleBid::new("Alice", 10, [("chair", 1)])],
        vec![SimpleBid::new("Bob", 20, [("chair", 1)])],
    ];
    let result = vcg_auction(&items, &bids).unwrap();
    assert_eq!(result.winning_bids, [&bids[1][0]]);
    assert_eq!(result.payments, [(&"Bob".into(), 10)]);
}

#[test]
fn simple_case() {
    let items = vec![("chair".into(), 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).unwrap();
    assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
    assert_eq!(result.payments, [(&"Alice".into(), 0), (&"Bob".into(), 2)]);
}

#[test]
fn non_exclusive_bids() {
    let items = vec![("chair".into(), 1), ("table".into(), 1)];
    let bids = vec![
        vec![SimpleBid::new("Alice", 5, [("chair", 1)])],
        vec![SimpleBid::new("Alice", 10, [("table", 1)])],
        vec![SimpleBid::new("Bob", 20, [("chair", 1), ("table", 1)])],
    ];
    let result = vcg_auction(&items, &bids).unwrap();
    assert_eq!(result.winning_bids, [&bids[2][0]]);
    assert_eq!(result.payments, [(&"Bob".into(), 15)]);
}

/// Example from the Wikipedia page
#[test]
fn wikipedia_example() {
    let items = vec![("apple".into(), 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).unwrap();
    assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
    assert_eq!(result.payments, [(&"Alice".into(), 4), (&"Bob".into(), 1)]);
}

#[test]
fn mutually_exclusive_bidders() {
    let items = vec![("chair".into(), 2)];
    let bids = vec![
        vec![SimpleBid::new("Alice", 5, [("chair", 1)])],
        vec![
            SimpleBid::new("Bob", 4, [("chair", 1)]),
            SimpleBid::new("Carol", 3, [("chair", 1)]),
        ],
    ];
    let result = vcg_auction(&items, &bids).unwrap();
    assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
    assert_eq!(result.payments, [(&"Alice".into(), 0), (&"Bob".into(), 3)]);
}

#[test]
fn no_valid_bids() {
    let items = vec![("apple".into(), 2)];
    let no_bid_cases: &[Vec<Vec<SimpleBid>>] = &[
        vec![],
        vec![vec![]],
        vec![vec![], vec![]],
        // Alice wants 3 apples, but only 2 are available
        vec![vec![SimpleBid::new("Alice", 5, [("apple", 3)])]],
    ];
    for no_bid_case in no_bid_cases {
        let result = vcg_auction(&items, no_bid_case).unwrap();
        assert!(result.winning_bids.is_empty());
        assert!(result.payments.is_empty());
    }
}

#[test]
fn simple_tiebreaker() {
    let items = vec![("chair".into(), 1)];
    let bids = vec![
        vec![SimpleBid::new("Alice", 10, vec![("chair", 1)])],
        vec![SimpleBid::new("Bob", 10, vec![("chair", 1)])],
    ];
    // tiebreak favors Bob
    let tiebreak = |_: &[Vec<&SimpleBid>]| 1;
    let result = vcg_auction_with_tiebreaker(&items, &bids, tiebreak).unwrap();
    assert_eq!(result.winning_bids, [&bids[1][0]]);
    assert_eq!(result.payments, [(&"Bob".into(), 10),]);
}

#[test]
fn unrelated_bids_same_bidder() {
    let items = vec![("chair".into(), 2), ("table".into(), 1)];
    let bids = vec![
        // Alice wants the chairs and the table independently of each other
        vec![SimpleBid::new("Alice", 10, vec![("chair", 2)])],
        vec![SimpleBid::new("Alice", 5, vec![("table", 1)])],
        vec![SimpleBid::new("Bob", 4, vec![("table", 1)])],
    ];
    let result = vcg_auction(&items, &bids).unwrap();
    assert_eq!(result.winning_bids, [&bids[0][0], &bids[1][0]]);
    assert_eq!(result.payments, [(&"Alice".into(), 4),]);
}