JabRef references

Boehmer N, Faliszewski P, Janeczko Ł and Kaczmarczyk A (2023), "Robustness of Participatory Budgeting Outcomes: Complexity and Experiments", In Algorithmic Game Theory. Cham , pp. 161-178. Springer Nature Switzerland.

[Abstract] [BibTeX]

Abstract: We study the robustness of approval-based participatory budgeting (PB) rules to random noise in the votes. First, we analyze the computational complexity of the #Flip-Bribery problem, where given a PB instance we ask for the number of ways in which we can flip a given number of approvals in the votes, so that a specific project is selected. This problem captures computing the funding probabilities of projects in case random noise is added. Unfortunately, it is intractable even for the simplest PB rules. Second, we analyze the robustness of several prominent PB rules (including the basic greedy rule and the Method of Equal Shares) on real-world instances from Pabulib. Using sampling, we quantify the extent to which simple, greedy PB rules are more robust than proportional ones, and we identify three types of (very) non-robust projects in real-world PB instances.

BibTeX:

@inproceedings{Boehmer2023,
  author = {Boehmer, Niclas and Faliszewski, Piotr and Janeczko, Łukasz and Kaczmarczyk, Andrzej},
  editor = {Deligkas, Argyrios and Filos-Ratsikas, Aris},
  title = {Robustness of Participatory Budgeting Outcomes: Complexity and Experiments},
  booktitle = {Algorithmic Game Theory},
  publisher = {Springer Nature Switzerland},
  year = {2023},
  pages = {161--178}
}

Aumann Y and Dombb Y (2010), "Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games", In Algorithmic Game Theory. Berlin, Heidelberg , pp. 66-77. Springer Berlin Heidelberg.

[Abstract] [BibTeX]

Abstract: We analyze the Pareto efficiency, or inefficiency, of solutions to routing games and load balancing games, focusing on Nash equilibria and greedy solutions to these games. For some settings, we show that the solutions are necessarily Pareto optimal. When this is not the case, we provide a measure to quantify the distance of the solution from Pareto efficiency. Using this measure, we provide upper and lower bounds on the ``Pareto inefficiency'' of the different solutions. The settings we consider include load balancing games on identical, uniformly-related, and unrelated machines, both using pure and mixed strategies, and nonatomic routing in general and some specific networks.

BibTeX:

@inproceedings{Aumann2010,
  author = {Aumann, Yonatan and Dombb, Yair},
  editor = {Kontogiannis, Spyros and Koutsoupias, Elias and Spirakis, Paul G.},
  title = {Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games},
  booktitle = {Algorithmic Game Theory},
  publisher = {Springer Berlin Heidelberg},
  year = {2010},
  pages = {66--77}
}

Kobayashi Y, Mahara R and Sakamoto S (2023), "EFX Allocations for Indivisible Chores: Matching-Based Approach", In Algorithmic Game Theory. Cham , pp. 257-270. Springer Nature Switzerland.

[Abstract] [BibTeX]

Abstract: One of the most important topics in discrete fair division is whether an EFX allocation exists for any instance. Although the existence of EFX allocations is a standing open problem for both goods and chores, the understanding of the existence of EFX allocations for chores is less established compared to goods. We study the existence of EFX allocation for chores under the assumption that all agent's cost functions are additive. Specifically, we show the existence of EFX allocations for the following three cases: (i) the number of chores is at most twice the number of agents, (ii) the cost functions of all agents except for one are identical ordering, and (iii) the number of agents is three and each agent has a personalized bi-valued cost function. Furthermore, we provide a polynomial time algorithm to find an EFX allocation for each case.

BibTeX:

@inproceedings{Kobayashi2023,
  author = {Kobayashi, Yusuke and Mahara, Ryoga and Sakamoto, Souta},
  editor = {Deligkas, Argyrios and Filos-Ratsikas, Aris},
  title = {EFX Allocations for Indivisible Chores: Matching-Based Approach},
  booktitle = {Algorithmic Game Theory},
  publisher = {Springer Nature Switzerland},
  year = {2023},
  pages = {257--270}
}

Botan S, Ritossa A, Suzuki M and Walsh T (2023), "Maximin Fair Allocation of Indivisible Items Under Cost Utilities", In Algorithmic Game Theory. Cham , pp. 221-238. Springer Nature Switzerland.

[Abstract] [BibTeX]

Abstract: We study the problem of fairly allocating indivisible goods among a set of agents. Our focus is on the existence of allocations that give each agent their maximin fair share---the value they are guaranteed if they divide the goods into as many bundles as there are agents, and receive their lowest valued bundle. An MMS allocation is one where every agent receives at least their maximin fair share. We examine the existence of such allocations when agents have cost utilities. In this setting, each item has an associated cost, and an agent's valuation for an item is the cost of the item if it is useful to them, and zero otherwise.

BibTeX:

@inproceedings{Botan2023,
  author = {Botan, Sirin and Ritossa, Angus and Suzuki, Mashbat and Walsh, Toby},
  editor = {Deligkas, Argyrios and Filos-Ratsikas, Aris},
  title = {Maximin Fair Allocation of Indivisible Items Under Cost Utilities},
  booktitle = {Algorithmic Game Theory},
  publisher = {Springer Nature Switzerland},
  year = {2023},
  pages = {221--238}
}

Wagner J and Meir R (2023), "Strategy-Proof Budgeting via a VCG-Like Mechanism", In Algorithmic Game Theory. Cham , pp. 401-418. Springer Nature Switzerland.

[Abstract] [BibTeX]

Abstract: We present a strategy-proof public goods budgeting mechanism where agents determine both the total volume of expenses and specific allocation. It is constructed as a modification of VCG to a non-typical environment, where we do not assume quasi-linear utilities or direct revelation. We further show that under plausible assumptions it satisfies strategyproofness in strictly dominant strategies, and consequently implements the social optimum as a Coalition-Proof Nash Equilibrium. A primary (albeit not an exclusive) motivation of our model is Participatory Budgeting, where members of a community collectively decide the spending policy of public tax dollars. In that scenario, charging individual payments from voters as the VCG method instructs would be undesirable, thus our second main result provides that, under further specifications relevant in that context, these payments will vanish in large populations, and can further be constructed as non-positive in some cases.

BibTeX:

@inproceedings{Wagner2023,
  author = {Wagner, Jonathan and Meir, Reshef},
  editor = {Deligkas, Argyrios and Filos-Ratsikas, Aris},
  title = {Strategy-Proof Budgeting via a VCG-Like Mechanism},
  booktitle = {Algorithmic Game Theory},
  publisher = {Springer Nature Switzerland},
  year = {2023},
  pages = {401--418}
}

Gao Z, Hastie T and Tibshirani R (2021), "Assessment of heterogeneous treatment effect estimation accuracy via matching", Statistics in Medicine. Vol. 40(17), pp. 3990-4013.