Single-object resource allocation in multiple bid declaration with preferential order

This paper proposes solutions to a problem called single-object resource allocation with preferential orders and efficient algorithms for semi-optimal allocations. Formalizations of resource allocation problems are widely used in many applications. Although many studies on allocation methods have focused on maximizing social welfare or total revenues, they have rarely taken into account agents' individual preferential orders that may have interfered with one another. Our proposed framework allocates one unit of resources to individual users but allows them to declare multiple resources with their own preferential orders. It then tries to allocate a resource to each agent by not only maximizing the total values but also considering the agent's preferences, at least, by ensuring that no or few dissatisfactions are reported. This is obviously a combinatorial problem to find optimal solutions. Thus, we propose efficient methods for semi-optimal solutions (allocations) that satisfy as many user preferences as possible. Finally, we analyze the quality of solutions and computation time by comparing them with the solutions obtained by CPLEX. Then, we experimentally demonstrate that the proposed methods are extremely efficient, while the reduced quality of their solutions is quite small.