text: In sponsored search, a number of advertising slots is available on a search results page, and have to be allocated among a set of advertisers competing to display an ad on the page. This gives rise to a bipartite matching market that is typically cleared by the way of an automated auction. Several auction mechanisms have been proposed, with variants of the Generalized Second Price (GSP) being widely used in practice. A rich body of work on bipartite matching markets builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik. We apply insights from this line of research into the structure of stable outcomes and their incentive properties to advertising auctions. We model advertising auctions in terms of an assignment model with linear utilities, extended with bidder and item specific maximum and minimum prices. Auction mechanisms like the commonly used GSP or the well-known Vickrey-Clarke-Groves (VCG) are interpreted as simply computing a in this model, for a suitably defined set of bidder preferences. In our model, the existence of a stable matching is guaranteed, and under a non-degeneracy assumption a bidder-optimal stable matching exists as well. We give an algorithm to find such matching in polynomial time, and use it to design truthful mechanism that generalizes GSP, is truthful for profit-maximizing bidders, implements features like bidder-specific minimum prices and position-specific bids, and works for rich mixtures of bidders and preferences.
  @cite_6: 
  @cite_19: The problem of eliciting honest preferences from individuals who must be assigned to a set of positions is considered. Individuals know that they will be charged for the positions to which they are assigned. A set of prices that provide no incentive for the individual to misrepresent his preferences is suggested. It is shown that these prices constitute an element of the optimal solution to the dual of a linear programming assignment problem. Both the optimal allocation and the prices to be charged can be derived by solving two linear programming problems once preferences have been elicited. The procedure can usefully be viewed as a simulation of a competitive market under conditions where such a market cannot be expected to function well. It results in an efficient allocation where all resources are valued at their opportunity costs and "consumer surplus" is maximized; its outcome thus has the desirable properties of competitive market equilibria.
  @cite_13: The goal of this chapter is to describe efficient auctions for multiple, indivisible objects in terms of the duality theory of linear programming. Because of its well-known incentive properties, we shall focus on Vickrey auctions. These are efficient auctions in which buyers pay the social opportunity cost of their purchases and consequently are rewarded with their (social) marginal product. We use the assignment model to frame our analysis.
  @cite_25: The assignment game is a model for a two-sided market in which a product that comes in large, indivisible units (e.g., houses, cars, etc.) is exchanged for money, and in which each participant either supplies or demands exactly one unit. The units need not be alike, and the same unit may have different values to different participants. It is shown here that the outcomes in thecore of such a game — i.e., those that cannot be improved upon by any subset of players — are the solutions of a certain linear programming problem dual to the optimal assignment problem, and that these outcomes correspond exactly to the price-lists that competitively balance supply and demand. The geometric structure of the core is then described and interpreted in economic terms, with explicit attention given to the special case (familiar in the classic literature) in which there is no product differentiation — i.e., in which the units are interchangeable. Finally, a critique of the core solution reveals an insensitivity to some of the bargaining possibilities inherent in the situation, and indicates that further analysis would be desirable using other game-theoretic solution concepts.
  @cite_20: The paper presents a model of an exchange economy with indivisible goods and money. There are a finite number of agents, each one initially endowed with a certain amount of money and at most one indivisible good. Each agent is assumed to have no use for more than one indivisible good. It is proved that the core of the economy is nonempty. If utility functions are increasing in money, and if the initial resources in money are in some sense “sufficient” the core allocations coincide with the competitive equilibrium allocations.
summary: The assignment model @cite_25 , (see also @cite_20 @cite_6 ) differs in that each player derives a certain value from being matched to each person of the opposite sex, and side payments between partners are allowed. The goal of each player is to maximize his or her payoff which is the sum of partner's value and monetary payment (positive or negative negative) from the partner. The set of stable outcomes is non-empty by a linear programming argument. In fact, each stable outcome corresponds to a maximum-weight matching, and player payoffs correpond to dual variables of the maximum matching LP. A man-optimal outcome is guaranteed to exist, and its allocation and prices are identical to the VCG mechanism for maximum weight matchings @cite_19 @cite_13 .