
Thursday,
October 28th 
9:00 am 
Continental Breakfast 
9:30 am 
Tuomas
Sandholm, Carnegie Mellon University
Eliciting Bid Taker Nonprice Preferences
in (Combinatorial) Auctions
Authors: Craig Boutilier, Tuomas Sandholm, Rob Shields
Recent algorithms provide powerful solutions to the problem
of determining costminimizing (or revenuemaximizing) 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)

10:00 am 
Jason
Hartline, Microsoft Research
NearOptimal Online Auctions
Authors: Jason Hartline, Avrim Blum
We consider the online auction problem proposed by BarYossef,
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 BHW02 and BKRW03.
We further improve on the results from BKRW03 for the online
postedprice} 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 apriori indistinguishable. We apply our online
auction solution to achieve good bounds for the attribute
auction problem with 1dimensional attributes.
(slides)

10:30 am 
Discussion 
11:00 am 
Break 
11:30 am 
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)

12:00 noon 
Lunch 
1:30 pm 
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. 
2:00 pm 
Sergei
Izmalkov, MIT
MultiUnit Open Ascending Price Efficient
Auction 
2:30 pm 
Weizhao
Wang, Illinois Institute of Technology/
TowardsTruthful Mechanism for Demand
Games
The family of the VickreyClarkeGroves (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 nonVCG 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, roundbased combination, and some more complex
combinations of outputs from subproblems. 
3:00 pm 
Discussion 
3:30 pm 
Break 
4:00 pm 
Anshul
Kothari, University of California,
Santa Barbara
Clearing Algorithm for MultiItem
Procurement Auctions
In this talk, I will present our work on multiitem multi
unit procurement auctions with budget constraints. This
generalizes an earlier result, on singleitem multiunit
procurement auctions, which was presented at the 2003 ACM
ElectronicCommerce 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
multipleunits 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 perunit
price of $c$. An interval bid is a triple $(l,u,c)$, expressing
that the seller can sell between $l$ and $u$ units, at perunit
price $c$. We have present optimal clearing algorithms for
the XORextension 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 peertopeer 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 nearlytight bounds on the price
of anarchy. 
4:30 pm
5:00 
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 normalform game. The first two algorithms,
one for 2player games and one for nplayer 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 2player games,
uses breadthfirst search to explore all possible paths
of the LemkeHowson 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 LemkeHowson algorithm for 2player
games, and Simplicial Subdivision and GovindanWilson for
nplayer games. 

Friday, October
29th 
9:00 am 
Continental Breakfast 
9:30 am 
Rakesh
Vohra, Kellogg School of Management,
Northwestern University
Characterizing Dominant Strategy
Mechanisms with Multidimensional Types
Authors: Rakesh Vohra, Hongwei Gui and Rudolf Muller
This paper provides a characterization of dominant strategy
mechanisms with quasilinear utilities and multidimensional
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.

10:00 am 
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.

10:30 am 
Discussion 
11:00 am 
Break 
11:30 am 
Tal
Heppenstall, Founder of PriMuni
LLC
Title TBA 
12:00 noon 
Lunch 
1:30 pm 
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. 
2:00 pm 
JeanFrancois
Richard, University of Pittsburgh
Computation of Nash Equilibrium Bid
Functions for Asymmetric Private Values First Price Auctions
Authors: Wayne Gayle and JeanFrancois 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. 
2:30 pm 
Discussion 
3:00 pm 
Break 
3:30 pm 
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.

4:00 pm
4:30 
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. 
Market Design Workshop
