1
Sealed Bid Multi-object Auctions
with Necessary Bundles
and its Application
to Spectrum Auctions
ver. 1.0
University of Tokyo 東京大学
松井知己 Tomomi Matsui
Iwate Prefectural University 岩手県立大学
渡辺隆裕 Takahiro Watanabe
2
Multi object Auction
Multi-object Auction: trading oil leases, furniture,
pollution rights, airport time slots, spectrum
licenses, and delivery routes, etc.
Bidders’ preferences are defined on sets of objects.
(combinatorial auction, simultaneous auction)
Results:
(1) Analysis from the point of view of game theory.
(2) Apply the result to spectrum auction.
3
Main result
We introduce following assumptions;
(1) each bidder has a positive reservation value
only for one special subset of objects
(necessary bundle)
(2) admissible bid is a pair of one subset of objects
and its price,
Game theoretic approach:
show the existence of a Nash equilibrium when
bidding unit is sufficiently small
Application to spectrum auction:
polynomial algorithm for the problem to maximize
auctioneer’s revenue
explicit description of a Nash equilibrium
4
Purpose of this talk
purpose of this talk = Find friends !
Combinatorial
optimization
Game theory
Multi-object
Auction
Multi-agent
system
Communication
searched on internet ⇒ found PRIMA2001
⇒ submitted paper ⇒ give a talk
⇒ find friends ⇒ further work !
5
Definitions (bidders)
Game theoretic descriptions
N ={1,2,…, n}: players (bidders)
M = {1,2,…, m}: objects
bundle: subset of objects
sealed bid auction: submit bids simultaneously
open bid auction (English, Japanese, Dutch,…)
strategies (admissible bids) of player i:
(Bi, bi) ∈2M×R+: (bundle, bidding price)
The bidding price bi is the amount of money
that player i is willing to pay for bundle Bi .
6
Assumption (strategies)
Assumption 1
each player i submits only one pair of
bundle and its price (Bi, bi) ∈2M×R+:
restricted but practical
combinatorial auction:
each player i submits bidding prices of
all the bundles fi : 2M→R+
general but impractical
(2M is a huge family)
7
bidding unit
ε : bidding unit (bidding grid)
Each bidding price is
a non-negative multiple of ε.
Zε={εｊ ｜ｊ is a non-negative integer}
strategies (admissible bids) of player i:
(Bi, bi) ∈2M×Zε
profile of bids : vector of bids of all the players
((B1,b1),(B2,b2),…, (Bn, bn))=(B, b)
B =(B1, B2,…, Bn )
b = ( b1, b2 ,…, bn)
8
Definitions (auctioneer)
Given a profile of bids
((B1,b1),(B2,b2),…, (Bn, bn))=(B, b),
auctioneer determines the set of winners
which maximizes auctioneer’s revenue.
Bundle Assignment Problem BAP(B, b)
(winner determination problem)
max. bTx = b1x1+ b2x2+‥＋bnxn
s. t. Ax ≦1, x ∈{0,1}N.
A=(aji) 0-1matrix {0,1}M×N
aji=1 ⇔ object j is in bundle Bi
9
Bundle assignment problem
BAP(B, b)
max. bTx = b1x1+ b2x2+‥＋bnxn
s. t. Ax ≦1, x ∈{0,1}N.
●
A=(aji) 0-1matrix {0,1}M×N
aji=1 ⇔ object j is in bundle Bi
● xi
=1 ⇔ auctioneer assigns
bundle Bi to player i.
● Ax ≦1: each object must belong to at
most one player
10
Bundle assignment problem
Bundle assignment problem has many names as
winner determination problem,
max. weight set packing problem,
max. weight independent set problem, and
max. weight clique problem.
theoretically hard: NP-hard
practically tractable: many commercial codes
solve BAP efficiently (e.g. CPLEX)
[Andersson, Tenhunen and Ygge (2000)]
11
multiple-optimal solutions
If BAP has multiple-optimal solutions, then
auctioneer chooses an optimal solution
uniformly at random.
Further work: Construct an algorithm for
selecting an optimal solution of BAP
uniformly at random.
The problem is much harder than BAP.
12
Definitions (bidders)
Vi(S): Each player i has a non-negative
reservation value Vi(S) for each bundle S.
Vi : 2M → Zδ (non-negative multiple of δ)
Assumption 2: Each bidder has a positive
reservation value only for one special bundle.
⇒ necessary bundle
necessary (bundle, price) of player i : (Ti , vi )
Vi(S) = vi ⇔ (S⊇Ti)
Vi(S) = 0 ⇔ (otherwise)
13
Nash equilibrium
profile of bids :
((B1,b1),(B2,b2),…, (Bn, bn))=(B, b)
Utility of player i : Ui (B, b)
Ui (B, b)=(Vi(Bi) ｰ bi ) Pr[player i is
selected]
profile (B*, b*) is a Nash equilibrium
⇔ ∀i∈N, ∀(Bi, bi) ∈2M×Zε,
Ui (B*, b*) ≧ Ui ((B*-i, b*-i), (Bi, bi))
((B*-i, b*-i), (Bi, bi)) : profile obtained from
(B*, b*) by replacing strategy of player i
with (Bi, bi)
14
Main results
Theorem 2: If the bidding unit ε is sufficiently
small, then Nash equilibrium exists.
size of bidding unit ε≦δ(n2n+1)
δ：unit of reservation value,
n: number of players
<proof: omitted>
profile (B*, b*) is a Nash equilibrium
⇔ ∀i∈N, ∀(Bi, bi) ∈2M×Zε,
Ui (B*, b*) ≧ Ui ((B*-i, b*-i), (Bi, bi))
((B*-i, b*-i), (Bi, bi)) : profile obtained from (B*,
b*) by replacing strategy of player i with (Bi, bi)
15
description of a Nash equilibrium
Classify the bidders
Passed bidders: bidders contained in every optimal
solution of BAP(B, b).
Questionable bidders: bidders contained in not all
but at least one optimal solution of BAP(B, b).
Rejected bidders: bidders never appearing in any
optimal solutions of BAP(B, b).
Optimal solution set: Ω (B, b):
set of all the optimal solutions of BAP(B, b).
16
Nash equilibrium
Theorem 1: Following profile (B*, b*) is a
Nash equilibrium;
questionable bidder i ： (B*i, b*i) = (Ti, vi)
rejected bidder i :
(B*i, b*i) = (Ti, vi)
passed bidder i :
B*i =Ti,
b*i: minimal vector in Zε
satisfying Ω (B*, b*) = Ω (T, v)
(solution sets are equivalent)
(Ti, vi ): (necessary bundle, reservation value)
<proof: omitted>
17
Application to spectrum auctions
18
Spectrum auction
Spectrum auction:
objects: spectrums (frequency channel for
cellular phone) are arranged in linear order
necessary bundles (Ti):
sequences of consecutive channels
channels :
1
2
3
4
5
6
7
T1
T2
T3
T4
8
9
10 11
19
Longest path problem
BAP corresponding to spectrum auction satisfies
the conditions;
(1) coefficient matrix A is totally unimodular,
(2) liner relaxation of BAP has an integer
valued optimal solution,
(3) equivalent to longest path problem.
20
longest path problem
directed graph
1
2
3
nodes: barrier of channels
arcs: ( j, j+1), necessary bundles
arc weight = reservation value
4 5 6 7 8 9 10 11
T1
T2
T3
T4
v1
v2
v
3
v4
21
longest path problem
longest path problem
1
2
3
4
5
6
7
8
9
10 11
T1
T2
T3
T4
v1
v2
v
3
v4
22
longest path problem
longestapath
problem
Finding
longest
path = winner determination
1
2
3
4
5
6
7
8
9
10 11
T1
T2
T3
T4
v1
v2
v
3
v4
23
random selection
Generally, solving BAP and random selection from
multiple-optimal solutions are hard.
Spectrum auction:
bundle assignment ⇒ longest path problem
random selection ⇒ random path generation
Key idea:
BAP(B, b) ⇒ linear relaxation ⇒ dual problem
bundle assignment: dynamic programming
random selection: path counting algorithm
explicit description of a Nash equilibrium:
complementality slackness theorem for linear
programming problems
(detail is omitted)
24
conclusion
Assumption 1 (multi-object auction)
each player i submits only one pair of bundle
and its price (Bi, bi) ∈2M×R+
Assumption 2: Each bidder has a positive reservation
value only for one special bundle,
called necessary bundle.
Theorem 2: If the bidding unit ε is sufficiently small,
then Nash equilibrium exists.
Theorem 1:
(Characterization of a Nash equilibrium)
25
END
26
Main results
Theorem 2: If the bidding unit ε is sufficiently
small, then (pure strategy) Nash equilibrium
exists.
mixed strategy: Nash showed that every
strategic form n-persons game with finite
number of strategies has a mixed strategy
Nash equilibrium.
size of bidding unit ε≦δ(n2n+1)
δ：unit of reservation value,
n: number of players
27
random selection
BAP(B, b) max{bTx | Ax ≦1, x ∈{0,1}N}
linear relaxation max{bTx | Ax ≦1, x≧0}
dual problem min{yTx | yTA ≧b, y≧0 }
y*：optimal dual solution
M*={j∈M | y*Tai=bi } ai : i th column vector
Lemma: M* is the set of passed and
questionable bidders.
Ordinary dynamic programming procedure
⇒ random selection of longest paths
© Copyright 2024 ExpyDoc
