تسلط قابل حل مزایده منطبق انگلیسی

It is well-known that the competitive allocation in a one-to-one matching market can be constructed with the Gale–Shapley algorithm. In this algorithm the buyers use a simple Walrasian bidding scheme to increase the market price until the excess demand vanishes. It is therefore natural to ask under which conditions rational buyers should use this bidding scheme in an English multi-object auction. This paper presents two auction games in which an iterated elimination of dominated strategies justifies the expected outcome.

Matching as a problem of strategic interaction was introduced in a seminal paper by Gale and Shapley (1962). They considered a model in which the members of two distinct groups of agents (the men and the women) can improve upon their status quo if they are matched to a member of the opposite group. Every agent has a strict ranking of all the opponents (including the option of staying alone) so that an allocation is determined by a one-to-one matching between two subsets of the two groups. Gale and Shapley called an allocation stable if there are no two agents who could both improve their situation if they were matched to each other instead. They proposed to construct a solution with the following repetition of offers and rejections: each man proposes a match to his most preferred partner; each woman keeps only the proposal which she likes most, and the rejected men become free to turn to their next best partner. After finitely many iterations this algorithm converges to the unique men-optimal stable allocation which is preferred by all the men to all other stable solutions. The Gale–Shapley algorithm is not only interesting as a computation device, it is also useful to describe economic reality. Thus it was used recently by Blum et al. (1997) to explain vacancy chains which are caused by job openings in certain high skill labor markets. The descriptive appeal is even stronger if one looks at Crawford and Knoer’s (1981) extension of the Gale–Shapley algorithm to allocation problems in which the matched agents have a natural conflict of interest over the price of the traded good. Instead of turning to next best partners the potential buyers now submit next best price offers so that the Gale–Shapley algorithm computes a history of myopically optimal bids in an English auction in which several (different) objects are sold simultaneously. Moreover, the set of stable solutions in this matching market coincides with the set of competitive equilibria1, while each iteration of the generalized Gale–Shapley algorithm can also be interpreted as an increase of the prices for the over-demanded objects. Thus Crawford and Knoer provide a market model in which the Walrasian tâtonnement process has the desired convergence properties and describes a natural myopic bidding behavior in a mechanism which can be implemented as an English multi-object auction.2 But in spite of the conceptual importance of the Walrasian tâtonnement, the descriptive appeal of the Gale–Shapley algorithm, and the enormous impact which this algorithm had (and still has) on the literature on two-sided matching markets no one has analyzed the strategic structure of such English matching auctions. So far the studies of the strategic aspects of the matching problem have been concentrated on revelation games. The papers by Dubins and Freedman (1981), Roth (1982) and Demange and Gale (1985) prove that it is a dominant strategy for the buyers to reveal their true preference order to a central agency who constructs the buyer-optimal stable solution (for instance with the Gale–Shapley algorithm). This property is very important as it generalizes Vickrey’s (1961) famous dominance result to the matching model, but it is only of limited interest for the analysis of real life mechanisms. Already Vickrey introduced his second price auction not to describe observable auctions but as ‘logically equivalent’3 to the English auction which he wanted to study. The Gale–Shapley algorithm can describe some existing organized markets if there are no transfer payments involved4, but it becomes an artificial planning device if prices have to be determined together with the matching. It is therefore important to know to what extent the dominance solvability of the (generalized) second price auctions also holds for the corresponding English matching auction. Unfortunately Vickrey’s ‘logical equivalence’ is an intuitive rather than a formal property even in the single object framework. Kamecke (1998) shows that, in spite of a widely held believe, it is not a dominant strategy in a single object private values English auction to increase the price in small steps until the true valuation is reached. To derive this property Milgrom and Weber (1982) had to restrict the bidders’ strategy sets drastically, but as soon as the bidders can react in a non-trivial manner to the opponents’ actions the simple English auction may have signalling equilibria which are as robust as the natural ‘myopic’ bidding strategy.5 It is easy to see that non-trivial reactions to observed bids cannot be excluded if an English multi-object auction allows to implement the Gale–Shapley bidding procedure: if, for instance, every competitor agrees not to bid for the first object after round one it may well be optimal to be the highest first round bidder for this object even if there are still more attractive alternatives available. The myopic ‘Gale–Shapley’ strategies are therefore not dominant, no matter how restrictive the auction game is formulated, and it is a non-trivial question, whether it is still possible to formalize some weaker ‘logical equivalence’ between English matching auctions and the corresponding revelation game. In this paper I will show under which conditions the dominance argument is sufficient to show that rational players submit the myopic bids prescribed by the Gale–Shapley algorithm. Unfortunately, I have to overcome three difficulties before I can prove this ‘logical equivalence’. Firstly, the underlying matching problem is much more complicated than the allocation problem solved by the single object English auction, and it is necessary to model this matching problem such that truth-telling is a dominant strategy in the corresponding direct mechanism. Secondly, the cooperative matching model has to be turned into a stage game such that the strategies of the players allow the decentralized construction of the generalized Gale–Shapley algorithm. Thirdly, the bidding rules have to be embedded in a Bayesian model of incomplete information in such a way that the robust signalling equilibria which Kamecke (1998) constructed in the single object auction are ruled out. These problems are solved in the three parts of Section 2. In the first part I introduce a symmetric matching problem with finite (discrete) transfer payments in which each buyer can be assigned to and pay for at most one object. Even though I will concentrate on the bidding strategies of the buyers, and hence on a one-sided strategic problem later, this symmetric formulation is convenient to relate the model to the standard matching literature. Some of the assumptions in this part are not very elegant nor very satisfactory from a descriptive point of view, but these assumptions are inherited from the matching literature and do therefore not affect the relationship between English matching auctions and the corresponding revelation games studied in this paper. In the second part I will turn the cooperative matching model into a stage game with well-defined action sets. The Gale–Shapley algorithm gives a vague notion of the natural solution of the matching auction, but it does not pin down natural bidding strategies. I define the rules for two alternative English matching auctions. The first is an ‘open outcry’ auction game in which the buyers themselves choose by how much they want to increase the price while the auctioneer enforces the stopping rule. The second generalizes Milgrom and Weber’s (1982) ‘Japanese’ auction to a model in which the agents choose only the object they want to bid for, while a price clock increases the prices until demand and supply are equal. In both these auctions the Gale–Shapley algorithm defines a myopic strategy which we consider as the natural solution of an English matching auction. In the third part of Section 2 I will embed these bidding rules in a Bayesian model of incomplete information. At first sight this may seem straightforward, but it turns out that the desired strong result in favor of the myopic Gale–Shapley bidding strategies holds only if the buyers remain sufficiently ignorant during the auction game. I implement this ‘lasting ignorance’ of the bidders with two types of assumptions. First I restrict the strategy space excluding every opportunity to delay the bidding for a round or to increase an own highest present offer. Then I extend the payoff function of the usual independent private values model to eliminate some of its restrictive properties. A general private net valuation for each bid destroys the linear relationship between prices and net payoffs, and in the open outcry auction a secret reservation price allows that the expected net payoffs may increase with the price of an object. In Section 3 I will argue that this ‘lasting ignorance’ is sufficient to get rid of the well-known problems of an iterated elimination of dominated strategies.6 Usually the outcome of such a procedure may depend on the order of elimination if it is possible that a strategy may change its status from ‘inferior’ to ‘just as good’ after an opponent’s strategy is removed. Marx and Swinkels (1997) show that this problem disappears if indifference of a decision maker implies that the opponents do also not care which strategy is used. Here I will use a related property locally. In Lemma 2 I show that ‘lasting ignorance’ implies the pervasiveness of the myopic strategies defined by the Gale–Shapley algorithm, i.e. the myopic strategies generate every feasible history in the game with a positive probability. This property turns out to be the key to the main result of the paper. It implies that a strategy is a best reply against a myopic Gale–Shapley strategy only if it is behaviorally equivalent to the myopic strategy in every (ex ante possible) part of the game tree so that a myopic strategy is never dominated. Moreover, pervasiveness also implies that every other strategy is eventually dominated by the myopic strategy so that there remains no other potential solution. It is quite remarkable that the introduction of secret reservation prices which are commonly used in the leading auction houses7 has this consequence for the open outcry auction.

One goal of this paper was to give more economic meaning to the Gale–Shapley algorithm by presenting an auction game in which rational agents should construct the outcome according to this iteration scheme. I showed under which conditions the buyers will indeed submit their W-strategies to the auctioneer, but this leaves us with the question whether the owners are interested to behave as specified in (W2) above. Suppose the auctioneer is an additional player who represents the owners’ interests and who decides which of the offers to keep in the next round. The auction is over if there is no progress in the bids. In this extension of the auction game the auctioneer is indifferent between all strategies which guarantee a progress in each round. But no matter how this indifference is broken up the buyers know that a new highest offer will be accepted sooner or later so that they will just repeat their W-bids until they are successful. This extension of the game can be interpreted as a (trivial) two-sided matching auction and it can give a two-sided strategic justification of the Gale–Shapley algorithm. It cannot, however, solve the difficult incentive problems which arise if the owners of the objects choose their reservation prices strategically or if they have to keep or reject their offers without a central coordinator. Such models would give the owners the opportunity to credibly manipulate the auction and it is well-known that they may well have an incentive to do so.