Computer Science and Game Theory

Authors and titles for April 2009

[1] arXiv:0904.1696 [pdf, other]

Title: Undirected Graphs of Entanglement 3

Walid Belkhir

Comments: 33 pages

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM)

[2] arXiv:0904.2060 [pdf, other]

Title: Complementary cooperation, minimal winning coalitions, and power indices

Zhigang Cao, Xiaoguang Yang

Comments: 60 pages

Journal-ref: Theoretical Computer Science, 470 (2013) 53-92

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

[3] arXiv:0904.2061 [pdf, other]

Title: Selfish Bin Covering

Zhigang Cao, Xiaoguang Yang

Comments: 16 pages

Journal-ref: Theoretical Computer Science, 412, 2011, 7049-7058

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

[4] arXiv:0904.2400 [pdf, other]

Title: Pricing Randomized Allocations

Patrick Briest, Shuchi Chawla, Robert Kleinberg, S. Matthew Weinberg

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[5] arXiv:0904.2511 [pdf, other]

Title: One-Counter Markov Decision Processes

Tomáš Brázdil, Václav Brožek, Kousha Etessami, Antonín Kučera, Dominik Wojtczak

Comments: Updated preliminary version, submitted to SODA2010

Subjects: Computer Science and Game Theory (cs.GT); Formal Languages and Automata Theory (cs.FL)

[6] arXiv:0904.2540 [pdf, other]

Title: What does Newcomb's paradox teach us?

David H. Wolpert Gregory Benford

Comments: Revised version with analysis extended and clarified; 22 pages, 1 table

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

[7] arXiv:0904.2541 [pdf, other]

Title: Disproof of the Neighborhood Conjecture with Implications to SAT

Heidi Gebauer

Comments: 12 pages, 1 figure

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

[8] arXiv:0904.3325 [pdf, other]

Title: Decision Problems for Nash Equilibria in Stochastic Games

Michael Ummels, Dominik Wojtczak

Comments: 22 pages, revised version

Subjects: Computer Science and Game Theory (cs.GT); Logic in Computer Science (cs.LO)

[9] arXiv:0904.3501 [pdf, other]

Title: Incentive Compatible Budget Elicitation in Multi-unit Auctions

Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, Lirong Xia

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

[10] arXiv:0904.3528 [pdf, other]

Title: Deconstruction of Infinite Extensive Games using coinduction

Pierre Lescanne (LIP)

Comments: 19 p

Subjects: Computer Science and Game Theory (cs.GT); Logic in Computer Science (cs.LO)

[11] arXiv:0904.4193 [pdf, other]

Title: On the Power of Randomization in Algorithmic Mechanism Design

Shahar Dobzinski, Shaddin Dughmi

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[12] arXiv:0904.0544 (cross-list from cs.NI) [pdf, other]

Title: Mission-Aware Medium Access Control in Random Access Networks

Jaeok Park, Mihaela van der Schaar

Comments: 28 pages, 8 tables, 8 figures

Subjects: Networking and Internet Architecture (cs.NI); Computer Science and Game Theory (cs.GT); Information Theory (cs.IT)

[13] arXiv:0904.0644 (cross-list from cs.CC) [pdf, other]

Title: Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng

Subjects: Computational Complexity (cs.CC); Computer Science and Game Theory (cs.GT)

[14] arXiv:0904.1435 (cross-list from cs.CC) [pdf, other]

Title: Reducibility Among Fractional Stability Problems

Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

Subjects: Computational Complexity (cs.CC); Computer Science and Game Theory (cs.GT)

[15] arXiv:0904.1701 (cross-list from cs.LO) [pdf, other]

Title: The Star Height Hierarchy Vs. The Variable Hierarchy

Walid Belkhir

Subjects: Logic in Computer Science (cs.LO); Computer Science and Game Theory (cs.GT)

[16] arXiv:0904.1703 (cross-list from cs.DM) [pdf, other]

Title: Closure Under Minors of Undirected Entanglement

Walid Belkhir

Subjects: Discrete Mathematics (cs.DM); Computer Science and Game Theory (cs.GT)

[17] arXiv:0904.2638 (cross-list from cs.LO) [pdf, other]

Title: Better Quality in Synthesis through Quantitative Objectives

Roderick Bloem, Krishnendu Chatterjee, Thomas A. Henzinger, Barbara Jobstmann

Subjects: Logic in Computer Science (cs.LO); Computer Science and Game Theory (cs.GT)

[18] arXiv:0904.3243 (cross-list from cs.GL) [pdf, other]

Title: The Business of Selling Electronic Documents

Manuel Oriol

Comments: 6 pages

Subjects: General Literature (cs.GL); Computer Science and Game Theory (cs.GT)

[19] arXiv:0904.4717 (cross-list from cs.LG) [pdf, other]

Title: Continuous Strategy Replicator Dynamics for Multi--Agent Learning

Aram Galstyan

Comments: 12 pages, 15 figures, accepted for publication in JAAMAS

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Adaptation and Self-Organizing Systems (nlin.AO)