6 papers
Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification
Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia +2
Large Language Models (LLMs) using chain-of-thought have demonstrated great potential for solving complex reasoning and planning tasks. Despite these advances, LLM-generated output…
The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
Brian Hu Zhang, Ioannis Anagnostides, Kiriaki Fragkia +2
The proper equilibrium, introduced by Myerson (1978), is a classic refinement of the Nash equilibrium that has been referred to as the "mother of all refinements." For normal-form…
The Complexity of Equilibrium Refinements in Potential Games
Ioannis Anagnostides, Maria-Florina Balcan, Kiriaki Fragkia +3
The complexity of computing equilibrium refinements has been at the forefront of algorithmic game theory research, but it has remained open in the seminal class of potential games;…
Beyond Symmetry in Repeated Games with Restarts
Henry Fleischmann, Kiriaki Fragkia, Ratip Emin Berker
Infinitely repeated games support equilibrium concepts beyond those present in one-shot games (e.g., cooperation in the prisoner's dilemma). Nonetheless, repeated games fail to cap…
Learning in Structured Stackelberg Games
Maria-Florina Balcan, Kiriaki Fragkia, Keegan Harris
We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the f…
Algorithmic Contract Design for Crowdsourced Ranking
Kiriaki Frangias, Andrew Lin, Ellen Vitercik +1
Ranking is fundamental to many areas, such as search engine optimization, human feedback for language models, as well as peer grading. Crowdsourcing, which is often used for these…