This thesis proposal aims to study problems that arise in economic settings from two aspects – game theoretic and computational. Economic settings form a natural setting where self interested agents interact with each other, often with a competitive spirit. In this thesis proposal, we ask how to design mechanisms that achieve the desired objectives such as social welfare or privacy, in the presence of the game theoretic interactions of the agents whose utilities are often not aligned with the objectives of the mechanism designer. We consider the design of mechanisms both in the presence and absence of money – a tool that is very useful, if present, to a mechanism designer to help align the utility of the agent with the overall objective.
In BGMS'11, we considered designing a pricing scheme to allocate limited resources to an online stream of buyers to maximize social welfare. This pricing scheme however fails to maintain the privacy of the purchase decisions of the buyers. In this proposal, we explore techniques to incorporate privacy in the pricing mechanism. The pricing mechanism naturally involves money. As a second question, we propose how in the absence of money, one can allocate limited resources to buyers to achieve proportional fairness in a strategy-proof manner.
The other perspective is computational. In DDSSS'13, we explored how well submodular functions, a class of functions used to model buyer valuations, can be approximated by some of its better understood sub-classes. Online allocation is an optimization problem that occurs often in economic settings. We propose to study online allocation of impressions to advertisers in the presence of multiple constraints (e.g. budget, number of impressions etc.) on the part of the advertisers. Prior work in this setting has considered the case where only one constraint is present.
Avrim Blum (Co-chair)
Anupam Gupta (Co-chair)
Jan Vondrak (IBM Almaden)