|
Thursday,
October 28th |
9:00 am |
Continental Breakfast |
9:30 am |
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)
|
10:00 am |
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)
|
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
Multi-Unit Open Ascending Price Efficient
Auction |
2:30 pm |
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. |
3:00 pm |
Discussion |
3:30 pm |
Break |
4:00 pm |
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. |
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 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. |
|
Friday, October
29th |
9:00 am |
Continental Breakfast |
9:30 am |
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.
|
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 |
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. |
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
|