Research map / Learning theory and algorithms / Submodular and game algorithms
Fair and Truthful Mechanisms for Dichotomous Valuations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use prioritized egalitarian (PE) allocation with a fixed priority order | Submodular dichotomous valuations · Submodular dichotomous valuations | Welfare maximization | Helped |
| Use prioritized egalitarian (PE) allocation with a fixed priority order | Submodular dichotomous valuations · Submodular dichotomous valuations | Lorenz domination and fairness guarantees | Helped |
| Randomize agent priorities before running PE | Submodular dichotomous valuations · Submodular dichotomous valuations | Ex-ante envy-freeness | Helped |
| Randomize agent priorities before running PE | Submodular dichotomous valuations · Submodular dichotomous valuations | Ex-post EFX | Helped |
| Extend dichotomous valuations to XOS valuations | Truthful allocation mechanisms · XOS valuations | Welfare maximization | Hurt |
| Allow desired item values to vary in [1, 1 + ε] for submodular valuations | Truthful allocation mechanisms · ε-dichotomous submodular valuations | Welfare approximation ratio | Hurt |
| Require a deterministic truthful mechanism to be approximately welfare maximizing and give an agent at least one desired item when she desires two | Allocation mechanisms · Three items, two ε-leveled agents | Feasibility of the stated welfare and fairness guarantees | Hurt |
| Require a randomized truthful-in-expectation mechanism to always be reasonable | Allocation mechanisms · Two items, two ε-leveled agents | Ex-post Lorenz domination, min-square, NSW, lex-min, or EFX | Hurt |
| Round reported ε-leveled values down and use randomized mechanism ℳᴸ | Additive ε-dichotomous valuations · ε-leveled valuations | Welfare approximation: ρ = 1/(1 + ε) | Helped |
| Use randomized mechanism ℳᴸ with rounded valuations and held-out items | Additive ε-dichotomous valuations · ε-leveled valuations | Truthfulness in expectation | Helped |
| Use randomized mechanism ℳᴸ with rounded valuations and held-out items | Additive ε-dichotomous valuations · ε-leveled valuations | Maximin share and EF1 guarantees: ρ = 1/(1 + ε) | Helped |
| Use PE for additive dichotomous valuations | Additive dichotomous valuations · Additive dichotomous valuations | Maximin share | Helped |
Closest papers by meaning
- Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations (AAAI 2026 · similarity 0.92)
- Weighted Envy-Freeness for Submodular Valuations (AAAI 2024 · similarity 0.91)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.91)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.90)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.