All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
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}))\)

You can read more about combinatorial auctions in [3].

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:

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: