Jeremy

Combinatorial Auctions (1)

Single Item Auction

  • Goal: Give the object to the player with maximum value.
  • In a way that cannot be strategically manipulated

Multiunit Auctions

  • Definition:

    • Allocation Algorithm: Give the k objects to the k highest bidders.

    • Payment Scheme: The winners pay an amount equal to the k+1st highest bid.

Example Combinatorial Valuations

  • Problem Statement

    • A set M of m indivisible items M={1,…,m}

    • A set N of n bidders N={1,…,n}

    • Bidders have preferences over subsets (bundles) of items A valuation is a real valued function for every subset S of items v(S) is the value the bidder obtains if he receives the bundle S

    • free disposal: monotone v(S)≤v(T) if S⊆T

    • normalized: v(∅)=0

  • Example

Roberts Theorem

  • Theorem (Roberts) If |A| ≥ 3, f is onto A, Vi = RA for every i, and (f, p1, . . . , pn) is incentive compatible then f is an affine maximizer.

Valuations

Take S,T with S∩T=∅

  • v is additive if v(S∪T)=v(S)+v(T)

Generally, v is not necessarily additive

  • S,T are Complements: v(S∪T) > v(S)+v(T) (Superadditive)

v(pair of shoes) > v(left shoe)+v(right shoe)

-S,T are Substitutes: v(S∪T) < v(S)+v(T) (Subadditive) v({margarine,butter}) < v(margarine)+v(butter)

E.g. Multiunit Auctions (Unit demand valuation)

Utility

  • The utility is v(S)-p

  • No externalities: the bidder cares only about the set of items he receives and not about how the rest of the items are allocated

Allocation

Social Welfare in Auctions

  • Example – Maximize SW

  • Goals

    1. Maximize social welfare

    2. Maximize revenue

    3. Minimize envy

  • Challenges

    1. Computational Complexity:
    • The allocation problem is computationally hard even for special cases.
    • How do we handle this?
    1. Representation and Communication:

    • The valuation functions are exponential size objects. •How can we even represent them?

    • How can we transfer enough information to the auctioneer so that a reasonable allocation can be found?

    1. Strategies:
    • Can we design incentive-compatible mechanisms?

  • Applications

    • Spectrum Auctions: Government sells licences/rights to transmit signals of specific electromagnetic wavelengths

    • Transportation: “Reverse” or procurement auction.

    • A commercial company (buyer) needs to buy transportation services for a large number of routes from various transportation providers (sellers).

    • Each supplier has a value for every bundle of routes.

Single-Minded Bidders

  • Definition

    1. A valuation v is called single-minded if there exists a bundle of items S∗ and a value v∗ ∈ R+ such that v(S) = v∗ for all S ⊇ S∗, and v(S) = 0 for all other S.

    2. A single-minded bid is the pair (S∗, v∗).

  • Example

  • Known valuations

  • The allocation problem

Computational Complexity

  • Proposition. The allocation problem among single-minded bidders is NP-hard.

  • More precisely, the decision problem of whether the optimal allocation has social welfare of at least k (where k is an additional part of the input) is NP-complete.

Approximation

  • Approximate allocation (single-minded)

  • Proposition. Approximating the optimal allocation among single-minded bidders to within a factor better than m^1/2−ε is NP-hard.

  • Running the VCG may need exponential time!

  • Even if we knew the valuations, we couldn’t be able to approximate the optimum social welfare by a factor better than m^1/2−ε in polynomial time.

Incentive-Compatible Mechanism

  • Compute the optimal allocation and charge VCG payments

    This is incentive-compatible

    Not computationally efficient

  • Take an approximate solution and charge VCG payments?

    The VCG payments work only with exact optimization.

The Greedy Mechanism for Single-Minded Bidders

  • Example

  • Theorem. The Greedy mechanism is efficiently computable, incentive compatible and produces a m^1/2 approximation of the optimal social welfare.

Incentive Compatibility

  • Proof Outline

    • First, we will show that a larger class of mechanisms are truthful.

    • Then, we will show that Greedy belongs to this class, and therefore is truthful.

Monotonicity

  • A bidder who wins with bid (S∗i , v∗i) keeps winning for any v′i ≥v∗i andforanyS′i ⊆S∗i (for any fixed settings of the other bids).

  • Example:

Critical Payments

  • Critical Payment: A bidder who wins pays the minimum value needed for winning: the infimum of all values v′i such that (S∗i , v′i ) still wins.

  • Example:

Incentive Compatibility

  • Lemma. A mechanism for single-minded bidders, in which losers pay 0, is incentive compatible if and only if it is Monotone and uses Critical Payment.

  • The Greedy is a mechanism for single-minded bidders, in which losers pay 0, and it is Monotone and uses Critical Payment. Therefore, it is incentive compatible.

Approximation

Part2

Other Valuations

Iterative Auctions

The Query Model

  • Indirect way of sending information about the valuations

  • The auction protocol repeatedly interacts with the different bidders, aiming to adaptively elicit enough information about the bidders’ preferences as to be able to find a good (optimal or close to optimal) allocation.

Advantages

  • Reduces the amount of information transferred
  • Preserve some privacy about the valuations
  • Makes bidder’s life easier (concentrates on the mechanisms queries) Bidder is a “Black-Box” represented by an oracle

Query Model

  • The auctioneer presents a bundle S, the bidder reports his value v(S) for this bundle.

Subadditive Valuations

  • v(S U T) <= v(S) + v(T)

  • Can we design incentive compatible mechanisms that approximate the optimal social welfare?

Affine Maximizers

  • Example 1

    A’={all the assignments that assign only the first item to a player} Optimize over A’, charge the VCG payments.

    • It is incentive compatible as an affine maximizer. - Poor approximation ratio.
    a b {a, b}
    v1 ε 1 1
    v2 ε 1 1

    • SW(ALG) = ε

    • SW(OPT) = 1+ε

    • Approximation ratio = SW(OPT)/SW(ALG) = (1+ε)/ε

  • Example 2

    i1 i2 M
    v1 1 1 1
    v2 1 1 1
    vn 1 1 1

    • SW(ALG) = 1

    • SW(OPT) = n

    • Approximation ratio = SW(OPT)/SW(ALG) = n

  • Exact optimization in A’ gives good approximation for A

(DNS) Mechanism for SA valuations

i) For each bidder i=1,…, n do:

  1. Query bidder i for the set M={1,…,m}

  2. For each item j=1,…,m do: Query bidder i for the item j

ii) Construct a bipartite graph G=(N,M,E)

  1. a vertex bi for every player i 2) a vertex aj for every item j

  2. E=(bi,aj)

  3. w(bi,aj)=vi(j)

iii) Compute a maximum weighted matching P of G

iv) Find the bidder i*∈ arg maxi vi(M)

v) Return the assignment with maximum S.W. among iii) and iv)

  • example

  • example 2

  • example 3

  • Theorem. The DNS mechanism is efficiently computable, incentive compatible and produces a O(m1/2) approximation of the optimal social welfare for subadditive valuations.

Item Bidding Auctions

  • Item-bidding or simultaneous auctions

    • Bidders simultaneously submit a single bid for each item.

    • Each item is sold in a single-item auction.

      • First price item-bidding auction

      • Second price item-bidding auction - All-pay item-bidding auction

    • Efficient computation

    • Non-truthful mechanisms

  • Example

  • Not Truthful

  • PoA ≥ 2

  • PoA ≤ 4

The PoA of item-bidding (simultaneous) auctions is constant for using first, second or all-pay single-item auctions in subadditive valuations.

Food for thought

Suppose that we run a non-truthful mechanism that guarantees the following:

It maximizes the social welfare for (non-true) valuations vi(S) > v’i(S) > vi(S)/4 (where vi are the true valuation).

  • What is the approximation to the optimal social welfare?

  • Suppose that you have an incentive compatible mechanism with O(m1/2) approximation of the optimal social welfare. Is this a better mechanism? Why?

  • Can you see the connection of the first mechanism to the PoA? How easy is it to find an equilibrium?