Fractional 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\). We want to solve the linear programming relaxation LPR of the winner determination problem:

\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_j & \mbox{ for every } j\in U\\ & \sum_{S \subseteq U} x_{i,S} \leq 1 & \mbox{ for every } i\in K\\ & x_{i,S} \geq 0 & \mbox{ for every } i\in K, S \subseteq U\\ \end{eqnarray*}

In the integer program, each variable \(x_{i,S}\) equals 1 if a bidder \(i\) receives the bundle \(S\), and zero otherwise. In the relaxation these variables correspond to fractional allocations.

Bidders are supposed to specify their bids through a demand query oracle: given prices \( p_j \) for each \( j \in U\), the bidder \(i\) reports \(S \subseteq U\) that maximizes \(v_{i,S} - \sum_{j \in S} p_j\).

Solution

We consider the following dual linear program DLPR:

\begin{eqnarray*} \mbox{min:} & \sum_{i \in K} u_i + \sum_{j \in U} b_j p_j & \\ \mbox{subject to:} & & \\ & u_i + \sum_{j \in S} p_j \geq v_{i,S} & \mbox{ for every } i \in K, S \subseteq U\\ & u_i \geq 0, p_j \geq 0 & \mbox{ for every } i \in K, j \in U\\ \end{eqnarray*}

This program has \(n + m\) variables but an exponential number of constraints. We solve it with the row generation technique, using demand queries to implement the separation oracle. Then we take the "reduced dual" where only the constraints encountered by the row generation algorithm exist, and look at its dual. This dual has the same solution as LPR but only as many variables as number of iterations of row generation algorithm. We can thus solve it directly.

example:

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

   // create auction
   const std::unordered_map<Bidder, Bids> bids {
      {"John", {
         {{"lemon", "orange"}, 1},
         {{"apple", "ball"}, 1},
      }},
      {"Bob", {
         {{"lemon", "apple"}, 1},
         {{"orange", "ball"}, 1},
      }},
   };
   const std::vector<Bidder> bidders {"John", "Bob"};
   const std::vector<Item> items {"apple", "ball", "orange", "lemon"};
   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_demand_query_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(
      std::move(bidders), std::move(items), get_bids, get_value, get_items
   );
   paal::auctions::fractional_determine_winners_in_demand_query_auction(
      auction,
      boost::make_function_output_iterator([&](Assignment a)
      {
         auto bidder = std::get<0>(a);
         auto& cur_items = std::get<1>(a);
         auto fraction = std::get<2>(a);
         social_welfare += fraction * valuation.call<paal::auctions::value_query>(bidder, cur_items);
         std::cout << bidder << " got a fraction " << fraction << " of 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 fractional_winner_determination_in_MUCA_example.cpp

The complexity

Time complexity: \(O(rows * (k * DQ_{time}) * LP_{time}(k + m, rows) + LP_{time}(k * rows, m + k))\) where \(rows\) is the number of rows generated by the row generation technique, \(DQ_{time}\) is the time complexity of one demand query, \(LP_{time}(col, row)\) is the time complexity of solving the \(LP\) with \(O(cols)\) columns and \(O(row)\) rows.

Memory complexity: \(O(DQ_{mem} + LP_{mem}(k + m, rows) + LP_{mem}(k * rows, m + k))\) where \(DQ_{mem}\) is the memory complexity of one demand query, \(LP_{mem}(col, row)\) is the memory complexity of solving the \(LP\) with \(O(col)\) columns and \(O(row)\) rows.

References

Algorithm is based on proof of theorem 11.24 described in [17], section 11.5.