
\section{Iterated Elimination of Weakly Dominated Strategies}
\label{app:iewds}

When considering subgame perfect equilibria of sequential item auctions, we wish to restrict our attention to ``natural'' equilibria, that exclude (for example) dominated overbidding strategies.  We therefore consider a natural and well-studied refinement of the set of subgame perfect equilibria: those that survive iterated elimination of weakly dominated strategies (IEWDS).  A strategy $s$ is \emph{weakly dominated} by a strategy $s'$ if, for every profile of other players' strategies $s_{-i}$, we have $u_i(s,s_{-i}) \leq u_i(s', s_{-i})$, and moreover there exists some $s_{-i}$ such that $u_i(s, s_{-i}) < u_i(s', s_{-i})$.  We can now define what it means for a strategy profile to survive iterated elimination of weakly dominated strategies.

\begin{definition}
Given an $n$-player game defined by strategy sets $S_1, \dotsc, S_n$ and utilities $u_i \colon S_1 \times \dotsc \times S_n \to \mathbb{R}$ we define a \emph{valid procedure for eliminating weakly dominated strategies} as a sequence $\{S_i^t\}$ such that for each $t$ there is an $i$ such that $S_j^t = S_j^{t-1}$ for $j \neq i$, $S_i^t \subseteq S_t^{t-1}$, and for all $s_i \in S_i^{t-1} \backslash S_i^t$ there is some $s_i' \in S_i^t$ such that $u_i(s_i', s_{-i}) \geq u_i(s_i, s_{-i})$ for all $s_{-i} \in \prod_{j \neq i}S_j^t$ and the inequality is strict for at least one $s_{-i}$.  We say that a strategy profile $s$ survives iterated elimination of weakly dominated strategies (IEWDS) if, for any valid procedure $\{S_i^t\}$, $s_i \in \cap_t S_i^t$.
\end{definition}


\section{Augmenting Path Orderings: An Example}
\label{app:conj}

In \cite{PaesLeme2012}, it was shown that there exist single-valued unit-demand auctions in which inefficient outcomes can occur when items are sold sequentially in an arbitrary order.  In this section we motivate that augmenting path ordering by showing that, for this example, the efficient outcome occurs when the items are sold according to their augmenting path order.

We begin by recalling the example.  There are three items, $\{A,B,C\}$, and 4 players $\{a,b,c,d\}$.  We fix an arbitrarily small constant $\epsilon > 0$.  Recall that the valuation of each player is specified by a real value $v$ and a set $S$ of items of interest; the player then has value $v$ for any item in $S$ and value $0$ for any other item.  The valuations in our example are given by:
\begin{itemize}
\item $v_a = \epsilon$ and $S_a = \{A\}$, 
\item $v_b = 1$ and $S_b = \{A, C\}$, 
\item $v_c = 1$ and $S_c = \{B, C\}$, and
\item $v_d = 1-\epsilon$ and $S_d = \{B\}$.
\end{itemize}
The welfare-optimal allocation is $(x_a, x_b, x_c, x_d) = (\emptyset, \{A\}, \{C\}, \{B\})$, for a social welfare of $3-\epsilon$.  The VCG prices are $(p_a, p_b, p_c, p_d) = (0, \epsilon, \epsilon, \epsilon)$.  Note that, in the terminology of Section \ref{sec:ordering}, player $a$ is the price-setter for each of the other players.  In \cite{PaesLeme2012} it is shown that if the items are auctioned in the order $(A,B,C)$, then the unique subgame perfect equilibrium that survives IEWDS leads to an inefficient outcome.

What are the augmenting path orderings in this example?  In this example, the augmenting path graph is a line, given by nodes $(a,A,b,C,c,B,d)$ in that sequence.  There is therefore a unique augmenting path ordering over the items: the order $(B, C, A)$.

We can now solve for the subgame perfect equilibrium of the auction when items are sold in this order.  We do so by analyzing the item auctions in reverse order.  When item $A$ is sold, the outcome depends on whether or not player $b$ won item $C$: if so, player $a$ will win item $A$ for a price of $0$, yielding $u_a = \epsilon$; if not, then player $b$ will win item $A$ for a price of $\epsilon$, yielding $u_b = 1 - \epsilon$ and $u_a = 0$.  This allows us to determine the outcome of the auction for item $C$: because player $b$ knows that she can win item $A$ for a price of $\epsilon$, she is willing to bid no more than $\epsilon$ on item $C$.  Thus, if player $c$ did not previously win item $B$, then player $c$ can win item $C$ with a bid of $\epsilon^+$, yielding $u_c = 1 - \epsilon$.  This ultimately allows us to determine the outcome of the first auction, the auction for item $B$.  Because player $c$ knows that he can win item $B$ for a price of $\epsilon$, she is willing to bid no more than $\epsilon$ on item $B$.  Since player $d$ obtains positive utility only if she wins item $B$, she is willing to bid as much as $v_d = 1 - \epsilon$ on item $B$.  We therefore have that player $d$ will choose to win item $B$ with a bid of $\epsilon^+$, obtaining utility $u_d = 1 - 2\epsilon$.  Applying our analysis of the subsequent auctions, we conclude that bidder $c$ will win item $C$ for a price of $\epsilon$, and then bidder $b$ will win $A$ for a price of $\epsilon$.

Note that this subgame perfect equilibrium, which is the unique equilibrium in undominated strategies, precisely implements the VCG outcome.  Moreover, our analysis extends easily to other values of $v_b, v_c$, and $v_d$, as long as they are all greater than $\epsilon$.

\section{Not all Augmenting Path Orderings lead to Efficiency}
\label{app:cex}

We now show that if the augmenting path graph is not a line, then some augmenting path orderings do not result in an efficient outcome, even if valuations are unit demand single-valued.

The example is as follows.  There are $3$ items, say $\{A, B, C\}$.  There are $4$ players.  Player $1$ wants all items and has value $1$.  Player $2$ wants only item $B$ and has value $2$.  Player $3$ wants item $B$ or $C$ and has value $3$.  Player $4$ want item $A$ or $C$ and has value $4$.

In this example, the VCG outcome is $(x_1, x_2, x_3, x_4) = (\emptyset, B, C, A)$, and the VCG prices are $(p_1, p_2, p_3, p_4) = (0, 1, 1, 1)$.  The augmenting path graph is a tree with player $1$ at the root, each item a child of player $1$, and each remaining player $i$ being the child of item $x_i$.  For this graph, every order over the items is an augmenting path order.

Suppose the items are sold in the order $(A, B, C)$.  In the VCG outcome, player $4$ obtains utility $v_4 - p_4 = 3$.  In the sequential play corresponding to the VCG outcome, players $1$ and $4$ both bid their values on item $A$.  Consider the following deviation by player $4$.  When item $A$ is sold, he bids $0$, causing player $1$ to win item $A$.  Item $B$ will sell next; players $2$ and $3$ will bid on it.  Consider what would happen if player $2$ wins item $B$: in this case, players $3$ and $4$ both bid their values on item $C$, and hence player $4$ wins $C$ and player $3$ ends with utility $0$.  We conclude that player $3$ prefers to win item $B$ at any price less than $v_3 = 3$, and hence will bid $3$ on item $B$, winning it.  Thus, when item $C$ is sold, only player $4$ places a non-zero bid, winning the item at price $0$.  We conclude that, after this deviation, player $4$ obtains utility $4$, and therefore the VCG outcome is not a SPE.



\section{Introduction}
\input{introduction.tex}

\paragraph{Related Work.}
\input{related.tex}

\section{Preliminaries}\label{sec:prelims}
\input{preliminaries.tex}

\section{Valuations with Restricted Complements}\label{sec:moh}
\input{moh.tex}

\section{Price of Anarchy of Simultaneous Single-Item Auctions}
\input{poa.tex}

\section{Expressiveness of Maximum-over-Hypergraph Valuations}\label{sec:connections}\label{SEC:CONNECTIONS}
\input{connections.tex}

\section{Composition of General Mechanisms}\label{sec:composition}\label{SEC:COMPOSITION}
\input{composition.tex}

\bibliographystyle{plain}



\subsection{Related Work}
\input{related}




\section{Introduction}
\input{introduction}

\section{Model and Preliminaries}
\input{model}

\section{A Simple Example}\label{sec:example}
\input{example}

\section{Lower Bound for Additive and Unit-demand Valuations}
\input{lower-bound}


\section{Extensions of the Lower Bound}
\input{extensions}

\section{The Impact of Item Ordering}
\label{sec:ordering}
\input{ordering}


\bibliographystyle{plain}




\subsection{A Class of Orderings}

Consider a profile of single-valued unit-demand valuations.  Let $x$ denote the VCG allocation (i.e., $x_i$ is the item allocated to bidder $i$).  We also write $x^{(-i)}$ to denote the VCG allocation when bidder $i$ is excluded.  For each $i$, the allocations $x$ and $x^{(-i)}$ define a directed bipartite graph between players and objects, where there is an edge between player $k$ and item $j$ if $x_k^{(-i)} = j$ but $x_k \neq j$, and there is an edge from item $j$ to player $k$ if $x_k^{(-i)} \neq j$ but $x_k = j$.  It is known that, for each player $i$, this graph is always a directed path from player $i$ to some other player $k$; this is the \emph{augmenting path for player $i$} and player $k$ is the \emph{price setter} of player $i$, i.e. the VCG price of player  $i$ is $v_k$. With no loss of generality we assume that every player has a price setter $k$.

Given a welfare-optimal matching $\pi$, that matches each player $i$ to an item $\pi(i)$, consider the following forest construction. Consider all price setters in decreasing value order. For each price setter $k$, we will create a tree and add it to the forest, as follows.  Consider all the items that are in the interest set of $k$, $S_k$, that are
not yet in the forest.  Add each such item to the tree as a child of player $k$.  Next, from each such item $j$, consider its optimally matched player $\pi^{-1}(j)$ and add this player to the tree as a child of $j$.  For each player $i$ that was added, consider all items that are in the interest set of $i$, $S_i$, that are not yet in the forest, and add each of these items to the tree as a child of $i$.  We continue this process, which is essentially a breadth-first traversal of the set of items, until there is no new item to be added. 

The above process creates a forest that contains a node for each item, for each player that is allocated an item in the optimal allocation, and for each price setter. Additionally, each player
belongs to the tree rooted at his price setter and his unique path in the tree to the price setter is an augmenting path in the initial bipartite graph. 
The reasoning is as follows: each tree contains all possible alternating paths ending at the price-setter, except alternating paths that contain items and players who have been included in the tree of a price setter with larger value. Since a player's price setter is the largest unallocated player with which he
is connected, through an alternating path, the claim follows.

We will refer to the above forest as the \emph{augmenting path graph} $G$. Given an augmenting path graph $G$, a \emph{post-order item traversal of $G$} is a depth-first, post-order traversal of the nodes of $G$, restricted to the nodes corresponding to items and rooted at price setters.  Note that this is an ordering over the items in the auction.  We also assume that trees are traversed in decreasing order of price-setters. Also note that this order is not necessarily unique, as it does not specify the order in which the children of a given node should be traversed.

\begin{defn}
The set of \emph{augmenting path orderings} of the items is the set of orderings corresponding to post-order item traversals of $G$.
\end{defn}

Our (refined) conjecture is that, for every instance of single-valued unit-demand bidders, there exists an augmenting path ordering such that the corresponding sequential auction admits a subgame perfect equilibrium that replicates the VCG outcome.  As an example, we show in Appendix \ref{app:conj} that this conjecture holds for the $3/2$ lower bound example from \cite{PaesLeme2012}.  We also show in Appendix \ref{app:cex} that it is not true that \emph{all} augmenting path orderings lead to efficient outcomes at equilibrium: there are examples in which multiple augmenting path orderings exist, and some orderings lead to inefficient outcomes at equilibrium.






