Assignment problems and their application in economics

Abstract

Four assignment problems are introduced in this thesis, and they are approached

based on the context they are presented in. The underlying graphs of

the assignment problems in this thesis are in most cases bipartite graphs with two

sets of vertices corresponding to the agents and the resources. An edge might show

the interest of an agent in a resource or willingness of a manufacturer to produce

the corresponding product of a market, to name a few examples.

The rst problem studied in this thesis is a two-stage stochastic matching

problem in both online and oine versions. In this work, which is presented in

Chapter 2 of this thesis, a coordinator tries to benet by having access to the

statistics of the future price discounts which can be completely unpredictable for

individual customers. In our model, individual risk-averse customers want to book

hotel rooms for their future vacation; however, they are unwilling to leave booking to

the last minute which might result in huge savings for them since they have to take

the risk of all the hotel rooms being sold out. Instead of taking this risk, individual

customers make contracts with a coordinator who can spread the risk over many

such cases and also has more information on the probability distribution of the future

prices. In the rst stage, the coordinator agrees to serve some buyers, and then in

the second stage, once the nal prices have been revealed, he books rooms for them

just as he promised. An agreement between the coordinator and each buyer consists

of a set of acceptable hotels for the customer and a single price. Two models for

this problem are investigated. In the rst model, the details of the agreements are

proposed by the buyer, and we propose a bicriteria-style approximation algorithm

that gives a constant-factor approximation to the objective function by allowing a

bounded fraction of our hotel bookings to overlap. In the second model, the details

of the agreements are proposed by the coordinator, and we show the prices yielding

the optimal prot up to a small additive loss can be found by a polynomial time

algorithm.

In the third chapter of this thesis, two versions of the online matching problem

are analyzed with a similar technique. Online matching problems have been studied

by many researchers recently due to their direct application in online advertisement

systems such as Google Adwords. In the online bipartite matching problem, the

vertices of one side are known in advance; however, the vertices of the other side

arrive one by one, and reveal their adjacent vertices on the oine side only upon

arrival. Each vertex can only be matched to an unmatched vertex once it arrives and

we cannot match or rematch the online vertex in the future. In the online matching

problem with free disposal, we have the option to rematch an already matched oine

vertex only if we eliminate its previous online match from the graph. The goal is to

maximize the expected size of the matching. We propose a randomized algorithm

that achieves a ratio greater than 0:5 if the online nodes have bounded degree. The

other problem studied in the third chapter is the edge-weighted oblivious matching in

which the weights of all the edges in the underlying graph are known but existence

of each edge is only revealed upon probing that edge. The weighted version of

the problem has applications in pay-per-click online advertisements, in which the

revenue for a click on a particular ad is known, but it is unknown whether the user

will actually click on that ad. Using a similar technique, we develop an algorithm

with approximation factor greater than 0:5 for this problem too.

In Chapter 4, a generalized version of the Cournot Competition (a foundational

model in economics) is studied. In the traditional version, rms are competing in

a single market with one heterogeneous good, and their strategy is the quantity

of good they produce. The price of the good is an inverse function of the total

quantity produced in the market, and the cost of production for each rm in each

market increases with the quantity it produces. We study Cournot Competition on

a bipartite network of rms and markets. The edges in this network demonstrate

access of a rm to a market. The price of the good in each market is again an

inverse function of the quantity of the good produced by the rms, and the cost of

production for each rm is a function of its production in dierent markets. Our

goal is to give polynomial time algorithms to nd the quantity produced by rms

in each market at the equilibrium for generalized cost and price functions.

The nal chapter of this thesis is on analyzing a problem faced by online

marketplaces such as Amazon and ebay which deal with huge datasets registering

transaction of merchandises between many buyers and sellers. As the size of datasets

grow, it is important that the algorithms become more selective in the amount of

data they store. Our goal is to develop pricing algorithms for social welfare (or

revenue) maximization that are appropriate for use with the massive datasets in

these networks. We specially focus on the streaming setting, the common model

for big data analysis. Furthermore, we include hardness results (lower bounds)

on the minimum amount of memory needed to calculate the exact prices and also

present algorithms which are more space ecient than the given lower bounds but

approximate the optimum prices for the goods besides the revenue or the social

welfare of the mechanism.