Computer Science – Computer Science and Game Theory
Scientific paper
2010-06-24
Computer Science
Computer Science and Game Theory
Scientific paper
In this paper, we study the class of competitive equilibria in two sided matching markets with general (non-quasilinear) utility functions. Mechanism design in general non-quasilinear setting is one of the biggest challenges in mechanism design. General non-quasilinear utilities can for example model smooth budget constraints as a special case. Due to the difficulty of dealing with arbitrary non-quasilinear utilities, a large fraction of the existing work have considered the simpler case of quasilinear utilities with hard budget constraints and they all rely on some form of ascending auction. For general non-quasilinear utilities, we show that such ascending auctions may not even converge in finite time. As such, almost all of the existing work on general non-quasilinear utility function (\cite{DG85,G84,Q82}) have resorted to non-constructive proofs based on fixed point theorems or discretization. In this paper, we give the first direct characterization of competitive equilibria in such markets. Our approach is constructive and solely based on induction. Our characterization reveals striking similarities between the payments at the lowest competitive equilibrium for general utilities and VCG payments for quasilinear utilities. We also show that the mechanism that outputs the lowest competitive equilibrium is group strategyproof. We also present a class of price discriminating truthful mechanisms for selling heterogeneous goods to unit-demand buyers with general utility functions and from that we derive a natural welfare maximizing mechanism for ad-auctions that combines pay per click and pay per impression advertisers with general utility functions. Our mechanism is group strategyproof even if the search engine and advertisers have different estimates of clickthrough rates. This also answers an open question raised by \cite{AMPP09}.
Alaei Saeed
Jain Kamal
Malekian Azarakhsh
No associations
LandOfFree
Competitive Equilibrium in Two Sided Matching Markets with General Utility Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Competitive Equilibrium in Two Sided Matching Markets with General Utility Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Competitive Equilibrium in Two Sided Matching Markets with General Utility Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-675371