| In this dissertation, we study three resource allocation problems and the various issues that arise in them. The first problem deals with pricing and scheduling the customers arriving at a service facility, with the objective of maximizing the profits of the facility, when the value of service and time-sensitivity of a customer are his private information. We analyze the problem by modelling the service facility as an M/M/1 queue. For the scenario in which each customer belongs to one of N types , and under simplifying assumptions on the problem parameters, we characterize the structure of the optimal pricing-scheduling policy and design a polynomial-time algorithm to find it. We extend these results to the case where the service provider is restricted to offer at most m different levels of service. Finally, for the case where the types of customers form a continuum and the customers have a generalized delay cost structure, we identify the conditions under which the optimal mechanism gives preemptive priority to the customers with a higher waiting cost.; The second problem is about allocating a set of indivisible objects to agents in a fair and efficient manner. Each agent desires at most one object and has a ranking over the objects. Moreover, agents are allowed to have the same ranking for multiple objects. For the extreme special case in which each agent partitions the available objects into sets that are acceptable and unacceptable to him, we provide an algorithm that is ordinally efficient, envy-free and group strategy proof (a stronger version of strategy proofness). We apply it iteratively to provide an algorithm for the general case that is both ordinally efficient and envy free.; The third problem studies the situation where a set of agents arrive simultaneously to a service facility. Each agent requires the facility for a certain length of time and incurs a cost for each unit of time spent in queue. The goal is to determine monetary compensations that be viewed as being "fair", when the agents are served in an efficient order. To that end, we propose two solution concepts (RP and CRP cores), which serve to place upper bounds on the cost share of any coalition of agents. The solutions differ in the definition of the expected worth of a coalition, when the agents are served in a random order. We study each of these two concepts, as well as their compatibility with additional fairness criteria. |
