Tuomas Sandholm, Carnegie Mellon University
Eliciting Bid Taker Non-price Preferences in (Combinatorial) Auctions

Authors: Craig Boutilier, Tuomas Sandholm, Rob Shields

Recent algorithms provide powerful solutions to the problem of determining cost-minimizing (or revenue-maximizing) allocations of items in combinatorial auctions. However, in many settings, criteria other than cost (e.g., the number of winners, the delivery date of items, etc.) are also relevant in judging the quality of an allocation. Furthermore, the bid taker is usually uncertain about her preferences regarding tradeoffs between cost and nonprice features. We describe new methods that allow the bid taker to determine (approximately) optimal allocations despite this. These methods rely on the notion of minimax regret to guide the elicitation of preferences from the bid taker and to measure the quality of an allocation in the presence of utility function uncertainty. Computational experiments demonstrate the practicality of minimax computation and the efficacy of our elicitation techniques. (paper, pdf)

Jason Hartline, Microsoft Research
Near-Optimal Online Auctions

Authors: Jason Hartline, Avrim Blum

We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu 2002 in which an auctioneer is selling identical items to bidders arriving one at a time. We give an auction that achieves a constant factor of the optimal profit less an $O(h)$ additive loss term, where $h$ is the value of the highest bid. Furthermore, this auction does not require foreknowledge of the range of bidders' valuations. On both counts, this answers open questions from BHW-02 and BKRW-03. We further improve on the results from BKRW-03 for the online posted-price} problem by reducing their additive loss term from $O(h \log h \log \log h)$ to $O(h \log \log h)$. Finally, we define the notion of an (offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori indistinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes. (slides)

Discussion

Bob Monroe, Carnegie Mellon University, Tepper School of Business
Billions and Billions Sourced -- Lessons Learned Building Electronic Markets

Creating effective online markets requires both science and art. Most of the talks at this workshop focus on the science of markets. For this talk, I hope to offer some insight into the art of making markets. I will provide an overview of the process and tools we created at a large internet auction provider to help our customers plan, configure, and execute effective reverse auctions. (slides)

Liad Blumrosen, Hebrew University of Jerusalem
On the Computational Power of Ascending Auctions

Joint work with Noam Nisan.

We study the power and limitations of various kinds of iterative combinatorial auctions. We compare different ways to elicit the bidders' preferences in order to find the optimal allocation of the items among the bidders. In particular, we characterize what can and cannot be achieved by different classes of ascending auctions.

Sergei Izmalkov, MIT
Multi-Unit Open Ascending Price Efficient Auction

Weizhao Wang, Illinois Institute of Technology/
TowardsTruthful Mechanism for Demand Games

The family of the Vickrey-Clarke-Groves (VCG) mechanisms is the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to optimization problems with a utilitarian objective function and their output should optimize the objective function. For many optimization problems, finding the optimal output is computationally intractable. If we apply VCG mechanisms to such polynomial time algorithms whose output approximates the optimal solution, the resulting mechanisms may no longer be truthful.

In light of these limitations, it is useful to study whether we can design a truthful non-VCG payment scheme that is computationally tractable for a given output method $\cal O$.

In this paper, we focus our attention on \emph{demand game} in which the agents' only available actions are to take part in the game or not to. For these problems, we prove that a truthful mechanism $M=({\cal O},p)$ exists if and only if $\cal O$ satisfies a certain monotone property. We also provide several general algorithms to compute the payments efficiently for various types of output. In particular, we show how a truthful payment can be computed through ``or/and'' combination, round-based combination, and some more complex combinations of outputs from subproblems.

Discussion

Anshul Kothari, University of California, Santa Barbara
Clearing Algorithm for Multi-Item Procurement Auctions

In this talk, I will present our work on multi-item multi unit procurement auctions with budget constraints. This generalizes an earlier result, on single-item multi-unit procurement auctions, which was presented at the 2003 ACM Electronic-Commerce Conference.

In our model, there is a buyer who is interested in procuring multiple units of a set of $n$ items, and has a budget constraint. Each seller sells only one type of item, but he can sell multiple-units of it. The buyer's utility function is represented as a weighted minimum function. That is, for a given solution (x_1, x_2, ..., x_n), where $x_i$ is the units for $i$th item, his utility is given as min(a_1.x_1, a_2.x_2, ..., a_n.x_n), where $a_i$s are positive constants. This utility functional models the case when the buyer is interested in procuring items in certain ratio. For example a computer needs one power supply, one cpu, one cpu fan, two power chords (one for CPU and one for monitor) etc and the computer manufacturer wants to purchase them in this ratio to avoid wastage.

A solution is called feasible if its total cost is less than the budget. Given sellers' bids, buyer's budget contraint and buyer's utlity function, the objective of the auction is to find the optimal feasible solution, which maximizes the buyer's utility. We present optimal clearing algorithms for the case when the sellers' bids are expressed as either point bids or interval bids. A point bid is a tuple $(u,c)$, expressing that the seller can sell $u$ units, at the per-unit price of $c$. An interval bid is a triple $(l,u,c)$, expressing that the seller can sell between $l$ and $u$ units, at per-unit price $c$. We have present optimal clearing algorithms for the XOR-extension of the two base schemes, where the sellers specifiy multiple bids but at most one can be taken.

I will also briefly mention our group's work on selfish load balancing in peer-to-peer systems. The problem is as follows. There is a set of clients, each of whom must choose a server from a permissible set of servers. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversly proportional to its speed, but it grows linearly with the number of clients matched to it. This interaction is natuarally modeled as an atomic congestion game. We analyze the Nash equilibrium for this game and prove nearly-tight bounds on the price of anarchy.

Ryan Porter, Stanford University
Simple Search Methods for Finding a Nash Equilibrium

Authors: Ryan Porter, Eugene Nudelman, and Yoav Shoham

We present three simple search methods for computing a sample Nash equilibrium in a normal-form game. The first two algorithms, one for 2-player games and one for n-player games, bias the search towards supports that are small and balanced, and employs a backtracking procedure to efficiently explore these supports. The third algorithm, for 2-player games, uses breadth-first search to explore all possible paths of the Lemke-Howson algorithm in parallel. Making use a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art-- the Lemke-Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan-Wilson for n-player games.

Rakesh Vohra, Kellogg School of Management, Northwestern University
Characterizing Dominant Strategy Mechanisms with Multi-dimensional Types

Authors: Rakesh Vohra, Hongwei Gui and Rudolf Muller

This paper provides a characterization of dominant strategy mechanisms with quasi-linear utilities and multi-dimensional types for a variety of preference domains. These characterizations are in terms of a monotonicity property on the underlying allocation rule. The main tool is a dual interpretation of the incentive compatibility constraints in terms of cycles in networks.

Yishay Mansour, Tel Aviv University
Competitive Algorithms for VWAP and Limit Order Trading
We introduce new online models for two important aspects of modern financial markets: Volume Weighted Average Price (VWAP) trading and limit order books. We provide an extensive study of competitive algorithms in these models and relate them to earlier online algorithms for stock trading.

Discussion

Tal Heppenstall, Founder of PriMuni LLC
Title TBA

Sham Kakade, University of Pennsylvania
Trading in Markovian Price Models

Joint work with Michael Kearns

In this talk, we examine a Markovian model for the price evolution of a stock, in which the probability of upward or downward movement is arbitrarily dependent on the current price itself (and perhaps some auxiliary state information). Our main result is a "universally profitable" trading strategy --- a fixed strategy whose profitability competes (in a sense to be made precise) with the optimal strategy that knows all of the underlying parameters of the Markov process.

Jean-Francois Richard, University of Pittsburgh
Computation of Nash Equilibrium Bid Functions for Asymmetric Private Values First Price Auctions

Authors: Wayne Gayle and Jean-Francois Richard

In this paper we present a powerful numerical algorithm to evaluate (inverse) bid functions for asymmetric first price auctions, where we allow for subgroups of bidders to have different distributions of private values (e.g. dealers and collectors in antique auctions ; or sub coalitions). We also propose critically needed 'acceleration' techniques to efficiently compute revenues for the auctioneer and the bidders within this framework. Using these algorithms we are then able to numerically explore whether key results derived within a symmetric framework (revenue equivalence, advantage to the outsider in the presence of a sub coalition) extend to the asymmetric case. They don't.

Discussion

Kamal Jain, Georgia Institute of Technology
A polynomial time exact algorithm to compute a market equilibrium

I will present a recent polynomial time exact algorithm to find a market equilibrium in Walras setting with linear utilities. The algorithm is based on solving a convex program with Ellipsoid algorithm with Simultaneous Diophantine equations. I will also present some combinatorial characterization of market equilibrium along the lines of minimum cost flow. The talk will be based on my recent FOCS paper.

Ronald Goettler, Carnegie Mellon University
Information Acquisition in a Limit Order Market

We model trading in a limit order market with differentially informed traders. After choosing whether to purchase information, agents with a private and common value motive for trade randomly arrive in a market and may either post prices (submit limit orders) or accept posted prices (submit market orders). If their orders have not executed, traders may reenter the market and change their previous orders. The model is thus a dynamic stochastic game with asymmetric information. We numerically solve for the equilibrium of the game, and characterize how information acquisition changes agents' strategies and affects the efficiency of market prices.

We demonstrate that for some costs of acquiring information, there are multiple equilibria. We show that optimal information acquisition can make all agents, including informed agents, worse off. In contrast to the Hirshleifer (1971) effect, in our model this occurs despite no change in the potential gains to trade as a result of information acquisition. Finally, we show that the limit order market is effective at consummating trade and generating consumer surplus, and compares favorably to a frictionless benchmark.