31:T414,md`# Vickery-Clarke-Groves auction example The [Vickery-Clarke-Groves](https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_auction) auction is a generalization of a "second price" auction. With a second price auction you have multiple bidders and one item to sell. When you have multiple items to sell, you don't want to use the second price, but instead use a more complicated calculation. This also works when the items don't have an order from best to worst. The main idea is to calculate the *total value* for a given configuration (matching bidders to items). Then we want to compare the total value with all the bidders to the total value if one bidder is removed. That's what that one bidder should pay. In the case where there's only one item, this becomes the second price auction. But I want to see what happens with multiple items, so I wrote this page to run the calculations. Three bidders **A B C** are bidding on three items **X Y Z**. Set the value to 0 if you want to essentially remove that bidder or item.`32:T646,{ const participants = "ABC"; let output_html = ``; let results = evaluate(bids); let revenue = []; output_html += `

` for (let p = 0; p < participants.length; p++) { const participant = participants[p]; let participants_winning_bid = bids[permutations[results.best_permutation_index][p]]; let new_bids = remove_participant(bids, participant); let new_results = evaluate(new_bids); let discount = results.best_total_value - new_results.best_total_value; revenue.push(participants_winning_bid - discount); output_html += `

Without ${participant}, what happens?

`; output_html += bid_table_html(new_bids); output_html += `

${participant}'s participation `; if (results.best_permutation_index === new_results.best_permutation_index) { output_html += `made no difference to what others received. It`; } output_html += ` increased the total value from ${new_results.best_total_value} to ${results.best_total_value}. This means they get a discount of ${discount}. The original bid was ${participants_winning_bid} so they end up paying ${participants_winning_bid - discount}.`; if (results.best_permutation_index === new_results.best_permutation_index) { output_html += ` They only pay when they cause others to not get what they want.`; } output_html += `

`; } output_html += `

`; return html`${output_html}

The total revenue is ${revenue.join(" + ")} = ${revenue.reduce((a, b) => a+b)}.`; }33:[] 2f:{"title":"Vickery-Clarke-Groves auction example","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"viewof bids = form(html`

Item	Bidder
A	B	C
X\n	\n	\n	\n
Y\n	\n	\n	\n
Z\n	\n	\n	\n

`)","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"md`Now we need to calculate all permutations:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":125,"value":"html`${bid_table_html(bids)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":61,"value":"{\n let tiebreaker = ``;\n let results = evaluate(bids);\n if (results.best_permutation_indices.length > 1) {\n tiebreaker = `${results.best_permutation_indices.slice(1).map(i => permutations_fmt[i]).join(\", \")} ${results.best_permutation_indices.length === 2? 'is':'are'} equally good but we just picked one to break the tie.`;\n }\n return md`This means **${permutations_fmt[results.best_permutation_index]}** is our best choice, with value **${results.best_total_value}**. ${tiebreaker}\n\nThe next step is to calculate the auction *without* each participant.`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":94,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":167,"value":"md`With the default values for the bids, the revenue is very low, only $2. This is in large part because bidder C doesn't value item X or item Y. When there are items that bidders don't care about, the revenue will be low. **Try increasing C's bid on X to 15** to see how the revenue goes way up when all three bidders care about an item. Another way to increase the revenue is to decrease the number of items. **Try decreasing the bids on item Z to 0** to see how the lack of items increases revenue.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":170,"value":"md`I think VCG auctions are really fascinating.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"md`## Implementation details`","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"permutations = ['AX BY CZ', 'AX BZ CY', 'AY BX CZ', 'AY BZ CX', 'AZ BX CY', 'AZ BY CX'].map(s => s.split(' '))","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"permutations_fmt = permutations.map(p => p.join(\" \"))","pinned":false,"hidden":false,"mode":"ojs"},{"id":30,"value":"function bid_table_html(bids) {\n // returning `` instead of html`` because I don't know how to embed html`` inside another html`` :-(\n let results = evaluate(bids);\n let rows = permutations.map((p, i) => `\n ${permutations_fmt[i]}\n :\n ${bids[p[0]]}+\n ${bids[p[1]]}+\n ${bids[p[2]]}=\n ${results.total_value[i]}\n `).join(\"\");\n return `${rows}

`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":105,"value":"function evaluate(bids) {\n let total_value = permutations.map(p => p.map(c => bids[c]).reduce((a, b) => a+b));\n let best_total_value = total_value.reduce((a, b) => Math.max(a, b));\n let best_permutation_indices = total_value.map((v, i) => v === best_total_value? i : -1).filter(i => i >= 0);\n let best_permutation_index = best_permutation_indices[0];\n return {\n total_value,\n best_total_value,\n best_permutation_indices,\n best_permutation_index,\n };\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":120,"value":"function remove_participant(bids, participant_name) {\n let new_bids = {};\n Object.assign(new_bids, bids);\n for (let key of Object.keys(new_bids)) {\n if (key[0] === participant_name) {\n new_bids[key] = 0;\n }\n }\n return new_bids;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}