University:
California State University, Northridge
Course:
ECON 101 | Economics for Everyday Life
Academic year:

2023
Views:

176

Pages:

3
Author:

Jithin J. I.

A CHARACTERIZATION OF OSP MECHANISMS Introduction In this section, we delve into the characterization of OSP (Ordinal Scoring Problem) mechanisms for binary allocation problems. We assume that the agents have finite domains. The goal is to understand the structural properties and mechanisms governing OSP. We'll discuss key observations, definitions, and insights that lead to a better understanding of these mechanisms. Basic Properties OSP-Graph of the - OSP mechanisms deal with binary allocation problems, where outcomes are binary (0 or 1). - We observe that the OSP-graph has edges with different weights based on the agents' preferences: - Positive-weight edges when an agent prefers 0 and 1 (w(a, b) = +ai). - Negative-weight edges when an agent prefers 1 and 0 (w(a, b) = ai). - These edges have strict inequalities due to the nature of agent preferences. Types and Structure of the Implementation Tree - We introduce the concepts of "0-always," "1-always," and "unclear" types for agents. - An agent's type is considered "sel-always" if they consistently prefer either 0 (sel = 0) or 1 (sel = 1). - Types that don't fall into either category are termed "unclear." Structure Queries of Admissible - Admissible queries in OSP mechanisms are characterized by two conditions: 1. 2. Homogeneous parts: Either all agents in a part consistently prefer 0 or 1. Agent revealability: When certain conditions are met, an agent's type becomes "revealable." Structure of Weight Cycles Negative- - Negative-weight cycles in OSP mechanisms have a special structure defined by four profiles. - These profiles involve preferences of agents for 0 and 1. - The absence of certain edges in the OSP-graph is a key characteristic of these cycles. Equivalence Interleaving to Weak - We show that, without loss of generality, we can focus on OSP mechanisms where agents are asked either top or bottom queries, except when agent types become revealable. - The notion of "extremal mechanisms" and "weak interleaving" is introduced. - We prove that an OSP mechanism exists if and only if an extremal mechanism with weak interleaving exists. Two-Way Greedy Algorithms - We emphasize that the characterization applies to both costs and valuations. - Monotone and antimonotone functions, in terms of type, are defined. - We discuss the connection between OSP mechanisms and adaptive priority algorithms. - New upper bounds on the approximation guarantee of OSP mechanisms are presented, independent of domain size or other assumptions. This understanding of OSP mechanisms and their structural properties is essential for designing, analyzing, and optimizing allocation mechanisms various scenarios. in