Browsing by Author "Munagala, Kamesh"

In public decision making, we are confronted with the problem of aggregating the conflicting preferences of many individuals about outcomes that affect the group. Examples of public decision making include allocating shared public resources and social choice or voting. We study these problems from the perspective of an algorithm designer who takes the preferences of the individuals and the constraints of the decision making problem as input and efficiently computes a solution with provable guarantees with respect to fairness and welfare, as defined on individual preferences.

Concerning fairness, we develop the theory of group fairness as core or proportionality in the allocation of public goods. The core is a stability based notion adapted from cooperative game theory, and we show extensive algorithmic connections between the core solution concept and optimizing the Nash social welfare, the geometric mean of utilities. We explore applications in public budgeting, multi-issue voting, memory sharing, and fair clustering in unsupervised machine learning.

Regarding welfare, we extend recent work in implicit utilitarian social choice to choose approximately optimal public outcomes with respect to underlying cardinal valuations using limited ordinal information. We propose simple randomized algorithms with strong utilitarian social cost guarantees when the space of outcomes is metric. We also study many other desirable properties of our algorithms, including approximating the second moment of utilitarian social cost. We explore applications in voting for public projects, preference elicitation, and deliberation.

The recent emergence of new successful two-sided online platforms has transformed the concept of a marketplace. Numerous two-sided mechanism design problems, including those studied in this thesis, are motivated by these platforms. Similar to any other mechanism design problem, we wish to optimize an objective in the presence of selfish agents. However, there are unique features to a two-sided market, such as supply uncertainty and the need for ensuring budget balance, which make these problems particularly challenging. In our problems, we design models to capture the two-sidedness, identify the challenges, and use algorithmic techniques to solve these problems.

We start with a Bayesian single item auction with n independent buyers. For this problem, we show how the existence of a trusted intermediary can result in a better outcome for buyers without hurting the seller's revenue. In this model, the intermediary gets to see the true valuations of buyers and will reveal some information after that in the form of a signal. The intermediary does not have any control over agents after sending this signal, and any agent only maximizes their utility. This essentially means that the seller will run an optimal auction conditioned on receiving any signal. For this problem, we design approximately optimal ways of revealing information.

The previous problem is an interesting model to show how a platform can mediate in the market and improve the outcome for every agent. That problem is a single item static problem. Next, we focus on pricing in two problems with multiple dynamic agents on the seller side. The first problem is an extension of the multiple-choice prophet inequality to the setting in which each item might disappear after an a priori unknown amount of time. This can be viewed as a way to model the supply uncertainty arising because of the fact that different sellers might depart after some time. Considering the importance of prophet inequalities in online posted pricing mechanisms, we hope that incorporating features of two-sided markets in the model and finding new prophet inequalities will be useful and provide new insights.

In our last problem, we design a model to capture a general dynamic two-sided market. In our model, agents (buyers and sellers) with heterogeneous valuations/costs, service quality requirements, and patience levels (or deadlines) arrive over time. Both buyers and sellers arrive to the market following Poisson processes, and each buyer/seller has a private value/cost for service, as well as a private patience level for receiving/providing service. In addition, each agent has a known location in an underlying metric space, where the metric distance between any buyer and seller captures the quality of the corresponding match. The platform knows the distribution over values/costs and patience levels and can post prices and wages at nodes in the metric space, as well as choose agents for matching. It uses these controls to maximize the social surplus subject to weak budget balance while guaranteeing a high match quality and a service time (with a high probability) smaller than their patience.

Efficiency and fairness are two major objectives in designing economic systems -- they provide guidelines on the desirability of economic solutions. However, perfectly efficient and fair utopian economies are often nonexistent or impractical, due to incentives, lack of information, computational hardness, etc. In this dissertation, we address this impossibility with methodology from the study of approximation algorithms. Through various cases in the field of computational economics, we demonstrate how to establish and improve the design of provably guaranteed approximations on an ideal yet impossible level of efficiency and fairness. En route, we resolve several open questions in computational social choice and mechanism design.

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.

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

\abstract

{\em Mechanism design} studies optimization problems taking into accounts of the selfish agents. {\em Network externality} is the effect a consumer receives from other consumers of the same good. This effect can be negative or positive. We first consider several mechanism design problems under the network externality assumption. The externality model used in this dissertation is more general than the widely used cardinality based model. In particular the network we consider in this dissertation is a graph, which is not necessarily complete. Our goal is to design {\em truthful} mechanisms to maximize the seller's revenue. Our main results under the network externality utility model are several optimal or near optimal mechanisms for {\em digital goods auctions}. To do so we invent several novel approximation schemes as well as applying results from the {\em approximation algorithm} literature. In particular when the agents exhibit negative network externality, we first model the problem as a two staged {\em pricing game}. We then show that the pricing game is an exact {\em potential game} which always admits a pure {\em Nash Equilibrium}. We then study the {\em best} and {\em worst} Nash Equilibrium in this game in terms of the revenue. We show two positive results. For the best Nash Equilibrium we show a $2$-approximation to the maximum revenue on bipartite graphs. For the worst Nash Equilibrium we use the notion of a {\em $\delta$-relaxed} equilibrium. In the sense that the prices for the same type of agents are within $\delta$ factor of each other. We accompany our positive results with matching hardness results. On the other hand, when the agents exhibit positive network externality, we take the {\em Myersonian} approach. We first give a complete characterization for all the truthful mechanisms. Using this characterization we present a truthful mechanism which achieves the optimal expected revenue among all the truthful mechanisms when the prior distributions of the agents are {\em independent} and {\em regular}. We also show near optimal mechanisms when the prior distributions are possibly {\em correlated}.

{\em Prior-free} auctions can approximate meaningful benchmarks for

non-identical bidders only when sufficient qualitative information

about the bidder asymmetry is publicly known.

We consider digital goods auctions where there is a {\em

total ordering} of the bidders that is known to the seller,

where earlier bidders are in some sense thought to have higher

valuations.

We define

an appropriate revenue benchmark: the maximum revenue that can be

obtained from a bid vector using prices that are nonincreasing in the

bidder ordering and bounded above by the second-highest bid.

This {\em monotone-price benchmark} is always as large as the well-known

fixed-price benchmark, so designing prior-free auctions with

good approximation guarantees is only harder.

By design, an auction that approximates the monotone-price benchmark

satisfies a very strong guarantee: it is, in particular, simultaneously

near-optimal for

essentially every {\em Bayesian} environment in which bidders'

valuation distributions have nonincreasing monopoly prices, or in

which the distribution of each bidder stochastically dominates that

of the next. Even when there is no distribution over bidders'

valuations, such an auction still provides a quantifiable

input-by-input performance guarantee. We design a simple $O(1)$-competitive prior-free

auction for digital goods with ordered bidders.