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; };
bidders, items, get_bids, get_value, get_items
);
// determine winners
Value social_welfare = 0;
bidders, items, get_bids, get_value, get_items
);
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.