Rice Univesrity Logo
    • FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Three Essays on Rationing, Matching and Scheduling

    Thumbnail
    Name:
    ESMEROK-DOCUMENT-2014.pdf
    Size:
    516.6Kb
    Format:
    PDF
    View/Open
    Author
    Esmerok, Ibrahim Baris
    Date
    2014-11-24
    Advisor
    Boylan, Richard
    Degree
    Doctor of Philosophy
    Abstract
    This dissertation consists of three chapters. In the first chapter, we are considering the problem of rationing a disposable indivisible good under satiated preferences. A standard of gains rationing (s.g.r.) method allocates successive units of good by following a linear ordering of individuals and non-zero demand pairs. The dual of a s.g.r. method is a standard of losses rationing (s.l.r.) method, it follows the same linear ordering to successively allocate units of deficit. In our main result, Theorem 1, we provide three characterizations of s.l.r. methods. The first characterization is by resource monotonicity (RM), strategy-proofness (SP), non-bossiness (NB), and a property we introduce in this chapter, independence of fully satisfied demand (IFSD). IFSD is weaker than both the well known consistency (CSY) axiom and a generalized version of RM that we introduce in this chapter, strong resource monotonicity (SRM). We offer the other two characterizations by replacing RM and IFSD in the first characterization with SRM, and by replacing IFSD and NB in the first characterization with CSY. We obtain an analogue of Theorem 1 for s.g.r. methods by using the duals of the axioms in Theorem 1. By combining SP and its dual with IFSD and its dual or with SRM or with the dual of SRM we provide three characterizations of fixed order priority rationing methods in Theorem 2. The second chapter is on roommate problems. We characterize Pareto efficient and group strategy-proof rules for roommate problems with an even number of individuals where individuals find all their potential partners acceptable. We define a priority rule (sequential dictatorship) as a recursive algorithm that matches individuals in successive rounds. Specifically in every round an individual with priority is matched to his top ranked partner among available individuals and the order of individuals with priority is a function of the prior matches. We then show that the class of Pareto efficient and group strategy-proof rules is equivalent to the family of priority rules. In our final chapter we consider a scheduling problem with deadlines. A group of individuals share a deterministic server which is capable of serving one job per unit of time. Every individual has a job and a cut off time slot (deadline) where service beyond this slot is as worthless as not getting any service at all. Individuals are indifferent between slots which are not beyond their deadlines (compatible slots). A schedule (possibly random) assigns the set of slots to individuals by respecting their deadlines. We only consider the class of problems where for every set of relevant slots (compatible with at least one individual) there are at least as many individuals who have a compatible slot in that set: we ignore the case of underdemand. For this class, we characterize the random scheduling rule which attaches uniform probability to every efficient deterministic schedule (uniform rule) by Pareto efficiency, equal treatment of equals, and probabilistic consistency (Chambers (2004)). We also provide an alternative description for the uniform rule by a ball drawing algorithm.
    Keyword
    Rationing; Assignment; Matching; Strategy-proofness; Probabilistic Consistency; More... Random Scheduling Less...
    Citation
    Esmerok, Ibrahim Baris. "Three Essays on Rationing, Matching and Scheduling." (2014) Diss., Rice University. https://hdl.handle.net/1911/87865.
    Metadata
    Show full item record
    Collections
    • Rice University Electronic Theses and Dissertations [13409]

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map

     

    Searching scope

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map