Fairness, Learning and Efficiency in Markets with Budgeted Agent

In almost all online markets with monetary transactions, the participants have a limited budget which restricts their ability to purchase their desired commodities. Models from mechanism design, algorithm design and auction theory which study these online markets often ignore this important constraint.;This dissertation presents a deep study of such markets with budget limited agents, using theoretical models as well as data from real world auction markets. In chapter 2, we study the problem of a budget limited buyer who wants to buy a set of commodities, each from a different seller, to maximize her value. The budget feasible mechanism design problem aims to design a mechanism which incentivizes the sellers to truthfully report their cost, and maximizes the buyer's value while guaranteeing that the total payment does not exceed her budget. Such budget feasible mechanisms can model a principal in a crowdsourcing market interested in recruiting a set of workers (sellers) to accomplish a task for her. We present simple and close to optimum mechanisms for this problem when the valuation of the buyer is a monotone submodular function.;In chapter 3, we present a deep study of the behavior of real estate agents in the new online advertising platform provided by Zillow. We analyze behavior of the agents through time using the provided data from Zillow. We use a no-regret based algorithm to estimate the value of agents for impression opportunities. We observe that a significant proportion of bidders initially do not use the bid recommendation tool which has been provided by Zillow. This proportion gradually declines over time. We argue that the agents gradually trust the system by learning that the platform adequately optimizes bids on their behalf and the increased effort of experimenting with alternative bids is not worth the potential increase in their net utility.;In chapter 4, we show equilibria of markets with budget limited agents can be used to achieve fairness for problems of matching without money with agents who have preferences over commodities. A unit budget with artificial money is given to each agent for achieving fairness. We also provide polynomial time algorithms for finding the equilibria of these markets.