Mechanisms for Fair Allocation Problems: No-Punishment Payment Rules in Verifiable Settings
Authors: G. Greco, F. Scarcello
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study allocation problems in a strategic setting where agents can misreport their private types, and we study mechanisms with verification from both the algorithmic and the computational complexity viewpoint. We show that in the given setting none of the classical impossibility theorems discussed above holds. In particular, we exhibit a payment rule pξ that turns any optimal allocation algorithm, i.e., any algorithm computing an optimal allocation given the reported types, into a mechanism with verification such that: The mechanism is truthful. This is shown by pointing out a number of properties of allocation problems which are of interest on their own. The computational complexity of the proposed mechanism is also studied. It turns out that it is #P-complete so that, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed. |
| Researcher Affiliation | Academia | Gianluigi Greco EMAIL Dipartimento di Matematica e Informatica Universit a della Calabria I-87036 Rende, Italy; Francesco Scarcello EMAIL DIMES Universit a della Calabria I-87036 Rende, Italy |
| Pseudocode | Yes | Figure 4: Payment rule pξ. Input: A type vector θ Θ, and a feasible allocation π for Sθ; Assumption: The verifier v (for t) is available, with v(π) = (v1, ..., vn); Notation: Sθ = A, G, ζθ , wθ = (w1, ..., wn), wv(π) = (wv1, ..., wvn); 1. Let C denote the set of all possible subsets of A; 2. For each i A and C C, 3. Compute an optimal allocation πC,i for C, img(π), ζ(vi,θ i) w.r.t. w(vi,θ i); 4. For each agent i A, 5. | For each set C C such that i C, 6. | | Let 1 C,i(π, θ) := wvi(πC,i) + P j C\{i} wj(πC,i); (=val(πC,i, w(vi,θ i))); 7. | Let 2 C,i(π, θ) := P j C\{i} wj(πC\{i},i); (=val(πC\{i},i, w(vi,θ i))); 8. | Let ξi(π, wθ) := P C C (|A| |C|)!(|C| 1)!|A|! ( 1 C,i(π, θ) 2 C,i(π, θ)); 9. Define pξ i (π, wθ) := ξi(π, wθ) wvi(π); Figure 5: Payment rule ˆpξ. Input: A type vector θ Θ, a feasible allocation π for Sθ, and an integer m > 0; Assumption:The verifier v (for t) is available, with v(π) = (v1, ..., vn); Notation: Sθ = A, G, ζθ , wθ = (w1, ..., wn), wv(π) = (wv1, ..., wvn); 1. Generate a set C of m subsets of A, and let ˆC := C {(A \ C) {i} | C C, i C} {A}; 2. For each i A and C ˆC, 3. | Compute an optimal allocation πC,i for C, img(π), ζ(vi,θ i) w.r.t. w(vi,θ i); 4. Compute an optimal allocation for πC\{i},i for C \ {i}, img(π), ζ(vi,θ i) w.r.t. w(vi,θ i); 5. For each agent i A, 6. Compute ξi(π, wθ) as in Figure 4 (steps 4 8), with C := ˆC; 7. Repeat Θ(log(1/δ)) times steps 1, 2, and 5, and 8. Let ˆξ(π, wθ) be the component-wise median vector of these vectors ξ(π, wθ); 9. Define ˆpξ i (π, wθ) := ˆξi(π, wθ) wvi(π); |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It does not mention any repository links, explicit code release statements, or code in supplementary materials. |
| Open Datasets | No | The paper discusses various application scenarios (e.g., Italian Research Assessment Program, Scheduling, Wireless Communication Networks) in Appendix A, but these are illustrative examples of where the theoretical framework *could* be applied, rather than actual datasets used for experimental evaluation within this paper. No specific datasets are identified or made available for the research presented. |
| Dataset Splits | No | The paper is theoretical and focuses on mechanism design and computational complexity. It does not conduct experiments with datasets, and therefore, no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper is theoretical and focuses on mechanism design and computational complexity. It does not describe any experimental implementation that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting mechanism design and complexity analysis, and does not include an experimental evaluation section with hyperparameters or training configurations. |