Computer Science and Game Theory

New submissions

• New submissions
• Replacements

New submissions for Fri, 10 May 24

[1]  arXiv:2405.05870 [pdf, other]

Title: Selecting the Most Conflicting Pair of Candidates

Authors: Théo Delemazure, Łukasz Janeczko, Andrzej Kaczmarczyk, Stanisław Szufa

Comments: Accepted for publication at IJCAI-24; 27 pages; 11 figures

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA)

We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences. By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them. Consequently, we design committee voting rules compliant with our desiderata, introducing conflictual voting rules. A subsequent deepened analysis sheds more light on how they operate. Our investigation identifies various aspects of conflict, for which we come up with relevant axioms and quantitative measures, which may be of independent interest. We support our theoretical study with experiments on both real-life and synthetic data.

[2]  arXiv:2405.05905 [pdf, other]

Title: Truthful Aggregation of LLMs with an Application to Online Advertising

Authors: Ermis Soumalias, Michael J. Curry, Sven Seuken

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI)

We address the challenge of aggregating the preferences of multiple agents over LLM-generated replies to user queries, where agents might modify or exaggerate their preferences. New agents may participate for each new query, making fine-tuning LLMs on these preferences impractical. To overcome these challenges, we propose an auction mechanism that operates without fine-tuning or access to model weights. This mechanism is designed to provably converge to the ouput of the optimally fine-tuned LLM as computational resources are increased. The mechanism can also incorporate contextual information about the agents when avaiable, which significantly accelerates its convergence. A well-designed payment rule ensures that truthful reporting is the optimal strategy for all agents, while also promoting an equity property by aligning each agent's utility with her contribution to social welfare - an essential feature for the mechanism's long-term viability. While our approach can be applied whenever monetary transactions are permissible, our flagship application is in online advertising. In this context, advertisers try to steer LLM-generated responses towards their brand interests, while the platform aims to maximize advertiser value and ensure user satisfaction. Experimental results confirm that our mechanism not only converges efficiently to the optimally fine-tuned LLM but also significantly boosts advertiser value and platform revenue, all with minimal computational overhead.

Replacements for Fri, 10 May 24

[3]  arXiv:2308.08047 (replaced) [pdf, ps, other]

Title: Correlated vs. Uncorrelated Randomness in Adversarial Congestion Team Games

Authors: Edan Orzech, Martin Rinard

Subjects: Computer Science and Game Theory (cs.GT)

[4]  arXiv:2308.09501 (replaced) [pdf, ps, other]

Title: Towards More Realistic Models for Refugee Integration: Anonymous Refugee Housing with Upper-Bounds

Authors: Šimon Schierreich

Subjects: Computer Science and Game Theory (cs.GT)

[5]  arXiv:2312.17364 (replaced) [pdf, ps, other]

Title: Randomness Requirements and Asymmetries in Nash Equilibria

Authors: Edan Orzech, Martin Rinard

Subjects: Computer Science and Game Theory (cs.GT)

• New submissions
• Replacements