vcg-auction

一个维克瑞-Clarke-Groves拍卖库。

许可

许可协议为以下之一

• Apache License, Version 2.0 (LICENSE-APACHE 或 http://apache.ac.cn/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非你明确声明，否则任何有意提交以包含在作品中的贡献，根据Apache-2.0许可证的定义，应双许可如上所述，不附加任何额外条款或条件。

lib.rs:

一个维克瑞-Clarke-Groves拍卖库。

给定一组物品和出价，计算最高价值的出价组合，以及每个获胜者必须支付的款项。款项是每个获胜者对其他出价者造成的损害。

兼容的出价类型实现 [Bid] 特性。

默认特性 rand 可以禁用，如果只希望使用非决斗实现。

出价组合

出价将投标人名称、出价值以及要出价的物品集合和数量关联起来。出价作为“出价集”的集合提供，其中出价集内的出价是互斥的。不同出价集中的出价不是互斥的。

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

在这里，Alice要么想要一把椅子出价5，要么两把椅子出价7。她的出价是互斥的，任何同时赢得两个出价的结果都不考虑。即使有三把椅子可用，Alice也不能赢得三把。

Bob的出价在另一个出价集中，所以Bob的出价与Alice的一个出价最多一个的组合是有效的。

互斥出价允许出价者表达他们的需求曲线，当他们对不同物品组合的估值不同时。

如果出价者想要为多个物品出价，而这些物品的估值无关，则可以将这些出价放在单独的出价集中，而不是列举所有组合。

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

在这里，Alice想要一把椅子出价5，一张桌子出价10，或者一张桌子和一把椅子出价15。

同样，如果投标人互斥，他们可以被放入同一个投标集合中。如果鲍勃和卡罗尔不希望当另一个人也赢得一把椅子时自己赢得椅子，他们的投标可以表达如下

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

不考虑双方都赢的结果，即使有 两把椅子可用。由于这些投标人不同，鲍勃赢得椅子的支付要考虑卡罗尔的排除。

示例

use vcg_auction::vcg_auction;

#[derive(Debug, PartialEq)]
struct Bid {
    name: String,
    value: u64,
    items: Vec<(String, u64)>,
}

impl Bid {
    fn new(
        name: impl Into<String>,
        value: u64,
        items: Vec<(String, u64)>,
    ) -> Self {
        Self {
            name: name.into(),
            value,
            items,
        }
    }
}

impl vcg_auction::Bid for Bid {
    type Name = String;
    type Value = u64;
    type Item = String;
    type Quantity = u64;

    fn bidder_name(&self) -> &Self::Name {
        &self.name
    }
    fn bid_value(&self) -> &Self::Value {
        &self.value
    }
    fn bid_items(&self) -> &[(Self::Item, Self::Quantity)] {
        &self.items
    }
}

#
#

// Two chairs up for auction.
let items = vec![("chair".into(), 2)];
let bids = vec![
    vec![
        Bid::new("Alice", 5, vec![("chair".into(), 1)]),
        Bid::new("Alice", 7, vec![("chair".into(), 2)]),
    ],
    vec![Bid::new("Bob", 4, vec![("chair".into(), 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".into(), 0), (&"Bob".into(), 2)]);

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

请参阅测试目录，其中使用浮点数作为投标值和物品数量，以及 secrecy 包以帮助保持投标值机密。对于必须实现 [Ord] 的浮点数投标值，您可能希望使用 ordered-float 或类似的包。