Winner Determination in MUCA

Problem definition.

We have a set of bidders \(K\), \(|K| = k\) and a set of all kinds of goods for sale \(U\), \(|U| = m\). Each good \( e \in U\) is available in \(b_e \in \mathbb{N}\) copies, \( B = min_e \{b_e\}\). Let \(v_{i,S} > 0\) be the valuation of a bidder \( i \in K\) for a bundle \(S \subseteq U\).

Winner determination problem can be formulated as the following integer linear program:

\begin{eqnarray*} \mbox{max:} & \sum_{i \in K} \sum_{S \subseteq U} v_{i,S} x_{i,S} & \\ \mbox{subject to:} & & \\ & \sum_{i \in K} \sum_{S: S \subseteq U, e \in S} x_{i,S} \leq b_e & \mbox{ for every } e\in U\\ & \sum_{S \subseteq U} x_{i,S} \leq 1 & \mbox{ for every } i\in K\\ & x_{i,S} \in \{0,1\} & \mbox{ for every } i\in K, S \subseteq U\\ \end{eqnarray*}

where \(x_{i,S}\) is 1 iff a bidder \( i \) gets assigned a bundle \( S \). Bidders are supposed to specify their bids through a \(\gamma\)-oracle (see gamma oracle query): given prices \( p_j \) for each \( j \in U\), and a bidding threshold \( z_i \geq 0 \), a \(\gamma\)-oracle of a bidder \( i \) either decides that \(v_{i,S} \leq z_i\) for all \(S \subseteq U\) (i.e., \( i \) cannot buy anything), or otherwise the oracle outputs \(S^* \subseteq U\) such that \( \frac{\sum_{j \in S^*} p_j}{v_{i,S^*} - z_i} \leq \gamma \cdot \frac{\sum_{j \in S} p_j}{v_{i,S} - z_i} \) for all \(S \subseteq U\) with \(v_{i, S} > z_i \).

Solution

We solve the problem using a combinatorial, primal dual algorithm.

Example

int main()
{
   using Bidder = std::string;
   using Item = std::string;
   using Items = std::unordered_set<Item>;
   using Value = double;
   using Bid = std::pair<Items, Value>;
   using Bids = std::vector<Bid>;

   // create auction
   const std::unordered_map<Bidder, Bids> bids {
      {"John", {
         {{"ball", "kite"}, 2},
         {{"umbrella"}, 3},
         {{"orange"}, 1.75},
         {{"ball", "kite", "umbrella"}, 5},
         {{"ball", "kite", "orange", "umbrella"}, 6.75},
      }},
      {"Bob", {
         {{"orange"}, 1.5},
         {{"apple"}, 2.0},
         {{"apple", "orange"}, 4},
      }},
      {"Steve", {
         {{"apple"}, 1},
         {{"umbrella"}, 4},
         {{"apple", "umbrella"}, 5},
      }},
   };
   const std::vector<Bidder> bidders {"John", "Bob", "Steve"};
   const std::vector<Item> items {"apple", "ball", "orange", "kite", "umbrella"};
   auto get_bids = [&](const Bidder& bidder) -> const Bids& { return bids.at(bidder); };
   auto get_value = [](const Bid& bid) { return bid.second; };
   auto get_items = [](const Bid& bid) -> const Items& { return bid.first; };
   auto auction = paal::auctions::make_xor_bids_to_gamma_oracle_auction(
      bidders, items, get_bids, get_value, get_items
   );

   // determine winners
   Value social_welfare = 0;
   auto valuation = paal::auctions::make_xor_bids_to_value_query_auction(
      bidders, items, get_bids, get_value, get_items
   );
   paal::auctions::determine_winners_in_gamma_oracle_auction(
      auction,
      boost::make_function_output_iterator([&](std::pair<Bidder, Items> p)
      {
         auto bidder = p.first;
         auto& cur_items = p.second;
         social_welfare += valuation.call<paal::auctions::value_query>(bidder, cur_items);
         std::cout << bidder << " got bundle: ";
         boost::copy(cur_items, std::ostream_iterator<Item>(std::cout, ", "));
         std::cout << std::endl;
      })
   );
   std::cout << "social welfare: " << social_welfare << std::endl;

   return 0;
}

complete example is winner_determination_in_MUCA_example.cpp

Approximation Ratio

\(e \cdot (2 \gamma + 1) \cdot m^{1 / (B + 1)}\).

Complexity

Time complexity: \(O(m + k^2 * \log_{1 + 2 \gamma} (c_{max} / c_{min}) * GO_{time})\), where \(GO_{time}\) is the time complexity of one gamma oracle query, \(c_{max} / c_{min}\) is respectively the maximum / minimum \(c_{i, S}\).
Memory complexity: \(O(k + \min(\sum_{j \in U} b_e, m * k) + GO_{mem})\), where \(GO_{mem}\) is the memory complexity of one gamma oracle query.

References

The algorithm is described in [3], section 6.