Ascending Price Auction

Motivation. The VCG Auction is DSIC and Welfare-maximizing. But it’s also very complicated to explain to all agents. Instead, let’s think of a simpler, intuitive idea: ascending price auctions. Now, in a Combinatorial Auction setting, there are two ways to ascend the price:

1. Ascending item price
2. Ascending bundle price Before we proceed, we need to introduce definitions and properties.

---

def. Demand. For valuation function $v$, let item prices $p_1,\dots ,p_n$. Agent demands bundle $S^{\ast }$ of this valuation if $S$ the utility-maximizing bundle, i.e:

$$S^{\ast }={\text{argmax}}_{S}v(S)-\sum _{j\in S}{p}_j$$

Remark. There may be multiple utility-maximizing bundle. Therefore we often collect all bundles that are utility-maximizing, and make it into a demand set $D$

Ascending Item Price Auction §

An Ascending item price auction has prices for each item, and increase the price of each item.

def. Walrasian Equilibrium. (WE) In a Combinatorial Auction, given the prices $p_1^{\ast },\dots ,p_j^{\ast }$, let goods in $X$ partitioned into $S_1,\dots ,S_n$. This allocation this is a W.E. if:

1. $S_i$ is demanded by $i$, (=$S_i$ maximizes $i$’s utility =$S_i\subseteq D_i$)
2. If $p_j^{\ast }>0$ then item $j$ has an owner.

thm. First Welfare Theorem. (FWT) Given price $p_1^{\ast },\dots ,p_j^{\ast }$, if Allocation W.E. is welfare-maximizing. Proof. Let $S_1^{\ast },\dots ,S_n^{\ast }$ be the welfare-maximizing partition/price to a Combinatorial Auction, i.e. the W.E. Then consider any other partition $T_1,\dots ,T_n$. Then:

■ Thus, we need only show that the allocation is a WE in order to show that it is welfare-maximizing. Now:

def. Ascending Item Price Auction.

1. Start at $p_j=0$ for all items
2. for all agents, agent $i$ “points to” all items ($D_i$) that maximizes ${\mu }_i(D_i)=v_i(D_i)-{\sum }_{j\in D_i}{p}_j$ at that price
3. If there are two agents that choose the same item, increase that item’s price by a small amount, $ϵ$.
   1. & You can choose which item price to raise first—different choices will lead to different final allocations.
4. Repeat, until for all items there is only one agent pointing to it.
5. Give that agent all the items they are pointing to at that price. We define a property (subset of Rational Taste) to assist the proof:

def. Substitutes Property. A value function $v$ satisfies the substitutes property if, the increase of one item’s price does not remove any other items from the bundle it demands. Example. In other words, there is no situation of “left shoe, right shoe” (complement goods). If the price of left shoe increases above what they want to pay, this person will drop out of the left shoe and right shoe both. This does not satisfy the substitutes property.

thm. (Ascending Item Price Auction Maximizes Welfare) If all agent’s value function $v_i$ satisfies the substitutes property, and no two agent values the good within $ϵ$ of each other the Ascending Item Price Auction terminates in a WE (and thus is welfare-maximizing via the FWT.) Proof.

1. Auction will terminate, because the item price is only increased when it is in someone’s demand set.
2. At termination, if the price of item $j$ is non-zero, it is in somebody’s demanded bundle $D{)}_i$. This is because
   1. the price was raised from zero because somebody was pointing to it
   2. two people cannot simultaneously drop out of it ($\pm ϵ$)
   3. The raise of another item’s price does not cause any agent to drop $j$
   4. ⇒ therefore if termination price $p_j^{\ast }>0$ then it is in somebody’s demand bundle $D_i$ (Second property of WE).
3. At every point in time, all agents point to only their demanded bundle. (First property of WE) ■

Ascending Personalized Bundle Price Auction. §

An Ascending bundle price auction has an individualized price for every bundle. We describe an alternative type of equilibrium and prove that such an allocation is maximizing. It is not DSIC.

def. Competitive Equilibrium. (CE) let personalized prices $p_i(S_i)$ for every agent, for every bundle, and allocation $S_1,\dots S_n$ be a partition of goods $X$. This price and allocation is a competitive equilibrium iff:

1. $S_i$ is demanded by $i$, i.e. it utility maximizes for $i$, i.e. $S_i\subseteq D_i$
   1. This is same as WE above.
2. It maximizes seller’s total revenue: ${\text{max}}_S{\sum }_{\forall i}{p}_i(S_i)$

thm. Competitive Equilibrium maximizes social welfare.

■

def. Ascending Bundle Price Auction.

1. let $p_{ij}$ be current prices, individualized for each bidder, for each bundle
2. Then find the revenue-maximizing partition $S_1,\dots ,S_n$
   1. There may be many, arbitrarily choose one.
3. let “Loser Set” $L:=\{i\mid S_i\ne \varnothing \}$, i.e. agents that don’t get anything
   1. For every loser $i\in L$ get their demand bundle $D_i$ at these prices
   2. Increase customized price of that bundle for $i$ by $ϵ$, i.e. $p_i(D_i)\leftarrow p_i(D_i)+ϵ$.
4. Repeat from 2, until $L=\varnothing$ or no agents demand anything. This all seems very arbitrary, but it will magically terminate at the CE.