Writeup By: Abhijit
Kadlag and Parag Sarda
Popularity of internet based auctions is rising. Poorly
informed sellers and time-critical items e.g. electronic components are being
benefited to a large extent by electronic auctions. Popular internet places
offering auction services are http://www.ebay.com,
http://www.zauction.com. Indian portals have also started offering
auction services to their users e.g. http://www.indiatimes.com,
http://www.rediff.com. This description of
iBundle and IGVA assumes the pre-requisite knowledge of standard auctioning
mechanisms and the GVA.
Standard auctions like English auction, Dutch auction, First
Price Sealed Bid auction, and Vickery auction are very popular. However demands
of people are becoming more and more sophisticated and combinatorial auctions
where a potential buyer can demand for part or whole of the set of items for
sale are gaining importance. The bids placed for such a subset of items for
sale is called a bundle e.g. Suppose there are items (A,B,C) for sell then a
buyer can put his bids on any of (A,B,C,AB,AC,BC,ABC) each of then being called
a bundle. Bundles are important in many real-world problems. For example:
consider a manufacturer that needs either components A and B, or just component
C shall like to put up bids on AB, C.
Although combinatorial auctions can be approximated by
multiple auctions on single items, this often results in inefficient outcomes.
iBundle- An efficient
ascending price bundle auction
The bundling problem is the problem of allocating items to
agents to maximize the sum value across the agents, allowing agents to have non
additive values for individual items.
iBundle is an iterative
combinatorial auction that allows agents to bid for bundles of items while the
auctioneer increases prices and maintains a provisional allocation. It is
optimal for a reasonable agent bidding strategy, in this case myopic or
short-sighted utility-maximizing agents that place best-response bids to
prices. The agents are myopic in the sense that they only consider the current
round of the auction. Each agent determines utility on all bundles and finds
out all bundles for which utility is maximum and
places bids on these bundles only. iBundle has been
proven to be optimal by a novel connection to primal-dual optimization theory
(Papadimitriou & Steiglitz 1982).
GVA is a sealed-bid auction, in which agents first
submit bids simultaneously, and then the auctioneer determines an allocation
and payments, the agent’s optimal strategy is to bid for, and compute the value
of, all bundles for which it has positive value. This is a computationally
intensive task as for |G| items there are 2^|G| bundles to value, each of which
may require solving a difficult optimization problem for the bidder. However,
combinatorial auctions introduce new computational complexities in mechanism
execution. In particular, the auctioneer’s winner-determination (WD)
problem, the problem of choosing bids to maximize revenue, is NP – hard
by reduction from the maximal weighted clique problem.
Counter intuitively in iBundle auctioning mechanism auctioneer
must solve a sequence of WD problems (one in each round) to maintain a
provisional allocation as agents bid however each WD problem in iBundle is
smaller than in the GVA, because agents bid for less bundles.
However iBundle does not have as strong truth revelation
properties as GVA. In iBundle rational agents with look ahead could manipulate
the outcome of iBundle to their advantage, and lead to the sub optimal
allocations. However, there is some evidence that myopic biding may be a
reasonable assumption in practice, perhaps because of the computational
complexity of strategic behavior.
Auction Mechanism
It is an ascending-price auction that allows agents to bid on
arbitrary combinations of bundles during the auction. The auctioneer increases
ask prices on bundles as bids are received and maintains
a set of winning bids in each round that maximize revenue.
There are 3 basic variations of iBundle. iBundle
(2) generates anonymous ask prices same to every agent. iBundle
(3) generates discriminatory ask prices for each agent and iBundle (d) switches
from anonymous to discriminatory ask prices dynamically, agent-by-agent.
- Definitions: Let G denote
the set of items to be auctioned, I denote the set of agents, and S
(sub set of G) denote a bundle of items. The auction proceeds in
rounds, indexed t => 1.
- Bids: Agents can place
additive-or (OR) exclusive-or (XOR) bids for bundles e.g. A bid (S1,
P1) OR (S2, P2) indicates that an agent
wants at most one of bundles S1 and S2. However the auction mechanism deals with
only XOR bids by converting each OR bid into an XOR bid.
- Auction Description:
The auction proceeds in rounds. Following elements are common
to all the 3 variants of iBundle. They differ only in the ask price update
mechanism. During each round the auctioneer announces new ask prices for each
of the bundle. The bidders put their new bid values on the bundles they want to
purchase. After receiving all the bids the auctioneer determines the winner by
solving one WD problem. Depending on the variation of iBundle new ask prices
are computed after this and the rounds continue. The auction terminates when
either each of the agents is allocated some bundle or when none of the agents
changes their bid from the previous round.
Announce Prices and
Allocation
Agent i associates a bid
price
with a bid for bundle S in round t. The price must either be
within e of, or greater than, the ask
price announced by the auctioneer (see below). Parameter e> 0 defines the minimal bid increment,
the minimal price increase in the auction. The auctioneer only needs to
announce a minimal set of new prices, because the price of every bundle is
implicitly at least the maximum price of the bundles that it contains and never
decreases between rounds. E.g. if price of bundle AB becomes Rs.100 Then the
price for bundle ABC is automatically at least Rs.
100.
The auctioneer announces a
provisional allocation of bundles to agents at the start of each round. Let 
represent an allocation of
bundles to agent i at the start of round t.
Bidding
Any bid below the ask price is invalid and ignored by the
auctioneer with two exceptions. First an agent repeating a bid for a bundle
that it receives in the current allocation may repeat the bid for the same
price, even if ask prices has increased. Second an agent can also bid below the
ask price for any bundle in any round – but then it cannot bid a higher price for
that bundle in the future. This allows an agent to bid for a bundle priced
slightly above its value.
Agents must repeat bids for bundles in the current allocation,
but can bid at the same price if the ask price has increased since the previous
round.
Winner Determination
The auctioneer solves a WDP in each round to find an
allocation of bundles to agents so as to maximize the revenue. First invalid
bids are rejected by the auctioneer. The new provisional allocation is found by
solving
such that no item is allocated to more than one agent, which
includes that if a bundle is allocated then it’s no subset is allocated to any
agent. This is called the feasibility criterion. The solution also
requires that the auctioneer only allocated bundles to agents that bid for them
and allocates at most one bundle to each agent. This is called bid_consistency.
Approximate winner determination
The auctioneer can also use an
approximate algorithm for WD, and still maintain the same incentives for myopic
agents to follow the same bidding strategy. This may be needed to be done to
reduce the computational expense of solving WDP.
Preprocessing and Termination
The auctioneer converts all OR bids
into XOR bids as a preprocessing step. This is done by creating dummy agents
for each OR bid placed by the buyer. E.g. suppose the bid was A OR B, then 2
dummy agents shall be created each of which shall one of the original bundles A
and B. WD and price update algorithms are executed as if the dummy agents are
real agents. The auction terminates when either All
the agents are happy i.e. each one of them receives some bundle or all agents
submit the same bids again in the next round.
The first condition makes sense due to XOR bidding as no myopic agent
shall be increasing its bids after winning one of the bundles it wanted. The second condition is more strict that the
first and implies that the bids are likely to be repeated in the further rounds
hence better stop now.
Price Update
The price update rules depends on one of the 3 auction
variations mentioned above. In iBundle (2) the ask prices are same for all the
agents. The new ask price in round t+1 for bundle S, pt+1(S), is
computed as
where unhappy is the set of agents that are not happy with
the new provisional allocation. e is the minimum bid increment as explained earlier.
In iBundle
(3) the ask prices are discriminatory i.e. different for each agent. The prices
increase only when the agent does not receive the bundle and only when the
agent bid at within e of the current ask price.
The new ask price in round t+1 for bundle S for agent i,
pit+1(S) is calculated as
where unhappy (i) is the set of
dummy agents I that are not happy. ( i.e. agent I when
agent I placed on XOR bid and received no bundle, or a dummy agent for every
bundle that agent I did not receive when agent I placed an OR bid).
In iBundle
(d) the prices are initially discriminatory but can become discriminatory during
the auction. The decision of switching to discriminatory prices is taken by
checking if prices are increased on at least two disjoint bundles as a
result of a single agent’s bid. Initially a set anon (t) contains all
the agents and all of them receive anonymous prices. The price update rule here
is same as iBundle (2). In each round the auctioneer calculates incri (t) which is the set of
bundles that will increase in price because of the bids placed by agent i. If incri (t) contains at least two
disjoint bundles then agent is removed from set anon (t+1) and its
prices are initialized to current anonymous prices before they are updated. The
price updated rule used for all agents receiving discriminatory prices is same
as in iBundle (3). The rule for switch can also be explained by defining the
term “safe bid”. An agent’s bids are safe if the agent is allocated a
bundle in the current allocation, or it doesn’t bid at or above the ask price
for any pair of compatible bundles S1, S2 such that. S1 Ç S2 = f. An agent starts receiving
discriminatory bids when he plays unsafe bids.
Proof of Optimality
The proof of iBundle optimality is inspired by a proof due to Bertsekas (1990) for a simpler iterative auction, and makes
an interesting connection with primal-dual theory of linear programming.
The Primal-dual algorithms have an interesting connection with the auction
mechanisms in that the allocation problem can be treated as primal and the
pricing problem can be treated as dual.
A problem is first formulated both as a primal and a dual
linear program. A primal-dual algorithm searches for feasible primal and dual
solutions that satisfy complementary slackness (CS) conditions, instead
of searching for an optimal primal (or dual) solution directly.
Complementary-Slackness
Theorem. Feasible primal and dual solutions are optimal if and only if they
satisfy complementary slackness conditions.
Thus the process becomes iterative by repeatedly trying to get
solutions which satisfy the CS conditions. The original problem becomes a
restricted problem by converting the integer programs into a primal linear
program and dual linear program. Each iteration in iBundle checks if the
solution satisfies the CS conditions which correspond to the two termination
conditions mentioned above.
IGVA: Iterative Generalized Vickrey Auction
GVA has the property of truth revelation and incentive
compatibility however the fundamental problem with GVA is that it requires
agents to compute and reveal their values for all combinations of items in the
first instance. An agent may have bounded-rational with limited computational
capability and it may become difficult for him to reveal all values
immediately. The paper “An Iterative
Generalized Vickrey Auction: Strategy-Proofness without Complete Revelation”
proposes an experimental design for an iterative combinatorial auction which
uses GVA mechanism. It proves that the auction mechanism gives Vickrey output
i.e. reveals the truth in some special cases while the experimental results
support it for all the cases.
In GVA the complete information revelation requirement arises
because it is a single shot auction. The
IGVA, as is claimed, can terminate with the same outcome of allocation and
payments but with less information revelation. However the
condition of allowing the agent to not to reveal all the values conflicts with
the truth or information revelation principle of auction design. The
other side of this approach is that one can design auctions which can not be
manipulated unless an agent can solve an NP-hard problem.
Solving GVA without complete information revelation: The algorithm is based on
the idea that one can solve GVA without having the full information about the
correct values from the agents. e.g. Suppose in a single item
auction the values of 3 agents are v1=20, v2=15 and v3=5. Then the Vickrey
outcome is to sell the item to agent 1 at value 15. Here instead of having the
exact information {20,15,5} it would have been
sufficient to know that { v1>=15,
v2=15, v3<=15} to compute the same outcome. Thus it is possible to have the
Vickrey outcome in an auction without complete information revelation.
Two approaches are proposed to reduce information revelation
but still retain the incentive capability. (1) Allow agents to submit bidding
programs, which the auctioneer can query to determine values for particular
bundles (2) Involve the agents dynamically during the execution of an algorithm
to compute the Vickrey outcome, and request additional information on-the-fly
as required.
The first approach suffers from many disadvantages. First the
agent may not trust the auctioneer in giving the all information for computing
his values. Again the cost of constructing such a program may be high and this
method only shifts the computational burden from the agent to the auctioneer.
The second approach asks the agents various kinds of approximate information in
the computational process e.g. “which bundle do you want at price p(S)” or “which
bundle has highest value out of S1, S2, S3” etc. For such
queries the agent can respond without any heavy computation.
Iterative auctions like iBundle and IGVA are this kind of
auctions. Even the classical English auction fails into this category as at
each iteration it is sufficient to know whether two or more agents have value
greater than the ask price. Parkes has shown that
iterative auctions can computer better solutions than single-shot auctions for
a simple model where the agent has bounded-rationality. Again they make the job
easier for the agent which has myopic best-response strategy and can bid for
the bundles with maximum utility in each round.
Auction Mechanism
IGVA is an ascending-price combinatorial auction and proceeds
in two phases, the second being optional.
In phase I the final allocation is determined and in Phase II the final
payments are determined. Some intermediate computation is performed at the end
of phase-I which determines whether to proceed for phase-II or not. Both
the phases follow the same rules as iBundle(3).
- Phase I
This phase is nothing but the iBundle algorithm. It terminates
when the iBundle algorithm terminates. Let S*=(S1*,S2*,…SI*)
denote the allocation at the end of
Phase I, P* denote the auctioneer’s revenue, W* 
I denote the set of agents that receive a
bundle in S* and P*bid =(Pbid,1*,Pbid,2*,…,Pbid,I*) denote the final bid price of each
agent for the bundle it receives in the final allocation, i.e. p*bid,1
= pbid,1(S1*).
- Intermediate
Computation
Here the auctioneer determines the initial discounts to each
agent and whether to enter Phase II or not.
Computing the initial discounts
The initial discount for each agent is calculated as
where
MAXREV(P-i) denotes the second-best
revenue-maximizing allocation to the auctioneer at the current ask prices.
Determination of Phase II computation
1. Compute the dependents 
for every agent
I 
W*. The dependents of agent i are
Where (W-i)* (I\i) denotes the set
of agents that receive a bundle in this allocation. i.e.
the dependent of an agent are those agents which receive a bundle with that agent but not without him.
2. If
then
set = 
i.e. remove all the dependents for the agent.
The set of ACTIVE I of agents is the set of agents which are
dependent of some agent at the current ask prices.
3. Initialize the set
of ACTIVE agents.
Phase II is skipped if
there are no active agents. The presence of an active agent means that more
information is required to compute the Vickrey payment.
- Phase II
Dummy agents are created by auctioneer in this phase to
compete with the existing agents. The bidding process continues forcing the
agents to reveal more and more information. The dummy agents have very large
values for the bundles so that the iBundle algorithm does not terminate due to
satisfaction of all the agents or the bids getting repeated.
This phase aims at
computing extra discount 
to each agent with dependents. Initially 
for all the agents and for each of the agents
that dropped out of the auction in Phase I a new dummy agent is
created. The valuation function of the dummy agent for agent j is based
on the asked prices (Note that discriminatory ask prices were followed for each
agent) for agent j. For bundles for which agent j had non-zero ask price the
ask price of dummy agent is L more than that while it is 0 for all the
others.
This phase also proceeds similar to iBundle, however some
additional work is done by the auctioneer after each round.
1.
Update the dependents of agents.
2.
For each agent I 
W* and with 
increment 
by 
is the increase in bid price by agent j for
bundle Sj* since the previous round.
3.
If 
then set 
4.
Update the set of ACTIVE agents.
5.
For all the dropped out agents, introduce new dummy agents,
with replacement if necessary. If the auction is in state of quiescence for the
active agents then for the active agents also dummy agents are introduced. The
active agents chosen for this are determined by using either of the following
rules: 1) An agent with all active dummies or 2) an active agent with no dummy
or 3) an active agent already has one dummy.
Termination
Phase II terminates when there is no active agent remaining.
- Final Payments
For each of the agents, payments are computed as
Worked Example
Consider the following case with two items A, B and three
agents
|
|
A |
B |
AB |
|
Agent 1 |
0 |
10 |
10 |
|
Agent 2 |
10 |
0 |
10 |
|
Agent 3 |
0 |
0 |
15 |
Phase 1: S* = (B, A,F) P*=15 W*= {1, 2} P*bid = (8, 7, 0)
At this stage
auction’s ask-price for AB will be 16, which is greater than Agent-3’s
valuation. So he will step out.
Intermediate computation:
S-1*
= (F,F, AB) W-1*
= {3} a(1) = {2} Δinit(1) = 15-15=0
S-2*
= (F,F, AB) W-2*
= {3} a(2) = {1} Δinit(2) = 15-15=0
Phase 2: Introduce
dummy agent for 3 with bids (0, 0, 15+L). Proceed normally. Agent 1 will drop
out after increasing the bid-price by 2. So agent 2 will get discount of 2.
Then Agent 2 will drop out after increasing value by 3. So Agent 1 will receive
discount of 3.
Final payments: Agent 1:
8-3=5 Agent2: 7-2= 5