Title: The Clock-Proxy Auction: A Practical Combinatorial Auction Design

We propose the clock-proxy auction as a practical means for auctioning many related items. A clock auction phase is followed by a last-and-final proxy round. The approach combines the simple and transparent price discovery of the clock auction with the efficiency of the proxy auction. Linear pricing is maintained as long as possible, but then is abandoned in the proxy round to improve efficiency and enhance seller revenues. The approach has many advantages over the simultaneous ascending auction. In particular, the clock-proxy auction has no exposure problem, eliminates incentives for demand reduction, and prevents most collusive bidding strategies.

Title: The communication complexity of the private value single item bisection auction

In this paper we present a new auction, the bisection auction, which can be used for the sale of a single indivisible object. We discuss the issue concerning the information revelation requirement of this auction and the associated amount of data that needs to be transmitted. We show that in the truth telling equilibrium the bisection auction is economical in its demand for information on the valuations of the players. It requires the players to transmit less information bits to the auctioneer than the Vickrey and English auctions. In particular, we prove that for integer valuations uniformly distributed on the interval [0, L) the bisection auction of n players requires in expectation transmission of at most 2n+log L information bits by the players. Compared with the corresponding number in the Vickrey auction which is nlog L, and in the English auction which is on average at least (1/3) nL, the bisection auction turns out to be the best performer.

Title: Applying learning algorithms to preference elicitation in combinatorial auctions

We consider the parallels between the preference elicitation problem in combinatorial auctions and the problem of learning an unknown function from learning theory. We show that learning algorithms can be used as a basis for preference elicitation algorithms. The resulting elicitation algorithms perform a polynomial number of queries. We also give conditions under which the resulting algorithms have polynomial communication. Our conversion procedure allows us to generate combinatorial auction protocols from learning algorithms for polynomials, monotone DNF, and linear-threshold functions. In particular, we obtain an algorithm that elicits XOR bids with polynomial communication. We then characterize the communication requirements of implementing Vickrey payments with an elicitation algorithm. This suggests a modification to the queries in our elicitation algorithms so that truthful bidding becomes an ex-post Nash equilibrium.

Title: Tolls for heterogeneous selfish users in multicommodity generalized congestion games

We prove the existence of tolls to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of tolls versus latency to collectively form the traffic pattern of a minimum average latency flow. This generalizes both the previous known results of the existence of tolls for multicommodity, homogeneous users and for single commodity, heterogeneous users (Cole, Dodis, and Roughgarden, 2003).

Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute tolls when the number of different types of users is bounded by a polynomial.

We show that our proof gives a complete characterization of flows that are enforceable by tolls. In particular, tolls exist to induce any traffic pattern that is the result of minimizing an arbitrary function from $\R^{E(G)}$ to the reals that is nondecreasing in each of its arguments. Thus, tolls exist to induce flows with minimum average weighted latency, minimum maximum latency, and other natural objectives.

We give an exponential bound on tolls that is independent of the number of network users and the number of commodities. We use this to show that multicommodity tolls also exist when users are not from discrete classes, but instead define a general function that trades off latency versus toll preference.

Finally, we show that our result extends to very general frameworks. In particular, we show that tolls exist to induce the Nash equilibrium of general nonatomic congestion games to be system optimal. In particular, tolls exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set $S$ is an arbitrary function of the latencies of the resources contained in $S$. Our exponential bound on size of tolls also holds in this case; and we give an example of a congestion game that shows this is tight: it requires tolls that are exponential in the size of the game.

Title: Approximation Algorithms for CAs with Complement-Free Bidders

We exhibit two polynomial-time approximation algorithms for the winner determination problem in combinatorial auctions. The first algorithm provides an O(log(n+m)) approximation for the case of complement-free bidders (where n is the number of bidders and the number of items). This is in contrast to the known impossibility result of Omega(m^(1/2-epsilon))-approximation for bidders with general valuations. The second algorithm provides a 2-approximation when bidders' valuations lie in the class XOS defined by Lehmann, Lehmann, and Nisan (LLN). This improves upon the algorithm of LLN that provides a 2-approximation only for the more restricted class of submodular valuations. We also prove several lower bounds related to our two algorithms.

Title: Optimal Distributed Protocols for Generalized Job Shop Scheduling Problems via Ascending Combinatorial Auctions

We consider a multi-round ascending combinatorial auction mechanism for generalized job shop scheduling with the goal of minimizing weighted tardiness. In particular, we adapt the efficient mechanism iBundle (Parkes 1999) for several variants of the job shop problem e.g. flowshop, bottleneck, and generalized flexible job shop scheduling. The scheduling problem is decomposed into single job agents that bid for a set of machine time-slot pairs that represents a job specific feasible schedule and an auctioneer that allocates a subset of the proposed schedules to agents so that a global feasible solution that minimizes total weighted tardiness is attained. Using approximate ``shadow price'' information obtained from an allocation produced by the auctioneer as prices for machine time slot pairs, job agents solves a local utility maximizing problem equivalent to a single job flexible job shop problem to determine a feasible schedule to bid for. The utility maximizing problem of agents are computationally tractable i.e. solvable in polynomial time. Numerical results indicate that allocations resulting from the auction are highly efficient compared to the central optimal solution.

Title: Negotiation-Range Mechanisms: Coalition-Resistant Markets

Negotiation-range mechanisms offer a novel approach to achieving efficient markets based on finding the maximum weighted matching in a weighted bipartite graph connecting buyers and sellers. Unlike typical markets, negotiation-range mechanisms establish negotiation terms between paired bidders rather than set a final price for each transaction. This subtle difference allows single-unit heterogenous negotiation-range markets to achieve desirable properties that cannot coexist in typical markets. This paper extends the useful properties of negotiation-range mechanisms to include coalition-resistance, making them the first markets known to offer protection from coalitions.

Title: An Exact Algorithm for Procurement Problems under a Total Quantity Discount Structure

In this paper, we study the procurement problem a buyer faces when he needs to purchase a variety of goods from suppliers who apply a discount policy that depends on the total amount of goods purchased. This policy implies that every supplier states a number of volume intervals and the volume interval in which the total amount ordered lies determines the discount. Moreover, the discounted prices apply to all goods bought from the supplier, not only to those goods exceeding the volume threshold. We refer to this cost-minimization problem as the TQD problem. We establish a mathematical formulation for this problem and argue that not only it is NP-hard, but also that there exists no polynomial-time approximation algorithm with a constant ratio (unless P=NP). Beside the basic form of the TQD problem, we also describe three variants. In a first variant, the market share one or more suppliers can obtain is constrained. Another variant allows the buyer to procure more goods than strictly needed, in order to reach a lower total cost. Finally, a third variant limits the number of winning suppliers. We show that the TQD problem and its variants can be solved by solving a series of min-cost-flow problems and we create an algorithm that exploits this property. The performance of this algorithm is evaluated by comparing it with a branch-and-cut and a branch-and-bound algorithm, both using the MIP solver of Ilog Cplex 8.1.