Combinatorial Auctions

Index:

# Preliminaries

We have a set $$U$$ of $$|U| = m$$ indivisible items that are concurrently being auctioned among a set $$K$$ of $$|K| = k$$ bidders. Every bidder $$i \in K$$ has a valuation function $$v_i : 2^U \to \mathbb{R}$$, $$v_i(S)$$ is the value that bidder $$i$$ obtains if she receives bundle of items $$S$$. A valuation must be monotone: for $$S \subseteq T$$ we have that $$v_i(S) \leq v_i(T)$$ and it must be normalized: $$v_i(\emptyset) = 0$$. There are $$b_j\geq1$$ copies of each item $$j$$. If all $$b_j$$ are equal to 1 then our auction is a Single-Unit Combinatorial Auction, otherwise we call it Multi-Unit Combinatorial Auction. An allocation of items $$S_1, \cdots, S_k$$ is valid if every item $$j$$ is allocated to at most $$b_j$$ bidders. The social welfare obtained by an allocation is $$\sum_i v_i(S_i)$$. Apart from receiving a bundle of items $$S_i$$, bidder $$i$$ might also be charged a price $$p_i$$. In such case her utility is equal to $$v_i(S_i) - p_i$$.

In winner determination problem the goal is to find a socially efficient allocation, that is one that maximizes social welfare among all allocations.

Let $$V = V_1 \times \cdots \times V_k$$ denote the space of all bidders' valid valuations, and let $$A$$ be the set of all items allocations. A mechanism $$(f, p)$$ for an auction is composed of an allocation mechanism $$f: V \to A$$ and pricing scheme $$p_i : V \to \mathbb{R}$$ for each bidder $$i$$. A mechanism could be randomized, in which case $$f(v), p_i(v)$$ and thus bidders' utilities are all random variables.

Here we use $$v_{-i}$$ to denote the tuple $$(v_1, \cdots, v_{i-1}, v_{i+1}, \cdots, v_k)$$ and $$V_{-i} = \prod_{j \neq i}V_j$$.

In the usual setting valuations of the bidders are private knowledge. In such case bidder $$i$$ might decide to "strategize", i.e., report valuation $$v_i$$ that is different from her real valuation $$\bar{v}_i$$ (throughout, we will be using this notation to denote real valuation), hoping that this will improve her utility. A desirable property for a mechanism is therefore to satisfy truthfulness, wherein each player maximizes her utility by reporting her true valuation. Formally:

A deterministic mechanism $$(f, p)$$ is truthful if for any bidder $$i$$, any $$v_{-i} \in V_{-i}$$, and any $$\bar{v}_i, v'_i \in V_i$$ we have $$\bar{v}_i(f(\bar{v}_i, v_{-i})) - p_i(\bar{v}_i, v_{-i}) \geq \bar{v}_i(f(v'_i, v_{-i})) - p_i(v'_i, v_{-i})$$

A randomized mechanism $$(f, p)$$ is truthful in expectation if for any bidder, any $$v_{-i} \in V_{-i}$$, and any $$\bar{v}_i, v'_i \in V_i$$ we have $$E(\bar{v}_i(f(\bar{v}_i, v_{-i})) - p_i(\bar{v}_i, v_{-i})) \geq E(\bar{v}_i(f(v'_i, v_{-i})) - p_i(v'_i, v_{-i}))$$

# Query Model Interface

Specifying a valuation in a combinatorial auction requires provididing a value for each of the possible $$2^m - 1$$ nonempty subsets. A naive representation would thus require $$2^m - 1$$ real numbers to represent a valuation, which is clearly impractical for more than about three dozen items. To overcome this problem, we use the interface for representing valuations, in which bidders are represented as oracles. There are different kinds of oracles, answering different types of queries:

• Value Query: The auctioneer presents a bundle $$S$$, the bidder reports her value $$v(S)$$ for this bundle.

In our library auctions with value query oracles are represented as class paal::auctions::value_query_auction_components (created using Components class), with the following components:

1. bidders range of bidders
2. items range of items
3. get_copies_num functor that returns the number of copies of the given item.
            get_copies_num_archetype {
CopiesNum operator()(Item);
}

Default component: paal::utils::return_one_functor (Single-Unit Combinatorial Auction)
4. value_query functor representing a value query oracle.
            value_query_archetype {
template <class ItemSet>
Value operator()(Bidder, const ItemSet&);
}

ItemSet is a Forward Range of Item elements that has an adequate size_type count(Item) method.

Example:
Complete example: value_query_example.cpp

namespace pa = paal::auctions;
using Bidder = std::string;
using Item = std::string;
using Value = unsigned int;
const std::vector<Bidder> bidders {"Pooh Bear", "Rabbit"};
const std::vector<Item> items {"honey", "baby carrot", "carrot", "jam"};
int operator()(Item item) const
{
return item == "baby carrot" ? 2 : 1;
}
};
template <class ItemSet>
Value operator()(Bidder bidder, const ItemSet& item_set) const
{
if (bidder == "Pooh Bear")
return item_set.count("honey") > 0 ? 10 : 0;
assert(bidder == "Rabbit");
Value res = 0;
for (Item item: item_set)
if (item.find("carrot") != std::string::npos) ++res;
return res;
}
};

Then we create the auction:

);

We can use it as follows:

std::cout << "bidders: ";
boost::copy(
auction.get<pa::bidders>(), std::ostream_iterator<Bidder>(std::cout, ", ")
);
std::cout << std::endl;
std::cout << "items with copies numbers: ";
for (auto item: auction.get<pa::items>())
std::cout << item << " = " << auction.call<pa::get_copies_num>(item) << ", ";
std::cout << std::endl;
std::cout << "pooh bear valuation: " <<
auction.call<pa::value_query>("Pooh Bear", std::set<Item>{"jam", "honey"}) <<
std::endl;
std::cout << "rabbit valuation: " <<
auction.call<pa::value_query>(
"Rabbit", std::unordered_set<Item>{"carrot", "baby carrot"}) <<
std::endl;

• Demand Query: The auctioneer presents item prices $$p_j$$ for each $$j \in U$$; the bidder reports a demand bundle under these prices, i.e., some set $$S$$ that maximizes utility $$v(S) - \sum_{i \in S} p_i$$.

Being able to answer demand queries appears to be a natural requirement from a bidder, as without this ability, if the bidder comes to a market in which the items have prices, she herself would not know what she prefers to buy.

In our library auctions with demand query oracles are represented as class paal::auctions::demand_query_auction_components (created using Components class), with the following components:

1. bidders as above
2. items as above
3. get_copies_num as above
4. demand_query functor representing a demand query oracle.
            demand_query_archetype {
template<class GetPrice>
std::pair<ItemsBundle, Value> operator()(Bidder, GetPrice);
}

GetPrice is a functor that for any item returns its price. The oracle should return a pair consisting of the result bundle $$S^*$$ and its corresponding utility $$v(S^*) - \sum_{i \in S^*} p_i$$.

Example:
Complete example: demand_query_example.cpp

namespace pa = paal::auctions;
namespace pds = paal::data_structures;
using Bidder = std::string;
using Item = std::string;
using Items = std::vector<Item>;
using Value = int;
const std::vector<Bidder> bidders {"Pooh Bear", "Rabbit"};
const Items items {"honey", "baby carrot", "carrot", "jam"};
template <class GetPrice>
std::pair<Items, Value>
operator()(Bidder bidder, GetPrice get_price) const
{
if (bidder == "Pooh Bear") {
const Value util = 10 - get_price("honey");
if (util <= 0) return std::make_pair(Items{}, 0);
return std::make_pair(Items{"honey"}, util);
}
assert(bidder == "Rabbit");
const Value baby_val = 2, val = 3;
auto const baby_price = get_price("baby carrot"), price = get_price("carrot");
const Value baby_util = baby_val - baby_price,
util = val - price, both_util = baby_val + val - baby_price - price;
if (baby_util <= 0 && util <= 0 && both_util <= 0) return std::make_pair(Items{}, 0);
if (baby_util >= util && baby_util >= both_util)
return std::make_pair(Items{"baby carrot"}, baby_util);
if (util >= both_util)
return std::make_pair(Items{"carrot"}, util);
return std::make_pair(Items{"baby carrot", "carrot"}, both_util);
}
};

Then we create the auction:

bidders, items, demand_query_func()
);

We can use it as follows:

auto get_price = [](Item item) { return item == "honey" ? 5 : 2; };
std::cout << "pooh bear buys: ";
auto got_pooh_bear = auction.call<pa::demand_query>("Pooh Bear", get_price);
boost::copy(got_pooh_bear.first, std::ostream_iterator<Item>(std::cout, ", "));
std::cout << std::endl;
std::cout << "rabbit oracle buys: ";
auto got_rabbit = auction.call<pa::demand_query>("Rabbit", get_price);
boost::copy(got_rabbit.first, std::ostream_iterator<Item>(std::cout, ", "));
std::cout << std::endl;

• $$\gamma$$-Oracle Query: The auctioneer presents $$\gamma \geq 1$$, item prices $$p_j$$ for each $$j \in U$$, and a bidding threshold $$z \geq 0$$; the bidder either reports that $$v(S) \leq z$$ for all sets $$S$$ (i.e., she cannot buy anything) or otherwise she outputs some set $$S^*$$ with $$v(S^*) > z$$ such that
$$\frac{\sum_{j \in S^*}p_j}{v(S^*) - z} \leq \gamma \cdot \frac{\sum_{j \in S}p_j}{v(S) - z}$$ for all $$S \subseteq U$$ with $$v(S) > z$$.

$$\gamma$$-oracle queries are not as natural as previously mentioned types of queries. However, for many natural bidding languages one can write a simple, polynomial time implementation of such oracle. Our library provides interfaces for creating $$\gamma$$-oracle auctions for a number of such bidding languages, see Bidding Languages Interface.

In our library auctions with $$\gamma$$-oracle valuations are represented as class paal::auctions::gamma_oracle_auction_components (created using Components class), with the following components:

1. bidders as above
2. items as above
3. get_copies_num as above
4. gamma value of $$\gamma$$
5. gamma_oracle functor representing a $$\gamma$$-oracle.
            gamma_oracle_archetype {
template<class GetPrice, class Threshold>
boost::optional<std::pair<ItemsBundle, paal::data_structures::fraction<Value, Value>>>
operator()(Bidder, GetPrice, Threshold);
}

GetPrice is a functor that for any item returns its price. Threshold is a parameter $$z$$ from $$\gamma$$-oracle definition. If $$v(S) \leq z$$ for all sets $$S$$ then oracle should return boost::none. Otherwise it should return a pair consisting of the result bundle $$S^*$$ and its corresponding fraction $$\frac{\sum_{j \in S^*}p_j}{v(S^*) - z}$$ (represented as object of class paal::data_structures::fraction).

Example:
Complete example: gamma_oracle_example.cpp

namespace pa = paal::auctions;
namespace pds = paal::data_structures;
using Bidder = std::string;
using Item = std::string;
using Items = std::vector<Item>;
using Value = int;
const std::vector<Bidder> bidders {"Pooh Bear", "Rabbit"};
const Items items {"honey", "baby carrot", "carrot", "jam"};
const int gamma_val = 2;
template <class GetPrice, class Threshold>
boost::optional<std::pair<Items, Frac>>
operator()(Bidder bidder, GetPrice get_price, Threshold z) const {
if (bidder == "Pooh Bear") {
const Value val = 10;
if (val <= z) return boost::none;
return std::make_pair(Items{"honey"}, Frac(get_price("honey"), val - z));
}
assert(bidder == "Rabbit");
const Value baby_val = 2, val = 3;
auto const baby_price = get_price("baby carrot");
auto const price = get_price("carrot");
auto const baby_frac = Frac(baby_price, baby_val - z),
frac = Frac(price, val - z),
both_frac = Frac(baby_price + price, baby_val + val - z);
auto check = [=](Frac candidate, Frac other1, Frac other2) {
if (candidate.den <= 0) return false;
auto check_single = [=](Frac candidate, Frac other) {
return other.den <= 0 || candidate <= gamma_val * other;
};
return check_single(candidate, other1) && check_single(candidate, other2);
};
if (check(baby_frac, frac, both_frac))
return std::make_pair(Items{"baby carrot"}, baby_frac);
if (check(frac, baby_frac, both_frac))
return std::make_pair(Items{"carrot"}, frac);
if (check(both_frac, baby_frac, frac))
return std::make_pair(Items{"baby carrot", "carrot"}, both_frac);
return boost::none;
}
};

Then we create the auction:

bidders, items, gamma_oracle_func(), gamma_val
);

We can use it as follows:

auto get_price_func = [](Item item) { return item == "honey" ? 5 : 2; };
std::cout << "pooh bear buys: ";
auto got_pooh_bear =
auction.call<pa::gamma_oracle>("Pooh Bear", get_price_func, 10);
if (!got_pooh_bear)
std::cout << "nothing";
else
boost::copy(got_pooh_bear->first, std::ostream_iterator<Item>(std::cout, ", "));
std::cout << std::endl;
std::cout << "rabbit oracle buys: ";
auto got_rabbit = auction.call<pa::gamma_oracle>("Rabbit", get_price_func, 1);
if (!got_rabbit)
std::cout << "nothing";
else
boost::copy(got_rabbit->first, std::ostream_iterator<Item>(std::cout, ", "));
std::cout << std::endl;

# Bidding Languages Interface

Alternative approach for succinctly representing bidders' valuations is to use so called bidding languages. Such language allows to encode "common" types of valuations in a simpler way than by using oracles. Still, algorithms in our library expect auctions created via Query Model Interface. Therefore, in order to solve an auction with a valuation encoded by some bidding language we need to first transform this valuation into a proper oracle. For the convenience of the user, we provide adequate adapter functions for a number of well-established bidding languages:

• Single-Minded Bids: A single-minded bid is a pair $$(S^*, v^*)$$, where $$S^*$$ is a subset of items and $$v^*$$ is a value. It corresponds to a valuation such that $$v(S) = v^*$$ for all $$S \supseteq S^*$$, and $$v(S) = 0$$ for all other $$S$$.

Example:
Complete example: single_minded_example.cpp

int main()
{
using Bidder = std::string;
using Item = std::string;
using Items = std::unordered_set<Item>;
using Value = int;
using Bid = std::pair<Items, Value>;
namespace pa = paal::auctions;
std::unordered_map<Bidder, Bid> bids {
{"Pooh Bear", {{"honey"}, 10}},
{"Rabbit", {{"baby carrot", "carrot"}, 2}},
};
std::vector<Bidder> bidders {"Pooh Bear", "Rabbit"};
std::vector<Item> items {"honey", "baby carrot", "carrot", "jam"};
auto get_value = [&](Bidder bidder) { return bids.at(bidder).second; };
auto get_items = [&](Bidder bidder) -> const Items& { return bids.at(bidder).first; };
auto get_copies_num = [](Item item) { return item == "baby carrot" ? 2 : 1; };
bidders, items, get_value, get_items, get_copies_num
);
Items bundle {"carrot", "honey", "jam"};
std::cout << "pooh bear valuation: " <<
auction.call<pa::value_query>("Pooh Bear", bundle) << std::endl;
std::cout << "rabbit valuation: " <<
auction.call<pa::value_query>("Rabbit", bundle) << std::endl;
return 0;
}

• Xor Bids: A xor bid is a collection of pairs $$(S_1, v_1), \cdots (S_t, v_t)$$, where each $$S_i$$ is a subset of items and each $$v_i$$ is a value. It corresponds to a valuation such that $$v(S) = \max_{i | S_i \subseteq S} v_i$$.

Example:
Complete example: xor_bids_example.cpp
int main()
{
using Bidder = std::string;
using Item = std::string;
using Items = std::unordered_set<Item>;
using Value = int;
using Bid = std::pair<Items, Value>;
using Bids = std::vector<Bid>;
namespace pa = paal::auctions;
std::unordered_map<Bidder, Bids> bids {
{"Pooh Bear", {
{{"honey"}, 10},
}},
{"Rabbit", {
{{"baby carrot"}, 1},
{{"carrot"}, 2},
{{"baby carrot", "carrot"}, 4},
}},
};
std::vector<Bidder> bidders {"Pooh Bear", "Rabbit"};
std::vector<Item> items {"honey", "baby carrot", "carrot", "jam"};
auto get_bids = [&](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 get_copies_num = [](Item item) { return item == "baby carrot" ? 2 : 1; };
bidders, items, get_bids, get_value, get_items, get_copies_num
);
Items bundle {"carrot", "honey", "baby carrot"};
std::cout << "pooh bear valuation: " <<
auction.call<pa::value_query>("Pooh Bear", bundle) << std::endl;
std::cout << "rabbit valuation: " <<
auction.call<pa::value_query>("Rabbit", bundle) << std::endl;
return 0;
}