Auctions, Equilibria, and Budgets

Loading...
Thumbnail Image

Date

2012

Authors

Bhattacharya, Sayan

Advisors

Munagala, Kamesh

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

378
views
545
downloads

Abstract

We design algorithms for markets consisting of multiple items, and agents with budget constraints on the maximum amount of money they can afford to spend. This problem can be considered under two broad frameworks. (a) From the standpoint of Auction Theory, the agents valuation functions over the items are private knowledge. Here, a "truthful auction" computes the subset of items received by every agent and her payment, and ensures that no agent can manipulate the scheme to her advantage by misreporting her valuation function. The question is to design a truthful auction whose outcome can be computed in polynomial time. (b) A different, but equally

important, question is to investigate if and when the market is in "equilibrium",

meaning that every item is assigned a price, every agent gets her utility-maximizing subset of items under the current prices, and every unallocated item is priced at zero.

First, we consider the setting of multiple heterogeneous items and present approximation algorithms for revenue-optimal truthful auctions. When the items are homogeneous, we give an efficient algorithm whose outcome defines a truthful and Pareto-optimal auction. Finally, we focus on the notion of "competitive equilibrium", which is a well known solution concept for market clearing. We present efficient algorithms for finding competitive equilibria in markets with budget constrained agents, and show that these equilibria outcomes have strong revenue guarantees.

Description

Provenance

Citation

Citation

Bhattacharya, Sayan (2012). Auctions, Equilibria, and Budgets. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/6143.

Collections


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.