PhD Proposal: Allocation in Networks with Economic Applications

Talk
Melika Abolhassani
Time: 
05.29.2015 13:00 to 14:30
Location: 

AVW 3258

In this proposal, three assignment problems are introduced and they are approached based on the context they are presented in. The underlying graph of assignment problems is usually a bipartite graph with two sets of vertices corresponding to agents and resources (generalized graph is also possible in some cases). An edge might show interest of the agent in that resource or willingness to produce of the corresponding product to name a few examples.
The first problem considered in this proposal is an online matching problem. In online matching problems 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 offline side upon arrival. Each vertex can only be matched to an unmatched vertex upon arrival 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 offline vertex only if we eliminate its previous online match from the graph. The goal is to maximize the expected size of matching. We propose a randomized algorithm that achieves a ratio greater than 0.5 if the online nodes have bounded degree. We generalize our approach to the case where edges are also weighted and the goal is to maximize the weight of edges of the matching we form.
The second problem is a two stage stochastic matching problem in both online and offline versions. In this work, a coordinator tries to benefit by having access to the statistics of 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 to huge savings for them since they have to take the risk of all hotel rooms being sold out. Instead of taking this risk, individual customers make contracts with a coordinator who can spread the risk over many customers he is giving service to and also have more information on the probability distribution of future prices. In the first stage, the coordinator agrees to serve some buyers, and then in the second stage, once the final prices have been revealed, he books rooms for them just as he promised. Agreements with buyers consist of a set of acceptable hotels and a price. We investigate two models for this problem. One with the details of agreements proposed by the coordinator in which we show prices yielding the optimal profit up to a small additive loss can be found by a polynomial time algorithm. In the second model, the details of agreements are proposed by the buyer, and we propose a bicriteria-style approximation that gives a constant-factor approximation to the objective function by allowing a bounded fraction of our hotel bookings to overlap.
The third assignment problem that is considered in this thesis is a generalized version of the Cournot Competition which is one of the foundational models in economics. In the traditional version, firms 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 in each market increases with the quantity it produces. We study Cournot Competition on a bipartite network of firms and markets. The edges in this network demonstrate access of a firm 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 firms, and the cost of production for each firm is a function of its production in different markets. Our goal is to give polynomial time algorithms to find the quantity produced by firms in each market at equilibrium for generalized cost and price functions.
Examining Committee:
Committee Chair: Dr. Mohammad Taghi Hajiaghayi
Dept's Representative Dr. V. S. Subrahmanian
Committee Member(s): Dr. Andrew Childs