Vickrey–Clarke–Groves Auction Implementation (VCG Mechanism)

8 minute read

Published:

This notebook and source code can be find via my github

import numpy as np
import pandas as pd
import random
from itertools import combinations
from sklearn.externals import joblib
from tqdm import tqdm_notebook
from matplotlib import pyplot as plt
import numba as nb

Introduce VCG Auction and implement it

What is VCG Auction? From Wiki :

Consider an auction where a set of identical products are being sold. Bidders can take part in the auction by announcing the maximum price they are willing to pay to receive N products. Each buyer is allowed to declare more than one bid, since its willingness-to-pay per unit might be different depending on the total number of units it receives. Bidders cannot see other people’s bids at any moment since they are sealed (only visible to the auction system). Once all the bids are made, the auction is closed.

All the possible combinations of bids are then considered by the auction system, and the one maximizing the total sum of bids is kept, with the condition that it does not exceed the total amount of products available and that at most one bid from each bidder can be used. Bidders who have made a successful bid then receive the product quantity specified in their bid. The price they pay in exchange, however, is not the amount they had bid initially but only the marginal harm their bid has caused to other bidders (which is at most as high as their original bid).

This marginal harm caused to other participants (i.e. the final price paid by each individual with a successful bid) can be calculated as: (sum of bids of the auction from the best combination of bids excluding the participant under consideration) - (what other winning bidders have bid in the current (best) combination of bids). If the sum of bids of the second best combination of bids is the same as that of the best combination, then the price paid by the buyers will be the same as their initial bid. In all other cases, the price paid by the buyers will be lower.

At the end of the auction, the total utility has been maximized since all the goods have been attributed to the people with the highest combined willingness-to-pay. If agents are fully rational and in the absence of collusion, we can assume that the willingness to pay have been reported truthfully since only the marginal harm to other bidders will be charged to each participant, making truthful reporting a weakly-dominant strategy. This type of auction, however, will not maximize the seller’s revenue unless the sum of bids of the second best combination of bids is equal to the sum of bids of the best combination of bids.

class VCG_Auction_Process(object):
    def __init__(self,value_mat_origin):
        self.value_mat_origin=value_mat_origin
        self.value_mat=self.value_mat_origin
        self.allocation=self.value_mat.columns # For single-item condition
        self.best_price=0 #Initialization
    @nb.jit
    def who_win(self):
        '''
        Pick up the winners for each item, if bids are the same, then a winner will be randomly picked
        '''
        self.winner_list=[] #Bidder index for each winner of the item
        self.second_price_list=[]
        winner_temp=[]
        for item_set in self.allocation:
            item_represent=item_set[0] #Because all other items in the set share the same value
            winner_temp.append(np.where(self.value_mat[item_represent]==np.max(self.value_mat[item_represent]))[0])
        for item_set_index,winner in enumerate(winner_temp):
            item_set=self.allocation[item_set_index] # The item set like [0,1]
            item_represent=item_set[0]# Representation
            if len(winner)>1:
                #print("Item set {:} has multiple winner: {:}".format(item_set,winner))
                random.seed(10)
                self.winner_list.append(random.choice(winner))
                second_price=sorted(self.value_mat[item_represent])[-2]
                # Add the payment of each winner, pay your value if the "same" occur
                self.second_price_list.append(second_price) 
            else:
                self.winner_list.append(winner[0])
                second_price=sorted(self.value_mat[item_represent])[-2]
                self.second_price_list.append(second_price)
        #print(self.value_mat)
        #print(self.winner_list)
        return self.winner_list,self.second_price_list
    
    def winner_price(self):
        '''
        Calculate the price that the winner does to other agents and the mechanism will charge the price for each winner
        
        Make sure function who_win is run in advance
        '''
        self.welfare_list=[] # List for the welfare contributed by the winner. the sum of this list is the social welfare
        self.price_list=[] # List for the price that the winner charged, for losers they don't pay
        value_winner_list=[]
        value_without_winner_list=[]
        # Get the value list of winner
        # With the winners
        for item_set_index,winner in enumerate(self.winner_list):
            item_set=self.allocation[item_set_index] # The item set like [0,1]
            item_represent=item_set[0]# Representation
            value_winner_list.append(self.value_mat[item_represent].iloc[winner])
        self.welfare_list=value_winner_list
        # Without the winners
        value_without_winner_list=self.second_price_list
        # Contribution of the winner
        
        ctrib_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,value_without_winner_list)))
        # Price of the winner charged by the mechanism
        self.price_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,ctrib_list)))
        return self.price_list,self.welfare_list
    def allocate_items(self,allocation):
        '''
        Allocate different sets of items
        '''
        self.allocation=allocation# Consider a finxed allocation case
        self.update_value_mat()
    @nb.jit
    def update_value_mat(self):
        '''
        Update the value of bidders for item sets as the value of item sets are the maximum value inside
        '''
        self.value_mat=self.value_mat_origin.copy()
        for set_index,item_set in enumerate(self.allocation):
            for bidder,value in self.value_mat.iterrows():
                self.value_mat.iloc[bidder][item_set]=np.max(self.value_mat.iloc[bidder][item_set])
                
    def find_best_allocation_price(self,current_price):
        if current_price>=self.best_price:
            self.best_allocation=self.allocation # Initialization
            self.best_price=current_price
        
    def begin(self,possible_allocations):
        f=open('allocation_price.txt','w+')
        for allocation in tqdm_notebook(possible_allocations): #Define your possible_allocations here:
            self.allocate_items(allocation)
            self.who_win()
            self.winner_price()
            self.find_best_allocation_price(np.sum(np.sum(self.price_list)))
            f.write('For Allocation: {:} Pirce charged by mechanism {:} and total {:}\n'.format(
            self.allocation,self.price_list,np.sum(self.price_list)))
        f.close()
        print('Best allocation: {:} and the mechanism charges {:}'.format(self.best_allocation,self.best_price))

You only need to define your possible allocation of items for iteration

Enumerate all the allocation to find the best allocation and price

# variables
value_mat_origin=pd.read_table('Assignment#2-Q8-values.txt',delimiter=' ',header=None,sep='\\t')
value_mat_origin=value_mat_origin.drop([8],axis=1)
value_mat_origin
01234567
02685954217634
1111853940221735
21925502449232131
32352345142138
4123542847171433
52227572743192336
6211955284616532
72012561841161039
824582848261530
920951104420637

Generate all possible allocation

columns=value_mat_origin.columns
columns=list(columns)
possible_allocations_8=[]
possible_allocations_7=[]
possible_allocations_6=[]
possible_allocations_5=[]
possible_allocations_4=[]
possible_allocations_3=[]
possible_allocations_2=[]
possible_allocations_1=[]
def divide(item,l):
    ll=l.copy()
    ll.remove(item)
    return ll
def merge_unit(two_item,l):
    '''
    Just deal with two items
    '''
    if len(two_item)>2:
        print('Emission of merge_unit')
    else:
        return [   [ [two_item[0]],[two_item[1]],l],[[two_item[0],two_item[1]],l]]
    
def add_allocation(unit_two,allocations):
    allocations.append(unit_two[0])
    allocations.append(unit_two[1])
    
def merge_three(three_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in three_items]+[l]
    allocations.append(head1)
    # two item in each set
    for the_left in three_items:
        l2=divide(the_left,three_items)
        head2=[[the_left],l2]+[l]
        allocations.append(head2)
    # Three item in each set
    head3=[three_items,l]
    allocations.append(head3)
    
def merge_four(four_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in four_items]+[l]
    allocations.append(head1)
    # two items in each set
    for two_item_set in combinations(four_items,2):
        two_item_set=list(two_item_set)
        left_item_set=list(set(four_items)-set(two_item_set))
        merge_three((left_item_set+two_item_set),l,allocations)
    # three items in each set
    for the_left in four_items:
        l3=divide(the_left,four_items)
        head3=[[the_left],l3]+[l]
        allocations.append(head3)
    # Four item in each set
    head4=[four_items,l]
    allocations.append(head4)

def merge_five(five_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in five_items]+[l]
    allocations.append(head1)
    # two items in each set
    for two_item_set in combinations(five_items,2):
        two_item_set=list(two_item_set)
        left_item_set=five_items.copy()
        for i in range(len(two_item_set)):
            left_item_set.remove(two_item_set[i])
        merge_four((left_item_set+two_item_set),l,allocations)
    # three items in each set (at most)
    for three_item_set in combinations(five_items,3):
        three_item_set=list(three_item_set)
        left_item_set=five_items.copy()
        for i in range(len(three_item_set)):
            left_item_set.remove(three_item_set[i])
        merge_three((left_item_set+three_item_set),l,allocations)
        
def merge_six(six_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in six_items]+[l]
    allocations.append(head1)
    # two items in the maximum set(at moist)
    for two_item_set in combinations(six_items,2):
        two_item_set=list(two_item_set)
        left_item_set=six_items.copy()
        for i in range(len(two_item_set)):
            left_item_set.remove(two_item_set[i])
        # Left set is all 1-item set
        head2=[[e] for e in left_item_set]+[two_item_set]+[l]
        allocations.append(head2)
        # Left set has 1 two-item set
        for left_two_item_set in combinations(left_item_set,2):
            left_two_item_set=list(left_two_item_set)
            left_left_item_set=left_item_set.copy()
            for j in range(2):
                left_left_item_set.remove(left_two_item_set[j])
                head3=[[e] for e in left_left_item_set]+[left_two_item_set]+[two_item_set]+[l]
                allocations.append(head3)
            # All the six-items divied into three two-item sets
            head4=[left_left_item_set]+[left_two_item_set]+[two_item_set]+[l]
            allocations.append(head4)
# 8 item sets
possible_allocations_8=[[[0,1,2,3,4,5,6,7]]]
joblib.dump(possible_allocations_8,'possible_allocations_8.asv')
print(len(possible_allocations_8))
1
# 7 item sets
for item in columns:
    possible_allocations_7.append([[item],divide(item,columns)])
joblib.dump(possible_allocations_7,'possible_allocations_7.asv')
print(len(possible_allocations_7))
8
# 6 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        unit=merge_unit([item,item2],l2)
        add_allocation(unit,possible_allocations_6)
joblib.dump(possible_allocations_6,'possible_allocations_6.asv')
print(len(possible_allocations_6))
112
# 5 item sets        
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            merge_three([item,item2,item3],l3,possible_allocations_5)
joblib.dump(possible_allocations_5,'possible_allocations_5.asv')
print(len(possible_allocations_5))
1680
# 4 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                merge_four([item,item2,item3,item4],l4,possible_allocations_4)
joblib.dump(possible_allocations_4,'possible_allocations_4.asv')
print(len(possible_allocations_4))
70560
# 3 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                for item5 in l4:
                    l5=divide(item5,l4)
                    merge_five([item,item2,item3,item4,item5],l5,possible_allocations_3)
joblib.dump(possible_allocations_3,'possible_allocations_3.asv')
print(len(possible_allocations_3))
5651520
# 2 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                for item5 in l4:
                    l5=divide(item5,l4)
                    for item6 in l5:
                        l6=divide(item6,l5)
                        merge_six([item,item2,item3,item4,item5,item6],l6,possible_allocations_2)
joblib.dump(possible_allocations_2,'possible_allocations_2.asv')
print(len(possible_allocations_2))
5765760
# 1 item sets
possible_allocations_1.append([[e] for e in columns])
possible_allocations_1=possible_allocations_1[0]
# Dump data
joblib.dump(possible_allocations_1,'possible_allocations_1.asv')
print(len(possible_allocations_1))
8

Run VCG Auction

vcg=VCG_Auction_Process(value_mat_origin)
vcg.begin(possible_allocations_6)
A Jupyter Widget



Best allocation: [[7], [4], [0, 1, 2, 3, 5, 6]] and the mechanism charges 144