VCG Auction (C++)

This repository contains a simple C++ implementation of the Vickrey–Clarke–Groves (VCG) mechanism for a combinatorial auction, where bundles of goods are represented using bitmasks.

The program computes:

1. The efficient allocation (maximizing total social welfare).
2. The VCG payment for each bidder (the externality imposed on the others).

The efficient allocation is found using a brute-force search over all bid combinations, so this implementation is intended for small instances only.

---

Repository Structure

• vcg.h
  Defines the Bid structure and declares the main functions, as well as the global variables used by the tests.

• vcg.cpp
  Implements:

  • computeMaxWelfare(...): finds the welfare-maximizing set of non-overlapping bids.
  • computeVCG(): prints the efficient allocation and the VCG payments for each bidder.

• vcg_test.cpp
  Contains a fixed test scenario and executes computeVCG(), also printing the expected output.

---

Data Model

Each bid is represented as:

struct Bid {
    int bidder_id;      // Bidder identifier
    int bundle_mask;    // Bitmask representing the bundle of goods
    double value;       // Declared value for the bundle
};