Bidding language

The structure of the bidding language in an auction is important because it can restrict the ability of agents to express their preferences. In addition, the expressiveness allowed also has a big impact of the the properties of the auction. This has prompted research that examines bidding languages and their expressiveness and the impact on winner determination [20, 19, 13]. In this section we will outline two aspects of bidding languages that are central to auctions (i) the structure of bids allowed, and (ii) the rules specified by the bid that restrict the choice of bids by the seller. 

Indivisible Bids. Now, suppose that bidders specify all-or-nothing constraints on the bids and state that the bids are indivisible. In addition, suppose that the bidders also submit multiple bids with an XOR bidding language. Let Mi denote the number of bids from supplier i, and N denote the number of suppliers. The winner determination problem can be formulated as a knapsack problem, introducing xij 0,1 to indicate that bid j from bidder i is... 

Following the notation in Section 2.3, let = (1,..., iV) denote the set of items for sale. The bidders are allowed to specify bundles S C Q, with a single price on the entire bundle and submit bids for multiple bundles via an XOR bidding language. We formulate this problem by introducing a decision variable Xi S) for each bundle S offered by bidder i. Each bidder provides a bid set Bi C 2. Let Pi S) denote the price offered by agent i for bundle 5, and consider bids in an exclusive-or language. 

This is a set packing formulation and is NP-hard [89]. There are special cases under which the structure of this problem simplifies and allows for polynomial time solutions. Many special cases arise out of constraints that reduce the constraint matrix to be totally unimodular [35]. A common example is the case where adjacent plots of land are being sold and bidders might want multiple plots but they need to be adjacent. However, real world problems will often not satisfy the fairly severe restrictions that provide a totally unimodular constraint matrix. Moreover, if the bidding language is not expressive then this can interact with the incentive properties of an auction because a bidder is not able to express her true valuation, even if that would be her equilibrium strategy. We wait until Section 4 for an extensive discussion of the interaction between computational constraints and incentives. 

In addition to identifying tractable special cases, for example for a subset of a larger type space, and developing fast algorithms, computational considerations often make it necessary to impose explicit constraints, for example to restrict the expressiveness of a bidding language or to restrict the range of outcomes considered by the mechanism. 

A third approach is to restrict the expressiveness of a bidding language within a mechanism to provide compactness. In restricting the expressiveness of a bidding language it is important to consider the effect on the equilibrium... 

Craig Boutilier and Holger Hoos. Bidding languages for combinatorial auctions. InProc. 17 th InternationalJoint Conference on Artificial Intelligence (IJCAI-01), 2001. 

With multiple items or multiattribute items the preference structure of agents can be exponentially large. For example, if there are n items and the agent has super-additive preferences then in general the agent could specify 2 bids. Multiattribute items with n binary attributes leads to similar informational complexity. Therefore an additional consideration is to provide a compact bid representation language that allows agents to implicitly specify their bid structure. 

The HP s narrative on postponement is well-known to many. They used the notion of core plus peripherals , which is a variation of modular design. HP built a core printer with a large number of common modules that did not vary with customers. They also created peripheral components, each with specific functionality, that could be assembled to the core at the distribution centers or at customer sites. This allowed HP to postpone customization of printers for its European customers, who needed multiple language support. Lucent Technology used the same principle for successfully bidding on a Saudi contract. By building the core in advance of the order, they could satisfy a stringent delivery time constraint in the Saudi contract (Hoyt et al. 2007 Chakravarty 2010). 

---