Index:
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}))\)
You can read more about combinatorial auctions in [3].
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:
get_copies_num_archetype {
CopiesNum operator()(Item);
}
Default component: paal::utils::return_one_functor (Single-Unit Combinatorial Auction)
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
We start with defining the auction components:
Then we create the auction:
We can use it as follows:
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:
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
We start with defining the auction components:
Then we create the auction:
We can use it as follows:
\(\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:
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
We start with defining the auction components:
Then we create the auction:
We can use it as follows:
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\).
Adapter functions:
Example:
Complete example: single_minded_example.cpp
1.8.5