### 1 unstable release

0.1.0 | May 4, 2024 |
---|

#**320** in Finance

**MIT/Apache**

17KB

174 lines

# vcg-auction

A Vickrey-Clarke-Groves auction library.

## License

Licensed under either of

- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

## Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

###
`lib.rs`

:

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 [

] trait.`Bid`

The default feature

can be disabled if only the non-tiebreaking
implementation is desired.`rand`

# 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 at most 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``)``]``)`
`]`
`]`

Here Alice wants a chair for 5, a table for 10, or a table and a chair for 15.

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`;`
`#``[``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``)``]``)``;`

See the tests directory for examples using floating point numbers for bid
values and item quantities, and the

crate to help keep bid values
confidential. For floating point bid values, which must implement [`secrecy`

],
you may want to use
`Ord`

or a similar
crate.`ordered-float`

#### Dependencies

~1MB

~16K SLoC